Approximate solution to maximizing a convex function

Question

I need your expertise in understanding or obtaining an algorithm for obtaining an approximation to the global supremum of a convex function $f$ over a convex set $X$. This problem is known to be $\textit{NP-Hard}$, so I wonder whether someone has attained an approximation to the problem or may have solved it under certain constraints in polynomial time (of course).

Would you know of such algorithm?

E.g. Given a convex set $S$ and an ellipsoid $E = (A,c)$ which is contained in $S \subseteq \mathbb{R}^n$, I want to find the farthest point from the ellipsoid which is not contained in the ellipsoid, hence the following in needed: $$ \arg\max_{x \in S}\ (x-c)^T A (x-c)$$ where $c \in \mathbb{R}^n$, and $A \in \mathbb{R}^{n \times n}$ a positive definite matrix.

please advise and thanks in advance.

Answer 1

This particular problem isn't NP in general, but ofc it depends on how $S$ is constructed. If $S$ is given by some nice, differentiable function, then it's just a matter of finding points on $\partial S$ at which the KKT conditions are satisfied - loosely speaking, points at which the gradient of $f(x)$ is perpendicular to the normal vector of $S$.

Of course, these points will not all be global (or even local) maxima, but one of them should be - thus you just have to exhaustively search all KKT points on the boundary of $S$ and therefore any algorithm that is based on finding KKT points will do just fine (which in turn simply amounts to finding solutions to some particular set of linear/nonlinear equations).

Answer 2

First special case

One special case that is tractable is when the extreme points of $S$ can be enumerated, and their number is polynomial in the description length of $S$. For example, it can happen when $S$ is polyhedral with a relatively small number of vertices.

In general, maximizing a convex function over a convex set $S$ is equivalent to maximizing a convex function over the extreme points of $S$. So you can exhaustively enumerate $f(x)$ over the extreme points of $S$, and choose the maximum.

Second special case

When $S$ is an ellipsoid itself. That is, when $$ S = \{ x : x^T B x \leq \alpha \} $$ In that case you have the well known TRS (Trust Region Subproblem) problem, for which there exist many algorithms. One well-known algorithm is described in the paper "Solving the Trust-Region Subprobblem by a Generalized Eigenvalue Problem" by Adachi et. al.