数学物理学报, 2020, 40(3): 641-649 doi:

论文

一般约束极大极小优化问题一个强收敛的广义梯度投影算法

马国栋,

A Strongly Convergent Generalized Gradient Projection Method for Minimax Optimization with General Constraints

Ma Guodong,

收稿日期: 2019-03-22  

基金资助: 广西自然科学基金.  2018GXNSFAA281099
国家自然科学基金.  11771383
玉林师范学院科研项目.  2019YJKY16
玉林师范学院科研项目.  G20150010

Received: 2019-03-22  

Fund supported: the NSF of Guangxi Province.  2018GXNSFAA281099
the NSFC.  11771383
the Research Projects of Yulin Normal University.  2019YJKY16
the Research Projects of Yulin Normal University.  G20150010

作者简介 About authors

马国栋,E-mail:mgd2006@163.com , E-mail:mgd2006@163.com

摘要

该文考虑求解带非线性不等式和等式约束的极大极小优化问题,借助半罚函数思想,提出了一个新的广义投影算法.该算法具有以下特点:由一个广义梯度投影显式公式产生的搜索方向是可行下降的;构造了一个新型的最优识别控制函数;在适当的假设条件下具有全局收敛性和强收敛性.最后,通过初步的数值试验验证了算法的有效性.

关键词: 非线性一般约束 ; 极大极小问题 ; 广义梯度投影算法 ; 全局收敛性 ; 强收敛性

Abstract

In this paper, minimax optimization problems with inequality and equality constraints is discussed. The original problem is transformed into an associated simple problem with a penalty term and only inequality constraints, then a new generalized gradient projection algorithm is presented. The main characters of the proposed algorithm are as follows:the improved search direction is generated by only one generalized gradient projection explicit formula; the new optimal identification function is introduced; the algorithm is globally and strongly convergent under some mild assumptions. Finally, the numerical results show that the proposed algorithm is promising.

Keywords: Nonlinear general constraints ; Minimax optimization problems ; Generalized gradient projection method ; Global convergence ; Strong convergence

PDF (385KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

马国栋. 一般约束极大极小优化问题一个强收敛的广义梯度投影算法. 数学物理学报[J], 2020, 40(3): 641-649 doi:

Ma Guodong. A Strongly Convergent Generalized Gradient Projection Method for Minimax Optimization with General Constraints. Acta Mathematica Scientia[J], 2020, 40(3): 641-649 doi:

1 引言

该文考虑求解如下非线性一般约束极大极小优化问题

$ \begin{equation} \min \{F(x)|\ f_j(x)\leq 0, \; j\in J_1;\ f_j(x) = 0, \; j\in J_2\}, \end{equation} $

其中$ F(x) = \max\{f_j(x), \; j\in I\} $, $ I = \{1, 2, \cdots, l\} $, $ J_1 = \{1, 2, \cdots, m'\}, $$ J_2 = \{m'+1, m'+2, $$ \cdots, m'+m\}, $函数$ f_j(x)(j\in I\cup J_1\cup J_2):\mathbb{R}^n\rightarrow \mathbb{R} $均为光滑实值函数.许多决策、金融、工程管理、经济问题都可描述为极大极小问题.然而,其目标函数的非光滑性使之不能利用光滑优化的算法直接求解,故其理论与数值方法的研究较光滑优化困难.但是,通过引入人工变量将原问题等价转化为带有不等式约束光滑优化问题,从而可以用许多经典的光滑优化方法如序列二次规划法[1-3]、信赖域法[4-5]、牛顿法[6]和内点法[7]等方法来求解.

另一方面,半罚函数方法是将带有等式约束优化问题等价地转化为只带有不等式约束问题进行求解,且此方法具有许多好的性质和应用[8-10].因此,将问题(1.1)等价地转化为如下半罚问题

$ \begin{equation} \min \bigg\{F(x;c)\triangleq F(x)-c\sum\limits_{j\in J_2}f_j(x)|\ f_j(x)\leq 0, \; j\in J_1;\ f_j(x)\leq0, \; j\in J_2 \bigg\}, \end{equation} $

其中半罚参数$ c $充分大,用于强迫不等式约束优化问题(1.2)的解落入原问题(1.1)的可行域,从而通过研究问题(1.2)获得问题(1.1)的解,在一定约束规格下,且当$ c $足够大,问题(1.2)和问题(1.1)的稳定点是等价的.

以Rosen梯度投影法[11-12]为基础的(广义)梯度投影型算法是一类典型的方法.该类算法具有良好的收敛性,且对中小型问题数值表现良好,引起了诸多的关注[10, 13-16].文献[14]对不等式约束问题的广义梯度投影算法进行了较为详尽的研究.文献[15]和[16]分别提出了求解无约束和不等式约束极大极小问题的广义梯度投影算法,且论证了算法的收敛性质.

该文借鉴半罚函数思想,提出了一个求解带有不等式和等式约束极大极小优化问题的广义梯度投影算法.算法构造了一个新型的最优识别控制函数,在每一次迭代中,搜索方向由一个广义梯度投影显示公式产生.在适当的假设条件下,算法具有全局收敛性和强收敛性.最后,初步数值试验验证了算法的有效性.

2 算法构造

为便于讨论,记问题(1.1)和(1.2)的可行集分别为$ X $$ \tilde{X} $,并引入如下记号:

类似于其他投影型算法,如文献[10, 13-16],本文亦需线性无关假设.

假设A1  函数$ f_j(x)(j \in {I\cup J}) $均一阶连续可微,且对于任意$ x\in \tilde{X } $,存在$ j_x \in I(x) $使得向量组$ \{\nabla f_j(x)-\nabla f_{j_x}(x), \ j\in I(x)\backslash\{j_x\}; \; \nabla f_j(x), j\in J(x)\} $线性无关.

假设A1等价于下面条件:

假设A1-1  任意$ t\in I(x), $向量组$ \{\nabla f_j(x)-\nabla f_t(x), \; j\in I(x)\backslash\{t\}; \; \nabla f_j(x), j\in J(x)\} $线性无关.

为叙述方便,对于给定的迭代点$ x^k\in \tilde{X} $及适当的常数$ \varepsilon, \; \delta > 0 $,本文使用以下记号:

$ \begin{equation} I_k: = I(x^k, \varepsilon) = \{j\in I: -\varepsilon\leq f_j^k-F^k\leq 0\}, \ J_k: = J(x^k, \delta) = \{j\in J_1: -\delta\leq f_j^k\leq 0\}, \end{equation} $

$ \begin{equation} F^k: = F(x^k), \; f_j^k: = f_j(x^k), \; g_j^k: = \nabla f_j(x^k), \; j \in I\cup J, l_k\in I(x^k), \; I_k^0: = I_k\backslash\{l_k\}, \end{equation} $

其中$ l_k \in I(x^k) $理论上可以任取,但为便于计算,可取$ l_k: = l_{x^k} = \min\{j: j\in I(x^k)\}. $

对于问题(1.1),其稳定点最优性条件为

$ \begin{equation} \left\{\begin{array} {l} \sum\limits_{j\in I_k}\lambda_j^k g_j^k+\sum\limits_{j\in J_k\cup{J_2}}\lambda_j^k g_j^k = 0;\; \sum\limits_{j\in I_k}\lambda_j^k = 1, \lambda_j^k\geq0, \; \lambda_j^k(f_j^k-F^k) = 0, \ j \in I_k;\\ \lambda_j^k\geq0, \; \lambda_j^kf_j^k = 0, \ f_j^k\leq0, \ j \in J_k;\ f_j^k = 0, \ j\in J_2, \end{array}\right. \end{equation} $

$ j\in (I\backslash{I_k})\cup(J\backslash{J_k}) $时, $ \lambda_j^k = 0 $.由(2.3)式易得

$ \begin{equation} \left\{ \begin{array} {ll} \sum\limits_{j\in I_k^0}\lambda_j^k(g_j^k-g_{l_k}^k)+\sum\limits_{j\in J_k}\lambda_j^kg_j^k+\sum\limits_{j\in J_2} (\lambda_j^k+c_k)g_j^k = -(g_{l_k}^k-c_k\sum\limits_{j\in J_2} g_j^k);\\ \lambda_{l_k}^k = 1-\sum\limits_{j\in I_k^0}\lambda_j^k\geq 0;\\ \lambda_j^k\geq0, \; \lambda_j^k(f_j^k-F^k) = 0, \ \; j \in I_k^0;\\ \lambda_j^k\geq0, \; \lambda_j^kf_j^k = 0, \ f_j^k\leq0, \ j \in J_k;\ (\lambda_j^k+c_k)f_j^k = 0, \ f_j^k = 0, \ j\in J_2. \end{array}\right. \end{equation} $

为检验当前迭代点$ x^k $是否满足最优性条件(2.3),定义广义梯度投影矩阵

$ \begin{eqnarray} P_k: = E_n-N_k Q_k, \end{eqnarray} $

其中$ E_n $$ n $阶单位阵,对于$ p > 0 $,矩阵

$ \begin{equation} N_k: = (g_j^k-g_{l_k}^k, \; j \in I_k^0;\; g_{j}^k, \; j \in J_k\cup J_2), \; Q_k: = (N_k^T N_k+D_k)^{-1}N_k^T, \end{equation} $

$ \begin{equation} L_k: = I_k^0\cup{J_k}\cup{J_2}, \ D_k: = {\rm diag}(D_{j}^{k}, \; j\in {L_k}), \; D_j^k: = \left\{\begin{array}{ll}(F^k-f_j^k)^p, & j\in I_k^0;\\ (-f_j^k)^p, & j\in J_k;\\ 0, &j\in J_2. \end{array}\right. \end{equation} $

$ (x^k, \; \lambda_{L_k}^k) $为问题(1.1)的稳定点对时,由(2.4)易得如下关系式:

进一步可得

$ \begin{equation} \left\{\begin{array}{ll} (N_k^T N_k+D_k)\lambda_{L_k}^k = -N_k^T(g_{l_k}^k-c_k\sum\limits_{j\in J_2} g_j^k), \\ \lambda^k_{L_k} = -Q_k(g_{l_k}^k-c_k\sum\limits_{j\in J_2} g_j^k), \ \tilde{\lambda}^k_{L_k} = -Q_kg_{l_k}^k.\end{array}\right. \end{equation} $

由(2.4)和(2.8)式,易知

$ \begin{equation} \lambda^k_{j} = \tilde{\lambda}^k_{j}, \ j\in I_k^0\cup J_k;\ \lambda^k_{j} = \tilde{\lambda}^k_{j}+c_k, \ j\in J_2. \end{equation} $

基于以上分析,引入如下最优识别控制函数:

$ \begin{equation} \rho_k: = \frac{\|P_kg_{l_k}^k\|^2+\omega_{k}+\bar\omega_k^2}{1+\|\mu^k_{L_k}\|_1}, \end{equation} $

其中

$ \begin{equation} \mu^k_{L_k}: = -Q_k(g_{l_k}^k-c_k\sum\limits_{j\in J_2} g_j^k), \ \tilde{\mu}^{k}_{L_k}: = -Q_{k}g_{l_k}^k, \ \ \mu_{l_k}^k: = 1-\sum\limits_{j\in I_k^0}\tilde{\mu}_j^k, \end{equation} $

$ \begin{equation} \omega_{k}: = \sum\limits_{j \in I_k^0\cup J_k}\max\{-\tilde{\mu}_{j}^{k}, \tilde{\mu}_{j}^{k}D_{j}^{k}\}+\sum\limits_{j \in J_2}{\mu}_{j}^{k}(-f_{j}^{k})^p, \ \ \; \bar\omega_k: = \max\{-\mu_{l_k}^k, 0\}. \end{equation} $

为说明以上各量的适定性及性质,给出以下引理.

引理2.1  设假设A1成立,有

(ⅰ)矩阵$ (N_k^T N_k+D_k) $正定;若$ x^k\rightarrow x^\ast, \; N_k\rightarrow N_\ast, \; D_k\rightarrow D_\ast, $则其极限矩阵$ (N_\ast^T N_\ast+D_\ast) $也正定;

(ⅱ) $ N_k^T P_k = D_kQ_k, \ \ N_k^T Q_k^T = E_{|L_k|}-D_k(N_k^T N_k+D_k)^{-1}; $

(ⅲ) $ (g_{l_k}^k)^{T}P_{k}g_{l_k}^k = \|P_{k}g_{l_k}^k\|^2+\sum\limits_{j\in L_k}(\tilde{\mu}_j^k)^{2}D_j^k; $

(ⅳ)如$ c_k > |\tilde{\mu}_j^k|, \ j\in J_2 $,则$ x^k $是问题$ (1.2) $稳定点$ \Longleftrightarrow $$ x^k $是问题$ (1.1) $的稳定点$ \Longleftrightarrow \rho_k = 0 $.

引理2.1(ⅰ)–(ⅲ)的证明可参照文献[14]中的引理1.1.9和文献[16]中的引理1,引理2.1(ⅳ)的证明可参照文献[9]中的引理2.2.

由以上引理知,若当前迭代点$ x^k $不是问题(1.1)的稳定点,有$ \rho_k > 0 $.进而,构造如下搜索方向

$ \begin{equation} d^k = \rho_k^\xi\{-P_kg_{l_k}^k+Q_k^T v^k_{L_k}\}, \end{equation} $

其中参数$ \xi\geq0 $,向量$ v^k_{L_k} = (v_j^k-\rho_k, \ j\in L_k), v_j^k $构造如下:

$ \begin{equation} v_{j}^{k} = \left\{\begin{array}{ll}-1+\bar\omega_k, & \; \tilde{\mu}_{j}^{k}<0, \; j \in I_k^0;\\ D_{j}^{k}+\bar\omega_k, & \; \tilde{\mu}_{j}^{k}\geq 0, \; j \in I_k^0, \end{array}\right. v_{j}^{k} = \left\{\begin{array}{ll}-1, & \; \tilde{\mu}_{j}^{k}<0, \; j \in J_k;\\ D_{j}^{k}, & \; \tilde{\mu}_{j}^{k}\geq 0, \; j \in J_k, \end{array}\right. v_{j}^{k} = (-f_j^k)^p, \ j\in J_2. \end{equation} $

基于引理2.1,接下来分析搜索方向$ d^k $的可行下降性.

引理2.2  设假设A1成立,方向$ d^k $满足

(ⅰ) $ {(g_{l_k}^k-c_k\sum\limits_{j\in J_2} g_j^k)}^{T}d^k\leq-\rho_k^{\xi}\bar{\omega}_k-\rho_k^{1+\xi} $;

(ⅱ) $ (g_{j}^k-c_k\sum\limits_{j\in J_2} g_j^k)^{T}d^k\leq-\rho_k^{1+\xi}, \; \forall\; j\in I(x^k)\backslash\{l_k\} $;

(ⅲ) $ (g_{j}^k)^{T}d^k\leq-\rho_k^{1+\xi}, \; \forall\; j\in {J(x^k)} $.

   (ⅰ)首先,由(2.11)–(2.14)式, (2.9)式及引理2.1(ⅲ),有

另外,由$ \mu_{l_k}^{k} $的定义可得$ \bar\omega_k\sum\limits_{j\in I_k^0}\tilde{\mu}_j^k = \bar\omega_k+\bar\omega_k(-\mu_{l_k}^{k}). $$ \mu_{l_k}^k\geq0 $,则$ \bar\omega_k = 0 $, $ \bar\omega_k(-\mu_{l_k}^{k}) = 0 = \bar\omega_k^2 $;若$ \mu_{l_k}^k < 0 $,则$ \bar\omega_k = -\mu_{l_k}^{k} $, $ \bar\omega_k(-\mu_{l_k}^{k}) = \bar\omega_k^2 $.因此, $ \bar\omega_k\sum\limits_{j\in I_k^0}\tilde{\mu}_j^k = \bar\omega_k+\bar\omega_k^2 $恒成立,于是,结合(2.10)式,有

$ \begin{eqnarray} {(g_{l_k}^k-c_k\sum\limits_{j\in J_2} g_j^k)}^{T}d^k &\leq&\rho_k^\xi\{-\|P_{k}g_{l_k}^k\|^2-\omega_k-\bar{\omega}_k-\bar{\omega}_k^2+\rho_k\|\mu_{L_k}^k\|_1\} \\ & = &-\rho_k^{\xi}\bar{\omega}_k-\rho_k^{1+\xi}. \end{eqnarray} $

(ⅱ)由(2.13)式及引理2.1(ⅱ)有

$ \begin{eqnarray} N_k^Td^k& = &\rho_k^\xi \{-N_k^TP_kg_{l_k}^k+N_k^TQ_k^Tv_{L_k}^k\} \\ & = &\rho_k^\xi\{-D_k Q_kg_{l_k}^k+v_{L_k}^k-D_k(N_k^TN_k+D_k)^{-1}v_{L_k}^k\}. \end{eqnarray} $

$ j\in(I(x^k)\backslash\{l_k\})\subseteq I_k^0 $时,有$ D_j^k = 0. $由(2.16)式有$ (g_j^k-g_{l_k}^k)^Td^k = \rho_k^\xi v_j^k -\rho_k^{1+\xi}. $再结合(2.14)式及结论(ⅰ),可得

(ⅲ)当$ j\in J(x^k)\subseteq J_k\cup J_2 $时,有$ D_j^k = 0. $由(2.16)和(2.14)式有$ (g_{j}^k)^Td^k = \rho_k^\xi v_j^k - \rho_k^{1+\xi}\leq-\rho_k^{1+\xi}. $

基于以上分析,下面给出算法的具体步骤.

算法A

步骤0 (初始化)  选初始点$ x^0\in \tilde{X} $,参数:$ \alpha, \beta\in (0, 1), \; \varepsilon, \delta, p, c_0, \gamma, \gamma_0 > 0, \; \xi\geq0 $.$ k: = 0 $.

步骤1 (修正罚参数$ c_k $)

$ \begin{equation} c_{k} = \left\{\begin{array}{ll}\max\{s_k, \ c_{k-1}+\gamma\}, & \hbox{如}\ s_k>c_{k-1};\\ c_{k-1}, & \hbox{如}\ s_k\leq c_{k-1}, \end{array}\right.\; s_k = \max\{|\tilde{\mu}_j^k|, \ j\in J_2\}+\gamma_0. \end{equation} $

步骤2 (最优识别)  对于迭代点$ x^k $,计算投影矩阵$ P_k $和识别函数$ \rho_k $,若$ \rho_k = 0 $,则$ x^k $为问题(1.1)的稳定点,停止;否则,按(2.13)–(2.14)式计算搜索方向$ d^k $,并转入步骤3.

步骤3 (线搜索)  计算$ \{1, \beta, \beta^2, \cdots\} $中满足以下不等式(2.18)和(2.19)的最大值$ t_k $.

$ \begin{equation} F(x^k+td^k;c_k)\leq F(x^k;c_k)-\alpha t \rho_k^{1+\xi}, \end{equation} $

$ \begin{equation} f_j(x^k+td^k)\leq0, \; \forall\; {j\in J}. \end{equation} $

步骤4 (更新)  令$ x^{k+1} = x^k+t_kd^k $,置$ k: = k+1 $,返回步骤1.

注2.1  由引理2.2知,易证(2.18)–(2.19)式对于充分小的正数$ t $恒成立,从而步骤3的线搜索是可以执行的,故上述算法A是适定的.

3 收敛性分析

本节分析算法A的全局收敛性和强收敛性.下面假设算法A产生无穷点列$ \{x^k\} $,往证其任一聚点$ x^\ast $都是问题(1.1)的稳定点,注意到指标集$ I_k, \; J_k $$ l_k $的有限选取性,不妨假设存在无穷子列$ {\cal K} $(必要时再取$ {\cal K} $的一个子列),使得

$ \begin{equation} x^k\stackrel{{\cal K}}{\rightarrow} x^\ast, \ I_k\equiv I_\ast, \; J_k\equiv J_\ast, \; l_k\equiv l_\ast, \; I_k^0\equiv I_{\ast}^0: = \{I_\ast\}\backslash{l_\ast}, \; L_k\equiv L_\ast: = {I_\ast^0\cup{J_\ast}\cup{J_2}}, \; \forall\ k\in {\cal K}. \end{equation} $

假设A2  算法A产生的点列$ \{x^k\} $有界.

引理3.1  设假设A1和A2成立,则存在正整数$ k_0 $,使得对于任意的$ k\geq k_0 $,有$ c_k \equiv \bar c $成立.

证明可参考文献[9]中的引理3.1.根据引理3.1,下文假设$ c_k = \bar c $恒成立,定义

$ \begin{equation} D_j^{\ast } = \left\{\begin{array}{lll}(F(x^\ast)-f_j(x^\ast))^p, &\;\mbox{ $j\in I_\ast^0$};\\ (-f_j(x^\ast))^p , &\;\mbox{ $ j\in J_\ast$}; \\0 , &\;\mbox{ $ j\in J_2$}, \end{array} \right.~~ D_\ast = {\rm diag}(D_{j}^{\ast}, \; j\in L_\ast), \end{equation} $

$ \begin{equation} N_\ast = (\nabla f_j(x^\ast)-\nabla f_{l_\ast}(x^\ast), \ j\in I_{\ast}^0;\; \nabla f_j(x^\ast), \ j\in J_\ast\cup J_2), \ Q_\ast = (N_\ast^T N_\ast+D_\ast)^{-1}N_\ast^T, \end{equation} $

$ \begin{equation} P_\ast = E_{n}-N_\ast Q_\ast, \ \tilde{\mu}_{L_\ast}^\ast = (\tilde{\mu}_j^\ast, \; j\in L_\ast) = -Q_\ast \nabla {f_{l_\ast}(x^\ast)}, \ \mu_{l_\ast}^\ast = 1-\sum\limits_{j\in I^0_\ast}\tilde{\mu}_j^\ast, \end{equation} $

$ \begin{equation} \bar{\omega}_\ast = \max\{-\mu_{l_\ast}^\ast, \; 0\}, \ \mu^*_{L_*} = -Q_*(\nabla f_{l_\ast}(x^\ast)-\bar{c}\sum\limits_{j\in J_2} \nabla f_j(x^\ast)), \end{equation} $

$ \begin{equation} \omega_\ast = \sum\limits_{j\in I_\ast^0\cup J_*}\max\{-\tilde{\mu}_j^\ast, \; \tilde{\mu}_j^\ast D_j^{\ast}\}+\sum\limits_{j\in J_2} \mu_j^*(-f_j(x^\ast))^p, \ \ \rho_{\ast} = \frac{\|P_{\ast}\nabla f_{l_\ast}(x^\ast)\|^2+\omega_\ast+\bar{\omega}_\ast^2}{1+\|\mu^*_{L_*}\|_1}. \end{equation} $

于是, $ (F(x^k; c_k), \; D_k, \; \rho_k)\rightarrow(F(x^\ast; \bar{c}), \; D_\ast, \; \rho_\ast) $.另外,由引理2.1可知,矩阵$ (N_\ast^T N_\ast+D_\ast) $正定,故序列$ \{v^k\}_{{\cal K}} $$ \{d^k\}_{{\cal K}} $有界.

引理3.2  设假设A1和A2成立,如果$ x^\ast $不是问题$ (1.1) $的稳定点,则$ \rho_\ast > 0 $,进而当$ k\in {\cal K} $充分大时, $ \rho_k\geq0.5\rho_\ast $,且$ \bar{t} = \mathrm{inf}\{t_k, \ k\in {\cal K}\} > 0. $

  首先,当$ x^\ast $不是问题(1.1)的稳定点时,类似于引理2.1 (iv)的分析,易证$ \rho_\ast > 0 $,因$ \bar c > |\tilde{\mu}_j^*|, \ \forall\ j\in J_2 $.进而$ \rho_k\geq0.5\rho_\ast $.为证$ \bar{t} > 0 $,只需证明对于$ {\cal K} $中充分大的$ k $以及充分小的正数$ t $($ k $无关),不等式(2.18)和(2.19)成立.

A1.分析不等式(2.18),由$ f_j(x) $的可微性及$ \{{d^k}\}_{{\cal K}} $的有界性,利用Taylor展开式有,记

为便于分析,进而记

对于$ j\in I $,此时分$ j\notin I(x^*) $$ j\in I(x^\ast) $两种情况讨论.

A11.当$ j\notin I(x^\ast) $,即$ f_j(x^\ast) < F(x^\ast) $时,有

A12.当$ j\in I(x^\ast) $,即$ f_j(x^\ast) = F(x^\ast) $时.由(2.1)式易知, $ k\in {\cal K} $充分大时,恒有$ I(x^\ast)\subseteq I_k, $$ j\in I_k. $$ j = l_\ast $,由引理2.2 (ⅰ)有

$ \begin{equation} (g_{l_\ast}^k-{\bar c}\sum\limits_{j\in J_2} g_j^k)^{T}d^k\leq-\rho_k^{\xi}\bar{\omega}_k-\rho_k^{1+\xi}\leq-\rho_k^{1+\xi}. \end{equation} $

$ j\neq l_\ast $, $ D_j^k = (F^k-f_j^k)^p\stackrel{{\cal K}}{\rightarrow}(F(x^\ast)-f_j(x^\ast))^p = 0 $,由引理2.1 (i)知$ (N_k^T N_k+D_k)^{-1}\rightarrow(N_\ast^T N_\ast+D_\ast)^{-1} $,进而由(2.16)式有$ (g_j^k-g_{l_k}^k)^Td^k = \rho_k^\xi v_j^k-\rho_k^{1+\xi}+O(D_j^k). $又由(2.14)式的第一个式子,有$ v_j^k\leq\bar{\omega}_k+O(D_j^k) $,结合(2.15)式,有

$ \begin{eqnarray} (g_j^k-{\bar c}\sum\limits_{j\in J_2}g_j^k)^Td^k&\leq& \rho_k^\xi \bar{\omega}_k+(g_{l_k}^k-{\bar c}\sum\limits_{j\in J_2}g_j^k)^Td^k-\rho_k^{1+\xi}+O(D_j^k) \\ &\leq& -2\rho_k^{1+\xi}+O(D_j^k)\leq-\rho_k^{1+\xi}+O(D_j^k). \end{eqnarray} $

因此,对于$ j\in I(x^\ast), $由Taylor展式及(3.7)和(3.8)式有

$ \begin{eqnarray} b_{j}^k(t)& = & f_j^k-F^k+t(g_j^k-{\bar c}\sum\limits_{j\in J_2}g_j^k)^Td^k+o(t)+\alpha t \rho_k^{1+\xi} \\ &\leq &-(1-\alpha)t\rho_k^{1+\xi}+o(t) \\ &\leq&-0.5t (1-\alpha)\rho_\ast^{1+\xi}+o(t)\leq 0. \end{eqnarray} $

由A11及A12的分析可知,对于$ {\cal K} $中充分大的$ k $及充分小的正数$ t $ (与$ k $无关),有$ F^k(t)\leq0 $,即不等式(2.18)恒成立.

A2.对于$ j\in J $,类似分$ j\notin J(x^*) $$ j\in J(x^*) $两种情况讨论.

A21.当$ j\notin J(x^\ast) $,即$ f_j(x^*) < 0 $时,由$ \{{d^k}\}_{{\cal K}} $的有界性及Taylor展式,有

$ \begin{equation} f_j(x^k+td^k) = f_j^k+O(t)\leq0.5f_j(x^*)+O(t)\leq0. \end{equation} $

A22.当$ {j\in J(x^\ast)} $,即$ f_j(x^*) = 0 $时,由(2.1)式易知, $ k\in {\cal K} $充分大时,恒有$ J(x^\ast)\subseteq J_k\cup J_2, $$ j\in J_k\cup J_2 $,进而$ D_j^k = (-f_j^k)^p\stackrel{{\cal K}}{\rightarrow}0 $.因此,由(2.16)式有$ (g_j^k)^Td^k = \rho_k^\xi v_j^k-\rho_k^{1+\xi}+O(D_j^k) $.进而,结合Taylor展式和(2.14)式,可得

因此,对于$ {\cal K} $中充分大的$ k $及充分小的正数$ t $ (与$ k $无关),不等式(2.19)恒成立.

综上所述,当$ k\in {\cal K} $充分大时, $ \bar{t} = \mathrm{inf}\{t_k, \ k\in {\cal K}\} > 0 $恒成立.

引理3.3  设假设A1和A2成立,算法A或有限步终止于问题$ (1.1) $的稳定点,或产生无穷点列$ \{x^k\} $,使得$ \{x^k\} $的任一聚点$ x^\ast $都是问题$ (1.1) $的稳定点,即算法A是全局收敛的.

  因$ c_k\geq s_k > |\tilde{\mu}_j^k| $, $ \forall\ j\in J_2 $,若算法A有限步迭代终止,由算法A步骤2及引理2.1 (ⅳ)知$ x^k $是问题(1.1)的稳定点.下面不妨设算法A产生无穷点列$ \{x^k\} $, $ x^\ast $为其任意一给定的聚点.由$ (2.18) $式易知, $ \{F(x^k; \bar c)\} $是单调下降的.又$ \lim\limits_{k\in {\cal K}}F(x^k; \bar c) = F(x^*; \bar c) $,因此$ \lim\limits_{k\rightarrow\infty}F(x^k; \bar c) = F(x^*; \bar c) $.$ x^\ast $不是问题$ (1.1) $的稳定点,则由引理3.2及(2.18)式有

此与$ \bar{t} > 0 $$ \rho_\ast > 0 $矛盾.

如下定理进一步分析算法A的强收敛性,其证明可参照文献[15,定理2]类似完成.

引理3.4  设假设A1和A2成立,参数$ \xi > 0 $,则(ⅰ) $ \lim\limits_{k\rightarrow\infty}\|x^{k+1}-x^k\| = 0 $; (ⅱ)若$ \{x^k\} $有孤立聚点$ x^\ast $,则$ \lim\limits_{k\rightarrow\infty}x^k = x^\ast $,即算法是强收敛的.

4 数值试验

本部分利用MATLAB R2015a进行编程,计算机配置为Windows 7, Intel(R) Core(TM) CPU 3.30GHz.参数设置为$ \alpha = 0.5, \; \beta = 0.5, \; \varepsilon = 10, \; \delta = 10, \; p = 2, \; c_0 = 2, \; \gamma = 1, \; \gamma_0 = 0.5, \; \xi = 0.01 $,终止准则为$ \rho_k\leq 10^{-5} $.选取文献[2]中的6个算例,并将其数值结果与文献[2]中算法(记为算法JZQM)、文献[1]中算法(记为算法YG)的结果相比较.从数值结果可以看出,三个算法近似最优目标函数值和所需的迭代次数相差甚微,故该文所提出的算法是有效的.

表 1中各个符号含义为:问题序号为文献[2]中的序号; "$ n $":自变量$ x $的维数; "$ l $":目标函数中$ f_j(x) $的个数; "$ {m'} $":不等式约束函数的个数; "$ {m} $":等式约束函数的个数; "$ x^0 $":初始点; "Ni":算法迭代次数; "$ F(x^*) $":算法终止时获得的近似最优目标函数值.

表 1   数值结果

问题$n/l$/$m'$$/m$$x^0$算法Ni$F(x^*)$
问题1$2/3/0/1$$(-1, 3)^T$算法A$14$$2.1266e-10$
算法JZQM$12$$2.0079e-10$
算法YG$13$$0$
问题2$2/3/0/1$$(-1, 1)^T$算法A$8$$-1$
算法JZQM$15$$-1$
算法YG$11$$-1$
问题3$2/6/2/0$$(1, 3)^T$算法A$20$$0.6256$
算法JZQM$15$$0.5832$
算法YG$18$$0.6164$
问题5$2/2/0/1$$(-1, 4)^T$算法A$20$$-5.8714$
算法JZQM$12$$-5.8754$
问题6$3/3/1/2$$(2, 3, 2)^T$算法A$8$$-3.8621$
算法JZQM$5$$-3.9345$
问题7$10/8/0/3$$(0, 1, 1, 1, 0, 0, 1, 1, 1, 0)^T$算法A$74$$2.3521e+003$
算法JZQM$52$$2.3339e+003$

新窗口打开| 下载CSV


参考文献

Yu Y H , Gao L .

Nonmonotone line search algorithm for constrained minimax problems

J Optimiz Theory App, 2002, 115 (2): 419- 446

DOI:10.1023/A:1020896407415      [本文引用: 2]

Jian J B , Zhang X L , Quan R , Ma Q .

Generalized monotone line search SQP algorithm for constrained minimax problems

Optimization, 2009, 58 (1): 101- 131

URL     [本文引用: 3]

Jian J B , Hu Q J , Tang C M .

Superlinearly convergent norm-relaxed SQP method based on active set identification and new line search for constrained minimax problems

J Optimiz Theory App, 2014, 163 (3): 859- 883

DOI:10.1007/s10957-013-0503-5      [本文引用: 1]

Wang F S , Wang C L .

An adaptive nonmonotone trust region method with curvilinear search for minimax problem

Appl Math Comput, 2013, 219, 8033- 8041

URL     [本文引用: 1]

Ye F , Liu H W , Zhou S S , et al.

A smoothing trust region Newton-CG method for minimax problem

Appl Math Comput, 2008, 199, 581- 589

URL     [本文引用: 1]

Chi X N , Wei H J , Wan Z P , et al.

Smoothing Newton algorithm for the circular cone programming with a nonmonotone line search

Acta Math Sci, 2017, 37B (5): 1262- 1280

[本文引用: 1]

Obasanjo E , Tzallas-Regas G , Rustem B .

An interior point algorithm for nonlinear minimax problems

J Optimiz Theory App, 2010, 144 (2): 291- 318

DOI:10.1007/s10957-009-9599-z      [本文引用: 1]

Mayne D Q , Polak E .

Feasible directions algorithms for optimization problems with equality and inequality constraints

Math Program, 1976, 11 (1): 67- 80

DOI:10.1007/BF01580371      [本文引用: 1]

Jian J B , Xu Q J , Han D L .

A strongly convergent norm-relaxed method of strongly sub-feasible direction for optimization with nonlinear equality and inequality constraints

Appl Math Comput, 2006, 182, 854- 870

[本文引用: 2]

Jian J B , Guo C H , Yang L F .

A new generalized projection method of strongly sub-feasible directions for general constrained optimization

Pac J Optim, 2009, 5 (3): 507- 523

[本文引用: 3]

Rosen J B .

The gradient projection method for nonlinear programming. Part I. Linear constraints

J Soc Ind Appl Math, 1960, 8 (1): 181- 217

URL     [本文引用: 1]

Rosen J B .

The gradient projection method for nonlinear programming. Part Ⅱ. Linear constraints

J Soc Ind Appl Math, 1961, 9 (4): 514- 532

DOI:10.1137/0109044      [本文引用: 1]

朱志斌, 王硕, 简金宝.

非线性优化一个超线性收敛的广义投影型可行方向法

应用数学学报, 2014, 37 (1): 179- 192

URL     [本文引用: 2]

Zhu Z B , Wang S , Jian J B .

A generalized projection feasible method with superlinear convergence for nonlinear optimization

Acta Math Appl Sin, 2014, 37 (1): 179- 192

URL     [本文引用: 2]

简金宝. 光滑约束优化快速算法-理论分析与数值试验. 北京: 科学出版社, 2010

[本文引用: 2]

Jian J B . Fast Algorithms for Smooth Constrained Optimization-Theoretical Analysis and Numerical Experiments. Beijing: Science Press, 2010

[本文引用: 2]

Ma G D , Jian J B .

An ε-generalized gradient projection method for nonlinear minimax problems

Nonlinear Dynam, 2014, 75 (4): 693- 700

DOI:10.1007/s11071-013-1095-1      [本文引用: 2]

Ma G D , Zhang Y F , Liu M X .

A generalized gradient projection method based on a new working set for minimax optimization problems with inequality constraints

J Inequal Appl, 2017, 2017, 51

DOI:10.1186/s13660-017-1321-3      [本文引用: 4]

/