Let $x = (x_1,\ldots,x_p) \in \mathbb R^p$. I'm solving the constrained optimization problem
$$\begin{align*}
\text{min} &\quad \sum_{i=1}^p (y_i-x_i)^2 \\
\text{s.t} &\quad \sum_{i=1}^p y_i – 1 &&=0\\
&\quad\forall i = \overline{1,p}: -y_i &&\le 0
\end{align*}$$
My attempt:
Let $f(y) = \sum_{i=1}^p (y_i-x_i)^2$, $h(y) = \sum_{i=1}^p y_i – 1$, and $g_i(y) = -y_i$ for all $i = \overline{1,p}$.
We have $f,g_i$ are convex and $h$ is linear. Let $\alpha =(1/p, \cdots, 1/p)$. Then $h(\alpha)=0$ and $g(\alpha) <0$ for all $i = \overline{1,p}$. It follows that Slater's condition is satisfied. By Karush-Kuhn-Tucker conditions, we have $$\begin{aligned} \begin{cases}
\forall i = \overline{1,p}:\mu_i &\ge 0 \\
\forall i = \overline{1,p}: g_i(y) &\le 0\\
h(y) &=0 \\
\forall i = \overline{1,p}:\mu_i g_i(y)&=0 \\
\nabla f (y)+ \lambda\nabla h (y)+ \mu_i \nabla g_i (y) &=0
\end{cases}
&\iff \begin{cases}
\forall i = \overline{1,p}:\mu_i &\ge 0 \\
\forall i = \overline{1,p}:-y_i &\le 0\\
\sum_{i=1}^p y_i – 1&=0 \\
\forall i = \overline{1,p}: -\mu_i y_i &=0 \\
\forall i = \overline{1,p}: 2(y_i – x_i) +\lambda – \mu_i &= 0
\end{cases} \\ \end{aligned}$$
Then I'm stuck at solving the last system of equations.
How can I proceed to solve it? Thank you so much!
Best Answer
Your problem can be rewritten as:
$$ \begin{alignat*}{3} \arg \min_{x} & \quad & \frac{1}{2} \left\| y - x \right\|_{2}^{2} \\ \text{subject to} & \quad & y \succeq 0 \\ & \quad & \boldsymbol{1}^{T} y = 1 \end{alignat*} $$
Then it is the exact problem as in Orthogonal Projection onto the Unit Simplex.