4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Is it easy to find the zeros of the Lagrangian $\|x\|^2_2-\lambda f(x)=0$ for some constant $\lambda$? $\endgroup$
    – Hans
    Commented May 29, 2018 at 17:26
  • 2
    $\begingroup$ A convex function on a compact convex set always attains its maximum on some extremal point. This may simplify the search --e.g. in the case of a polyhedron $\endgroup$
    – Pietro Majer
    Commented May 29, 2018 at 17:33
  • 2
    $\begingroup$ Your question is too general. Is it a question at the research level? Did you try googling? $\endgroup$
    – user64494
    Commented May 29, 2018 at 17:38
  • $\begingroup$ Thanks for helping out. I wanted to mention that I knew the max is attained it attains on some external point, however how can it be find? The sublevel set can be any convex set, not just polyhedron $\endgroup$
    – user3492773
    Commented May 29, 2018 at 17:39

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Assuming that such form means the dot product then if $x_0$ is the origin, then it's always zero! Thus, how this helps in finding the farthest point from the origin in a convex compact nonempty set? $\endgroup$
    – user3492773
    Commented May 29, 2018 at 18:21
  • $\begingroup$ $x_0$ is not the origin. It is the point in $C$ closest to the origin. If $C$ does not contain the origin, then $x_0\in \partial C$. If the boundary $\partial C$ is $C^1$, then the above variational inequality reduces to the usual Lagrange multipliers approach. If the boundary is not differentiable then the above inequality says that the vector $-x_0$ belongs to the outer normal cone. You need some information about of $f$ to be able to handle the convex set $\{f\leq 1\}$. $\endgroup$
    – Liviu Nicolaescu
    Commented May 29, 2018 at 19:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .