1
$\begingroup$

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?

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

3 Answers 3

1
$\begingroup$

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.

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

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

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

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .