Minimization a function with respect to a norm I have troubles undersatnding the solution of the LP from a textbook given as:
$\min c^Tx $ s.t. $\|x\|_2^2 \le 1$ where $c\not=0.$
The textbook started by using Cauchy-Schwarz inequality to get:
$c^Tx \ge -\|c\|_2\|x\|_2 \ge -\|c\|_2 \ \forall x\in \mathbb{R}^n$ s.t. $\|x\|_2 \le 1$ $\quad\quad$
(I find it uneasy relating the C-S inequality: $|uv|\le |u||v|, \forall u,v \in \mathbb{R}^n$ to $c^T x$)
The text continued: the inequality becomes equality when $x=-c/\|c\|_2.$
Conclusion: $\min c^Tx = -\|c\|_2$.
 A: From Cauchy-Schwarz inequality in any inner product space we get $|c\circ x|\leq \|c\|\cdot\|x\|$, so $c\circ x\geq -\|c\|\cdot\|x\|.$ If $\|x\|\leq 1$ then $\|c\|\cdot\|x\|\leq \|c\|$, so $c\circ x\geq -\|c\|$.
On the other hand, if we take $x=-c/\|c\|$ (this point satisfies $\|x\|=1$) we obtain $$c\circ x = -\frac{c\circ c}{\|c\|} = -\frac{\|c\|^2}{\|c\|}=-\|c\|.$$
This shows that $c\circ x$ is never smaller than $-\|c\|$ but it attains this value somewhere in the domain. This shows that this is a minimal velue.
One can ask how do we know to consider $x=-c/\|c\|$. It's known that the equality in C-S inequality $|c\circ x|\leq \|c\|\|x\|$ holds iff $c$ and $x$ are linearly dependent. Moreover $\|c\|\cdot\|x\|=\|c\|$ iff $\|x\|=1$. These gives the way to find the argument $x$ minimizing our function.
A: I would suggest the classical method for constrained optimization. The Lagrange multipliers! Introduce a dummy variable y and consider the problem min$c^{T}x $ subject to $\left\|x \right\|^{2}+y^{2}=1$. Then L=$c_{1}x_{1}+...+c_{n}x_{n}-\lambda (x_{1}^{2}+....+x_{n}^{2}+y^{2})$ and using partial differentiation we get $c_{1}=2\lambda x_{1}, ....,c_{n}=2\lambda x_{n}, -2\lambda y=0$ and since $\lambda\neq 0$ (because otherwise we would get x=0 which is certainly not a minimizer) we obtain y=0 and $\left\|x \right\| =1$. Thus $\left\|c \right\|^{2}=4\lambda ^{2}\left\|x \right\|$ =4$\lambda ^{2} $. Since we want to minimize we choose $\lambda =-\frac{\left\|c \right\|}{2}$ and obtain $x_{1}=-\frac{c_{1}}{\left\| c\right\|},....,x_{n}=-\frac{c_{n}}{\left\|c \right\|}$
and hence the minimum is
-$\frac{\left\|c \right\|^{2}}{\left\|c \right\|}$=
-$\left\|c \right\|$.! There are also other ways to solve such problems eg by Fenchel duality, where we produce a dual problem much easier to solve!
A: Since the linear map $f(x)= c^Tx$ is open it is clear that the solution must lie on the boundary $\|x\|=1$.
Cauchy Schwartz gives $|f(x)| \le \|c\|$ for all $\|x\| = 1$, so in particular,
$f(x) \ge -\|c\|$ for all $x$. Since $f(-{c \over \|c\|}) = -\|c\|$, we see that $-{c \over \|c\|}$ is a minimiser.
