How to deal with the constraint $a \leq \|x\|_2 \leq b$ in an optimization problem?

Question

How to solve the following optimization problem?

$$\begin{array}{c l} \underset {x} {\text{minimize}} & c^{\top} x\\ \text{subject to}~& a \leq \|x\|_2 \leq b \end{array} $$

Can we convert it into a convex optimization problem?

Answer 1

You can't really convert it to a convex problem (admissible set is not convex) and you don't need to.

Of course assume $0 < a < b$ and $c \neq 0$. We can square the constraint to get an equivalent constraint $$ a^2 \leq \lVert x \rVert_2^2 \leq b. $$ Split it up into two constraints: $$ \lVert x \rVert_2^2 -b \leq 0,\quad \quad - \lVert x\rVert^2_2 +a^2 \leq 0 $$ Then we have to go through the usual Lagrange Multiplier Routine. Define $f:\mathbb{R}^n \rightarrow \mathbb{R}$, $g:\mathbb{R}^n \rightarrow \mathbb{R}^2$ $$ f(x) := c^\top x, \quad g(x) := \begin{pmatrix} \lVert x \rVert^2_2 - b \\ -\lVert x \rVert_2^2 + a^2 \end{pmatrix} $$ for all $x \in \mathbb{R}^2$. So $$ \nabla f(x) = c,\quad \nabla g(x) = \left( 2x, -2x \right). $$ Since both constraints cannot be active at the same time and $x \neq 0$ when one constraint is active, the LICQ holds. So we can search for the minimizer among the KKT-points.

There are of course no KKT-points in the interior. Now assume that the first constraint is active, i.e. $\lVert x \rVert^2_2 = b$. Then we need to find some Lagrange multiplier $\lambda_1 \geq 0$ such that $$ \nabla f(x) + \lambda_1 \nabla g_1(x) = 0 \iff c + 2\lambda_1 x = 0. $$ Observe that $\lambda_1 \neq 0$ is impossible. It is equivalent that $x = -\frac{1}{2\lambda_1} c$. Since we assumed $\lVert x \rVert_2 = b$, we must have $$ \lambda_1 = \frac{\lVert c \rVert_2}{2b} $$ as the multiplier. So our candidate for KKT-point is $z_1 := - b\frac{c}{\lVert c \rVert_2}$. It is very easy to check that it is in fact admissible.

So now assume that the second constraint is active, i.e. $\lVert x \rVert_2^2 = a^2$. Then we need to find a Lagrange-multiplier $\lambda_2 \geq 0$ such that $$ \nabla f(x) + \lambda_2 \nabla g_2(x) = 0 \iff c - 2\lambda_2 x = 0. $$ It hence holds that $x = \frac{c}{2\lambda_2}$, since $\lambda_2 = 0$ is clearly not a solution. Same procedure as in the first case yields the KKT-point $z_2 := a\frac{c}{\lVert c \rVert_2}$. Clearly an admissible point. So these are all possible cases.

Finding out which KKT-point is the minimizer is very easy: A minimum must exist since the objective function is continuous and the admissible set is compact. We have already argued as to why the minimum is a KKT-point. Sojust check which KKT-point yields the smaller value. $$ f(z_1) = -b \lVert c \rVert_2, \quad f(z_2) = a\lVert c \rVert_2 $$ So $z_1$ is our desired minimizer.

Answer 2

$$ \begin{array}{ll} \underset {{\bf x}} {\text{minimize}} & \langle {\bf c}, {\bf x} \rangle \\ \text{subject to}~& a \leq \| {\bf x} \|_2 \leq b \end{array} $$

Using Cauchy-Schwarz,

$$ \langle {\bf c}, {\bf x} \rangle \geq - \| {\bf c} \|_2 \| {\bf x} \|_2 \geq \color{blue}{- b \| {\bf c} \|_2} $$

Answer 3

To make things interesting, let $b>0$.

If $a \le 0$, then clearly, we can drop the constraint $a\le \|x\|$ .

If $x^*$ is optimal and $\|x^*\|<b$, then $c^Tx^*<0$, let $\hat{x}=\frac{bx^*}{\|x^*\|}$, then $$c^T(\hat{x}-x^*)=b\frac{c^Tx^*}{\|x^*\|}-c^Tx^*=(c^Tx^*)\left(\frac{b}{\|x^*\|}-1 \right)<0$$

Also check that $\hat{x}$ is feasible. Hence we found out if $x^*$ is optimal, then we have $\|x^*\|$=b. Hence, we can drop the constraint $a\le \|x\|$.