# Converting problem with norm bound to SOCP problem

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.

• Even for $n=1$ you need to assume $w\geq 0$ and for higher $n$ the inequality between norms becomes hopelessly nonconvex. Jan 6 at 21:08
• You are correct. However, the problem might still be recasted to a convex problem. See the edit to the question. Jan 7 at 11:56
• 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$). Jan 9 at 18:06
• You are correct. I fixed it. Jan 9 at 20:33

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).