# projected gradient method, multiple constraints

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?

-

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.

-
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