Optimization of Linear Term Under $ {L}_{1} $, $ {L}_{2} $ and $ {L}_{\infty} $ Inequality Norm Constraints

Question

Problem

Solve for optimal value in the following problem, where $p=1,2$ and $\infty$, respectively. $$\min_x c^Tx\\ \text{s.t. } \Vert x \Vert_p \leq 1$$

What I Have Done

My TA for convex optimization says that this is a famous and useful result but does not provide more details. I figured out that for $l_{\infty}$-norm, the optimal value is $\Vert c\Vert_1$. However, when it comes to $l_1$ and $l_2$, I do not now what to do.

Can you provide some materials about this problem, thank you in advance.

Answer 1

You wish to minimize $f(x)=\sum_{i=1}^n c_ix_i$ under the condition that

$$\left\{\begin{array}{cccc} \sum_{i=1}^n |x_i| \leq 1&&&p=1\\ \sum_{i=1}^n x_i^2 \leq 1&&&p=2\\ \max |x_i| \leq 1&&&p=\infty\\ \end{array}\right. $$

Notice that $\nabla f(x) = c$ for all $x\in \mathbb R^n$, so a minimum must be on the boundary of the domain. In other words, we need only consider equalities above.

---

The case $p=2$ is easily dealt with Lagrange multipliers, and we can see that $x=-c/{\lVert c \rVert}_2$. Another way to see this is via good ol' Cauchy-Schwarz:

$$\left|c^Tx\right| = \left|\langle c, x \rangle\right| \leq {\lVert c \rVert}_2\,{\lVert x \rVert}_2$$

Hence, the best you could possibly do for $p=2$ is $c^Tx = -{\lVert c \rVert}_2\,{\lVert x \rVert}_2 = -{\lVert c \rVert}_2$, where the first equality is only possible if $x$ is a scalar multiple of $c$ and the second equality follows from ${\lVert x \rVert}_2 = 1$. Therefore, $x=-c/{\lVert c \rVert}_2$.

---

For the other cases, these boundaries are no longer smooth: they have corners. Nonetheless, a Lagrange multiplier mentality should still help.

Anytime we're at the boundary, if we're able to move along the boundary in some direction given by $-\nabla f = -c$ (ie, in some direction given by any of its components), we will be sensing a decrease in the value of $f$. In this manner, we'll either arrive at some $k$-dimensional 'wall' $(0<k<n)$, or at a corner $($in a sense, a '$0$-dimensional wall'$)$ of the boundary.

However, if we arrive at a wall, that's because the wall is perpendicular to $-c$. Hence, moving along the wall is okay: $f$ does not decrease along the wall, but it does not increase either. Since every wall contains a corner, we may therefore assume without loss of generality that we have arrived at a corner.

It follows that for $p=1,\infty$ you need only check the corners of your domain.

---

For $p=1$, the corners are the vectors $\pm e_i$, where $e_i$ is the vector whose $i$-th coordinate is $1$ and all others are $0$. In this case, $c^T(\pm e_i) = \pm c_i$, so $x$ is chosen so that $i$ maximizes $|c_i|$ and the signal is chosen so that the result is negative, ie

$$x = -\text{sgn}\left(c_{\text{argmax}_i\,|c_i|}\right)\cdot e_{\text{argmax}_i\,|c_i|}$$

---

For $p=\infty$, the corners are the vectors $(\pm 1, \pm 1, \dots, \pm 1)$. In this case, it's easy to see that

$$x = \Big(-\text{sgn}(c_1), -\text{sgn}(c_2), \dots, -\text{sgn}(c_n)\Big)$$

Answer 2

Remark:

• this is a minimization problem, the solution should be nonpositive.
• The case when $c=0$ is obvious.

We can focus on $c \ne 0$.

When $p=1$, this is a linear programming problem, of which the optimal solution exists at the corner points, which are points with all zeros besides one entry, which is either $1$ or $-1$. Hence the optimal value is $-\max_i |c_i|=-\|c\|_\infty$.

For $p=2$, we can use Langrange multiplier to show that the optimal solution is a multiple of $c$ (recall steepest descent). Hence the optimal point is at $\frac{-c}{\|c\|}$.

Answer 3

These problems can be solved just with common sense. We don't need Lagrange multipliers or anything fancy.

When $p = 1$, the best thing you can do is put all your weight behind the largest component of $c$. That's how you get the most bang for your buck. So if the component of $c$ that is greatest in magnitude is $c_i$, and $c_i > 0$, then we should take $x$ to be the vector that has a $-1$ in the $i$th position and zeros elsewhere.

When $p = \infty$, the best thing you can do is take the components of $x$ to be $\pm 1$. If $c_i > 0$, then take $x_i = -1$. If $c_i < 0$, then take $x_i = 1$.

When $p = \infty$, take $x$ to be the unit vector that points in the direction opposite $c$.