How to minimize the Bregman divergence on a convex hull spanned from a set of vectors? everyone.
It has been well known that the following minimization problem of a Bregman divergence with linear inequality
can be solved by successively projecting the current point to each constraint $\mathbf{a}_i^\top\mathbf{x}\leq b_i$ with a correction step, where $A=\begin{bmatrix} \mathbf{a}_1 & \ldots & \mathbf{a}_n \end{bmatrix}$, $\mathbf{b}=\begin{bmatrix} b_1 & \ldots & b_n \end{bmatrix}^\top$ and $n$ is the number of the constraints.
\begin{align}
\min_\mathbf{x}&D_\varphi(\mathbf{x},\mathbf{y})\\
\mathrm{s.t.}&A^\top\mathbf{x}\leq\mathbf{b}
\end{align}
Since each linear inequality constraint defines a half-space and the intersection of these half-spaces is a polyhedron, it is indeed an optimization problem on a polyhedron.
However, if the polyhedron is given by the convex hull description spanned by a set of vectors $\{\mathbf{v}_i\}_{i=1}^n$, i.e.
\begin{align}
\min_{\mathbf{x},\alpha}&D_\varphi(\mathbf{x},\mathbf{y})\\
\mathrm{s.t.}&\mathbf{x}=\sum_{i=1}^n{\alpha_i\mathbf{v}_i}\\
&0\leq\alpha_i\leq 1,\;\forall i=1,\ldots,n\\
&\sum_{i=1}^n{\alpha_i}=1
\end{align}
how can it be solved?
It seems that the problem can be solved by first converting the convex hull constraint to its half-space description, which is composed of a set of linear inequality constraints, and then applying the successive projection algorithm. However, it is not simple to obtain such a representation except in some special cases. Then, how can I solve this problem?
Any suggestion is welcome and I appreciate your help. Thank you very much!
 A: I am not aware of this successive projection algorithm: Can you provide a reference for it? In principle, I don't see a problem with what you are doing, because you only have $n$ nonnegativity constraints for the $\alpha$s, and two more for the equality constraint; unless you need a full-dimensional polytope for your successive projection to work.
If you are using Bregman divergence for minimizing a convex function, and your domain can be described as a simplex (of extreme points), you may want to try a non-Euclidean Bregman divergence, such as the entropy, or by \ell^p norms. They give much better complexity estimates, see e.g.


*

*Section 2, in: Nesterov, Nemirovski. On first order algorithms for \ell_1/nuclear norm minimization [2013]. http://www2.isye.gatech.edu/~nemirovs/ActaFinal_2013.pdf

*Section 5.7, in: Juditsky, Nemirovski. First Order Methods for Nonsmooth Large-Scale Convex Optimization [2012]. http://www2.isye.gatech.edu/~nemirovs/MLOptChapterI.pdf
A: I have no idea what the Bregman divergence is, but to me the two problem are just equivalent. 
You are implicitly assuming that your polyhedron is limited. If this holds, than the two representations are equivalent and you can use the one it suites you the most. They are the two faces of the same coin.
Clearly the first formulation uses half of the variables...and by the way, what is $y$?
