Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to minimize convex objective $f(X)$, for matrix $X$ s.t. $X\ge 0$ component-wise, and $X1^T = 1^T$.

I want to use projected gradient descent. However, I only know how to project on feasible set of any of the constraints, but not both at the same time.

But projecting on boundary of one feasible set, may bring the solution out of the feasible set for the other one. What is the standard method to overcome this?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Projecting onto the simplex is straightforward, solutions crop up from time to time. Here is an example: C. Michelot, "A finite algorithm for finding the projection of a point onto the canonical simplex of $\mathbb{R}^n$". JOTA, 50(1):195–200, 1986.

It is also a simple linear programming problem.

This is an elaboration that belongs in the comments but is too long:

Perhaps I am missing something here, but from what you have above, my understanding is that if you write $X^T = \begin{bmatrix}x_1 & \cdots & x_n \end{bmatrix}$, then you want $[x_i]_j \geq 0$ for all $i,j$, and $\sum_j [x_i]_j = 1$, for all $i$. If you let $\Sigma = \{\sigma \in \mathbb{R}^n | \sigma_i \geq 0,\ \sum \sigma_i = 1 \} $, then the space of matrices $X$ satisfying the constraints is basically $\Sigma^n$.

So, if you are at some point $X$ and have a direction $\Delta$ and some step size $\lambda$, then you are trying to project $X+\lambda \Delta$ onto the feasible set. You would do so by projecting each row of $X+\lambda \Delta$ separately onto $\Sigma$ and then recombining to get the projected step.

share|improve this answer
    
But here we are not interested in projecting on the whole simplex. Instead, we are interested in projecting to the intersection of a simplex and the non-negative orthant. –  user25004 Jul 19 '12 at 21:12
    
Each row of $X$ is a member of a simplex. Project the corresponding members of the gradient onto the corresponding simplex, then combine. –  copper.hat Jul 19 '12 at 21:16
    
I do not see how the other constraint $X\ge 0$ is satisfied here? –  user25004 Jul 20 '12 at 19:49
    
Please see my elaboration above. If I am missing something, please explain. –  copper.hat Jul 20 '12 at 20:05
    
Let $\Sigma_i = \{\sigma \in \mathbb{R}^n | \sigma_i \geq 0,\ \sum \sigma_i = 1 \}$. My problem is that I do not know how to project on $\Sigma_i$. I know how to project on $ \{\sigma \in \mathbb{R}^n | \sigma_i \geq 0 \}$ and how to project on $ \{\sigma \in \mathbb{R}^n | \sum \sigma_i = 1 \}$; but not on $\Sigma_i$. –  user25004 Jul 20 '12 at 20:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.