Solving Optimization Problem (Orthogonal Projection) Using Projected Sub Gradient / Dual Projected Subgradient

Question

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.

1. Could anyone solve it using KKT?
2. 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.

Answer 1

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

1. $ \mathcal{S} \in \mathbb{E} $ is Convex.
2. $ f : \mathbb{E} \rightarrow \mathbb{R} $ is convex.
3. $ {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

Answer 2

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.