Prove optimality of constrained convex optimization problem analitically (using KKT conditions)

Question

I'm trying to prove that the constrained convex minimization problem with decision variable $\boldsymbol{x} \in \mathbb{R}^{n}$ given by

$$ \min_{\boldsymbol{x}} \Vert \boldsymbol{x} \Vert_{2} \text{ s.t.}$$

$$ \Vert \boldsymbol{x} \Vert_{1} = 1, $$

$$ \boldsymbol{0} \leq \boldsymbol{x} \leq \boldsymbol{1} $$

has an optimal solution $\boldsymbol{x}^{\star}$ where $x_{i}^{\star} = 1/n$, for all $i$. I 'know' this solution to be true by solving the optimization problem numerically (and it makes intuitive sense) but I haven't been able to prove it analytically. I tried to invoke the necessary and sufficient KKT conditions of the Lagrangian $\mathcal{L}(\boldsymbol{x}, \boldsymbol{\mu}, \lambda)$ but I couldn't quite figure out how to choose $(\boldsymbol{\mu}^{\star}, \lambda^{\star})$ and then prove it to be a saddle point. Any help would be appreciated. Cheers!

Answer 1

When solving by hand, I typically ignore the inequality constraints first. Then, using only the objective and equality constraints, I solve for an optima candidate. Last, I check if this candidate satisfies the inequality constraints. If this is the case, then problem solved.

The Lagrangian

$$ \mathcal{L}\left(\mathbf{x},\lambda\right)=\mathbf{x}^{\top}\mathbf{x}+\lambda\left(\mathbf{1}^{\top}\mathbf{x}-1\right) $$

Stationarity Condition

$$ \mathbf{0} = \nabla_{\mathbf{x}}\mathcal{L}\left(\mathbf{x},\lambda\right) = \mathbf{x}-\lambda\cdot\mathbf{1} $$

from which we get $x_{i}=\lambda$ for all $i\in\{1,...,n\}$.

Primal Feasibility Condition (Equality)

$$ 0=\nabla_{\lambda}\mathcal{L}\left(\mathbf{x},\lambda\right)=\mathbf{1}^{\top}\mathbf{x}-1 $$

from which, combined with result from the stationarity condition, we get $x_{i}=\lambda=\frac{1}{n}$

Primal Feasibility (Inequality) Check

$0\leq x_{i}=\frac{1}{n}\leq 1$ satisfies the inequality constraints. So this is the solution that we look for.

Answer 2

There are a few ways to solve this.

First, note that $\|x\|_2 \le \|x\|_1 \le \sqrt{n}\|x\|_2$, this is straightforward to show (using the fact that $(a-b) \ge 2ab$).

In particular, $\|x\|_2 \ge {1 \over \sqrt{n}}$, and choosing $x={1 \over n} (1,...,1)$ satisfies all constraints, hence is a solution.

Second, if you want to use KKT, note that the problem is equivalent to $\min\{ \|x\|_2^2 | x_1+\cdots x_n = 1 , x_k \ge 0\}$ and consider the relaxed problem $\min\{ \|x\|_2^2 | x_1+\cdots x_n = 1 \}$ to get $2x_k + \lambda = 0$. In particular, $x_k$ is constant and from this we get $x={1 \over n} (1,...,1)$. Since this satisfies the constraints of the original problem, it is the solution.