I'm reading this pdf about an implementation of the PDHG algorithm for convex minimization. At the beginning of page 9, authors make an operation I can't not understand.
In short, this is what happens:
Let $K \in \mathbb{R}^{m \times n}, x \in \mathbb{R}^n, y \in \mathbb{R}^m$. $f^*$ and $g$ are convex functions, $\partial f^*$ and $\partial g$ are their respctive subdifferentials. I define the following:
$$u = \begin{bmatrix} x \\ y \end{bmatrix}$$
$$M_k = \begin{bmatrix} \frac{1}{\tau}I & -K^T \\ -K & \frac{1}{\sigma}I \end{bmatrix}$$
$$R(u) = \begin{bmatrix} \partial g(x) + K^Ty \\ \partial f^*(y) -Kx \end{bmatrix}$$
For this question it is not important if $\tau$ and $\sigma$ are variable or constant.
The iterates of the PDHG algorithm satisfy (eq 35 in the paper): $$0 \in R(u_{k+1}) + M_k(u_{k+1} - u_k) \tag{1}$$ The optimally condition is (eq 36 in the paper): $$0 \in R(u^*) \tag{2}$$ Also $R$ is a monotone operator: $$(u-\hat{u})^T(R(u) - R(\hat{u})) \geq 0, \forall u, \hat{u}$$ Subtracting equation 1 from 2 results: $$M_k(u_{k+1} - u_k) \in R(u^*) - R(u_{k+1}) \tag{3}$$ Everything ok until next step: how to take the inner product of equation 3 with $(u^* - u_{k+1})$ to get: $$(u^* - u_{k+1})^TM_k(u_{k+1} - u_k) \geq (u^* - u_{k+1})^T(R(u^*) - R(u_{k+1}))$$ I don't know how authors get this result. Is it calculated from the definition of subdiferential or its resolvent? How can I take the inner product with a set and get an inequality?
Edit: The notation used by authors is pretty ugly. If I do:
Let $R$ be monotone and let $u\in R(x), v\in R(y) \Rightarrow u-v \in R(x) - R(y)$ then $$(x-y)^T(u-v) \ge 0$$ I also have $M_k(u-v) \in R(x) - R(y)$
Let $m_k = M_k(u - v) \Rightarrow m_k \in R(x) - R(y) \Rightarrow (x - y)^Tm_k \geq 0$
And at the end I just replace $x = u^*, y = u^{k+1}$.
So the step $$(u^* - u_{k+1})^TM_k(u_{k+1} - u_k) \geq (u^* - u_{k+1})^T(R(u^*) - R(u_{k+1}))$$ Is unnecessary, maybe incorrect, and confusing.
Thanks xel!
I haven't read the rest of the paper, but the way you (and they) present it is the following: Let $R$ be monotone and let $u_0\in R(x), v_0\in R(y)$, then $$ (x-y)^T(u_0-v_0) \ge (x-y)^T(u-v) $$ for all $u\in R(x), v\in R(y)$, which is not true. However, the (relevant) conclusion $$ (u^*-u_{k+1})^T M_k (u_{k+1}-u_k) \ge 0 $$ is still true and follows simply from monotonicity.
So there are two possibilties; either the statement follows from some special property of the matrix $M_k$ or; it was just a mistake that went unnoticed because the only relevant conclusion is still true (personally I believe the second option to be much more likely).