设 $\mathbb{R}^{p}$ 和 $\mathbb{R}^{q}$ 是有限维欧式空间, 并且每个空间上的內积和诱导范数分别表示为 $\langle \cdot,\cdot \rangle$ 和 $\|\cdot\|=\sqrt{\langle \cdot,\cdot \rangle}.$ 假设 $h:\mathbb{R}^{q}\rightarrow \mathbb{R}$ 是凸函数, $f:\mathbb{R}^{p}\rightarrow \mathbb{R}\cup\{+\infty\}$ 和 $g:\mathbb{R}^{q}\rightarrow \mathbb{R}\cup\{+\infty\}$ 是扩展实值下半连续凸函数, $\Phi :\mathbb{R}^{q} \times \mathbb{R}^{p} \rightarrow \mathbb{R}$ 是连续可微函数, $K:\mathbb{R}^{q} \rightarrow \mathbb{R}^{p}$ 是有界线性算子. 函数 $f$ 的共轭函数定义为 $f^*(y)=\sup\limits_{x\in\mathbb{R}^{p}}\{\langle{y,x}\rangle-f(x)\}$.

考虑如下带有双线性耦合项的鞍点问题

问题 (1.1) 在许多领域有着广泛的应用, 比如信号与图像处理、压缩感知、机器学习、博弈论等, 许多学者研究了问题 (1.1), 详情见文献 [1⇓-3]. 求解问题 (1.1) 的相关算法已经有很多, 其中最经典的是 Arrow-Hurwicz 方法^[4], 即原始对偶算法. 从初始点 $(x_{0},y_{0})\in \mathbb{R}^{q}\times \mathbb{R}^{p}$ 开始, 具体迭代为

其中 $\tau>0, \sigma>0$ 是步长参数. 该方法在图像处理中也被称作原始对偶混合梯度算法. 若 $f^{*}$ 的定义域有界且步长很小时, 可基于原始对偶间隙函数得到 $O(\frac{1}{N})$ 的遍历收敛率, 具体的收敛性分析^[2,5]. 但是 Arrow-Hurwicz 方法在一般情况下不收敛^[6]. 为了克服这一缺点, 许多学者提出了不同的改进方法^[7⇓⇓-10].

受文献 [9] 的启发, 周丹青等^[11] 提出了一类黄金比率原始对偶算法求解如下鞍点问题

这里 $h$ 是可微函数. 具体迭代为

其中 $\tau, \sigma>0$. 若 $\tau(\sigma\|K\|^{2}+2L_{h})\leq\psi$, $\psi\in(1,\phi]$ ($\phi$ 是黄金比率), 周丹青等证明了算法 (1.3) 的收敛性以及 $O(\frac{1}{N})$ 遍历收敛率.

注意到, 在问题 (1.1) 和 (1.2) 中涉及到一个双线性函数, 但是在实际应用中许多函数往往不满足双线性性. 因此, 如何研究带非线性二元函数的鞍点问题显得尤为重要. 最近, Zhu 等^[12] 考虑了如下鞍点问题

这里 $h$ 是可微函数. Zhu 等^[12] 提出了如下原始对偶算法

其中 $\rho_{n-1} > 0, \eta_{n-1} = \frac{\rho_{n-1}}{2}$, $L_{n-1} = L_{11} + L_{h} + L_{21}^{2}(2+\rho_{n-1}L_{22})\rho_{n-1}$ ( $L_{11}$、 $L_{21}$ 和 $L_{22}$ 是各个 Lipschitz 常数, 见假设 2.2). 在函数 $\nabla_{x}\Phi(x,y)$ 和 $\nabla_{y}\Phi(x,y)$ 关于 $x$ 和 $y$ 是 Lipschitz 连续的假设下证明了算法 (1.5) 的收敛性以及 $O(\frac{1}{N})$ 遍历收敛率. 值得注意的是, 算法 (1.5) 对于邻近算子参数 $L_{n}$ 的取值范围严重依赖于 Lipschitz 常数, 且单次循环迭代步骤较多, 这将严重影响算法的收敛速度. 此外, 函数 $h$ 可微这一假设比较强. 事实上, 许多函数并不满足可微性. 因此, 如何在不可微情况下提出加速的算法求解问题 (1.4) 是本文讨论的重点.

本文受到文献 [11,12] 的启发, 我们提出了求解问题 (1.4) 的黄金比率原始对偶算法, 证明了由算法产生的序列收敛到问题 (1.4) 的解, 并用数值实验验证了算法的优势. 本文所得的结果改进和推广了文献 [11,12] 中相应结果.

全文用 $\mathbb{N}$ 表示正整数集, 用 $\phi$ 表示黄金比率, 即 $\phi=\frac{1+\sqrt{5}}{2}$. 设 $w:\mathbb{R}^{q}\rightarrow \mathbb{R}\bigcup \{+\infty\}$ 为扩展实值下半连续凸函数, 其有效域记为 dom$(w):=\{x\in \mathbb{R}^{q}:w(x)<+\infty\}$. 设 $x\in \mathbb{R}^{q}$, $w$ 在点 $x$ 的次微分记为 $\partial w(x)$, 即 $\partial w(x):=\{\xi \in \mathbb{R}^{q}:w(y)\geq w(x)+\langle\xi,y-x\rangle, \forall y\in \mathbb{R}^{q}\}$, $w$ 在点 $x$ 的邻近点映射定义为

问题 (1.4) 的原始问题与对偶问题分别为

为了证明本文的主要结果, 我们需要如下假设.

假设 2.1 对于问题 (1.4), 设存在 $(\bar{x},\bar{y})\in ({\rm dom}(h)\cap {\rm dom}(g))\times {\rm dom}(f)$ 使得

并且 $({\rm dom}(h)\cap {\rm dom}(g))\times {\rm dom}(f)\subseteq {\rm dom}(\Phi)$ 以及 $\mathcal{L}(\bar{x},\bar{y})$ 是有界的.

注 2.1 假设 2.1 是凸凹极小极大问题中的标准假设. 它保证了强对偶性 $(P^{*}=D^{*}=\mathcal{L}(\bar{x},\bar{y}))$ 以及问题 $P^{*}$、 $D^{*}$ 解的存在性^[14].

假设 2.2 对任意的 $y\in {\rm dom}(f)$, $x\in {\rm dom}(g)\cap {\rm dom}(h)$, $\Phi(x,y)$ 关于 $x$ 和 $y$ 分别是凸函数和凹函数. 此外, 对任意的 $x_{1}, x_{2}\in {\rm dom}(g)\cap {\rm dom}(h)$ 和 $y_{1}, y_{2}\in {\rm dom}(f)$ 满足

注 2.2 假设 2.2 广泛用于求解凸凹极小极大问题^[12,13], 即要求 $\nabla_{x}\Phi(x,y)$ 和 $\nabla_{y}\Phi(x,y)$ 关于 $x$ 和 $y$ 是 Lipschitz 连续的.

假设 2.3 对任意的 $u_{n}\in \partial h(x_{n})$, $u_{n-1}\in \partial h(x_{n-1})$, 存在 $L_{h}>0$ 满足

注 2.3 若 $h$ 是可微的, 则假设 2.3 退化为文献 [11,12] 中的梯度 Lipschitz 连续性假设.

由假设 2.1 知问题 (1.4) 的鞍点集非空, 并记为

引理 2.1^[1] 设 $w:\mathbb{R}^{q}\rightarrow \mathbb{R}\bigcup \{+\infty\}$ 是扩展实值闭正常凸函数, $\lambda>0$ 以及 $x\in \mathbb{R}^{q}$, 则

引理 2.2^[14] 设 $\{a_{n}\}_{n\in \mathbb{N}}$ 和 $\{b_{n}\}_{n\in \mathbb{N}}$ 是非负实数列. 如果存在 $N>0$ 使得 $a_{n+1}\leq a_{n}-b_{n}$, $\forall n\geq N$, 那么 $\lim\limits_{n\rightarrow\infty}a_{n}$ 存在且 $\lim\limits_{n\rightarrow\infty}b_{n}=0$.

引理 2.3^[14] 对任意 $x,y,z\in \mathbb{R}^{q}$ 和 $\alpha \in \mathbb{R}$ 有

设 $(\bar{x},\bar{y})$ 是问题 (1.4) 的解, 则

取 $\bar{u} \in \partial h(\bar{x})$, 则上式等价于

故问题 (1.4) 的原始对偶间隙函数定义为

显然, $P(x),D(y)$ 和 $G(x,y)$ 都是凸函数且 $G(x,y)\geq0.$ 对任意的 $y\in {\rm dom}(f)$, $x\in {\rm dom}(g)\cap {\rm dom}(h)$, $G(x^{*},y^{*}) = 0$ 当且仅当 $(x^{*},y^{*})$ 是问题 (1.4) 的鞍点.

本文提出如下算法

注 3.1 当 $\Phi(x,y) = \langle Kx,y \rangle$ 且 $h$ 是可微函数时, 算法 1 就退化为文献 [11,算法 1].

注 3.2 算法 1 是完全可分裂的, 即在每次迭代中不依赖于求解任何子问题或线性方程组. 而且算法1 完全不同于文献 [12,算法 1] 的变体 1 (记为 Alg.1(v1)), 本文的算法更加的简洁, 数值效果更好, 见数值实验部分.

为了证明收敛性结果, 我们首先证明如下引理.

引理 3.1 假设 $\{(x_{n},y_{n},z_{n})\}_{n\in \mathbb{N}}$ 是由算法 1 产生的序列, $(\bar{x},\bar{y})\in S$ 以及 $\bar{u} \in \partial h(\bar{x})$, 那么对于任意的 $(x,y) \in \mathbb{R}^{q}\times \mathbb{R}^{p}$, 有

证 由引理 2.1 可得

由 $G(x,y)$ 的定义知

上式结合 (3.2) 式有

又因为 $x_{n}-z_{n}=\psi(x_{n}-z_{n+1})$, 以及函数 $\Phi(\cdot,\cdot)$ 关于第一变元的凸性和关于第二变元的凹性, 有

由于 $h$ 是凸函数, 则次梯度算子是单调的. 故 $\langle u_{n}- \bar{u},x_{n}-\bar{x}\rangle \geq 0$. 因此 (3.1) 式成立. 证毕.

下面给出算法的收敛性证明.

定理 3.1 假设 $\{(x_{n},y_{n},z_{n})\}_{n\in \mathbb{N}}$ 是由算法 1 产生的序列, $(\bar{x},\bar{y})\in S$ 以及 $\bar{u} \in \partial h(\bar{x})$. 则 $\{(x_{n},y_{n})\}_{n\in \mathbb{N}}$ 收敛到问题 (1.4) 的解, 即收敛到 $S$ 中的一个元素.

证 由引理 2.3, 引理 3.1, 假设 2.2 和 Cauchy-Schwarz 不等式得

注意到 $x_{n+1}=\frac{\psi}{\psi-1}z_{n+2}-\frac{1}{\psi-1}z_{n+1}$ 和 $z_{n+2}-z_{n+1}=\frac{\psi-1}{\psi}(x_{n+1}-z_{n+1})$. 由引理 2.3 可得

由于

则由 (3.3) 和 (3.4) 式可得

因为 $\tau(2L_{h}+2L_{11}+L_{12})\leq \psi, \psi \in (1,\phi]$ 且 $L_{12}+2L_{21}\leq \frac{1}{\sigma}$, 则 $\psi-\tau L_{h}-\tau L_{11}-\tau L_{12}\geq\tau L_{h}+\tau L_{11}$ 以及 $\frac{\tau}{\sigma}-\tau L_{12}-2\tau L_{21}\geq0$. 又因为 $\psi\leq\phi$, 故 $\psi-1-\frac{1}{\psi}\leq0$. 因此上式可简化为

令

注意到 $G(x_{n},y_{n})\geq 0$, 则

显然 $a_{n}\geq0$, $b_{n}\geq 0$. 由引理 2.2 知 $\lim\limits_{n\rightarrow\infty}a_{n}$ 存在以及 $\lim\limits_{n\rightarrow\infty}b_{n}=0$. 又由 $x_{n}-z_{n}=\psi(x_{n}-z_{n+1})$ 以及 $b_{n}$ 的定义可知

因为 $\lim\limits_{n\rightarrow\infty}a_{n}$ 存在, 故 $\{z_{n+1}\}_{n\in \mathbb{N}}$ 和 $\{y_{n}\}_{n\in \mathbb{N}}$ 是有界的. 进一步有 $\{(z_{n+1},y_{n})\}_{n\in \mathbb{N}}$ 有界. 又因为 $\lim\limits_{n\rightarrow\infty}\|z_{n}-x_{n}\|=0$, 所以 $\{x_{n}\}_{n\in \mathbb{N}}$ 也有界.

下面证明 $\{(x_{n},y_{n})\}_{n\in \mathbb{N}}$ 收敛到问题 (1.4) 的一个解. 不妨假设 $\{(x_{n+1},y_{n})\}_{n\in \mathbb{N}}$ 的子列 $\{(x_{n_{k}+1},y_{n_{k}})\}_{k\in \mathbb{N}}$ 收敛于 $(x^{*},y^{*})$. 则 $\lim\limits_{k\rightarrow\infty}x_{n_{k}}=\lim\limits_{k\rightarrow\infty}x_{n_{k}+1}=x^{*}, \lim\limits_{k\rightarrow\infty}y_{n_{k}}=\lim\limits_{k\rightarrow\infty}y_{n_{k}-1}=y^{*}$. 对任意的 $(x,y)\in \mathbb{R}^{q}\times \mathbb{R}^{p}$, 选取 $u_{n_{k}} \in \partial h(x_{n_{k}})$, 由引理 2.1 得如下不等式组

由于 $g$, $f^{*}$ 是下半连续的, 则在上式中令 $k\rightarrow \infty$ 且两边同时除以 $\tau(\tau>0)$, 选取 $u^{*} \in \partial h(x^{*})$ 得

因此 $(x^{*},y^{*})\in S$. 同时对任意的 $(\bar{x},\bar{y})\in S$, 以上证明仍然成立. 因此, 在 (3.5) 式中可用 $(x^{*},y^{*})$ 去代替 $(\bar{x},\bar{y})$, 得到

由此可得 $\lim\limits_{k\rightarrow\infty}a_{n_{k}}=0$. 又因为 $\{a_{n}\}_{n\in \mathbb{N}}$ 单调不增, 故 $\lim\limits_{n\rightarrow\infty}a_{n}=0$. 因此 $\lim\limits_{n\rightarrow\infty}x_{n}=\lim\limits_{n\rightarrow\infty}z_{n+1}=x^{*}$ 且 $\lim _{n \rightarrow \infty} y_{n}=y^{*}$. 证毕.

下面给出算法 1 的 $O(\frac{1}{N})$ 遍历收敛速率.

定理 3.2 假设 $\{(x_{n},y_{n},z_{n})\}_{n\in \mathbb{N}}$ 是由算法 1 产生的序列, $(\bar{x},\bar{y})\in S$ 以及 $\bar{u} \in \partial h(\bar{x})$. 设 $N\geq 1$ 是任意正整数, 正整数 $t$ 是满足 $0<t<N$, 并定义

则

证 由 (3.5) 和 (3.6) 式知, 对任意的 $n\geq 1$, 有 $2\tau G(x_{n},y_{n})\leq a_{n}-a_{n+1}$. 从 $n=t,\cdots,N$, 将以上不等式相加, 得 $2\tau \sum\limits_{n=t}^{N}G(x_{n},y_{n})\leq a_{t}-a_{N+1}\leq a_{t}$. 注意到, $G(x,y)=P(x)+D(y)$ 且 $P(x)$ 和 $D(y)$ 是凸函数, 由 Jessen 不等式和 (3.7) 式得

上式联合 $a_{t}=\frac{\psi}{\psi-1}\|z_{t+1}-\bar{x}\|^{2}+\frac{\tau}{\sigma}\|y_{t-1}-\bar{y}\|^{2}+\tau (L_{h}+ L_{11})\|x_{t}-x_{t-1}\|^{2}$ 可得结论. 证毕.

注 3.3 定理 3.1 从以下两个方面改进了文献 [12,定理 2]

(i) 将 $h$ 的可微性弱化到不可微.

(ii) 本文提出的算法完全不同于文献 [12,算法 1] 的变体 1, 在算法的形式上更为精简. 算法 1 采用了黄金比率凸组合技术, 这可以显著的减少算法的迭代次数与运行时间, 见数值实验部分.

注 3.4 当 $\Phi(x,y) = \langle Kx,y \rangle$ 且 $h$ 是可微函数时, 由本文定理 3.1 和 3.2, 我们可以重新获得文献 [11,定理 3.1 和 3.2].

本节给出数值实验, 通过两个例子将本文算法 1 与文献 [12,算法 1] 的变体 1 (记为 Alg.1(v1)) 进行比较. 所有代码均在 MATLAB R2018a 和 Windows10 系统下运行, 计算机基本参数为 Intel(R) Core(TM) i5-8250U CPU@1.60GHz, 其中 “iter” 表示程序迭代次数, “CPU time” 表示程序运行时间, 单位为秒. 算法的终止条件为 $||[x_{n};y_{n}] - [x_{n-1};y_{n-1}]||^{2}\leq err$ (err 为提前设定的误差).

例 4.1^[12] 考虑如下二次规划问题

其中 $A_{i}\in \mathbb{R}^{q\times q}$ 是对称半正定矩阵, $b_{i}\in \mathbb{R}^{q}$, $c_{i}\in \mathbb{R}.$$A_{0}$ 是正定矩阵, $D:=10$. 显然, (4.1) 式可转化为问题 (1.4), 其中 $X:=\{x\in \mathbb{R}^{q}:\|x\| \leq D\}$, $g(x):=\delta_{X}(x)$, $f^{*}(y):=\delta_{\mathbb{R}^{p}_{+}}(y)$, $\Phi(x,y):=\Sigma^{p}_{i=1}y_{i}w_{i}(x)$, $w_{i}(x):=\frac{1}{2}x^{T}A_{i}x+b_{i}^{T}x+c_{i}$. 设初始点 $x_{0}=y_{0}=(0,0,\cdots 0)^{T}$, $A_{0}$, $A_{i}$, $b_{0}$, $b_{i}$, $c_{i}$ 分别是服从正态分布的随机矩阵、随机向量、随机数. 在此情况下, 我们对比了两种算法在不同维数 $p$, $q$ 和不同误差情况下的数值效果. 见表1和表2.

参数选取如下

算法 1 设 $\tau=0.1, \sigma=0.1, \psi=1.6.$

文献 [12,算法 1] 的变体 1: 设 $\rho=0.8, \eta=\frac{\rho}{2}, L_{11}=10, L_{f}=10, L_{21}=20, L_{22}=20$.

例 4.2 考虑下述极大极小博弈问题

其中 $\Delta_{q}:=\{x\in \mathbb{R}^{q}_{+}:\Sigma^{q}_{j=1}x_{j}=1\}$, $\Delta_{p}:=\{y\in \mathbb{R}^{p}_{+}:\Sigma^{p}_{i=1}y_{i}=1\}$. 显然, (4.2) 式可转化为问题 (1.4), $g(x):=\delta_{\Delta_{q}}(x), f^{*}(y):=\delta_{\Delta_{p}}(y)$, $h(x):=\frac{1}{N}\sum\limits^{N}_{j=1}\log(1+\exp(a_{j}^{T}x))$, $\Phi(x,y):=\langle j(x),k(y)\rangle$, $j_{i}(x):=\frac{b_{i}}{1+x_{i}}$, $k_{i}(y):=y_{i}$. 设初始点 $x_{0}=y_{0}=(0,0,\cdots 0)^{T}$, $a_{j}$ 是服从正态分布的随机向量. 在此情况下, 我们对比了两种算法在不同维数 $p$, $q$ 和不同误差情况下的数值效果. 见表3和表4.

参数选取如下

算法 1 设 $\tau$=0.8, $\sigma$=0.8, $\psi$=1.2.

文献 [12,算法 1] 的变体 1 设 $\rho=1.4, \eta=\frac{\rho}{2}, L_{11}=10, L_{f}=10, L_{21}=20, L_{22}=20$.

例 4.3 考虑下述极大极小问题

其中 $\Delta_{q}:=\{x\in \mathbb{R}^{q}_{+}:\Sigma^{q}_{j=1}x_{j}=1\}$, $\Delta_{p}:=\{y\in \mathbb{R}^{p}_{+}:\Sigma^{p}_{i=1}y_{i}=1\}$. 显然, (4.3) 式可转化为问题 (1.4), $g(x):=\delta_{\Delta_{q}}(x), f^{*}(y):=\delta_{\Delta_{p}}(y)$, $h(x):=\|x\|_{1}$, $\Phi(x,y):=\langle j(x),k(y)\rangle$, $j_{i}(x):=\frac{b_{i}}{1+x_{i}}$, $k_{i}(y):=y_{i}$. 设初始点 $x_{0}=y_{0}=(1,1,\cdots 1)^{T}$, $a_{j}$ 是服从正态分布的随机向量. 由于 $h$ 是非光滑函数, 所以文献 [12,算法 1] 的变体 1 以及文献 [11,算法 1] 不能求解本例子. 取 $\psi=1.2$, 在不可微点 $x_{n-1}^{i}=0 (x_{n-1}$ 的第 $i$ 个分量), 取次梯度 $u_{n-1}^{i} = 0 \in \partial h(x_{n-1}^{i})$. 在此情况下, 我们对比了算法 1 在不同维数 $p$, $q$, 不同步长和不同误差情况下的数值效果. 见表5、表6. 更进一步, 我们在 $p=q=150$ 以及 $err=10^{-30}$ 两种情况下分别给出了CPU time关于步长 ($\tau, \sigma$) 的三维曲面图以及剖面图, 见图1、图2、图3、图4.

注 4.1 从数值实验的结果来看, 我们有

(i) 算法 1 与文献 [12,算法 1] 的变体 1 都收敛到问题的解.

(ii) 从 CPU 运行时间来看 (针对例 4.1 与例 4.2), 在适当参数的选取下, 算法 1 优于文献 [12,算法 1], 见表1-4.

(iii) 从迭代次数来看, 在适当参数的选取下, 例 4.2 中算法 1 随着维度和精度的增加仍然表现出很强的稳定性, 较文献 [12,算法 1] 的变体 1 数值效果更佳, 见表3和表4.

(iv) 例 4.3 中, 在 $err=10^{-10}$, $p=q=50$, $p=q=100$, $p=q=150$ 的情况下, 我们选取了多组步长, 得到 $\tau=0.8$, $\sigma=0.7$ 时的数值效果最佳, 见表5及图1, 图2; 以及在 $p=q=100$, $err=10^{-10}$, $err=10^{-20}$, $err=10^{-30}$ 的情况下, 我们选取了多组步长, 同样得到 $\tau=0.8$, $\sigma=0.7$ 时的数值效果最佳, 见表6及图3, 图4.

(v) 算法 1 在 $h$ 光滑与非光滑的条件下同样适用.