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\)，其定义为

对于任意的\((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定义为

同样当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

相对于

Damped iteration为一个\(x^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

Douglas-Rachfold updating

The last equation:

Case: Alternating direction method of multipliers

Case: Constrained optimization

Consensus Optimization

参考资料

• Monotone Operators - Boyd
• Monotone Operator Splitting Methods - Boyd