# Formal proof of convergence of fixed point iteration inspired in dynamic programming

I have problems deriving formal proofs of following problem inspired in dynamic programming:

$V^{k+1}=\min_{\mu'}G(\mu',V^k)=T(V^k)$

$\mu^{k+1}=\arg \min_{\mu'} G(\mu',V^k)=\mu^*(V^k)$

where $V\in\mathcal{V}$ and $\mu\in\mathcal{U}$.

We make the following assumptions:

• $\mathcal{V}$ and $\mathcal{U}$ are compact.
• $G(\mu,V)$ is convex and differentiable in $\mu$ and thus $\mu^*(V)$ is unique.
• $\mu^*(V)$ is differentiable in $V$.
• $\mu^*(V)$ is an interior point for every $V\in \mathcal{V}$.
• $T$ is a contraction mapping, i.e., $\|\frac{\partial T(V)}{\partial V}\|<1$.

Since $T$ is a contraction mapping, $V^k$ converges to the (unique) fixed point of $T$. It is obvious then that $\mu^k$ also converges, since it is unique for each $V^k$ and $V^k$ converges.

However, I'm having problems deriving a "formal" proof for the whole fixed point system:

$(V,\mu)=F\left((V,\mu)\right)=(T(V),\mu^*(V))$

This fixed point system will have a unique solution if $F$ is a contraction mapping in the space $\mathcal{V}\times\mathcal{U}$, i.e., $\|\frac{\partial F(V,\mu)}{\partial (V,\mu)}\|<1$ in the product norm. Since $F$ does not depend on $\mu$, $\|\frac{\partial F(V,\mu)}{\partial \mu}\|=0$. Now choosing the $\infty$ norm for the Jacobian the norm would be:

$\|\frac{\partial F(V,\mu)}{\partial (V,\mu)}\|=\max\{\|\frac{\partial T(V)}{\partial V}\|,\|\frac{\partial \mu^*(V)}{\partial V}\|\}$

Now, from the assumptions we know that $\|\frac{\partial T(V)}{\partial V}\|<1$, but I don't know how to prove that $\|\frac{\partial \mu^*(V)}{\partial V}\|<1$ using the given assumptions, or if I overlooked something important.

Please feel free to correct any mistakes or give any ideas. Any help would be greatly appreciated.

Thank you very much.

• Minor notational nitpick: even though the scope of $\mu$ is specified by the $\min$ and $\arg \min$ operations, it might be be best to use a different symbol than your sequential variable $\mu^z$. – Ian Sep 12 '16 at 13:41
• It was a typo, thank you. I'll correct the notation. – Jorge del Val Sep 12 '16 at 13:42
• I actually read over it again (I was referring to the formulation at the top). It makes sense now (you take an argmin to get a value of $\mu$ and store that as your next iterate for $\mu$). I think your newest version with $\mu'$ is a bit clearer though (it stresses that $\mu'$ is just a "dummy variable). – Ian Sep 12 '16 at 13:45
• Okay, I put $\mu'$ instead for the auxiliary optimization variable. I want it to be clear that the sequential variable is the result of the optimization in that variable, and thus call them in a similar way. Thank you for your comments! – Jorge del Val Sep 12 '16 at 13:47
• Anyway, I'm not sure I see the problem. $F((V,\mu))$ is "really" a function only of $V$, not of $\mu$. (You want $\mu$ to be an argument so that you have a mapping from a space to itself, but there is no actual dependence on $\mu$.) So you can choose a norm on the $(V,\mu)$ variables which only cares a "tiny bit" about $\mu$, like $\| (V,\mu) \|=\sqrt{\| V \|_1^2 + \epsilon^2 \| \mu \|_2^2}$ where $\| \cdot \|_1$ and $\| \cdot \|_2$ are some given norms and $\epsilon$ is sufficiently small. Then $F$ should be a contraction in such a norm by virtue of the fact that $T$ is. – Ian Sep 12 '16 at 13:47

I think you need regularity assumptions on the convexity with respect to $\mu$. If not a small change in $V$ may produce a large change in $\mu^*$. The mapping $T$ may well be Lipschitz-contracting without convexity in $\mu$. But usually $T$ is not differentiable without that convexity.

• Thank you for the sugestion. I think that assumption was already made in line 4. – Jorge del Val Sep 12 '16 at 14:04
• Yes but without a lower bound say on the second derivative w.r.t. $\mu$ the function $\mu^*$ need not even be differentiable w.r.t. $V$ – H. H. Rugh Sep 12 '16 at 14:06
• You are right, I will edit for differentiability assumptions. – Jorge del Val Sep 12 '16 at 14:09
• OK, but note that with e.g. $G(\mu,V)=\mu^4 - 4\mu V$ the critical point $\mu^*=V^{1/3}$ is not differentiable w.r.t. $V$. – H. H. Rugh Sep 12 '16 at 14:10
• If you assume $\mu^*$ differentiable with a bounded derivative then the idea of @Ian works fine. But I think it is a bit 'cheating' to make such an assumption on $\mu^*$. I think as already mentioned you should rather impose lower convexity bound on $G$ w.r.t. $\mu$. But just my opinion – H. H. Rugh Sep 12 '16 at 14:19