Maximizing a convex function with a convex constraint

Question

Given a convex function $f : \mathbb{R}^n \to [0,\infty)$, the objective is to find the farthest point in the level set $\left\lbrace x \in \mathbb{R}^n \mid f(x) \leq 1\right\rbrace$ (Assuming that such set is non empty, and closed and compact), i.e.

$$ \begin{aligned} & \underset{x \in \mathbb{R}^n}{\text{maximize}} & & \left| \left| x\right| \right|_2 \\ & \text{subject to} & & f(x) \leq 1 . \end{aligned} $$

Is it possible? Is there any solvers out which can solve such problem?

Please advise.

Thanks in advance.

Answer 1

Under your assumptions, this is a concave programming problem (i.e., minimization of a concave function subject to convex constraints) with compact constraint set, and therefore has a global minimum at an extreme of the feasible set, i.e., satisfying $f(x) = 1$. (Although there may be other globally optimal points not at an extreme).

There are off the shelf global optimizers, such as BARON and YALMIP's BMIBNB, which will accept such a problem. Whether they manage to solve the problem to optimality (or to within a specified non-zero tolerance of optimality) depends on the size (dimension) and difficulty of the problem. In particular, you haven't told us anything about f(x) other than it is convex and that $f(x) \le 1$ is compact.

If there are a small enough number of extreme points of $f(x) \le 1$ such that they can be readily determined, a simple option is to evaluate the objective at all these points, i.e., brute force enumeration, and pick the best.

if f(x) were linear (affine) (which I guess it is not, presuming that f(x) is scalar single inequality, given your claim of feasible set compactness), then this would be (with squaring of the objective function) a non-convex Quadratic Programming problem, for which there are additional off the shelf solver options to solve to global optimality, such as CPLEX QP solver with optimality target set to 3.

Answer 2

First, for any closed set $\newcommand{\bR}{\mathbb{R}}$ $C\subset \bR^n$, not necessarily compact, there is a closest point to the origin. To see this pick a minimizing sequence $x_\nu$. It is bounded, admits a convergent subsequence whose limit is a point that minimizes the distance to the origin within $C$.

If additionally $C$ is convex then there exists a unique $x_0\in C$ that minimizes the distance to the origin and this point is the solutions of the following variational inequality

$$ (x_0, x-x_0)\geq 0,\;\;\forall x\in C. $$

For details I refer to Theorem 5.2 in

H.Brezis: Functional Analysis, Sobolev Spaces and Partial Differential Equations, Springer Verlag, 2011.

For the maximum to exist one needs to require that $C$ be compact. In this case the maximum occurs at an extremal point point of $C$ which is necessarily on the boundary. It is the point such that $x_0 belongs to the cone of outer normals.