2
$\begingroup$

I am currently researching some robust control problems, and I ended up with the following optimization problem:

\begin{align} \max_{x,w} ~&~ f(x,w) \\ {\rm s.t.} ~&~ g(x,w) \le 0 \\ ~&~ \|w\|\le \|x\| \\ ~&~ x,w\in\mathbb{R}^n \end{align}

The functions $f,g$ are linear, e.g. $f(x,w) = c^\top x + d^\top w$ and $g(x,w) = Ax + Bw - g$ for matrices $A,B$ and vectors $c,d,g$.

If $n=1$, the problem can be recast as an SOCP as $\|w\| \le \|x\|$ is equivalent to $w^\top w \le x^2$, which can be recast as the pair of contstraints $w^\top w \le xv$ and $x=v$, and the first can be rewritten as $\left\|\begin{bmatrix} w \\ x-v\end{bmatrix}\right\| \le x+v$.


Can this program be recasted as an SOCP problem for $n\ge 2$?


Edit: The problem might be recasted as a convex program even if the constraint itself is non-convex. For example, if $g = g(x)$ is independent of $w$, and $f(x,w)=c^\top x + d^\top w$, then for any fixed $x$, we have:

$$ \max_{w: \|w\|\le \|x\|} f(x,w) = c^\top x + \|d\|\|x\| $$

Indeed, the inequality $\le$ follows from Hoelder's inequality, and $\ge$ follows from choosing $w = \frac{\|x\|}{\|d\|}d$. Thus, the problem is equivalent to: \begin{align} \max_{x} ~&~ c^\top x + \|d\|\|x\| \\ {\rm s.t.} ~&~ g(x) \le 0 \\ ~&~ x\in\mathbb{R}^n \end{align} which is convex. I wonder if "tricks" like that can be used for the general problem.

$\endgroup$
4
  • 1
    $\begingroup$ Even for $n=1$ you need to assume $w\geq 0$ and for higher $n$ the inequality between norms becomes hopelessly nonconvex. $\endgroup$ Jan 6 at 21:08
  • $\begingroup$ You are correct. However, the problem might still be recasted to a convex problem. See the edit to the question. $\endgroup$
    – Miel Sharf
    Jan 7 at 11:56
  • $\begingroup$ You confuse $w$ and $x$ in "$\|w\| \le \|x\|$ is equivalent to $x^\top x \le w^2$". The constraint $w^T w <= x^2$ is not convex and your reformulation is not equivalent (since it forces $x \geq 0$). $\endgroup$
    – LinAlg
    Jan 9 at 18:06
  • $\begingroup$ You are correct. I fixed it. $\endgroup$
    – Miel Sharf
    Jan 9 at 20:33
1
+50
$\begingroup$

You can omit $x$ from the objective since you can always perform a reformulation via the epigraph. For fixed $w$, the problem is equivalent to deciding if there is a $x$ such that $||x|| \geq ||w||$ and $Ax \leq g - Bw$.

This is NP-hard since it a generalization of maximizing a quadratic function over the unit box $\{ x : ||x||_1 \leq 1\}$, which is known to be NP-complete (see Some optimal inapproximability results by Håstad).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.