Solving Optimization Problem (Orthogonal Projection) Using Projected Sub Gradient / Dual Projected Subgradient Given the following optimization problem (Orthogonal Projection):
$$
{\mathcal{P}}_{\mathcal{T}} \left( x \right) = \arg \min _{y \in \mathcal{T} } \left\{ \frac{1}{2} {\left\| x - y \right\|}^{2} \right\}
$$
Where $ \mathcal{T} = \left\{ x \mid {e}^{T} x = k, \; \forall i, \: 0 \leq {x}_{i} \leq 1 \right\} $ and $ \forall i, \,{e}_{i} = 1 $ and $k $ is known.
I tried solving it using KKT yet couldn't get into a solution.
I was able to solve it using CVX yet I wanted a method I can see what happens.


*

*Could anyone solve it using KKT?

*How can solve it using iterated method? It seems to fit Projected Sub Gradient / Dual Projected Subgradient yet I couldn't calculate the items needed.


Thank You.
 A: This is a Community Wiki Solution.
Feel free to edit and add.
I will point up and mark solution for any other solution made by the community.
KKT
The Lagrangian is given by:
$$ L \left( y, \lambda \right) = \frac{1}{2} {\left\| y - x \right\|}^{2} + \mu \left( {e}^{T} y - k \right) - {\lambda}_{1}^{T} y + {\lambda}_{2}^{T} \left( y - e \right) $$
The KKT Constraints:
\begin{align}
\left( 1 \right) \; & {\nabla}_{y} L \left( y, \lambda \right) = y - x + \mu e - {\lambda}_{1} + {\lambda}_{2} & = 0 \\
\left( 2 \right) \; & {\nabla}_{\mu} L \left( y, \lambda \right) = {e}^{T} y - k & = 0 \\
\left( 3 \right) \; & -{\lambda}_{1}^{T} y & = 0 \\
\left( 4 \right) \; & {\lambda}_{2}^{T} \left( y - e \right) & = 0 \\
\left( 5 \right) \; & {\lambda}_{1} & \geq 0 \\
\left( 6 \right) \; & {\lambda}_{2} & \geq 0
\end{align}
Multiplying $ \left( 1 \right) $ by $ {e}^{T} $ and using $ \left( 2 \right) $ yields:
$$ {e}^{T} y - {e}^{T} x + \mu {e}^{T} e +{e}^{T} {\lambda}_{2} \Rightarrow \mu = \frac{ {e}^{T} x - k }{ n - {e}^{T} {\lambda}_{1} + {e}^{T} {\lambda}_{2} } $$
Plugging the result into $ \left( 1 \right) $ yields
Seems to be hard to get analytic solution.
Any other way to solve this system of equations?
Under Work...
Feel free to continue.
Projected Subgradient
Dual Projected Sub Gradient
Given a Problem in the form:
\begin{align*}
\arg \min_{x} & \quad f \left( x \right) \\
s.t. & \quad {g}_{i} \left( x \right) \leq 0 , \; i = 1, 2, \cdots, m \\
& \quad x \in \mathcal{S}
\end{align*}
Where


*

*$ \mathcal{S} \in \mathbb{E} $ is Convex.

*$ f : \mathbb{E} \rightarrow \mathbb{R} $ is convex.

*$ {g}_{i} : \mathbb{E} \rightarrow \mathbb{R} $ is Convex.


Then, from Amir Beck's Lecture Notes, The Dual Projected Sub Gradient is given by:


*

*Pick $ {\lambda}^{0} \in {\mathbb{R}}_{+} $.

*For $ k = 0, 1, 2, \cdots $ Calculate:


*

*$ {x}_{k} = \arg \min_{x \in \mathcal{S}} \left\{ f \left( x \right) + \sum_{i = 1}^{m} {\lambda}_{i}^{k} {g}_{i} \left( x \right) \right\} $.

*$ {\lambda}_{i}^{k + 1} = {\left[ {\lambda}_{i}^{k} + {t}_{k} \frac{ {g}_{i} \left( {x}^{k} \right) }{ {\left\| {g}_{i} \left( {x}^{k} \right) \right\|}_{2} } \right]}_{+} $.



In this problem $ f \left( y \right) = \frac{1}{2} { \left\| y - x \right\| }^{2} $, $ i = 1, 2, ..., n, \; {g}_{i} \left( y \right) = -{y}_{i} $, $ i = n + 1, n + 2, ..., 2n, \; {g}_{i} \left( y \right) = {y}_{i} - 1 $ and $ \mathcal{S} = \left\{ x \mid {e}^{T} x = k \right\} $.
The Sub Problem $ {x}_{k} = \arg \min_{x \in \mathcal{S}} \left\{ f \left( x \right) + \sum_{i = 1}^{m} {\lambda}_{i}^{k} {g}_{i} \left( x \right) \right\} $ should be solved using Projected Sub Gradient.
In this case the Projection Operator is given by $ {\mathcal{P}}_{{e}^{T} x = k} \left( x \right) = x - e {\left( {e}^{T} e \right)}^{-1} \left( {e}^{T} x - b \right) $.
The Gradient of $ L \left( y, \lambda \right) = \frac{1}{2} { \left\| y - x \right\| }^{2} + \sum_{i = 1}^{m} {\lambda}_{i} {g}_{i} \left( x \right) $ is given by $ {\nabla}_{y} L \left( y, \lambda \right) = y - x + {\left[ \left( {\lambda}_{n + 1} - {\lambda}_{1} \right), \left( {\lambda}_{n + 2} - {\lambda}_{2} \right), \cdots, \left( {\lambda}_{2n} - {\lambda}_{n} \right) \right]}^{T} $.
This is a MATLAB code which implements the method:
function [ vY ] = ProjX( vX, numElmntsK )
%UNTITLED6 Summary of this function goes here
%   Detailed explanation goes here

numDim  = size(vX, 1);
vE      = ones([numDim, 1]);

hProjFunc   = @(vY) vY - (vE * ((vE.' * vE) \ ((vE.' * vY) - numElmntsK)));
hGFunc      = @(vY) [-vY; (vY - vE)];
hGradLFun   = @(vY, vLambda) vY - vX - vLambda(1:numDim) + vLambda((numDim + 1):(2 * numDim));

% numIterDual = 6000;
numIterProj = 150;

vY          = vE;
vY          = numElmntsK * (vY / sum(vY));
vLambda     = 0.5 * ones([(2 * numDim), 1]);
stepSize    = 0.0075;

minConstVal = inf;

minConstThr = 0.00005;

while(minConstVal > minConstThr)
    % Dual Projected Sub Gradient
    for jj = 1:numIterProj
        % Projetcted Sub Gradient
        vY = hProjFunc(vY - (stepSize * hGradLFun(vY, vLambda)));
    end
    vLambda = vLambda + (stepSize * hGFunc(vY) / norm(hGFunc(vY), 2));
    vLambda = max(vLambda, 0);

    minConstVal = abs(sum(vLambda .* hGFunc(vY)));
end


end

A: I've worked this problem out before, and from what I remember, you should get from your optimality conditions that $y^*= \min(\max(x+\mu 1,0),1)$, where $\mu$ is chosen so that $1^Ty^* = k$. In words, to project onto the intersection of a box ($0\le y \le 1$) and a plane ($1^Ty = k$), move in the direction normal to the plane until the projection onto the box is on the plane. 
This matlab code should do it.
function y = projboxplane(x,k)
    n = length(x);    
    breaks = [-x(:); 1-x(:)];
    [breaks,sigma] = sort(breaks);
    slope = cumsum((-1).^(sigma>n));
    f = cumsum([0;slope(1:end-1).*diff(breaks)]);
    ix = sum(f <= k);
    mu = breaks(k) + (k-f(ix))/slope(ix);
    y = min(max(x + mu,0),1);

The ideas in the Duchi et al. paper mentioned in the comments can also be applied to avoid the sort to get a linear time algorithm.
