Linear program with quadratic (L2 norm) constraint

Question

I would like to solve an optimization problem of the type

$$ \min_x x^T c, \quad s.t. \|x\|_2 \leq k \; \land \; a \leq x_i \leq b \; \forall i$$

efficiently (note the quadratic norm constraint), where $x, c \in \mathbb{R}^N$ and $a, b, k \in\mathbb{R}$. The dimension $N$ is large, i.e., in the ten thousands. How would I do this?

In case this makes it any easier: in my particular example, $a=0$, i.e., all entries of $x$ need to be positive. This does not hold for $c$, though.

This 6-year old question is probably related, but answers there are inconclusive, and my case is less general. (The $H$ in that question is simply the identity matrix in my problem.)

Answer 1

Your problem is a second order cone programming (SOCP) problem. There are specialized interior point solvers for these kinds of problems that can be very efficient.

Answer 2

Let me give a solution for more general constraints: $\|x\|_2 \le k$, $x_i \in [a_i,b_i]$ for all $i$, for some prescribed numbers $a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n$ such that $a_i \le b_i$ for all $i$. That is, my solution doesn't require the $a_1 = \ldots = a_n$ or $b_1 = b_2 = \ldots = b_n$.

---

By Lagrange dualizaiton, one can write. $$ \begin{split} \min_{\|x\|_2 \le k,\; x \in \Pi_i [a_i,b_i]}x^Tc &= \sup_{\lambda \ge 0}\min_{x \in \Pi_i [a_i,b_i]}x^Tc - \lambda(k^2 - x^Tx)\\ &= \sup_{\lambda \ge 0}-k^2\lambda + \inf_{x \in \Pi_i [a_i,b_i]}\lambda x^Tx + x^Tc. \end{split} $$

Now, for fixed $\lambda \ge 0$, the inner problem is solved by taking

$$ x_i(\lambda) :=\begin{cases}-\dfrac{c_i}{2\lambda},&\mbox{ if }-\dfrac{c_i}{2\lambda} \le a_i \le -\dfrac{c_i}{2\lambda} \le b_i,\\a_i,&\mbox{ if }-\dfrac{c_i}{2\lambda} \le a_i,\\b_i,&\mbox{ if} -\dfrac{c_i}{2\lambda} \ge b_i.\end{cases} \tag{1} $$

Thus the original problem can be written as

$$ \min_{\lambda \ge 0, \|x(\lambda)\|_2 \le k} -k^2\lambda +\lambda\|x(\lambda)\|^2 + x(\lambda)^Tc = \min_{\lambda \ge 0, \|x(\lambda)\|_2 \le k} x(\lambda)^Tc, $$

which is a one-dimensional optimization problem in $\lambda$. Once this is solved, the solution to the original problem is obtained via formula (1).