Optimizing multivariable functions by sections

Question

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?

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.