<p>Given a problem </p>

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

<p>where $f$ is strongly convex in $Y$ and strongly concave in $X$</p>

<p>How to show that the following iterative processes will finally converge and how is the speed?</p>

<p>\begin{equation}
x_k=\arg\max_{x \in X} f(x,y_{k-1})
\end{equation}</p>

<p>\begin{equation}
y_k=\arg\min_{y \in Y} f(x_{k-1},y)
\end{equation}</p>

<p><strong>UPDATE 1</strong>: <em>The problem is being rewritten in order to distinguish from <a href="https://cstheory.stackexchange.com/questions/24975/iteratively-minimizing-the-function">another question</a> which looks similar.</em></p>

<p><strong>UPDATE 2</strong>: <em>The function $f$ is now strongly convex in $Y$ and strongly concave in $X$</em></p>

CC BY-SA 3.0
2014-07-02T10:30:17.963Z
@RB Thanks for pointing this out. I have rewritten the problem.
user25492
CC BY-SA 3.0
2014-07-02T10:41:05.037Z
As mentioned at the other question convexity (concavity) itself isn't enough. Without being strongly convex this isn't guaranteed to converge.
R B
CC BY-SA 3.0
2014-07-03T03:01:06.633Z
You should edit your original question instead.  I am closing this one.
Lev Reyzin
CC BY-SA 3.0
2014-07-03T03:32:47.520Z
@RB Thanks, I have updated the function as strongly convex in $Y$ and strongly concave in $X$
user25492
CC BY-SA 3.0
2014-07-03T03:33:41.493Z
@LevReyzin Thanks for pointing this out. I have modified the question so now it asks for proof.
user25492
CC BY-SA 3.0
2014-07-03T05:29:14.123Z
It doesn't matter, if the problem is not jointly convex in both variables, there are no general guarantees. It does sometimes work quite well, though.
Sasho Nikolov
<reference-request><optimization><proofs>
Proof of convergence of alternative minimization/maximization
user25492
# Proof of convergence of alternative minimization/maximization

(Asked by: username_0 on 2014-07-02)

Given a problem

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

where $f$ is strongly convex in $Y$ and strongly concave in $X$

How to show that the following iterative processes will finally converge and how is the speed?

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

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

**UPDATE 1**: *The problem is being rewritten in order to distinguish from [another question](https://cstheory.stackexchange.com/questions/24975/iteratively-minimizing-the-function) which looks similar.*

**UPDATE 2**: *The function $f$ is now strongly convex in $Y$ and strongly concave in $X$*

**Tags:** reference-request, optimization, proofs
> **Comments:**
> **username_0**: @RB Thanks for pointing this out. I have rewritten the problem.  
> **username_1**: As mentioned at the other question convexity (concavity) itself isn't enough. Without being strongly convex this isn't guaranteed to converge.  
> **username_2**: You should edit your original question instead.  I am closing this one.  
> **username_0**: @RB Thanks, I have updated the function as strongly convex in $Y$ and strongly concave in $X$  
> **username_0**: @LevReyzin Thanks for pointing this out. I have modified the question so now it asks for proof.  
> **username_3**: It doesn't matter, if the problem is not jointly convex in both variables, there are no general guarantees. It does sometimes work quite well, though.  

---

## 0 answers

