Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $f$ be a jointly convex function of 2 variables say $x,y$. I am interested in solving the optimization problem $$\min_{x,y\in\Delta} f(x,y)$$ where $\Delta$ is a $d$ dimensional simplex. An intuitive algorithm that I have come up with is a coordinate mirror descent algorithm, where in each iteration we perform two steps. In the first step I fix one variable, say $x$, and optimize w.r.t y (almost) exactly by performing many steps of mirror descent, with the entropy function. The second step is similar to the first step, but now we shall perform mirror descent w.r.t. the second variable. This algorithm is performed repeatedly until convergence.

My question is that have people studied such algorithms? I know that there is literature on coordinate descent, but I have not seen any coordinate mirror descent type of algorithms. I am particularly interested in convergence guarantees, and rates of convergence. Intuitions/counter-examples are also welcome.

I know that I can avoid mirror descent procedure, and instead perform gradient descent coordinate-wise. The reason why I want to avoid this is because mirror descent with the entropy function is a natural fit when the constraint set is a simplex, and I can devise simple exponential updates for each sub problem being solved.

P.S. Turns out that, such coordinate mirror descent algorithms, will converge provably. For further results see the following paper. http://arxiv.org/abs/1309.2249

share|improve this question
    
Perhaps you would care to enlighten me as to what "mirror descent" is, and what "the entropy function" is?! –  Igor Rivin Jul 16 '13 at 1:28
    
mirror descent is an optimization algorithm for convex functions, that utilizes distances defined by the Bregman divergence of another convex function $\phi$. In this case since our optimization problem is over simplex, a good choice of $\phi$ is $\phi(x)=\sum_{i} x_i \log (x_i)$, when $x\in \Delta$ with $\Delta$ being the simplex in $\mathbb{R}^{n}$, and $\infty$ otherwise. For more details kindly look at the paper "Mirror descent and nonlinear projected subgradient methods for convex optimization" by Amir Beck and Marc Teboulle, where they discuss minimizing a convex function over simplex. –  gmravi2003 Jul 16 '13 at 5:31
    
Ah, ok, thanks! –  Igor Rivin Jul 16 '13 at 12:29
    
I just want to point out that the key word for your question is: 'alternating minimization' or 'coordinate descent'. This area has grown significantly: see en.wikipedia.org/wiki/Random_coordinate_descent –  Cristóbal Guzmán Apr 13 at 23:01
    
Thanks Cristobal. I would like to point out that the posted problem has been solved. Here is a link to the paper. arxiv.org/abs/1309.2249 –  gmravi2003 Apr 13 at 23:34

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.