0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Ian Sep 12 '16 at 13:41
  • $\begingroup$ It was a typo, thank you. I'll correct the notation. $\endgroup$ – Jorge del Val Sep 12 '16 at 13:42
  • $\begingroup$ 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). $\endgroup$ – Ian Sep 12 '16 at 13:45
  • $\begingroup$ 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! $\endgroup$ – Jorge del Val Sep 12 '16 at 13:47
  • $\begingroup$ 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. $\endgroup$ – Ian Sep 12 '16 at 13:47
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the sugestion. I think that assumption was already made in line 4. $\endgroup$ – Jorge del Val Sep 12 '16 at 14:04
  • $\begingroup$ 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$ $\endgroup$ – H. H. Rugh Sep 12 '16 at 14:06
  • $\begingroup$ You are right, I will edit for differentiability assumptions. $\endgroup$ – Jorge del Val Sep 12 '16 at 14:09
  • $\begingroup$ 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$. $\endgroup$ – H. H. Rugh Sep 12 '16 at 14:10
  • $\begingroup$ 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 $\endgroup$ – H. H. Rugh Sep 12 '16 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.