【求解变分不等式】

介绍

设 $\theta :R^n\to (?\infty ,\infty ]$ 为闭正常凸函数，$F:R^n\to R^n$为向量
值和连续映射。广义变分不等式$(GVI)$[9,19]形式如下$$x^{?}\in R^n,\theta (x)?\theta (x^{?})+(x?x^{?}{)}^{T}F(x^{?})\ge 0,?x\in R^n.$$
保留$\infty ?\infty =\infty$的算术运算。在本文中，我们关注$F$是单调的情况，即$(F(x)?F(y){)}^T(x?y)\ge 0$，对于所有$x,y\in R^n$。在本文中，我们对$MGVI(\theta ,F)$做了以下额外的假设:
$(a)$单调算子$F$是$Lipschitz$连续的,其中$Lipschitz$ 常数 $L>0$。
$(b)$$MGVI(\theta ,F)$的解集，表示为${\Omega }^{?}$，非空。

各种凸优化问题可以表述为$MGVIs$，例如最小绝对收缩和选择算子(LASSO,least absolute shrinkage and selection operator/$l_1$正则化最小二乘)问题、基追问题[7]、基追去噪问题[5]，和 $Dantzig$ 选择器 [6]，等等。此外，单调广义变分不等式($MGVI$，monotone generalized variational inequality)包含经典单调变分不等式 ($MVI$,monotone variational inequality)。通过设置$\theta ={\delta }_C$( ${\delta }_C$是$C$的指标函数，如果是$x\in C$，则等于$0$，否则等于$\infty$。),其中$C?R^n$是一个非空闭凸集，则 $MGVI$ 就以下列形式简化为$MVI$
$$x^{?}\in C,(x?x^{?}{)}^{T}F(x^{?})\ge 0,?x\in C.$$
设$f:R^n\to (?\infty ,\infty ]$为闭正常凸函数，$f$的邻近算子定义如下
P r o x f : x ? a r g m i n { f ( y ) + 1 2 ∥ x ? y ∥ 2 : y ∈ R n } Prox_f:x \mapsto argmin\{f(y)+\frac{1}{2}\|x-y\|^2 : y \in R^n\} Proxf?:x?argmin{f(y)+21?∥x?y∥2:y∈Rn}

设$f:R^n\to (?\infty ,\infty ]$为闭正常凸函数。那么接下来的三个条件是等价的:
$1.p=Pro{x}_f(x).$
$2.x?p\in ?f(p).$
$3.$ 对于所有$w\in R^n$，都有$(x?p{)}^T(p?w)\ge f(p)?f(w).$

$l_1$正则化最小二乘问题

对线性逆问题：
$b=Ax+w$,其中$b\in R^m,A\in R^{m\times n}$已知,$w$为噪音，求解$x$。

让噪声最小，最小二乘法求解：
$\tilde{x}=\underset{x}{\mathrm{argmin}}\Vert Ax?b{\Vert }^2$
若$m=n$且$A$非奇异,$x=A^{?1}y$。但是很多情况下，$A$病态，用最小二乘法求解时，系统微小的扰动都会导致结果差别很大。为了求解病态线性系统的逆问题，可以使用$l_2$正则化最小二乘（也叫Tikhonov regularization，Ridge regression）
x ~ = arg ? min ? x { 1 2 ∥ A x ? b ∥ 2 + λ ∥ x ∥ 2 } \widetilde{x}=\mathop{\arg\min}\limits_{x}\{\frac{1}{2}\|Ax-b\|^2+\lambda\|x\|_2\} x =xargmin?{21?∥Ax?b∥2+λ∥x∥2?}，
即 m i n x ∈ R n f ( x ) : = { 1 2 ∥ A x ? b ∥ 2 + λ ∥ x ∥ 2 } \mathop{min}\limits_{x\in R^n}f(x):=\{\frac{1}{2}\|Ax-b\|^2+\lambda\|x\|_2\} x∈Rnmin?f(x):={21?∥Ax?b∥2+λ∥x∥2?}

而$l_1$正则化最小二乘（Lasso，least absolute shrinkage and selection operator，最小绝对值收敛和选择算子）问题。
m i n x ∈ R n f ( x ) : = { 1 2 ∥ A x ? b ∥ 2 + λ ∥ x ∥ 1 } \mathop{min}\limits_{x\in R^n}f(x):=\{\frac{1}{2}\|Ax-b\|^2+\lambda\|x\|_1\} x∈Rnmin?f(x):={21?∥Ax?b∥2+λ∥x∥1?}
对无约束问题$minf(x)，x\in R^n$
梯度下降法$$x_k=x_{k?1}?t_{k?1}?f(x_{k?1})$$
梯度下降法对可微函数可直接求微分，对不可微函数引入了次梯度（subgradient），次微分（subdifferential）概念
投影算子（projection,Pc）
$$Pc=Pro{x}_{t_k{\delta }_C}$$
$$x_k=Pc(x_{k?1}?t_{k?1}?f(x_{k?1}))$$
近端线性 x k = arg ? min ? x { f ( x k ? 1 ) + < x ? x k ? 1 , ? f ( x k ? 1 ) > + 1 2 t k ? 1 ∥ x ? x k ? 1 ∥ 2 } x_k=\mathop{\arg\min}\limits_{x}\{f(x_{k-1})+<x-x_{k-1},\nabla f(x_{k-1})>+\frac{1}{2t_{k-1}}\|x-x_{k-1}\|^2\} xk?=xargmin?{f(xk?1?)+<x?xk?1?,?f(xk?1?)>+2tk?1?1?∥x?xk?1?∥2}
$$f(x_{k?1})+<x?x_{k?1},?f(x_{k?1})>+\frac{1}{2t_{k?1}}\Vert x?x_{k?1}{\Vert }^2=\frac{1}{2t_{k?1}}\Vert x?(x_{k?1}?t_{k?1}?f(x_{k?1})){\Vert }^2+D$$
D为常数
x k = arg ? min ? x { 1 2 t k ∥ x ? ( x k ? 1 ? t k ? 1 ? f ( x k ? 1 ) ) ∥ 2 } x_k=\mathop{\arg\min}\limits_{x}\{\frac{1}{2t_k}\|x-(x_{k-1}-t_{k-1}\nabla f(x_{k-1}))\|^2\} xk?=xargmin?{2tk?1?∥x?(xk?1??tk?1??f(xk?1?))∥2}
对无约束问题$minf(x)+g(x)，x\in R^n$
x k + 1 = arg ? min ? x { f ( x k ) + < x ? x k , ? f ( x k ) > + 1 2 t k ∥ x ? x k ∥ 2 + g ( x ) } x_{k+1}=\mathop{\arg\min}\limits_{x}\{f(x_k)+<x-x_k,\nabla f(x_k)>+\frac{1}{2t_k}\|x-x_k\|^2+g(x)\} xk+1?=xargmin?{f(xk?)+<x?xk?,?f(xk?)>+2tk?1?∥x?xk?∥2+g(x)}
x k + 1 = arg ? min ? x { 1 2 ∥ x ? ( x k ? t k ? f ( x k ) ) ∥ 2 + t k g ( x ) } x_{k+1}=\mathop{\arg\min}\limits_{x}\{\frac{1}{2}\|x-(x_k-t_k\nabla f(x_k))\|^2+t_kg(x)\} xk+1?=xargmin?{21?∥x?(xk??tk??f(xk?))∥2+tk?g(x)}
即$$x_{k+1}=Pro{x}_{t_{k}g}(x_k?t_k?f(x_k))$$

基追问题

$$\begin{gathered} \min \Vert x{\Vert }_1 \\ s.t.Ax=b \end{gathered}$$
其中$A\in R^{m\times n},b\in R^n$

可分离两块凸优化模型

$$\begin{gathered} \min {\theta }_1(x)+{\theta }_2(x) \\ s.t.Ax+By=c \end{gathered}$$
其中$A\in R^{m\times n},B\in R^{m\times q},c\in R^m$，
${\theta }_1:R^n\to (?\infty ,\infty ]$和${\theta }_2:R^q\to (?\infty ,\infty ]$为两个正常闭和凸函数

迭代收缩阈值算法（ISTA，Iterative Shrinkage-Thresholding Algorithm）

ISTA

取$$f(x)=\frac{1}{2}\Vert Ax?b{\Vert }^2,g(x)=\lambda \Vert x{\Vert }_1$$
$$?f(x_k)=A^T(Ax?b),t_k=\frac{1}{L_k}$$
得
$$x_{k+1}=Pro{x}_{\frac{1}{L_k}\lambda \Vert {\Vert }_1}(x_k?\frac{1}{L_k}{A}^T(A{x}_k?b))$$
$L$是$?f(x)$的$Lipschitz$常数,$L>{\lambda }_{max}(A^{T}A)$
由${\mathrm{T}}_{\lambda t_k}=Pro{x}_{t_k\lambda \Vert {\Vert }_1}=Pro{x}_{\lambda t_k}$得
$$x_{k+1}=T_{\frac{\lambda }{L_k}}(x_k?\frac{1}{L_k}{A}^T(A{x}_k?b))$$
收缩阈值算子（Shrinkage-Thresholding operator ）
$${\mathrm{T}}_{\lambda }(x)=sgn(x)max(|x|?\lambda ,0)=max(0,x?\lambda )+min(0,x+\lambda )$$
$x_k$收敛速度$O(\frac{1}{t})$

matlab核心代码

T = @(tau, x) max(0, x - tau) + min(0, x + tau);% 收缩阈值函数
x_new =  T(lambda/L0, x_old - (1/L0)*A'*(A*x_old-b));

FISTA改进：

快速迭代收缩阈值算法(FISTA，Fast Iterative Shrinkage-Thresholding Algorithm）

$step0:$
$$y_1=x_0,t_1=1$$
$stepk(k\ge 1):$
$$x_{k+1}=T_{\frac{\lambda }{L_k}}(y_k?\frac{1}{L_k}{A}^T(A{x}_k?b))$$
$$t_{k+1}=\frac{1+\sqrt{1+4t_k^2}}{2}$$
$$y_{k+1}=x_k+(\frac{t_k?1}{t_{k+1}})(x_k?x_{k?1})$$
$x_k$收敛速度$O(\frac{1}{t^2})$

广义外梯度法(GEM,Generalized Extragradient Method)

外梯度法(EM,Extragradient Method)

广义外梯度法（Generalized Extragradient Method）
由外梯度法（EM,Extragradient Method）推广得到，其中EM采用投影算子（$Pc$,projection operator),适用于求解$MVI（\theta ,F,C）$;GEM采用邻近算子($Prox$,proximity operator)，适用于求解$MGVI（\theta ,F）$,其他步骤基本相同，都是预估校正算法

GEM

$l_1$正则化最小二乘问题，由KKT条件，易知
$$\theta (x)=\lambda \Vert x{\Vert }_1,F(x)=A^T(Ax?b)$$
${\beta }^k\le \frac{\nu }{L},\nu \in (0,1),L$为$F(x)$的$Lipschitz$常数
GEM是预估校正算法
预测：$${\tilde{x}}_k=Pro{x}_{{\beta }^k\theta }(x_k?{\beta }^{k}F(x_k))$$
校正：$$x_{k+1}=Pro{x}_{{\beta }^k\theta }(x_k?{\beta }^{k}F({\tilde{x}}_k))$$

邻近收缩算法 （PCA，proximity and contraction algorithms)

收缩阈值算子（$\mathrm{T}$），投影算子（$P_C$）是特殊的邻近算子($Prox$)
邻近算子具有收缩性质，也就是生成的序列 { x k } \{x_k\} {xk?}会收敛

邻近点算法（PPA，proximity point algorithms)

邻近梯度算法(PGA，proximity gradient algorithms)

使用邻近算子（Prox)作为近似梯度
变分不等式
$$\theta ({\tilde{x}}^k)?\theta (x^{?})+({\tilde{x}}^k?x^{?}{)}^{T}F(x^{?})\ge 0$$
单调
$$({\tilde{x}}^k?x^{?}{)}^T(F({\tilde{x}}^k)?F(x^{?}))\ge 0$$

$PG{A}_{a1}$

$$F(x)=Mx+q$$
M半正定，不需要对称
$x^0\in R^n$，并且$\gamma \in (0,2),{\alpha }_k^{?}\ge \frac{1}{\Vert I+{\beta }^k{M}^T{\Vert }_2^2}$
$\text{预测器:}$选择${\beta }^k>0$，且${\tilde{x}}^k=Pro{x}_{{\beta }^k\theta }(x^k?{\beta }^{k}F(x^k))$;
$\text{校正器:}$设$d(x^k,{\tilde{x}}^k,{\beta }^k)=(I+{\beta }^k{M}^T)(x^k?{\tilde{x}}^k)$，并且计算${\alpha }_k^{?}=\frac{\Vert x^k?{\tilde{x}}^k{\Vert }^2}{\Vert d(x^k,{\tilde{x}}^k,{\beta }^k){\Vert }^2}$。设置$x^{k+1}=x^k?\gamma {\alpha }_k^{?}d(x^k,{\tilde{x}}^k,{\beta }^k)$。

$PG{A}_{a2}$

$$F(x)=Mx+q$$
M对称半正定，$G=I+\beta M$
$x^0\in R^n$，$\beta >0$，并且$\gamma \in (0,2)$，${\alpha }_k^{?}\ge \frac{1}{{\lambda }_{max}(G)}$
$\text{预测器:}{\tilde{x}}^k=Pro{x}_{\beta \theta }(x^k?\beta F(x^k))$;
$\text{校正器:}$设$d(x^k,{\tilde{x}}^k)=x^k?{\tilde{x}}^k$，并且计算${\alpha }_k^{?}=\frac{\Vert x^k?{\tilde{x}}^k{\Vert }^2}{\Vert d(x^k,{\tilde{x}}^k){\Vert }_G^2}$，设置$x^{k+1}=x^k?\gamma {\alpha }_k^{?}d(x^k,{\tilde{x}}^k)$。

$PG{A}_{b1}$

$F(x)$单调
$x^0\in R^n$，并且$\gamma \in (0,2)$ ，${\alpha }_k^{?}\ge \frac{1}{2}$
$\text{预测器:}$选择${\beta }^k>0$，使得${\beta }^k\Vert F(x^k)?F({\tilde{x}}^k)\Vert \le \nu \Vert x^k?{\tilde{x}}^k\Vert$，其中${\tilde{x}}^k=Pro{x}_{{\beta }^k\theta }(x^k?{\beta }^{k}F(x^k))$;
$\text{校正器:}$设置$d(x^k,{\tilde{x}}^k,{\beta }^k)=(x^k?{\tilde{x}}^k)?{\beta }^k(F(x^k)?F({\tilde{x}}^k))$，并且计算${\alpha }_k^{?}=\frac{(x^k?{\tilde{x}}^k{)}^{T}d(x^k,{\tilde{x}}^k,{\beta }^k)}{\Vert d(x^k,{\tilde{x}}^k,{\beta }^k){\Vert }^2}$，设置$x^{k+1}=x^k?\gamma {\alpha }_k^{?}d(x^k,{\tilde{x}}^k,{\beta }^k)$。

$PG{A}_{b2}$

$$F(x)=Ax+c$$
A对称半正定,$G=I?\beta M$,G对称正定
$x^0\in R^n$，$0<\beta <\frac{1}{{\lambda }_{max}(A)}$，并且$\gamma \in (0,2)$
$\text{预测器:}{\tilde{x}}^k=Pro{x}_{\beta \theta }(x^k?\beta F(x^k))$;
$\text{校正器:}$设$d(x^k,{\tilde{x}}^k)=x^k?{\tilde{x}}^k$，设置$x^{k+1}=x^k?\gamma d(x^k,{\tilde{x}}^k)$。

交替方向乘子法（ADMM，alternating direction method of multipliers）

$$mi{n}_{x,y,z}{\theta }_1(x)+{\theta }_2(x)+{\theta }_3(x)$$
$$s.t.f(x,y,z)=0$$
拉格朗日函数$$L(x,y,z,\lambda )={\theta }_1(x)+{\theta }_2(x)+{\theta }_3(x)+\lambda f(x,y,z)$$
$\lambda$为拉格朗日乘子
增广拉格朗日函数$$L(x,y,z,\lambda )={\theta }_1(x)+{\theta }_2(x)+{\theta }_3(x)+\lambda f(x,y,z)+\frac{\rho }{2}\Vert f(x,y,z){\Vert }_2^2$$
$\lambda$为拉格朗日乘子,$\rho$罚因子

ADMM

$$mi{n}_{x,y,z}{\theta }_1(x)+{\theta }_2(x)$$
$$s.t.Ax+By=c$$
$\text{初始化:}{x}^0\in R^n$，$y^0\in R^q$，${\lambda }^0\in R^m$，并且$\rho >0.$
$\text{一般步骤:}$对$k=0,1,$…执行以下步骤:
( a ) x k + 1 ∈ arg ? min ? { θ 1 ( x ) + ρ 2 ∥ A x + B y k ? c + 1 ρ λ k ∥ 2 : x ∈ R n } ; (a)x^{k+1}\in \mathop{\arg\min}\{\theta_1(x)+\frac{\rho}{2}\|Ax+By^k-c+\frac{1}{\rho}\lambda^k\|^2:x\in R^n\}; (a)xk+1∈argmin{θ1?(x)+2ρ?∥Ax+Byk?c+ρ1?λk∥2:x∈Rn};
( b ) y k + 1 ∈ arg ? min ? { θ 2 ( y ) + ρ 2 ∥ A x k + 1 + B y ? c + 1 ρ λ k ∥ 2 : x ∈ R q } ; (b)y^{k+1}\in \mathop{\arg\min}\{\theta_2(y)+\frac{\rho}{2}\|Ax^{k+1}+By-c+\frac{1}{\rho}\lambda^k\|^2:x\in R^q\}; (b)yk+1∈argmin{θ2?(y)+2ρ?∥Axk+1+By?c+ρ1?λk∥2:x∈Rq};
$(c){\lambda }^{k+1}={\lambda }^k+\rho (A{x}^{k+1}+B{y}^{k+1}?c).$

交替方向线性近似乘子法（AD-LPMM，linearized proximal）

交替方向近似乘子法（AD-PMM,proximal）的一个特例
$\text{初始化:}{x}^0\in R^n$，$y^0\in R^q$，${\lambda }^0\in R^m$，
$\rho >0$，$\alpha \ge \rho {\lambda }_{max}(A^{T}A)$，$\beta \ge \rho {\lambda }_{max}(B^{T}B).$
$\text{一般步骤:}$对$k=0,1,$…执行以下步骤:
$(a)x^{k+1}=Pro{x}_{\frac{1}{\alpha }{\theta }_1}[x^k+\frac{\rho }{\alpha }{A}^T(A{x}^k+B{y}^k?c+\frac{1}{\rho }{\lambda }^k)];$
$(b)y^{k+1}=Pro{x}_{\frac{1}{\beta }{\theta }_2}[y^k+\frac{\rho }{\beta }{B}^T(A{x}^{k+1}+B{y}^k?c+\frac{1}{\rho }{\lambda }^k)];$
$(c){\lambda }^{k+1}={\lambda }^k+\rho (A{x}^{k+1}+B{y}^{k+1}?c).$