Relation
关系这个词跟映射有点相似，对于一个关系\(R\)，其是\((x, y)\)的一个集合集合。其中\(\text{dom }R=\{x|(x,y)\in R\}\)，\(R(x)=\{y\vert (x,y)\in R\}\)，其零集合是\(\{x| (x,y)\in R, y=0\}\)。
Operations on Relation
-
inverse. \(R^{-1}=\{(y, x)\vert (x,y)\in R\}\) -
composition. \(RS=\{(x, y)\vert (x,z)\in R, (z,y)\in S\}\) -
scalar multiplication. \(\alpha R=\{(x, \alpha y)\vert (x,y)\in R\}\) -
addition. \(R+S=\{(x, y+z)\vert (x,y)\in R, (x,z)\in S\}\) -
resolvent operator. \(S=(I+\lambda R)^{-1}\)
通过以上的运算可以看出，relation有点类似于凸函数中epigraph的那种集合定义。
Monotone Operations
对于一个单调的relation \(F\)，其定义为
\[(u-v)^T(x-y)\geq 0 \]对于任意的\((x, y), (u,v)\in R\). 一个最大单调\(F\)的定义为，没有其他单调relation包含\(F\)。
\(F\)是最大单调当且仅当\(F\)是一个连接的曲线，其斜率不存在负值。
Case: Subgradient \(F=\partial f(x)\)
Nonexpansive and contractive operator
对于一个\(L-\)Lipschitz连续的operator \(F\)，其nonexpansive和contraction的定义分别为\(L=1\)和\(L<1\)。
Characters:
Resolvent operation and Cayley operator
对于一个relation \(F\)，当\(F\)是单调且nonexpansive时，\(R\) operator是contractive的。\(F\)的cayley operator定义为
\[C=2R-I=2(I+\lambda F)^{-1}-I \]同样当F是单调的时候，其cayley operator \(C\)是nonexpansive。
Proof:
Case:
Proximal
promial
Indicator
Fixed point of operators & zero set of \(F\)
这里有个很重要的定理就是Cayley和resolvent的Fixed point等价于\(F\) relation的zero set。也就是
Theorem: Banach fixed point theorem
当\(F\)是contraction，dom \(F=R^n\)，那么\(F(x)\)会收敛到一个唯一的fixed point。
Damped iteration of a nonexpansive operator
相对于
\[x^{k+1}=F(x^k) \]Damped iteration为一个\(x^k\)和\(F(x^k)\)的组合
\[x^{k+1} = \theta^k x^k+(1-\theta^k)F(x^k) \]Proof:
Case:
Operator Splitting
这里要解决的问题是一个relation \(F=A+B\)，单独队\(F\)进行求解可能比较麻烦而分开对\(A\)和\(B\)求解更简单。
Theorem: 如果A和B是maximal monotone，那么
\[0\in A(x)+B(x) \Leftrightarrow C_AC_B(z)=z \]其中\(x=R_B(z)\)
Proof:
证明也是比较简单，使用定义就可以得到。
Peaceman-Rachford & Douglas-Rachfold Splitting
\[\begin{align} &\text{Peaceman-Rachford}:\qquad z^{k+1}=C_AC_B(z^k)\\ &\text{Douglas-Rachfold}:\qquad z^{k+1}=\frac 1 2(I+C_AC_B)(z^k)\\ \end{align} \]Douglas-Rachfold updating
The last equation:
Case: Alternating direction method of multipliers
Case: Constrained optimization
