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 a single constraint, but not both at the same time (i.e. their intersection).

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.

  • $\begingroup$ 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. $\endgroup$ – user25004 Jul 19 '12 at 21:12
  • $\begingroup$ Each row of $X$ is a member of a simplex. Project the corresponding members of the gradient onto the corresponding simplex, then combine. $\endgroup$ – copper.hat Jul 19 '12 at 21:16
  • $\begingroup$ I do not see how the other constraint $X\ge 0$ is satisfied here? $\endgroup$ – user25004 Jul 20 '12 at 19:49
  • $\begingroup$ Please see my elaboration above. If I am missing something, please explain. $\endgroup$ – copper.hat Jul 20 '12 at 20:05
  • 1
    $\begingroup$ @user2987: If I recall, the algorithm was very simple, project onto the affine hull of the simplex and then zero the coordinates with negative barycentric coordinates. Then continue with the affine hull of non negative barycentric coordinates. $\endgroup$ – copper.hat Nov 8 '16 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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