Maximizando uma função convexa (minimizando uma função côncava) com uma restrição linear

O problema é

onde $f(\mathbf{x}) = \sum_{i=1}^N\sqrt{1+\frac{x_i^4}{(\sum_{i=1}^{N}x_i^2)^2}}$ ,
$\mathbf{x} = [x_1,x_2,...,x_N]^T \in \mathbb{R}^{N\times 1}$ e
$\mathbf{A} \in \mathbb{R}^{M\times N}$

Podemos ver que $f(.)$ Está na forma de $\sqrt{1+y^2}$ e é uma função convexa.
Também pode ser mostrado que f (.) É delimitado em $[\sqrt{2}, 2]$ .

Este é um problema de minimização convexo com uma restrição linear.

Quais são os algoritmos padrão usados ​​para resolver esse tipo de problema?

Usando a natureza específica do problema, é possível resolvê-lo usando qualquer software / pacote de otimização padrão?

Você pode tirar proveito da estrutura do problema, embora eu não conheça nenhum solucionador pré-empacotado que faça isso por você.

Essencialmente, o que você está procurando é minimizar uma função côncava sobre um polítopo convexo (ou poliedro convexo). Uma pesquisa rápida encontrou algumas fontes relevantes (lembro-me vagamente de uma delas mencionada quando participei de uma aula de programação não-linear há mais de quatro anos):

Falk, JE, e Hoffman, KL Minimização côncava através de polítopos em colapso , Operations Research, 1986, vol. 34, n. 6, p. 919-929.

Hoffman, KL Um método para minimizar globalmente funções convexas sobre conjuntos convexos , Mathematics Programming, 1981, vol. 20, p. 22-31.

Benson, HP Um algoritmo finito para minimização côncava sobre um poliedro , Naval Research Logistics, 1985, vol. 32, n. 1, p. 165-177.

Um monte de referências no site de Christophe Meyer .

Existem mais fontes se o Google "minimizar a função côncava sobre o polítopo" (ou substituir "polítopo" por "poliedro").

Eu participei há alguns anos de uma palestra sobre otimização. Naquela época, usamos o Matlab em combinação com o YALMIP.

O Wiki do YALMIP

Esse problema pode ser visto como uma diferença no problema de programação das funções convexas (DC). Há uma extensa literatura sobre programação DC, você pode pesquisar estudos relacionados lá. Um dos métodos mais conhecidos é o método DCA, veja, por exemplo: http://lma.univ-pau.fr/meet/mamern09/en/Lethi-MAMERN09.pdf

Outro artigo recente que examina a literatura de DC em certa medida e pode ser útil é: https://arxiv.org/pdf/1511.01796.pdf

Você também pode usar algum método mais geral para problemas não suaves, por exemplo, o método baseado em proxy fornecido em: http://num.math.uni-goettingen.de/~ssabach/BST2013.pdf

Eu ofereceria o algoritmo de Frank Wolfe e métodos relacionados para sua consideração. Basicamente, você lineariza a função objetivo e resolve o LP resultante a cada iteração. Penso, no entanto, que você precisaria adicionar limites em para tornar essa abordagem eficaz.$x$