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

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?

• Have you tried to solve a 2D instance graphically? Feb 16 at 7:43
• @RodrigodeAzevedo Oh, I see. It seems that the inner constraint is never active.
– Ryan
Feb 16 at 8:08

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.

• Thanks very much for your answer. Can I still use this method if there are other linear constraints in this optimization problem?
– Ryan
Feb 16 at 8:07
• Depends on how they look and you might have to adapt the reasoning accordingly Feb 16 at 8:13

$$\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}$$

• This answer clearly shows that $a \leq \|x\|_2$ is inactive. Thanks so much!
– Ryan
Feb 16 at 9:22

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^*\|, 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\|$$.

• Thanks very much for your answer. Yes, it is very interesting that $a < b$ does not affect the result.
– Ryan
Feb 18 at 12:39