Maximizando una función convexa (minimizando una función cóncava) con una restricción lineal

El problema es

donde $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}$ y
$\mathbf{A} \in \mathbb{R}^{M\times N}$

Podemos ver que $f(.)$ Tiene la forma de $\sqrt{1+y^2}$ y es una función convexa.
También se puede mostrar que f (.) Está acotado en $[\sqrt{2}, 2]$ .

Este es un problema de minimización convexo con una restricción lineal.

¿Cuáles son los algoritmos estándar utilizados para resolver este tipo de problemas?

Usando la naturaleza específica del problema, ¿es posible resolverlo usando algún paquete / software de optimización estándar?

Puede aprovechar la estructura del problema, aunque no conozco ningún solucionador preempaquetado que lo haga por usted.

Esencialmente, lo que está buscando es minimizar una función cóncava sobre un politopo convexo (o poliedro convexo). Una búsqueda rápida sacó algunas fuentes relevantes (recuerdo vagamente que se mencionó una de estas cuando tomé una clase sobre programación no lineal hace más de cuatro años):

Falk, JE y Hoffman, KL Minimización cóncava mediante politopos colapsantes , Investigación de operaciones, 1986, vol. 34, núm. 6, pág. 919-929.

Hoffman, KL Un método para minimizar globalmente las funciones convexas sobre conjuntos convexos , Programación matemática, 1981, vol. 20, p. 22-31.

Benson, HP Un algoritmo finito para la minimización cóncava sobre un poliedro , Naval Research Logistics, 1985, vol. 32, núm. 1, pág. 165-177.

Un montón de referencias en el sitio web de Christophe Meyer .

Hay más fuentes si Google "minimiza la función cóncava sobre el politopo" (o reemplaza "politopo" con "poliedro").

Hace algunos años asistí a una conferencia sobre optimización. En aquel entonces utilizamos Matlab en combinación con YALMIP.

El Wiki de YALMIP

Este problema puede verse como una diferencia del problema de programación de funciones convexas (CC). Existe una extensa literatura sobre programación DC, puede buscar estudios relacionados allí. Uno de los métodos más conocidos es el método DCA; consulte, por ejemplo: http://lma.univ-pau.fr/meet/mamern09/en/Lethi-MAMERN09.pdf

Otro artículo reciente que examina la literatura de DC hasta cierto punto y que podría ser útil es: https://arxiv.org/pdf/1511.01796.pdf

También puede usar un método más general para problemas no suaves, por ejemplo, el método basado en prox que se proporciona en: http://num.math.uni-goettingen.de/~ssabach/BST2013.pdf

Me ofrezco el algoritmo de Frank Wolfe y métodos relacionados para su consideración. Básicamente, linealiza la función objetivo y resuelve el LP resultante en cada iteración. Sin embargo, creo que necesitaría agregar límites en para que este enfoque sea efectivo.$x$