<p>It's not hard to show that if $f$ is <a href="http://en.wikipedia.org/wiki/Convex_function#Strongly_convex_functions" rel="nofollow">strongly convex</a> then this approach converges and you can give an upper bound on the number of iterations needed.</p>

<p>If $f$ is strictly convex, but not strongly convex, this might converge very slow or even not converge at all.</p>

<p>If $f$ is not convex at all, you are likely to end in a local optima rather than the global one.</p>

<p>You might also like to take a look at  the <a href="http://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm" rel="nofollow">Expectation–maximization algorithm</a> which is quite similar, but also deals with unobserved values.</p>

<p>Also, there are applications where $f$ is a non-convex function at all with respect to $x,y$, but it is convex w.r.t. each of them (e.g. $f(x,y)=xy$).
In these problems, the iterative process you describe is many times used in practice and works quite well.</p>

CC BY-SA 3.0
2014-06-25T07:23:46.663Z
Thanks for your answer. Is there any references about this method?
Lib
CC BY-SA 3.0
2014-06-23T10:09:37.023Z
2014-06-23T10:19:40.710Z
2014-06-23T10:19:40.710Z
R B
<p>This is a very popular heuristic method in machine learning, known as <em>alternating minimization</em>. You can easily find <a href="http://scholar.google.com/scholar?hl=en&amp;q=alternating%20minimization&amp;" rel="nofollow">tons of papers</a> using it. Often the setting in which it is used is when $f(x,y)$ is convex in $x$ and $y$ separately (so each minimization step can be done via some variant of gradient descent), but not jointly convex. In this case, as RB notes, it is not apriori clear that this method converges to an optimal solution at all. A classical paper by <a href="http://www.ece.tamu.edu/~tieliu/WWW/ECEN647-SP14_files/CT-SD84.pdf" rel="nofollow">Csiszar and Tusnady</a> gives a general "five point criterion" for convergance to the global optimum, and proves that it holds for $f$ equal to the KL-divergence. More recently, <a href="http://arxiv.org/pdf/1212.0467v1.pdf" rel="nofollow">Jain, Nethrapalli and Singhavi</a>, and <a href="http://arxiv.org/pdf/1312.0925v3.pdf" rel="nofollow">Hardt</a> have analyzed variants of this approach for the matrix completion problem.</p>

CC BY-SA 3.0
2014-06-27T00:14:47.060Z
2014-07-04T07:05:14.407Z
2014-07-04T07:05:14.407Z
Sasho Nikolov
<p>Consider the problem</p>

<p>\begin{equation}
\min_{x\in X, y \in Y} f(x,y)
\end{equation}</p>

<p>Can I solve the problem by iteratively solving the following two sub problems?</p>

<p>\begin{equation}
x_{k+1} = \arg\min_{x\in X} f(x,y_k)
\end{equation}</p>

<p>\begin{equation}
y_{k+1} = \arg\min_{ y \in Y} f(x_k,y)
\end{equation}</p>

<p>If yes, is there any books/papers talking about this kind of approach?</p>

<p>Thanks</p>

<reference-request><optimization>
Iteratively minimizing the function
Lib
# Iteratively minimizing the function

(Asked by: username_0 on 2014-06-23)

Consider the problem

\begin{equation}
\min\_{x\in X, y \in Y} f(x,y)
\end{equation}

Can I solve the problem by iteratively solving the following two sub problems?

\begin{equation}
x\_{k+1} = \arg\min\_{x\in X} f(x,y\_k)
\end{equation}

\begin{equation}
y\_{k+1} = \arg\min\_{ y \in Y} f(x\_k,y)
\end{equation}

If yes, is there any books/papers talking about this kind of approach?

Thanks

**Tags:** reference-request, optimization


---

## 2 answers

### Answer by username_1 on 2014-06-23. Score: 3 | Accepted answer

It's not hard to show that if $f$ is [strongly convex](http://en.wikipedia.org/wiki/Convex_function#Strongly_convex_functions) then this approach converges and you can give an upper bound on the number of iterations needed.

If $f$ is strictly convex, but not strongly convex, this might converge very slow or even not converge at all.

If $f$ is not convex at all, you are likely to end in a local optima rather than the global one.

You might also like to take a look at the [Expectation–maximization algorithm](http://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm) which is quite similar, but also deals with unobserved values.

Also, there are applications where $f$ is a non-convex function at all with respect to $x,y$, but it is convex w.r.t. each of them (e.g. $f(x,y)=xy$).
In these problems, the iterative process you describe is many times used in practice and works quite well.

> **Comments:**
> **username_0**: Thanks for your answer. Is there any references about this method?  

---

### Answer by username_2 on 2014-06-27. Score: 4

This is a very popular heuristic method in machine learning, known as *alternating minimization*. You can easily find [tons of papers](http://scholar.google.com/scholar?hl=en&q=alternating%20minimization&) using it. Often the setting in which it is used is when $f(x,y)$ is convex in $x$ and $y$ separately (so each minimization step can be done via some variant of gradient descent), but not jointly convex. In this case, as RB notes, it is not apriori clear that this method converges to an optimal solution at all. A classical paper by [Csiszar and Tusnady](http://www.ece.tamu.edu/~tieliu/WWW/ECEN647-SP14_files/CT-SD84.pdf) gives a general "five point criterion" for convergance to the global optimum, and proves that it holds for $f$ equal to the KL-divergence. More recently, [Jain, Nethrapalli and Singhavi](http://arxiv.org/pdf/1212.0467v1.pdf), and [Hardt](http://arxiv.org/pdf/1312.0925v3.pdf) have analyzed variants of this approach for the matrix completion problem.


---

