0
$\begingroup$

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!

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks! I like this approach, so I guess it is always valid that any optimal solution that satisfies the relaxed optimization problem (in terms of inequality constraint), which then also happens to satisfy the inequality constraints is by definition an optimal solution to the original problem? $\endgroup$ Commented Jan 20, 2024 at 10:46
  • 1
    $\begingroup$ @BartWolleswinkel don't quote me on this but I believe the inequality constraints make the optima less optimal, so if the optima of the relaxed problem satisfies the inequality constraints, then everything's good. $\endgroup$ Commented Jan 20, 2024 at 13:43
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks for your answer, but I'm not sure I understand all steps. I guess it's trivial to prove that $x_{i} = 1/n$ for all $i$ is á solution, but why would $\Vert \boldsymbol{x} \Vert_{2} \geq 1/n$ hold? Clearly, $\Vert \boldsymbol{0} \Vert_{2} = 0$? I also don't quite get what you mean with with $x_{k}$? Thanks! $\endgroup$ Commented Jan 20, 2024 at 10:37
  • $\begingroup$ I was missing a square root symbol. $\endgroup$ Commented Jan 20, 2024 at 14:12
  • $\begingroup$ The $x_k$ are the individual components of $x$, the equation is the KKT condition for the relaxed problem. $\endgroup$ Commented Jan 20, 2024 at 14:17

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.