求解极大极小问题的共轭梯度法

Conjugate Gradient Method for Solving Minimax Problems

摘要: 本文研究了极大极小问题的求解方法，利用指数罚函数对该问题进行光滑化处理，将其转化成光滑的无约束优化问题，并利用共轭梯度法来求解含有罚参数的无约束优化问题。最后，我们给出了数值算例来验证该算法求解极大极小问题的有效性。

Abstract: This paper studies the method for solving the minimax problem, the exponential penalty function is used for smoothing the problem which can be transformed into a smooth unconstrained optimization problem. We also use the conjugate gradient method to solve the unconstrained optimization with penalty parameters problem. Finally, numerical results are given to illustrate the effectiveness of the algorithm for solving minimax problems.

1. 引言

极大极小问题是一类重要的非光滑优化问题，且在工程设计、经济管理 [1] [2] 等领域有着广泛的应用，同时也与非线性规划问题有着密切的联系。

极大极小问题的一般形式为

$\begin{array}{l}\underset{x\in R^{\text{n}}}{\min }F\left(x\right)\\ F\left(x\right)=\underset{i=1,\cdots ,m}{\max }{f}_i\left(x\right),\end{array}$ (1)

其中， $f_i\left(x\right):R^n\to R$ 是连续可微的函数。

近年来，众多学者对极大极小问题的算法进行了研究。通过构造罚函数，提出一个有效的算法求解极大极小问题，如文献 [3]；通过构造可调节熵函数的区间扩展和一些区域删除测试规则， [4] 提出了一种新的区间算法，该算法可以获得极大极小问题的最优解；文献 [5] 提出了一种截断的集合平滑牛顿法来解决极小极大问题。最近，一种用于求解极大极小问题的平滑FR共轭梯度法由文献 [6] 提出，其实验结果表现良好。

综上文献，我们知道罚函数在极大极小问题的求解过程中起到了重要的作用，该罚函数由 [7] 提出，其形式为

$g\left(x,t\right)=t\ln {\displaystyle \underset{i=1}{\overset{m}{\sum }}\exp }\left(\frac{g_i\left(x\right)}{t}\right),$ (2)

其中，t是罚参数， $g_i\left(x\right)$ 是光滑可微的函数。利用罚函数(2)，极大极小问题(1)可以被转化为一个光滑的无约束优化问题，其形式为

$\min \tilde{F}\left(x,t\right),$ (3)

$\tilde{F}\left(x,t\right)$ 是光滑可微函数，且被定义为

$\tilde{F}\left(x,t\right)=t\ln {\displaystyle \underset{i=1}{\overset{m}{\sum }}\exp }\left(\frac{f_i\left(x\right)}{t}\right),$

其中 $t>0$ 是罚参数。此时，对非光滑的极大极小问题(1)的求解可以等价于对光滑的无约束优化问题(3)的求解。

另外，我们还对带有张量结构的极大极小问题进行研究。一个m阶n维的张量 $\mathcal{A}=\left(a_{i1,i2,\cdots ,im}\right)$，其中 $1\le i1,i2,\cdots ,im\le n$，对一个n维向量x， $\mathcal{A}{x}^{m-1}$ 是一个向量，它的第i的元素是

${\left(\mathcal{A}{x}^{m-1}\right)}_i={\displaystyle \underset{i2,\dots ,im=1}{\overset{n}{\sum }}{a}_{ii2\cdots im}{x}_{i2}\cdots x_{im}},i,j=1,\cdots ,n$

下面我们给出具有张量结构的极大极小问题的形式。首先定义如下函数：

$w^i\left(x\right)={\mathcal{A}}^i{x}^{m-1}-\left|x\right|-b^i,i=1,2,\cdots ,h$ (4)

其中， $\mathcal{A}$ 是一个m阶n维的张量， $b^i$ 是n维向量。对(4)中的绝对值项进行光滑化处理后，有

$w^i\left(x\right)={\mathcal{A}}^i{x}^{m-1}-\sqrt{x^2+t}-b^i,i=1,2,\cdots ,h$

则对于 $\max \left\{w_1^i\left(x,t\right),w_2^i\left(x,t\right),\cdots ,w_m^i\left(x,t\right)\right\}$，由(2)可得出如下函数

${\tilde{w}}^i\left(x,t\right)=t\ln {\displaystyle \underset{j=1}{\overset{n}{\sum }}\exp \left(\frac{{\left({\mathcal{A}}^i{x}^{m-1}\right)}_j-\sqrt{x_j^2+t}-b_j^i}{t}\right)}$

此时，对于下式

$\max \left\{{\tilde{w}}_1^i\left(x,t\right),{\tilde{w}}_2^i\left(x,t\right),\cdots ,{\tilde{w}}_m^i\left(x,t\right)\right\}$

利用指数罚函数(2)，我们可以得到如下光滑的函数

${\tilde{O}}^i\left(x,t\right)=t\ln {\displaystyle \underset{i=1}{\overset{h}{\sum }}\exp \left(\frac{{\tilde{w}}^i\left(x,t\right)}{t}\right)}$ (5)

那么，对于张量结构的极大极小问题就可以转化为对(5)式的求解。

本文的目的是使用共轭梯度法来求解光滑后的极大极小问题，具体安排如下：第2部分，给出求解光滑后的极大极小问题的算法；第3部分给出该算法求解两类极大极小问题的数值实验；第4部分总结。

2. 共轭梯度算法

共轭梯度类算法 [8] [9] [10] 由于其收敛速度快、存储量小以及稳定性高等优点被广泛应用于无约束优化问题的求解中，其最早由Hestenes和Stiefle提出。著名的共轭梯度法有Fletcher-reeves (FR)方法，Hestenes-Stiefel (HS)方法和Dai-Yuan (DY)方法等。本节给出针对光滑后的极大极小问题的共轭梯度法及其算法。

设 $x_k$ 为当前迭代点，对光滑后的极大极小问题(3)，即一个无约束优化问题

$\min \tilde{F}\left(x,t\right),$

记函数值 ${\tilde{F}}_k=\tilde{F}\left(x_k,t_k\right)$，梯度 ${\tilde{g}}_k=\tilde{g}\left(x_k,t_k\right)$，则搜索方向为

${\tilde{d}}_k=\{\begin{array}{ll}-{\tilde{g}}_k,\hfill & \text{if}k=0,\hfill \\ -{\tilde{g}}_k+{\beta }_k{\tilde{d}}_{k-1},\hfill & \text{if}k>0,\hfill \end{array}$

其中， ${\tilde{\beta }}_k$ 为一个参数，常用的 ${\tilde{\beta }}_k$ 有：

$\begin{array}{l}{\tilde{\beta }}_k^{HS}=\frac{{\tilde{g}}_k^{\text{T}}{\tilde{y}}_{k-1}}{{\tilde{d}}_{k-1}^{\text{T}}{\tilde{y}}_{k-1}},{\tilde{\beta }}_k^{DY}=\frac{{\Vert {\tilde{g}}_k\Vert }^2}{{\tilde{d}}_{k-1}^{\text{T}}{\tilde{y}}_{k-1}},{\tilde{\beta }}_k^{LS}=\frac{{\tilde{g}}_k^{\text{T}}{\tilde{y}}_{k-1}}{-{\tilde{g}}_{k-1}^{\text{T}}{\tilde{d}}_{k-1}},\\ {\tilde{\beta }}_k^{FR}=\frac{{\Vert {\tilde{g}}_k\Vert }^2}{{\Vert {\tilde{g}}_{k-1}\Vert }^2},{\tilde{\beta }}_k^{PR}=\frac{{\tilde{g}}_k^{\text{T}}{\tilde{y}}_{k-1}}{{\Vert {\tilde{g}}_{k-1}\Vert }^2},{\tilde{\beta }}_k^{PR+}=\max \left\{\frac{{\tilde{g}}_k^{\text{T}}{\tilde{y}}_{k-1}}{{\Vert {\tilde{g}}_{k-1}\Vert }^2},0\right\}.\end{array}$

其中， ${\tilde{y}}_{k-1}={\tilde{g}}_k-{\tilde{g}}_{k-1}$。此时，共轭梯度法的迭代形式为

$x_{k+1}=x_k+{\alpha }_k{\tilde{d}}_k,$

其中 ${\alpha }_k$ 为线搜索产生的步长。常用的线搜索为Wolfe线搜索：

$\tilde{F}\left(x_k+{\alpha }_k{\tilde{d}}_k,t_k\right)-\tilde{F}\left(x_k,t_k\right)\le \delta {\alpha }_k{\tilde{g}}_k^{\text{T}}{\tilde{d}}_k,$

${\tilde{d}}_k^{\text{T}}\tilde{g}\left(x_k+{\alpha }_k{\tilde{d}}_k,t_k\right)\ge \sigma {\tilde{d}}_k^{\text{T}}{\tilde{g}}_k,$

以及Amijo线搜索

${\alpha }_k=\max \left\{{\rho }^{-j},j=0,1,2,\cdots \right\},$

$\tilde{F}\left(x_k+{\alpha }_k{\tilde{d}}_k,t_k\right)-\tilde{F}\left(x_k,t_k\right)\le \delta {\alpha }_k{\tilde{g}}_k^{\text{T}}{\tilde{d}}_k.$

为解决更复杂的无约束优化问题以及得到更精确的解，谱共轭梯度法 [11] [12] [13]、三项共轭梯度法 [14] [15] [16] 等方法被提出，在解决大规模无约束优化问题、互补问题以及张量等问题都有良好的数值效果。结合文献 [11]，本文给出针对光滑化后的极大极小问题的搜索方向与步长：

${\tilde{d}}_k=\{\begin{array}{ll}-{\tilde{g}}_k,\hfill & \text{if}k=0,\hfill \\ -{\tilde{\theta }}_k{\tilde{g}}_k+{\tilde{\beta }}_k^{FR}{\tilde{d}}_{k-1},\hfill & \text{if}k>0,\hfill \end{array}$ (6)

在(6)中，

${\tilde{\theta }}_k=\frac{{\tilde{d}}_{k-1}^{\text{T}}{\tilde{y}}_{k-1}}{{\Vert {\tilde{g}}_{k-1}\Vert }^2}.$

步长 ${\alpha }_k>0$ 满足

$\tilde{F}\left(x_k+{\alpha }_k{\tilde{d}}_k,t_k\right)-\tilde{F}\left(x_k,t_k\right)\le \rho {\alpha }_k^2{\Vert {\tilde{d}}_k\Vert }^2,$ (7)

${\tilde{d}}_k^{\text{T}}\tilde{g}\left(x_k+{\alpha }_k{\tilde{d}}_k,t_k\right)\ge -2\sigma {\alpha }_k{\Vert {\tilde{d}}_k\Vert }^2,$ (8)

其中， $0<\rho <\sigma <1$。

下面，我们给出求解极大极小问题的光滑化共轭梯度法：

算法2.1

步1：给定常数 $\varsigma \in \left(0,1\right),0<\rho <\sigma <1,\epsilon >0$，初始点 $\left(x_0,t_0\right)\in \left(R^n,R\right)$，令 $k=0$ ；

步2：若 $\Vert {\tilde{g}}_k\Vert \le \epsilon$，则停止计算，否则转步3；

步3：根据(7)、(8)计算步长 ${\alpha }_k$ ；

步4：令 $x_{k+1}=x_k+{\alpha }_k{\tilde{d}}_k$， $t_{k+1}=\varsigma t_k$，由(6)计算搜索方向 ${\tilde{d}}_{k+1}$ ；

步5：计算 ${\tilde{F}}_{k+1}$， ${\tilde{g}}_{k+1}$，令 $k=k+1$，转步2。

为证明算法的收敛性，我们首先给出如下假设：

假设2.1：

(A1) 水平集 $\Omega$ 有界，水平集为 $\Omega =\left\{x\in R^n|\tilde{F}\left(x,t\right)\le \tilde{F}\left(x_0,t_0\right)\right\}$ ；

(A2) 在 $\Omega$ 的一个邻域U中，函数是连续可微且其导数是Lipschitz连续的，即

$\Vert \tilde{g}\left(x,t\right)-\tilde{g}\left(y,t\right)\Vert \le L\Vert x-y\Vert ,\forall x,y\in U,$

其中L是Lipschitz常数。

由假设2.1可得，存在一个常数 $\Gamma >0$，使得

$\Vert \tilde{g}\left(x,t\right)\Vert \le \Gamma ,x\in \Omega .$

引理2.1： ${\tilde{d}}_k$ 由(6)式给出，则

${\tilde{g}}_k^{\text{T}}{d}_k\le -c{\Vert {\tilde{g}}_k\Vert }^2,c>0$ (9)

证 当 $k=0$ 时，(9)式显然成立，假设 $k\ge 1$ 时满足 ${\tilde{g}}_{k-1}^{\text{T}}{d}_{k-1}\le -c{\Vert {\tilde{g}}_{k-1}\Vert }^2$，则

$\begin{array}{c}{\tilde{g}}_k^{\text{T}}{\tilde{d}}_k=-{\tilde{\theta }}_k{\Vert {\tilde{g}}_k\Vert }^2+\frac{{\Vert {\tilde{g}}_k\Vert }^2}{{\Vert {\tilde{g}}_{k-1}\Vert }^2}{\tilde{d}}_{k-1}^{\text{T}}{\tilde{g}}_k=\frac{{\tilde{g}}^2}{{\Vert {\tilde{g}}_{k-1}\Vert }^2}\left(-{\tilde{d}}_{k-1}^{\text{T}}{\tilde{g}}_k+{\tilde{d}}_{k-1}^{\text{T}}{\tilde{g}}_{k-1}+{\tilde{d}}_{k-1}^{\text{T}}{\tilde{g}}_k\right)\\ =\frac{{\Vert {\tilde{g}}_k\Vert }^2}{{\Vert {\tilde{g}}_{k-1}\Vert }^2}{\tilde{d}}_{k-1}^{\text{T}}{\tilde{g}}_{k-1}\le c\frac{{\Vert {\tilde{g}}_k\Vert }^2}{{\Vert {\tilde{g}}_{k-1}\Vert }^2}\left(-{\Vert {\tilde{g}}_{k-1}\Vert }^2\right)=-c{\Vert {\tilde{g}}_k\Vert }^2.\end{array}$

引理2.2：若假设2.1成立，则

${\displaystyle \underset{k\ge 0}{\sum }\frac{{\Vert {\tilde{g}}_k\Vert }^4}{{\Vert {\tilde{d}}_k\Vert }^2}}<+\infty$ (10)

证 由假设A(2)和(8)式，我们有

$\left(2\sigma +L\right){\alpha }_k{\Vert {\tilde{d}}_k\Vert }^2\ge -{\tilde{g}}_k{\tilde{d}}_k,$

移项后两边同时平方可得

${\alpha }_k^2{\Vert {\tilde{d}}_k\Vert }^2\ge {\left(\frac{1}{2\sigma +L}\right)}^2\frac{{\left({\tilde{g}}_k{\tilde{d}}_k\right)}^2}{{\Vert {\tilde{d}}_k\Vert }^2},$

结合(7)式，

${\displaystyle \underset{k\ge 0}{\sum }\frac{{\left({\tilde{g}}_k{\tilde{d}}_k\right)}^2}{{\Vert {\tilde{d}}_k\Vert }^2}\le }{\displaystyle \underset{k\ge 0}{\sum }\left\{\tilde{F}\left(x_k\right)-\tilde{F}\left(x_{k+1}\right)\right\}}<+\infty$

故由引理2.1可得(10)式成立。

由引理2.1和引理2.2，我们可以得出如下的收敛性定理。

定理2.1：若假设2.1成立，则算法2.1满足

$\underset{k\to \infty }{\lim \inf }\Vert {\tilde{g}}_k\Vert =0.$ (11)

证 反证法，假设定理不成立，存在常数 $\epsilon >0$，对任意 $k\ge 0$，有

$\Vert {\tilde{g}}_k\Vert \ge \epsilon ,$

根据(6)式，有

${\tilde{d}}_k\text{=}-{\tilde{\theta }}_k{\tilde{g}}_k+{\tilde{\beta }}_k^{FR}{\tilde{d}}_{k-1},$

两边同时平方后除以 ${\left({\tilde{g}}_k^{\text{T}}{\tilde{d}}_k\right)}^2$，有

$\frac{{\Vert {\tilde{d}}_k\Vert }^2}{{\Vert {\tilde{g}}_k\Vert }^4}=\frac{{\Vert {\tilde{d}}_k\Vert }^2}{{\left({\tilde{g}}_k^{\text{T}}{\tilde{d}}_k\right)}^2}={\left(\frac{{\Vert {\tilde{g}}_k\Vert }^2}{{\Vert {\tilde{g}}_{k-1}\Vert }^2}\right)}^2\frac{{\Vert {\tilde{d}}_{k-1}\Vert }^2}{{\Vert {\tilde{g}}_k\Vert }^4}+\frac{2{\tilde{\theta }}_k}{{\Vert {\tilde{g}}_k\Vert }^2}-\frac{{\tilde{\theta }}_k^2}{{\Vert {\tilde{g}}_k\Vert }^2}\le \frac{{\Vert {\tilde{d}}_{k-1}\Vert }^2}{{\Vert {\tilde{g}}_{k-1}\Vert }^4}+\frac{1}{{\Vert {\tilde{g}}_k\Vert }^2}$

即

$\frac{{\Vert {\tilde{d}}_k\Vert }^2}{{\Vert {\tilde{g}}_k\Vert }^4}\le {\displaystyle \underset{i=0}{\overset{k-1}{\sum }}\frac{1}{{\Vert {\tilde{g}}_i\Vert }^2}\le \frac{k}{{\epsilon }^2}}$

因此，我们有

${\displaystyle \underset{k\ge 0}{\sum }\frac{{\Vert {\tilde{g}}_k\Vert }^4}{{\Vert {\tilde{d}}_k\Vert }^2}\ge {\epsilon }^2}{\displaystyle \underset{k\ge 0}{\sum }\frac{1}{k}}=+\infty$

与假设矛盾，因此(11)式成立。

3. 数值实验

本部分，我们给出用算法2.1求解极大极小问题的数值算例，3.1中计算常规的极大极小问题，算例取自文献 [3]，通过给出算例结果与最优值的误差证明算法的有效性。3.2中给出算法2.1计算带有张量结构的极大极小问题的数值结果，数值结果表明算法2.1在求解带有张量结构的极大极小问题时有良好的数值表现。

3.1. 极大极小问题

本部分给出光滑化算法计算极大极小问题的数值算例，其中的参数设置具体为 $\epsilon =10e-4$， $\rho =0.3$， $\sigma =0.7$， $\varsigma =0.5$， $t_0=2$。表1给出实验结果，其中n，m分别为变量、函数的数目，图1~3为算法2.1在求解算例时，函数值随着迭代步数的数值表现。由表1和图1~3我们可以观察到算法2.1在求解极大极小问题时具有良好的数值表现。

例1 Cresent [3]

$h\left(x\right)=\max \left\{x_1^2+{\left(x_2-1\right)}^2+x_2-1,-x_1^2-{\left(x_2-1\right)}^2+x_2+1\right\},$

$n=2,h\left(x^{*}\right)=0,x_0={\left(0,0\right)}^{\text{T}}.$

例2 Mifflin 1 [3]

$h\left(x\right)=-x_1+\max \left\{x_1^2+x_2^2-1,0\right\},$

$n=2,h\left(x^{*}\right)=-1,x_0={\left(2,2\right)}^{\text{T}}.$

例3 Mifflin 2 [3]

$h\left(x\right)=-x_1+2\left(x_1^2+x_2^2-1\right)+1.75\max \left\{\pm \left(x_1^2+x_2^2-1\right)\right\},$

$n=2,h\left(x^{*}\right)=-1,x_0={\left(0,0\right)}^{\text{T}}.$

Table 1. Numerical results for example 1 - 3

表1. 例1~例3的实验结果

Figure 1. The numerical results of Cresent

图1. Cresent的实验结果

Figure 2. The numerical results of Mifflin 1

图2. Mifflin 1的实验结果

Figure 3. The numerical results of Mifflin 2

图3. Mifflin 2的实验结果

3.2. 带张量结构的极大极小问题

本部分给出算法2.1求解带有张量结构的极大极小问题的数值算例，为了便于计算，数值算例中的张量使用的是对称张量，其中的参数设置为 $\epsilon =10e-2$， $\sigma =0.7$， $\rho =0.3$， $\varsigma =0.5$， $t_0=2$，且选取 $\Vert x_{k+1}-x_k\Vert \le \epsilon$ 作为算法的终止条件。表2给出实验结果，其中n，m分别是张量的阶数和维数，图4~5为算法2.1在求解算例时，函数值随着迭代步数的数值表现。由表2和图4~5我们可以观察到算法2.1可以有效求解带有张量结构的极大极小问题。

考虑两个3阶2维的张量 ${\mathcal{A}}^1=\left(a_{i1i2i3}^1\right)$ 和 ${\mathcal{A}}^2=\left(a_{i1i2i3}^2\right)$，以及两个向量为 $b^1={\left(6,2\right)}^{\text{T}}$ 和 $b^2={\left(2,8\right)}^{\text{T}}$，给出如下两个算例：

例4： ${\mathcal{A}}^1$ 为 $a_{111}^1=a_{222}^1=10$，其余元素为3， ${\mathcal{A}}^2$ 为 $a_{111}^2=a_{222}^2=6$，其余元素为3。初始向量为 $x_0={\left(2,6\right)}^{\text{T}}$。

例5： ${\mathcal{A}}^1$ 为 $a_{111}^1=a_{222}^1=1$，其余元素为3， ${\mathcal{A}}^2$ 为 $a_{111}^1=a_{222}^1=10$，其余元素为6。初始向量为 $x_0={\left(5,2\right)}^{\text{T}}$。

Table 2. Numerical results for example 4 - 5

表2. 例4~例5的实验结果

Figure 4. The numerical results of example 4

图4. 例4的实验结果

Figure 5. The numerical results of example 5

图5. 例5的实验结果

4. 结论

本文通过指数罚函数，对极大极小问题进行光滑化处理，将非光滑的极大极小问题转化为光滑的无约束优化问题，并给出针对带有罚参数的无约束优化问题的共轭梯度算法。为验证算法的有效性，我们同时给出了该算法求解常规的极大极小问题和带有张量结构的极大极小问题的数值实验，根据数值实验的结果，该算法在迭代次数、下降速度、误差等方面都具有良好的表现。在以后的研究中，对于更复杂的大规模的极大极小问题，可以运用不同的线搜索或不同的步长进行优化，以得到更快的下降速度和更良好的数值表现。