Q1

Consider the following question

Show that if \(\forall y \in \operatorname{dom}(g), \partial g(prox_f (y)) \supseteq \partial g(y)\), then \(prox_{f+g}(x) = prox_{f}(prox_{g}(x))\)

Proof:

\[prox_{f+g} = argmin \frac{1}{2} ||z - x||_2^2 + f(z) + g(z)\] \[prox_{f} = argmin \frac{1}{2} ||z - x||_2^2 + f(z)\] \[prox_{g} = argmin \frac{1}{2} ||z - x||_2^2 + g(z)\] \[0 \in prox_{f+g}(x) - x + \partial f(prox_{f+g}(x)) + \partial g(prox_{f+g}(x)))\] \[0 \in prox_{g}(x) - x + \partial g(prox_g(x))\] \[0 \in prox_f(prox_g(x)) - prox_g(x) + \partial f(prox_f(prox_g(x)))\]

Sum up the last 2 statement, we know

\[0 \in prox_f(prox_g(x)) - x + \partial g(prox_g(x)) + \partial f(prox_f(prox_g(x)))\]

Let \(y = prox_g(x)\), \(0 \in prox_f(y) - x + \partial g(y) + \partial f(prox_f(y))\)

because \(\partial g(prox_f (y)) \supseteq \partial g(y)\), therefore we have

\[0 \in prox_f(y) - x + \partial g(prox_f (y)) + \partial f(prox_f(y))\]

apparently this says, \(prox_f(y)\) satisfy, \(0 \in prox_{f+g}(x) - x + \partial f(prox_{f+g}(x)) + \partial g(prox_{f+g}(x)))\),

which means \(prox_f(prox_g(x)) = prox_{f+g}(x)\)

Q2

Use Holder’s inequality to show that for \(f(x)=\|x\|_p\),

its subdifferential is \(\partial f(x) = argmax_{\|z\|_q \leq 1} z^T x\)

It’s too hard to write it form the blog latex, so I chose to put a solution pdf here

comments powered by Disqus