Solución aproximada a la maximización de una función convexa

Question

Necesito su experiencia para entender u obtener un algoritmo para obtener una aproximación al sumo global de una función convexa $f$ sobre un conjunto convexo $X$ . Se sabe que este problema $\textit{NP-Hard}$ Así que me pregunto si alguien habrá logrado una aproximación al problema o lo habrá resuelto con ciertas restricciones en tiempo polinómico (por supuesto).

¿Conoce algún algoritmo de este tipo?

Por ejemplo, dado un conjunto convexo $S$ y un elipsoide $E = (A,c)$ que figura en $S \subseteq \mathbb{R}^n$ Quiero encontrar el punto más alejado del elipsoide que no está contenido en el elipsoide: $$ \arg\max_{x \in S}\ (x-c)^T A (x-c)$$ donde $c \in \mathbb{R}^n$ y $A \in \mathbb{R}^{n \times n}$ una matriz definida positiva.

por favor aconsejar y gracias de antemano.

Answer 1

Este problema en particular no es NP en general, pero por supuesto depende de cómo $S$ se construye. Si $S$ viene dada por alguna función bonita y diferenciable, entonces sólo es cuestión de encontrar puntos en $\partial S$ en los que se cumplen las condiciones KKT, es decir, los puntos en los que el gradiente de $f(x)$ es perpendicular al vector normal de $S$ .

Por supuesto, no todos estos puntos serán máximos globales (ni siquiera locales), pero uno de ellos debería serlo, por lo que basta con buscar exhaustivamente todos los puntos KKT en la frontera de $S$ y, por lo tanto, cualquier algoritmo basado en la búsqueda de puntos KKT funcionará perfectamente (lo que, a su vez, equivale simplemente a encontrar soluciones a un determinado conjunto de ecuaciones lineales/no lineales).

Answer 2

Primer caso especial

Un caso especial que es manejable es cuando los puntos extremos de $S$ se pueden enumerar, y su número es polinomial en la longitud de la descripción de $S$ . Por ejemplo, puede ocurrir cuando $S$ es poliédrica con un número relativamente pequeño de vértices.

En general, la maximización de una función convexa sobre un conjunto convexo $S$ es equivalente a maximizar una función convexa sobre los puntos extremos de $S$ . Así que puede enumerar exhaustivamente $f(x)$ sobre los puntos extremos de $S$ y elige el máximo.

Segundo caso especial

En $S$ es un elipsoide. Es decir, cuando $$ S = \{ x : x^T B x \leq \alpha \} $$ En ese caso nos encontramos ante el conocido problema TRS (Trust Region Subproblem), para el que existen muchos algoritmos. Un algoritmo muy conocido es el descrito en el artículo "Solving the Trust-Region Subprobblem by a Generalized Eigenvalue Problem" de Adachi et. al.