1
$\begingroup$

The setting is the following, I have a full-dimensional polytope $\mathcal{F}: A \cdot x \leq \vec{b}$ that has been transformed such that it contains the origin: $\vec{0} \in \mathcal{F}$. I need to find the point with a maximum $L_2$ norm in this polytope, which equates solving the following quadratic program:

$$ \arg \max_{\vec{x}\in \mathcal{F}} \ \vec{x}^T \cdot I \cdot \vec{x} $$

I tried doing so using cvxpy, but that tells me that this program is not a disciplined convex. I can kind of imagine that this program has a concave objective function and therefore is not solvable using convex optimization techniques, so I am wondering whether there is some other way of solving it.

Its clear that the solution to this problem is at a vertex of the polytope, and I therefore think that there must be some linear programming trick to find it without enumerating all vertices.

$\endgroup$

1 Answer 1

1
$\begingroup$

Whether or not your problem has a solution depends on whether or not the feasible region is unbounded. Let $P:=\{x:Ax\leq b\}$. You say that $P$ is a polytope (and hence is bounded). In this case, the Bolzano-Weierstrass theorem guarantees the existence of a global maximum (since the feasible region is compact).

Finding the global solution is NP-hard (can be found via vertex enumeration as you mention), but you might consider: DOI:10.1007/s12532-011-0033-9.

If you will accept a local solution, then you might try one of two approaches: LCP or simplex-style.

For the LCP (linear complementarity problem) approach, notice that the KKT conditions of the original problem $$ \max_x\{\|x\|_2^2 : Ax\leq b\} $$ can be written as $$ x = A^\top\lambda,\;Ax\leq b,\;\lambda\geq0,\;\lambda^\top(Ax-b)=0, $$ which give the LCP$(q,M)$ $$ \mbox{find } \lambda : 0 \leq b-Ax=-AA^\top\lambda + b \perp \lambda \geq0, $$ where $q := b$ and $M := -AA^\top$. Then you may use standard LCP techniques to obtain a (local) solution.

For the simplex-style approach, we can consider using the Frank-Wolfe method to linearize the objective after each step, and if the iterate doesn't change between two successive Frank-Wolfe steps, then we've found a local solution.

$\endgroup$
1
  • 1
    $\begingroup$ This was very helpful, thank you for your answer! $\endgroup$
    – Patrickens
    Commented Oct 20, 2023 at 12:25

You must log in to answer this question.

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