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.
Best Answer
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.