Let $f(x_1,x_2,\ldots,x_n)$ be function of several real variables $x_1, x_2, \ldots, x_n$. Suppose that every local maximum of $f(x_1,x_2,\ldots,x_n)$ is actually a global maximum. The question is to prove under what circumstances the maximum value of $f(x_1,x_2,x_3,\ldots,x_n)$ can be obtained by the following algorithm:

  1. Take some set initial values $\{x_1^{(0)},x_2^{(0)},\ldots,x_n^{(0)}\}$ and maximize $f(x_1,x_2^{(0)},\ldots,x_n^{(0)})$ as a function of $x_1$ obtaining some value $x_1^{(1)}$.

  2. Maximize $f(x_1^{(1)},x_2,x_3^{(0)},\ldots,x_n^{(0)})$ as a function of $x_2$, obtaining $x_2^{(1)}$.

  3. Repeat $n$ times with each variable to obtain the set $\{x_1^{(1)},x_2^{(1)},\ldots,x_n^{(1)}\}$.

  4. Start again at the step 1, with the set of values $\{x_1^{(1)},x_2^{(1)},\ldots,x_n^{(1)}\}$ and continue with steps 2 and 3 to find the set $\{x_1^{(2)},x_2^{(2)},\ldots,x_n^{(2)}\}$.

  5. Repeat the process until convergence, i.e. $\{x_1^{(\infty)},x_2^{(\infty)},\ldots,x_n^{(\infty)}\}$ is such that $f(x_1^{(\infty)},x_2^{(\infty)},\ldots,x_n^{(\infty)})$ is maximum.

Is there some standard name for this optimization method?, what is the speed of convergence?


1 Answer 1


Let consider the equivalent minimization problem of the given problem. Then method that you mentioned is known as co-ordinate descent method (otherwise it is can be called as coordinate ascend method). For locally convex function, it can be shown that it converges to the minima. It uses the majorization approach to ensure that the objective function decreases in each step however we need to ensure that $\|x^{k+1}-x^{k}\| \geq \epsilon$, for some $\epsilon > 0$.

To know more about it, you can check out this paper by Nesterov.

  • 1
    $\begingroup$ Many thanks for the answer! Just a comment: I guess $-f$ needs not to be a convex function. For example for $f(x_1,x_2)=\sin(x_1)+\sin(x_2)$ every local minimum is also a global minimum but it is not convex. $\endgroup$ Sep 10, 2015 at 17:23
  • $\begingroup$ Yes, you are completely right. I have to update my answer then. Thanks. $\endgroup$
    – Rajat
    Sep 10, 2015 at 17:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .