constraintsconvex optimizationsimplex
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?
It appears that there are methods for accelerated projected/proximal gradient descent, though no one seems to have worked out how to combine the state-of-the-art best methods for accelerated gradient descent (e.g., Adam, RMSprop, etc.) with projected/proximal gradient descent yet -- so you can choose either projected/proximal gradient descent with a sub-par method of acceleration, or normal gradient descent with a method of acceleration that works better in practice.
In other detail... there are multiple methods of acceleration: e.g., simple momentum, Nesterov acceleration, Adagrad, Adadelta, RMSprop, Adam. In practice, experience (with ordinary gradient descent) suggests that some of these perform better than others. For instance, for some machine learning tasks, right now Adam appears to be the most effective of those.
When you move from ordinary gradient descent to projected/proximal gradient descent, there has been some work on combining some of those methods of acceleration to proximal gradient descent... but the literature lags a bit. For instance, it appears that no one has worked out how to apply Adam-style momentum to projected or proximal gradient descent. Perhaps in time the literature will catch up.
I think a rigorous proof of convergence is not so easy but can certainly be found in several books on the topic. I will give you a heuristic approach to see the plausibility of the algorithm. I focus on the first part of your question for now.
Heuristic arguments
$\qquad\qquad\qquad\qquad\qquad\qquad\quad$
$\qquad\qquad\qquad\qquad\qquad\qquad$
$\qquad\qquad\qquad\qquad\qquad\qquad$
Best Answer
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.