Optimization of Linear Term Under $ {L}_{1} $, $ {L}_{2} $ and $ {L}_{\infty} $ Inequality Norm Constraints 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.
 A: 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)$$
A: 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\|}$.
A: 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$.
