Orthogonal Projection onto a Variation of the Unit Simplex

convex optimizationconvex-analysisduality-theoremsorthogonality

Given the set $T_{\alpha}=\{x\in\mathbb{R}^n:\sum x_i=1,0\leq x_i\leq \alpha\}$
For which $\alpha$ the set is non-empty?
Find a dual problem with one dual decision variable to the problem of finding
the orthogonal projection of a given vector $y ∈\mathbb{R}^n$ onto $T_α$.

I found that $\alpha\geq1/n$ and when i tried to calculate the dual function I did the following.
$\min$ $||x-y||^2$
s.t
$\sum x_i=1$
$0\leq x_i\leq\alpha\to X=\{x:0\leq x_i\leq\alpha\}$
Setting the lagrangian to be $L(x,\lambda)=||x-y||^2+2\lambda(\sum x_i-1)$,we would like to minimize the lagrangian w.r.t x then :
$$\underset{x\in X}{\min}L(x,\lambda)=\sum x_i^2+2(\lambda-y_i)x_i+||y||^2-2\lambda$$
$$\frac{\partial L}{\partial x_i}=2x_i+2(\lambda-y_i)=0\to x_i^*=\left\{\begin{array}{rcl} y_i-\lambda&0\leq y_i-\lambda\leq\alpha\\
\alpha&y_i-\lambda>\alpha\\
0&y_i-\lambda<0\end{array}\right.$$

and the dual function is $q(\lambda)=-2\lambda+||y||^2+\left\{\begin{array}{rcl}n\alpha^2+2n\alpha\lambda-2\alpha\sum y_i&y_i-\lambda>\alpha\\
-\sum [y_i-\lambda]_+^2&\mbox{else}\end{array}\right.$

and the derivative of $q$ is:
$$q'(\lambda)=-2+\left\{\begin{array}{rcl}2n\alpha &y_i-\lambda>\alpha\\
2\sum[y_i-\lambda]_+^2&\mbox{else}\end{array}\right.$$

I'm not sure if I've found the right dual function and if I've found the right derivative and write matlab code that solves the dual and finds the projection of $y$

Best Answer

This is basically Projection onto the Simplex with some modifications.
The problem is given by:

$$ \begin{alignat*}{3} \arg \min_{x} & \quad & \frac{1}{2} \left\| x - y \right\|_{2}^{2} \\ \text{subject to} & \quad & 0 \leq {x}_{i} \leq \alpha \\ & \quad & \boldsymbol{1}^{T} x = 1 \end{alignat*} $$

The problem is valid for $ \alpha \geq \frac{1}{n} $ otherwise the constraint $ \boldsymbol{1}^{T} x = 1 $ isn't feasible.
For $ \alpha \geq 1 $ the problem matches the Projection onto the Simplex as the upper boundary can not be an active constraint (Well it is for 1, but then it is equivalent for the equality constraint and the non negativity).

The Lagrangian in that case is given by:

$$ \begin{align} L \left( x, \mu \right) & = \frac{1}{2} {\left\| x - y \right\|}^{2} + \mu \left( \boldsymbol{1}^{T} x - 1 \right) && \text{} \\ \end{align} $$

The trick is to leave non negativity constrain implicit.
Hence the Dual Function is given by:

$$ \begin{align} g \left( \mu \right) & = \inf_{0 \leq {x}_{i} \leq \alpha} L \left( x, \mu \right) && \text{} \\ & = \inf_{0 \leq {x}_{i} \leq \alpha} \sum_{i = 1}^{n} \left( \frac{1}{2} { \left( {x}_{i} - {y}_{i} \right) }^{2} + \mu {x}_{i} \right) - \mu && \text{Component wise form} \end{align} $$

Taking advantage of the Component Wise form the solution is given:

$$ \begin{align} {x}_{i}^{\ast} = { \left( {y}_{i} - \mu \right) }_{0 \leq \cdot \leq \alpha} \end{align} $$

Where the solution includes the inequality constrains by Projecting onto the box $ \mathcal{B} = \left\{ x \mid 0 \leq {x}_{i} \leq \alpha \right\} $.

The solution is given by finding the $ \mu $ which holds the constrain (Pay attention, since the above was equality constrain, $ \mu $ can have any value and it is not limited to non negativity as $ \lambda $).

The objective function (From the KKT) is given by:

$$ \begin{align} 0 = h \left( \mu \right) = \sum_{i = 1}^{n} {x}_{i}^{\ast} - 1 & = \sum_{i = 1}^{n} { \left( {y}_{i} - \mu \right) }_{0 \leq \cdot \leq \alpha} - 1 \end{align} $$

The above is a Piece Wise linear function of $ \mu $.

Since the function is continuous yet it is not differentiable due to its piece wise property theory says we must use derivative free methods for root finding. One could use the Bisection Method for instance.

MATLAB Code

I wrote a MATLAB code which implements the method with Bisection Root Finding. I verified my implementation vs. CVX. The MATLAB Code which is accessible in my StackExchange Mathematics Q3972913 GitHub Repository.

Related Question