数学物理学报, 2024, 44(4): 1037-1051

最优化与变分不等式的可行解序列的有限终止性

王茹钰, 赵文玲,*, 宋道金

山东理工大学数学与统计学院 山东淄博 255049

The Finite Termination of Feasible Solution Sequence for Optimization and Variational Inequality

Wang Ruyu, Zhao Wenling,*, Song Daojin

School of Mathematics and Statistics, Shandong University of Technology, Shandong Zibo 255000

通讯作者: *赵文玲, E-mail: actams@wipm.ac.cn; actams@apm.ac.cn

收稿日期: 2023-07-7   修回日期: 2024-02-25  

基金资助: 山东省自然科学基金(ZR2021MA066)

Received: 2023-07-7   Revised: 2024-02-25  

Fund supported: Shandong Provincial Natural Science Foundation(ZR2021MA066)

摘要

为了在更弱的条件下, 给出最优化问题 (OP) 与变分不等式问题 (VIP) 的可行解序列的有限终止性, 在这类问题的解集上引进了一个增广映射, 分别建立了解集关于可行解序列广义弱尖锐性的概念. 这个新概念是传统的弱尖锐性与强非退化概念的扩充与推广, 其克服了最优化与变分不等式在许多情况下解集不具有弱尖锐性或强非退化性的缺陷. 在这些问题的解集满足广义弱尖锐性的条件下, 提供其可行解序列有限终止于解集的充分与必要条件. 这些结果是现有相关文献中在弱尖锐或强非退化条件下相应结果的推广, 同时也为许多最优化算法的有限终止性提供了更弱的充分条件.

关键词： 最优化问题; 变分不等式问题; 可行解序列; 广义弱尖锐性; 有限终止性

Abstract

To provide a finite characterization of feasible solution sequences for optimization problems (OP) and variational inequality problems (VIP), an augmented set value map is introduced for the solution sets of these problems. Additionally, the concepts of augmented weak sharpness with respect to feasible solution sequences are established. These novel notions extend the traditional concepts of weak sharpness and strongly non-degeneracy relative to feasible solution sequences, addressing the limitation that solution sets often lack weak sharpness or strongly non-degeneracy in many cases. When the feasible solution sets of optimization problems and variational inequality problems exhibit augmented weak sharpness, the necessary and sufficient conditions for the finite termination of feasible solution sequences are provided for each problem. These conditions extend the corresponding results found in existing literature, where solution sets are weak sharp or strongly non-degenerate. Furthermore, sufficient conditions with fewer restrictions are provided for the finite termination of various optimization algorithms.

Keywords： Optimization problem; Variational inequality problem; Feasible solution sequence; Augmented weak sharpness; Finite termination

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

本文引用格式

王茹钰, 赵文玲, 宋道金. 最优化与变分不等式的可行解序列的有限终止性[J]. 数学物理学报, 2024, 44(4): 1037-1051

Wang Ruyu, Zhao Wenling, Song Daojin. The Finite Termination of Feasible Solution Sequence for Optimization and Variational Inequality[J]. Acta Mathematica Scientia, 2024, 44(4): 1037-1051

1 引言

考虑如下最优化问题

$\begin{equation*} \min_{x\in S} f(x), \end{equation*}$

其中, $ S\subset \mathbb{R}^{n} $ 是非空闭凸集, $ f:\mathbb{R}^{n}\rightarrow \mathbb{R} $ 是正常的. 假设此问题的最优解集 $ \bar{S}\neq\emptyset $, 稳定点集

$\begin{equation*} \hat{S}=\{x\in S\mid\exists u\in\partial f(x),\quad \text{使得}\quad \langle u, y-x\rangle\geq0,\quad \forall y\in S\}, \end{equation*}$

其中, $ \partial f(x) $ 是 $ f $ 在 $ x $ 点的广义次微分 [1,定义8.3], 简称为次微分. 值得注意的是, 在一般情况下, 下述关系

$\begin{equation} \bar{S}\subseteq \hat{S} \end{equation}$

并不成立. 但是当 $ f $ 在 $ \mathbb{R}^{n} $ 上是局部 Lipschitz 时, (1.1) 式成立. 特别当 $ f $ 在 $ \mathbb{R}^{n} $ 上具有凸性时, (1.1) 式中等式成立, 并且它的次微分与凸分析中通常意义的次微分是一致的.

对于最优化问题算法所产生的可行解序列的有限终止性问题, 长期受到了广泛的关注与研究. 在这些研究中, 早期由 Rockafellar[2], Polyak[3] 与 Ferris[4] 相继给出的最优化问题解集的弱尖锐性与强非退化性, 它们中的任意一个都被证明是临近点算法 (Proximal point algorithm) (见文献 [2,5⇓⇓⇓⇓⇓⇓-12])与某些重要的迭代算法[13⇓⇓⇓⇓⇓⇓⇓⇓⇓-23] 具有有限终止性的充分条件. 此外, 还注意到解集的这个特性在误差界与灵敏度分析中起着重要的作用[24⇓⇓⇓⇓⇓⇓-31], 并且在半无限规划的``平静"问题中也得到了有效的应用[32].

值得提出的是, 上述算法产生的可行解序列的有限终止性, 不仅依赖于解集的弱尖锐性或者强非退化性, 而且还依赖于算法的具体结构特点. 因此, 进一步来研究在弱尖锐性或强非退化性的条件下, 一个不依赖于具体算法的可行解序列具有有限终止的条件, 更具有普遍的意义. 较早研究这个问题的是 Burke 与 Moré[14], 他们对光滑的规划问题, 在可行解序列收敛到一个强非退化点的条件下, 给出了该序列有限终止于稳定点的充分与必要条件 (见文献 [14,推论 3.5]. 这里注意到强非退化概念与弱尖锐性概念有着密切的联系. 特别地, 在凸规划中, 强非退化概念是弱尖锐性概念的特例. 而在非凸规划中，强非退化性与弱尖锐性并无包含关系. 继文献 [14] 之后, Buke 与 Ferris[33] 对光滑凸规划在解集具有弱尖锐性且可行解序列满足两个假设条件之下, 给出了该序列有限终止的充分与必要条件(见文献 [33,定理 4.7]).

为了将这个结果推广到变分不等式中, Marcotte 与 Zhu[34] 首先给出了其解集弱尖锐的定义, 然后在与文献 [33,定理 4.7] 类似的条件下, 将这个结果推广到连续的伪单调 $ ^+ $ 的变分不等式中 (见文献 [34,定理 5.2]), 而且要求其可行解集是紧致的. 后来 Xiu 与 Zhang[12] 对文献 [34,定理 5.2] 进行了改进, 他们去掉了该定理中的伪单调 $ ^+ $ 与可行解集是紧致的条件, 只对连续的伪单调变分不等式, 在可行解序列的极限是一个解点同时又是弱尖锐的 (见文献 [12,定义 3.1]) 假设下, 得出了同样的结果 (见文献 [12,定理 3.2]). Zhou 与 Wang[35]对上述文献 [12,33] 中的两个结果做了进一步的推广与改进: 一方面将文献 [33,定理 4.7] 中对可行解序列的两个假设条件去掉了, 同时将这个定理推广到非光滑凸规划中 (见文献 [35,定理 3.1]). 另一方面将文献 [12,定理 3.2] 中的伪单调性去掉了, 在有界的可行解序列的任一聚点是解点且是弱尖锐的条件下得出了同样的结果(见文献 [35,定理 3.3]).

在上述文献中, 解集的弱尖锐性质以及强非退化性质, 在许多情况下并不成立 (见本文第 2 节). 根据这些情况, 本文针对最优化问题和变分不等式问题, 分别在它们的解集上引进了一个广义映射 (单值的或多值的), 建立了解集关于可行解序列的广义弱尖锐性的概念. 这个新概念是凸规划问题中解集的弱尖锐性概念的实质性推广. 值得注意的是, 不论在凸规划或者非凸规划中, 广义弱尖锐性的概念都包含弱尖锐性和强非退化性, 也就是说, 弱尖锐性和强非退化性都是广义弱尖锐性的特例. 第 3 节分别在解集是广义弱尖锐性的条件下, 给出了可行解序列有限终止于解集的充分与必要条件. 这些结果分别包含了现有相关文献 [12,14,21,33⇓-35] 中相应的结果 (见本文第 3 节的推论). 此外, 建立的广义弱尖锐性的概念也为许多最优化算法的有限终止性提供了更弱的充分条件.

下面介绍本文用到的一些概念与符号.

设 $ N\subseteq \{1, 2, \cdots\} $ 是一个无限子序列, $ C^{k}\subset \mathbb{R}^{n}(k=1,2,\cdots) $. 定义

$\begin{equation*} \limsup_{k\rightarrow \infty }C^{k} =\{x \in \mathbb{R}^{n}\mid\ \text{存在}\ N\ \text{与}\ x^{k}\in C^k,\quad\text{使得}\ \lim_{k\in N,k\rightarrow \infty }x^{k} = x\}, \end{equation*}$
$\begin{equation*} \liminf_{k\rightarrow \infty }C^{k} =\{x \in \mathbb{R}^{n}\mid\ \text{存在}\ x^{k}\in C^{k},\quad\text{使得}\ \lim_{k\rightarrow \infty} x_{k}=x\}. \end{equation*}$

据上述定义即知

$\begin{equation*} \liminf_{k\rightarrow \infty }C^{k} \subseteq\limsup_{k\rightarrow \infty }C^{k}. \end{equation*}$

设 $ C\subset \mathbb{R}^{n} $, $ \bar{x}\in C $, $ C $ 在点 $ \bar{x} $ 的切锥定义为

$\begin{equation*} T_{C}(\bar{x})=\{d\in \mathbb{R}^{n}\mid\ \text{存在}\ x^{k}\in C,x^{k}\rightarrow \bar{x}, \tau^{k}\downarrow 0, (k\rightarrow \infty), \text{使得}\ \lim_{k\rightarrow \infty}(x^{k}-\bar{x})/\tau^{k}=d\}. \end{equation*}$

集合 $ C $ 在点 $ \bar{x} $ 的正则法锥定义为

$\begin{equation*} \hat{N}_{C}(\bar{x})=\{d\in \mathbb{R}^{n} \mid \langle d,x-\bar{x}\rangle\leq o(\|x-\bar{x}\|),x\in C\}. \end{equation*}$

一般意义下, 集合 $ C $ 在点 $ \bar{x} $ 的法锥定义为

$\begin{equation*} N_{C}(\bar{x})=\limsup_{x^k\in C,x^k\rightarrow \bar{x}}\hat{N}_C(x^k). \end{equation*}$

集合 $ C $ 的极锥定义为

$\begin{equation*} C^{\circ}=\{y\in \mathbb{R}^{n}\mid \langle y,x\rangle\leq 0,\forall x\in C\}. \end{equation*}$

由文献 [1,命题 6.5] 可知

$\begin{equation*} T_{C}(x)^{\circ}=\hat{N}_C(x). \end{equation*}$

当 $ C $ 是凸集时, 据文献 [1,定理 6.9] 有

$\begin{equation*} N_{C}(\bar{x})=\hat{N}_C(\bar{x})=\{d\mid \langle d,x-\bar{x}\rangle\leq 0,\forall x\in C\}. \end{equation*}$

设 $ x\in \mathbb{R}^{n} $, $ x $ 在闭集 $ C $ 上的投影定义为

$\begin{equation*} P_C(x)=\arg\min_{y\in C}\|y-x\|. \end{equation*}$

注意由上述定义可知, 当 $ C $ 是闭凸集时, $ P_C(\cdot) $ 是单值映像. 但是当 $ C $ 是一般闭集时, $ P_C(\cdot) $ 可能是一集值映像.

点 $ x $ 到集合 $ C $ 的距离定义为

$\text{ dist}(x,C)=\inf_{y\in C}\|y-x\|.$

如果 $ C $ 是闭集, 则有

$\text{ dist}(x,C)=\|P_{C}(x)-x\|.$

设函数 $ \psi(\cdot) $ 在点 $ x\in C $ 的次微分 $ \partial\psi(x)\neq\emptyset $, 则 $ \psi(\cdot) $ 在点 $ x $ 的投影次微分定义为

$\begin{equation*} P_{T_{C}(x)}(-\partial\psi(x))=\left\{P_{T_{C}(x)}(-u)\mid u\in \partial\psi(x)\right\}. \end{equation*}$

如果 $ \psi(\cdot) $ 在点 $ x\in C $ 的某个邻域内是连续可微的, 由文献 [1,练习 8.8]{18} 知 $ \partial\psi(x)= \{\nabla\psi(x)\} $, 这意味着此时投影次微分等价由此投影梯度 $ P_{T_{C}(x)}(-\nabla\psi(x)). $

如果存在 $ k_{0} $, 当 $ k{\geq} k_{0} $ 时 $ x^{k}\in C $ 成立, 则称序列 $ \{x^{k}\}\subset \Bbb{R}^n $ 有限终止于 $ C $.

2 最优化与变分不等式解集的广义弱尖锐性

本节首先介绍有关文献中关于最优化问题 (OP) 与变分不等式问题 (VIP) 的解集的弱尖锐性与强非退化性等概念. 之后, 分别给出了最优化 (OP) 与变分不等式 (VIP) 问题的解集关于可行解序列的广义弱尖锐性的概念, 并阐明这个新概念是凸规划解集的弱尖锐性概念与单调变分不等式解集的弱尖锐概念的实质性推广. 同时在可行解满足通常的假设下, 对一般的最优化 (OP) 与变分不等式 (VIP) 问题, 讨论了解集的广义弱尖锐性与弱尖锐性或强非退化性之间的包含关系. 最后给出若干例子, 表明它们的解集不具有弱尖锐性或强非退化性, 但是对于满足一定条件的可行解序列, 它们的解集却具有广义弱尖锐性.

对于最优化问题

$\begin{equation*} {\rm (OP)}\qquad\qquad\min_{x\in S} f(x). \end{equation*}$

下面先给出最优化问题中弱尖锐性的定义[4,33].

定义 2.1 在最优化问题 (OP) 中, 如果存在常数 $ \alpha> 0 $, 使得对 $ \forall x\in \bar{S} $ 有

$\begin{equation*} f(y)-f(x)\geq \alpha\cdot {\rm dist}(y,\bar{S}),\quad\forall y\in S, \end{equation*}$

则称为解集 $ \bar{S}\subset S $ 是具有弱尖锐性的, 其中, 常数 $ \alpha> 0 $ 与集合 $ \bar{S} $ 分别称为 $ f $ 在 $ S $ 上的弱尖锐模和弱尖锐域.

如果 (OP) 是非光滑的凸规划, 那么 $ \bar{S} $ 是 (OP) 中具有模 $ \alpha $ 的弱尖锐集, 当且仅当

$\begin{equation} \alpha B\subset \partial f(x)+[T_{S}(x)\cap N_{\bar{S}}(x)]^{\circ},\quad\forall x\in \bar{S}, \end{equation}$

其中, $ B $ 是一单位球 (见文献 [33,定理 2.6c]).

如果 (OP) 是光滑的凸规划, 那么 $ \bar{S} $ 是 (OP) 中具有模 $ \alpha $ 的弱尖锐集, 当且仅当

$\begin{equation} -\nabla f (\bar{x})\in \text{ int} \bigcap_{x\in\bar{S}}[T_{S}(x)\cap N_{\bar{S}}(x)]^{\circ},\quad\forall \bar{x}\in \bar{S}. \end{equation}$

上面的等价条件成立, 见文献 [33,推论 2.7c]. 这里在 $ f $ 是光滑的情况下, (2.2) 与 (2.1) 式是等价的, 这是因为 $ \nabla f(\cdot) $ 在$ \bar{S} $ 上是常值向量 (见文献 [36,推论 6]).

为了将解集的这种特性推广到一般的光滑非凸规划问题的解集中, 文献 [20,21,30] 用 (2.2) 式定义了它的解集的弱尖锐性的概念. 但在本文对 (2.1) 式进行了修改后, 用来定义了一般规划问题解集的弱尖锐性, 即下面的定义 (2.2).

定义 2.2 设在 (OP) 中, 对 $ \forall x\in S $, $ \partial f(x)\neq\emptyset $. 如果存在常数 $ \alpha>0 $, 使得

$\begin{equation} \alpha B\subset \partial f(x)+[T_{S}(x)+ \hat{N}_{\bar{S}}(x)]^{\circ},\quad\forall x\in \bar{S} \end{equation}$

成立, 则称解集 $ \bar{S}\subset S $ 是弱尖锐集.

注 2.1 在 (2.3) 式中采用 $ \hat{N}_{\bar{S}}(\cdot) $, 而不是采用 (2.1) 式中的 $ N_{\bar{S}}(\cdot) $, 这是因为在一般情况下, $ \bar{S} $ 不一定是凸集. 当 $ \bar{S} $ 是非凸集时, 根据文献 [1,命题 6.5] 知, $ \hat{N}_{\bar{S}}(\cdot) $ 是闭凸锥, 而$ N_{\bar{S}}(\cdot) $ 仅是一个闭锥, 而且有关系

$\begin{equation*} \hat{N}_{\bar{S}}(\cdot)\subseteq N_{\bar{S}}(\cdot). \end{equation*}$

因此, 由上式可知

$\begin{equation*} [T_S(x)\cap N_{\bar{S}}(x)]^\circ\subseteq[T_S(x)\cap\hat{N}_{\bar{S}}(x)]^\circ. \end{equation*}$

采用 $ \hat{N}_{\bar{S}}(\cdot) $ 可以使得定义 2.2 更加宽松.

考虑变分不等式问题

$\begin{equation*} {\rm (VIP)}\qquad\qquad \text{求}\ \bar{x}\in S \text{使得} \langle F(\bar{x}),y-\bar{x}\rangle\geq0,\quad\forall y\in S, \end{equation*}$

其中 $ S\subset \mathbb{R}^n $ 是非空的闭凸集, $ F:S\rightarrow \mathbb{R}^n $, (VIP) 的解集 $ \bar{S}\neq\emptyset $.

对于变分不等式问题 (VIP), 文献 [12,34,35] 用 (2.2) 式 (其中 $ \nabla f(\cdot $) 用 $ F(\cdot) $ 代替) 来定义了其解集的弱尖锐性. 考虑定义 (2.2), 并用 $ \hat{N}_{\bar{S}}(\cdot) $ 代替 (2.2) 式中的 $ N_{\bar{S}}(\cdot) $, 得到了下面的定义.

定义 2.3 在 (VIP) 中, 如果有

$\begin{equation*} -F(\bar{x})\in {\rm int} \bigcap_{x\in\bar{S}}[T_{S}(x)\cap \hat{N}_{\bar{S}}(x)]^{\circ}, \forall \bar{x}\in \bar{S}, \end{equation*}$

称解集 $ \bar{S}\subset S $ 是弱尖锐集.

定义 2.4[14,22,30] 在光滑的 (OP) 中, 如果

$\begin{equation} -\nabla f(\bar{x})\in {\rm int} N_S(\bar{x}), \forall \bar{x}\in \bar{S}, \end{equation}$

则称解集 $ \bar{S}\subset S $ 为强非退化集.

类似地, 在 (VIP) 中, 如果

$\begin{equation} -F(\bar{x})\in {\rm int} N_S(\bar{x}), \forall \bar{x}\in \bar{S}. \end{equation}$

则称解集 $ \bar{S}\subset S $ 为强非退化集, 满足 (2.4)或 (2.5) 式的点, 称为强非退化点.

如前面所述, 在许多情况下, 解集不具有弱尖锐性或强非退化性, 为了克服这种缺陷, 下面引进解集关于可行解序列的广义弱尖锐性的概念.

定义 2.5 对于最优化问题 (OP), 假设其解集 $ \bar{S}\subset S $ 是闭的, 对任意 $ x\in S $, $ \{x^k\}\subset S $, $ \partial f(x)\neq\emptyset $. 如果下面两种情况 (1) 与 (2) 之一成立

(1) 集合 $ K=\{k\mid x^k\notin \bar{S}\} $ 是有限集;

(2) 当 $ K=\{k\mid x^k\notin \bar{S}\} $ 是无穷序列, 则存在增广映射 $ H:\bar{S}\rightarrow 2^{\mathbb{R}^{n}} $, 使得

(a) 存在常数 $ \alpha>0 $, 满足

$\begin{equation*} \alpha B\subset H(z)+[T_{S}(z)\bigcap\hat{N}_{\bar{S}}(z)]^{\circ}, \forall z\in \bar{S}; \end{equation*}$

(b) 对于 $ \forall u^{k}\in \partial f(x^k) $, $ \forall v^{k}\in H(P_{\bar{S}}(x^{k})) $ 都有

$\begin{equation*} \limsup_{k\in K, k\rightarrow \infty}\psi_{k}：=\frac{1}{\|x^{k}-P_{\bar{S}}(x^{k})\|} \langle u^{k}-v^{k}, x^{k}-P_{\bar{S}}(x^{k})\rangle\geq0. \end{equation*}$

则称 $ \bar{S} $ 关于可行解序列 $ \{x^k\} $ 是广义弱尖锐集.

类似地, 对于变分不等式问题 $ VIP(F, S) $, 假设其解集 $ \bar{S}\subset S $ 是闭的, $ \{x^k\}\subset S $. {如果下面两种情况 (1) 与 (2) 之一成立}

(1) 集合 $ K=\{k\mid x^k\notin \bar{S}\} $ 是有限集;

(2) 当 $ K=\{k\mid x^k\notin \bar{S}\} $ 是无穷序列, 则存在增广映射 $ H:\bar{S}\rightarrow 2^{\mathbb{R}^{n}} $, 使得

(a) 存在常数 $ \alpha>0 $, 满足

$\begin{equation*} \alpha B\subset H(z)+[T_{S}(z)\bigcap\hat{N}_{\bar{S}}(z)]^{\circ}, \forall z\in \bar{S}; \end{equation*}$

(b') 对于 $ \forall v^{k}\in H(P_{\bar{S}}(x^{k})) $ 都有

$\begin{equation*} \limsup_{k\in K, k\rightarrow \infty}\psi_{k}'：=\frac{1}{\|x^{k}-P_{\bar{S}}(x^{k})\|} \langle F(x^{k})-v^{k}, x^{k}-P_{\bar{S}}(x^{k})\rangle\geq0. \end{equation*}$

则称 $ \bar{S} $ 关于可行解序列 $ \{x^k\} $ 是广义弱尖锐集.

接下来讨论 $ \bar{S} $ 的广义弱尖锐性与其它几个概念 (弱尖锐性, 强非退化性) 的关系.

2.1 最优化问题 (OP) 是非光滑的情况

命题 2.1 设在凸规划 (OP) 中, 若解集 $ \bar{S}\subset S $ {具有弱尖锐性}, 则对任意 $ \{x^k\}\subset S $, $ \bar{S} $ 关于 $ \{x^k\} $ 是广义弱尖锐性的.

证 由于 (OP) 是凸规划, 据文献 [37,定理 23.4] 知, 对 $ \forall x\in \mathbb{R}^n, \partial f(x)\neq\emptyset $, 并且其解集 $ \bar{S} $ 是闭凸集, 因此 $ \hat{N}_{\bar{S}}(\cdot)=N_{\bar{S}}(\cdot) $, 并且 $ P_{\bar{S}}(\cdot) $ 是单值映像. 设 $ \{x^k\}\subset S $, $ K=\{k\mid x^k\notin \bar{S} \}$ 是一无穷序列, 则设

$\begin{equation*} H(z)=\partial f(z), \forall z\in \bar{S}. \end{equation*}$

由假设 $ \bar{S} $ 是弱尖锐集, 因此由 (2.1) 式即知, 定义 2.5 中 (a) 成立. 又因为 $ f(\cdot) $ 是 $ \mathbb{R}^n $ 上的凸函数, 所以 $ \partial f(\cdot) $ 是单调的, 由此易知定义 2.5 中 (b) 成立. 证毕.

注 2.2 由命题 2.1 与后面的命题 2.3, 命题 2.7 表明, (OP) 与 (VIP) 的解集的广义弱尖锐性分别是凸规划解集的弱尖锐性与单调变分不等式解集的弱尖锐性的推广. 下面这个简单例子表明解集不具有弱尖锐性, 但是对满足一定条件的可行解序列, 解集是广义弱尖锐性的.

例 2.1 对于最优化问题

$\begin{equation*} \min_{x\in S}f(x)=\frac{1}{2}x^2, \end{equation*}$

其中, $ S=\{x\in \mathbb{R}\mid x\geq0\} $. 易知, $ \bar{S}=\{0\} $. 由于 $ [T_S(0)\cap N_{\bar{S}}(0)]^\circ=(-\infty, 0] $, $ \nabla f(0)=0 $, 所以解集 $ \bar{S} $ 不具有弱尖锐性. 现取 $ \lambda>0 $, 设 $ H(0)=\lambda $, 则易证对 $ x^k\geq\lambda $ 的可行解序列 $ \{x^k\} $, 定义 2.5 中的 (a), (b) 成立, 因此, $ \bar{S} $ 关于 $ \{x^k\} $ 是广义弱尖锐集.

为了方便, 简记下面符号

$\begin{equation*} G:=\bigcap_{x\in \bar{S}}[T_S(x)\cap\hat{N}_{\bar{S}}(x)]^{\circ}. \end{equation*}$

命题 2.2 设在凸规划 (OP) 中, 解集 $ \bar{S}\subset S $ 满足

$\begin{equation} -\partial f(x)\cap(-N_S(x))\subset {\rm int} G, \forall x\in \bar{S}, \end{equation}$

则对任意 $ \{x^k\}\subset S $, $ \bar{S} $ 是广义弱尖锐性的.

证 由文献 [37,定理 23.4] 知, 对 $ \forall x\in \mathbb{R}^n $, $ \partial f(x) $ 是非空紧致集. 由文献 [36,定理 5] 知, $ \partial f(x)\cap(-N_S(x)) $ 在 $ \bar{S} $ 上是一个非空且紧致的常值集合. 因此由 (2.6) 式知, 存在常数 $ \alpha>0 $, 对 $ \forall x\in \bar{S} $ 有

$\begin{equation*} \alpha B-\partial f(x)\cap(-N_S(x))\subset[T_S(x)\cap N_{\bar{S}}(x)]^{\circ}. \end{equation*}$

由上式即得

$\begin{eqnarray*} \ \alpha B&\subset&\partial f(x)\cap(-N_S(x))+[T_S(x)\cap N_{\bar{S}}(x)]^{\circ}\\ &\subset&\partial f(x)+[T_S(x)\cap N_{\bar{S}}(x)]^{\circ}, \forall x\in \bar{S}, \end{eqnarray*}$

即 $ \bar{S} $ 是一个弱尖锐集, 从而由命题 2.1 即得证明.

2.2 (OP) 是光滑的情况

命题 2.3 设在光滑凸规划 (OP) 中, 若解集 $ \bar{S}\subset S $ 满足

$\begin{equation} -\nabla f(x)\in {\rm int} G, \forall x\in \bar{S}, \end{equation}$

即 $ \bar{S} $ 是弱尖锐集, 则对任意 $ \{x^k\}\subset S, \bar{S} $ 是广义弱尖锐性的.

证 由于 $ f(\cdot) $ 是光滑的, 所以 $ \partial f(x)=\{\nabla f(x)\} $, 而且对 $ \forall x\in \bar{S} $ 有 $ \nabla f(x)\in-N_S(x) $, 从而由 (2.7) 式与命题 2.2 即得证明.

命题 2.4 设在光滑规划 (OP) 中, 对解集 $ \bar{S}\subset S $, $ \{x^k\}\subset S $ 及 $ \forall z^k\in P_{\bar{S}}(x^k) $ 满足

$\begin{equation} \lim_{k\rightarrow\infty}\|\nabla f(x^k)-\nabla f(z^k)\|=0. \end{equation}$

如果 $ \bar{S} $ 是弱尖锐的, 则 $ \bar{S} $ 关于 $ \{x^k\} $ 是广义弱尖锐性的.

证 设 $ K=\{k\mid x^k\notin \bar{S}\} $ 是一无穷序列. 令 $ H(z)=\nabla f(z) $, $ \forall z\in \bar{S} $. 由假设 $ \bar{S} $ 是弱尖锐的, 因此, 由定义 2.2 知定义 2.5 中 (a) 成立. 再据 (2.8) 式即得

$\begin{equation*} \limsup_{k\in K, k \rightarrow\infty}\psi_{k}=\limsup_{k\in K, k \rightarrow\infty} \frac{1}{\|x^{k}-z^{k}\|}\langle\nabla f(x^{k})-\nabla f(z^{k}), x^{k}-z^{k}\rangle=0, \end{equation*}$

即定义 2.5 中 (b) 成立, 亦即 $ \bar{S} $ 关于 $ \{x^k\} $ 是广义弱尖锐性的.

命题 2.5 设在光滑的 (OP) 中, $ \{x^k\}\subset S $. 如果 $ \{\nabla f(x^k)\} $ 有界且它的任一聚点 $ \bar{p} $ 满足 $ -\bar{p}\in {\rm int} G $, 则 $ \bar{S} $ 关于 $ \{x^k\} $ 是广义弱尖锐性的.

证 设 $ K=\{k\mid x^k\notin \bar{S}\} $ 是一无穷序列. 由假设 $ \{\nabla f(x^k)\} $ 有界, 因此 $ \{\nabla f(x^k)\}_{k\in K} $ 必有一聚点 $ \bar{p} $, 满足 $ -\bar{p}\in \text{ int} G $, 即存在常数 $ \alpha>0 $, 使得

$\begin{equation} \alpha B\subset\bar{p}+[T_{S}(z)\cap\hat{N}_{\bar{S}}(z)]^{\circ}, \forall z\in\bar{S}. \end{equation}$

令 $ H(z)=\bar{p} $, $ \forall z\in\bar{S} $, 由 (2.9) 式知, 定义 2.5 中 (a) 成立. 设 $K_{0} \subset K$ 使得

$\begin{equation} \lim_{k\in K_{0}, k\rightarrow\infty}\nabla f(x^{k})=\bar{p}. \end{equation}$

由 (2.10) 式即得

$\begin{eqnarray*} \limsup_{k\in K, k \rightarrow\infty}\psi_{k}\geq\limsup_{k\in K_{0}, k \rightarrow\infty}\psi_{k} =\lim_{k\in K_{0}, k\rightarrow\infty}\frac{1}{\| x^{k}-P_{\bar{s}}(x^{k})\|}\langle\nabla f(x^{k}) -\bar{p}, x^{k}-P_{\bar{S}}(x^{k})\rangle=0, \end{eqnarray*}$

即定义 2.5 中 (b) 成立, 亦即 $ \bar{S} $ 关于 $ \{x^k\} $ 是广义弱尖锐性的.

命题 2.6 设在光滑规划 (OP) 中, $ \{x^k\}\subset S $ 有界且它的任一聚点是强非退化点, 则 $ \bar{S} $ 关于 $ \{x^k\} $ 是广义弱尖锐性的.

证 设 $ K=\{k\mid x^k\notin \bar{S}\} $ 是一无穷序列. 则由假设 $ \{x^k\}_{k\in K} $ 必有一聚点 $ \bar{x} $. 设 $ K_0\subset K $ 使得

$\begin{equation} \lim_{k\in K_0, k\rightarrow\infty}x^k=\bar{x}. \end{equation}$

由假设 $ \bar{x} $ 是强非退化点及 $ \nabla f(\cdot) $ 的连续性, 据文献 [30,命题 5.1] 可知 $ \bar{x} $ 是 $ \bar{S} $ 的一个孤立点, 从而有 $ T_{\bar{S}}(\bar{x})=\{0\} $, $ \hat{N}_{\bar{S}}(\bar{x})=T_{\bar{S}}(\bar{x})^{\circ}=\mathbb{R}^n $. 因此有

$\begin{equation} [T_{S}(\bar{x})\cap\hat{N}_{\bar{S}}(\bar{x})]^{\circ}=T_{S}(\bar{x})^{\circ}=N_{S}(\bar{x}). \end{equation}$

这样根据 (2.4) 与 (2.12) 式知存在常数 $ \alpha>0 $ 使得

$\begin{equation} \alpha B\subset\nabla f(\bar{x})+N_{S}(\bar{x})=\nabla f(\bar{x})+[T_{S}(\bar{x})\cap\hat{N}_{\bar{S}}(\bar{x})]^{\circ}. \end{equation}$

现在定义增广映射 $ H:\bar{S}\rightarrow 2^{\mathbb{R}^{n}} $

$\begin{equation} H(z)=\left\{\begin{array}{ll} \ \nabla f(\bar{x}), z=\bar{x},\\ \ \mathbb{R}^{n}, z\in \bar{S}\setminus\{\bar{x}\}. \end{array} \right. \end{equation}$

根据 (2.13) 和 (2.14) 式, 有

$\begin{equation*} \alpha B\subset H(z)+[T_{S}(z)\cap\hat{N}_{\bar{S}}(z)]^{\circ},\ \forall z\in\bar{S}, \end{equation*}$

即定义 2.5 中 (a) 成立.又因为 $ \bar{x} $ 是 $ \bar{S} $ 的孤立点, 因此据 (2.11) 式对所有充分大的 $ k\in K_{0} $, 有 $ P_{\bar{S}}(x^{k})=\bar{x} $. 从而据 (2.11), (2.14) 式与 $ \nabla f(\cdot) $ 的连续性即得

$\begin{eqnarray*} \limsup_{k\in K,k \rightarrow\infty}\psi_{k}&\geq&\limsup_{k\in K_{0},k \rightarrow\infty}\psi_{k} =\lim_{k\in K_{0},k\rightarrow\infty}\frac{1}{\| x^{k}-\bar{x}\|}\langle\nabla f(x^{k}) -\nabla f(\bar{x}),x^{k}-\bar{x}\rangle=0, \end{eqnarray*}$

即定义 2.5 中 (b) 成立, 亦即 $ \bar{S} $ 关于 $ \{x^k\} $ 是广义弱尖锐性的.

2.3 变分不等式的情况

对于 (VIP), 可以分别仿照命题 2.1, 命题 2.5 与命题 2.6 的证明, 得出以下命题.

命题 2.7 设在 (VIP) 中, $ F $ 是单调的, $ \bar{S}\subset S $ 是一闭集. 如果 $ \bar{S} $ 是弱尖锐集, 则对任意的 $ \{x^k\}\subset S $, $ \bar{S} $ 关于 $ \{x^k\} $ 是广义弱尖锐性的.

命题 2.8 设在 (VIP) 中, $ \bar{S}\subset S $ 是一闭集, $ \{x^k\}\subset S $. 如果 $ \{F(x^k)\} $ 有界且它的任一聚点 $ \bar{p} $ 满足 $ -\bar{p}\in {\rm int} G $, 则 $ \bar{S} $ 关于 $ \{x^k\} $ 是广义弱尖锐性的.

命题 2.9 设在 (VIP) 中, $ F(\cdot) $ 在 $ S $ 上连续. 如果 $ \{x^k\}\subset S $ 有界且它的任一聚点是强非退化点, 则 $ \bar{S} $ 关于 $ \{x^k\} $ 是广义弱尖锐性的.

由上述命题可知, 对于一般的 (OP) 与 (VIP), 在适当假设条件下, 解集的弱尖锐性或强非退化性都蕴含着解集的广义弱尖锐性. 为了进一步说明这个新概念具有较大的包容性, 下面给出几个例子, 它们表明其解集不具有弱尖锐性或强非退化性, 但是对于满足一定条件的可行解序列, 它们的解集是广义弱尖锐性的.

例 2.2 考虑变分不等式问题 (VIP)

$\begin{equation*} F(x)=(\cos x_{1},{\rm e}^{x_{2}}), \end{equation*}$

其中

$\begin{equation*} S=\{x\in \mathbb{R}^{2}\mid 0\leq x_{1}\leq \frac{\pi}{2},x_{2}\geq0\}, \bar{S}=\{(0,0),(\frac{\pi}{2},0)\}. \end{equation*}$

当 $ x\in\bar{S} $ 时有

$\begin{equation} F(x)=\left\{\begin{array}{ll} (1,1), &\text{当}\ x=(0,0),\\ (0,1), &\text{当}\ x=(\frac{\pi}{2},0),\\ \end{array} \right. \end{equation}$
$\begin{equation} N_{S}(x)=\left\{\begin{array}{ll} \{\xi\in \mathbb{R}^{2}\mid \xi_{1}\leq0,\xi_{2}\leq 0\}, &\text{当}\ x=(0,0),\\ \{\xi\in \mathbb{R}^{2}\mid \xi_{1}\geq0,\xi_{2}\leq 0\}, &\text{当}\ x=(\frac{\pi}{2},0),\\ \end{array} \right. \end{equation}$

这是一个非单调的变分不等式问题. 由 (2.15), (2.16) 式可知, $ \bar{S} $ 不是一个强非退化集, 因为 $ x=(\frac{\pi}{2},0) $ 不是一个强非退化点.

下面证明 $ \bar{S} $ 对于满足下述条件的 $ \{x^{k}\}\subset S $是一个广义弱尖锐集.

(i) $\{x^{k}\}\subset\{x\in \mathbb{R}^{2}\mid x_{1}\leq\frac{\pi}{4}\}\cup\{x\in \mathbb{R}^{2}\mid x_{1}\geq\frac{\pi}{4}, x_{1}+x_{2}\geq\frac{\pi}{2}\}; $

(ii) $\lim\limits_{k\rightarrow\infty} {\rm dist}(x^{k},\bar{S})=0. $

为此, 设 $ K=\{k\mid x^{k}\notin \bar{S}\} $ 是一个无穷序列. 取 $ \lambda\in(0,\frac{1}{2}) $, 引进增广映像

$\begin{equation} H(x)=\left\{\begin{array}{ll} (\lambda,\lambda), &\text{当}\ x=(0,0),\\ (-\lambda,\lambda), &\text{当}\ x=(\frac{\pi}{2},0).\\ \end{array} \right. \end{equation}$

由 (2.16) 和 (2.17) 式可知定义 2.5 中的条件 (a) 成立. 现在对 $ k\in K $, 有

$\begin{equation*} \psi_{k}:=\frac{1}{\|x^{k}-P_{\bar{S}}(x^{k})\|}\langle F(x^{k})- H(P_{\bar{S}}(x^{k})),x^{k}-P_{\bar{S}}(x^{k})\rangle, \end{equation*}$

其中

$\begin{equation} P_{\bar{S}}(x^{k})=\left\{\begin{array}{ll} (0,0), \text{当}\ x_{1}^{k}\leq\frac{\pi}{4},\\[3mm] (\frac{\pi}{2},0), \text{当}\ x_{1}^{k}\geq\frac{\pi}{4}.\\ \end{array} \right. \end{equation}$

据条件 (ii) 有界序列 $ \{x^{k}\}_{k\in K} $ 的聚点只能是 $ \bar{x}=(0,0) $ 或 $ \bar{x}=(\frac{\pi}{2},0) $. 不失一般性, 设 $ \bar{x}=(\frac{\pi}{2},0) $ 是其一个聚点, 由此存在无穷子列 $ K_{0}\subseteq K $ 使得

$\begin{equation} \lim_{k\in K_{0},k\rightarrow\infty}x^{k}=(\frac{\pi}{2},0). \end{equation}$

据 (2.17), (2.18) 和 (2.19) 式, 当 $ k\in K_{0} $ 充分大时, 有

$\begin{eqnarray*} \ \psi_{k}&=&\frac{1}{\|x^{k}-\bar{x}\|}[(\cos x_{1}^{k}+\lambda)(x_{1}^{k}-\frac{\pi}{2})+({\rm e}^{x_{2}^{k}}-\lambda)x_{2}^{k}]\\ &\geq&\frac{1}{\|x^{k}-\bar{x}\|}[\cos x_{1}^{k}(x_{1}^{k}-\frac{\pi}{2})+({\rm e}^{x_{2}^{k}}-2\lambda)x_{2}^{k}] { (\text{由} (i))}\\ &\geq&\frac{1}{\|x^{k}-\bar{x}\|}(x_{1}^{k}-\frac{\pi}{2})\cos x_{1}^{k} {(\text{由} \lambda\in(0,\frac{1}{2}))}. \end{eqnarray*}$

再据 (2.19) 式即得

$\begin{equation*} \limsup_{k\in K,k\rightarrow\infty}\psi_{k}\geq\lim_{k\in K_{0},k\rightarrow\infty}\frac{1}{\|x^{k}-\bar{x}\|}(x_{1}^{k}-\frac{\pi}{2})\cos x_{1}^{k}=0, \end{equation*}$

即定义 2.5 中 (b) 成立.

例 2.3 考虑最优化问题 (OP)

$\begin{equation*} \min_{x\in S}f(x)=\sin x_1 \cos x_2, \end{equation*}$

其中

$\begin{equation*} S=\{x\in \mathbb{R}^{2}\mid 0\leq x_1\leq \frac{\pi}{2},\ 0\leq x_2\leq \frac{\pi}{2}\}, \end{equation*}$
$\begin{equation*} \bar{S}=\{x\in \mathbb{R}^{2}\mid x_1=0, 0\leq x_2\leq \frac{\pi}{2}\}\cup\{x\in \mathbb{R}^{2}\mid 0\leq x_1\leq \frac{\pi}{2}, x_2=\frac{\pi}{2}\}, \end{equation*}$
$\begin{equation*} \nabla f(x)=(\cos x_1\cos x_2,-\sin x_1\sin x_2), \end{equation*}$
$\begin{equation} \nabla f(x)=\left\{\begin{array}{ll} (0, 0),& x=(0,\frac{\pi}{2}),\\[3mm] (\cos x_2, 0),& x_1=0,\ 0\leq x_2< \frac{\pi}{2},\\[3mm] (0,-\sin x_1),& 0< x_1\leq \frac{\pi}{2},\ x_2=\frac{\pi}{2}, \end{array} \right. \end{equation}$

这里的解集 $ \bar{S} $ 是非凸集. 有

$\begin{equation} [T_S(x)\cap \hat{N}_{\bar{S}}(x)]^\circ =\left\{\begin{array}{ll} \mathbb{R}^2,& x=(0,\frac{\pi}{2}),\\[3mm] \{x\in \mathbb{R}^2\mid x_1\leq0,-\infty<x_2<+\infty\},& x_1=0,\ 0\leq x_2< \frac{\pi}{2},\\[3mm] \{x\in \mathbb{R}^2\mid -\infty<x_1<+\infty,x_2\geq0\},& 0< x_1\leq \frac{\pi}{2},\ x_2=\frac{\pi}{2}. \end{array} \right. \end{equation}$

由 (2.20), (2.21) 式得

$\begin{equation*} \nabla f(x)\!+\![T_S(x)\cap \hat{N}_{\bar{S}}(x)]^\circ =\left\{\begin{array}{ll} \mathbb{R}^2,& x=(0,\frac{\pi}{2}),\\[3mm] \{x\in \mathbb{R}^2\mid x_1\leq \cos x_2,-\infty\!<\!x_2\!<\!+\infty\},& x_1=0,\ 0\leq x_2< \frac{\pi}{2},\\[3mm] \{x\in \mathbb{R}^2\mid -\infty\!<\!x_1\!<\!+\infty,x_2\geq -\sin x_1\},& 0<x_1\leq \frac{\pi}{2},\ x_2\!=\!\frac{\pi}{2}. \end{array}\right. \end{equation*}$

由上式即知本例中的解集 $ \bar{S} $ 不是一个弱尖锐集, 这是因为定义 2.5 中的常数 $ \alpha $ 不存在. 由上式可以明显看出 $ \alpha $ 是集合 $ \bar{S}\setminus \{(0,\frac{\pi}{2})\} $ 上的函数, 当 $ x_1\rightarrow0 $ 或 $ x_2\rightarrow\frac{\pi}{2} $ 时, $ \alpha\rightarrow0 $.

现在取定充分小的 $ \varepsilon>0 $. 证明当无穷序列 $ \{x^k\}\subset\{x\in \mathbb{R}^2\mid \varepsilon\leq x_1\leq\frac{\pi}{2}-\varepsilon,\varepsilon\leq x_2\leq\frac{\pi}{2}-\varepsilon\} $ 时, 解集 $ \bar{S} $ 是广义弱尖锐性的. 为此取

$\begin{equation} \lambda=\min\{\cos ^2(\frac{\pi}{2}-\varepsilon),\sin ^2\varepsilon\}. \end{equation}$

显然, $ \lambda>0 $. 在 $ \bar{S} $ 上引进增广映射

$\begin{equation} H(x)=\left\{\begin{array}{ll} (0, 0),& x=(0,\frac{\pi}{2}),\\[3mm] (\lambda, 0),& x_1=0,0\leq x_2< \frac{\pi}{2},\\[3mm] (0,-\lambda),& 0< x_1\leq \frac{\pi}{2},x_2=\frac{\pi}{2}. \end{array} \right. \end{equation}$

由 (2.21), (2.23) 式可知定义 2.5 中 (a) 成立. 现在证明 (b) 也成立. 注意到 $ x^k $ 在 $ \bar{S} $ 上的投影仅有下面 (1) 与 (2) 两种情况

(1) $ P_{\bar{S}}(x^k)=(0,x^k_2) $ 且 $ 0\leq x_2^k<\frac{\pi}{2} $;

(2) $ P_{\bar{S}}(x^k)=(x^k_1,\frac{\pi}{2}) $ 且 $ 0< x_1^k\leq\frac{\pi}{2} $.

对于情况 (1), 利用 (2.22) 式, 有

$\begin{eqnarray*} \ \Psi_k&=&\frac{1}{\|x^k-P_{\bar{S}}(x^k)\|}\langle\nabla f(x^k)-H(P_{\bar{S}}(x^k)),x^k-P_{\bar{S}}(x^k)\rangle\\ &=&\cos x_1^k\cos x_2^k-\lambda \geq \cos ^2(\frac{\pi}{2}-\varepsilon)-\lambda\geq0. \end{eqnarray*}$

对于情况 (2), 同样利用 (2.22) 式就得出

$\begin{eqnarray*} \Psi_k&=&\frac{x_2^k-\frac{\pi}{2}}{|x_2^k-\frac{\pi}{2}|}(-\sin x_1^k\sin x_2^k+\lambda) =\sin x_1^k\sin x_2^k-\lambda \geq \sin ^2\varepsilon-\lambda\geq0. \end{eqnarray*}$

从而得出 $ \limsup_{k\rightarrow\infty}\Psi_k\geq0 $, 即 (b) 成立.

注意, 在这个例子中, 当 $ x^k $ 满足 $ x^k_1+x^k_2=\frac{\pi}{2} $ 时, $ P_{\bar{S}}(x^k) $ 是多值的, 即 $ P_{\bar{S}}(x^k)=\{(0, x^k_2),(x_1^k,\frac{\pi}{2})\} $. 由上面的证明可知, 对 $ \forall z^k\in P_{\bar{S}}(x^k) $, 条件 (b) 都成立.

类似的例子还有很多, 比如下面的例子.

例 2.4 最优化问题 (OP)

$\begin{equation*} \min_{x\in S}f(x)=x_1\log (1+x_2)+\frac{1}{2}(x_1-1)^2(x_2-1)^2, \end{equation*}$

其中

$\begin{equation*} S=\{x\in \mathbb{R}^2\mid x_1\geq0,x_2\geq0,x_1^2+x_2^2\leq1\}, \bar{S}=\{(1,0),(0,1)\}. \end{equation*}$

例 2.5 变分不等式问题 (VIP)

$\begin{equation*} F(x)=(-x_1{\rm e}^{1-x_2^2},x_2(x_2^2-1)), \end{equation*}$

其中

$\begin{equation*} S=\{x\in \mathbb{R}^2\mid -1\leq x_1\leq 1,-1\leq x_2\leq1\}, \end{equation*}$
$\begin{equation*} \bar{S}=\{((-1)^i,(-1)^j)\mid i=1,2;\ j=1,2\}. \end{equation*}$

3 有限终止性

在这一节中, 在解集是广义弱尖锐性的条件下, 分别给出了最优化问题 (OP) 与变分不等式问题 (VIP) 的可行解序列有限终止于解集的必要与充分条件. 在这两个结果的推论中分别包含了相关文献中在解集是弱尖锐的或强非退化条件下的相应结果. 最后, 给出了一个最优化问题的例子, 来验证结论的正确性.

3.1 最优化问题情况

定理 3.1 设在最优化问题 (OP) 里, $ \bar{S}\subset S $ 是一闭集, 对 $ \forall x\in S $, $ \partial f(x)\neq\emptyset $, 如果 $ \bar{S} $ 关于 $ \{x^{k}\}\subset S $ 是广义弱尖锐集. 则下面结论 (1) 与 (2) 成立

(1) 设 (1.1) 式成立. 如果 $ \{x^k\} $ 有限终止于 $ \bar{S} $, 则有

$\begin{equation} 0\in\liminf_{k\rightarrow\infty}P_{T_{S}(x^{k})}(-\partial f(x^{k})); \end{equation}$

(2) 如果 (3.1) 式成立, 则 $ \{x^k\} $ 有限终止于 $ \bar{S} $.

证 (1) 如果 $ x^k\in \bar{S} $, 则根据假设 (1.1), 可知 $ \exists u^k\in\partial f(x^k) $, 使得 $ -u^k\in N_S(x^k) $. 因此据 $ S $ 的凸性与投影分解, 即知 $ P_{T_S(x^k)}(-u^k)=0 $, 即 (3.1) 式成立.

(2) 设 (3.1) 式成立.下面证明 $ \{x^{k}\} $ 有限终止于 $ \bar{S} $, 否则 $ K=\{k\mid x^{k}\notin\bar{S}\} $ 将是一个无穷序列. 这样据 $ \bar{S} $ 关于 $ \{x^{k}\}\subset S $ 的广义弱尖锐性, 存在映射 $ H:\bar{S}\rightarrow 2^{R^{n}} $与常数 $ \alpha>0 $ 使得

$\begin{equation} \alpha B\subset H(z)+[T_{S}(z)\cap\hat{N}_{\bar{S}}(z)]^{\circ}, \forall z\in\bar{S}, \end{equation}$

并且对 $ \forall u^{k}\in\partial f(x^{k}) $, $ \forall z^k\in P_{\bar{S}}(x^k) $ 与 $ v^{k}\in H(z^{k}) $, 有

$\begin{equation} \limsup_{k\in K, k\rightarrow\infty}\Psi_k=\frac{1}{\|x^{k}-z^{k}\|}\langle u^{k}-v^{k}, x^{k}-z^{k}\rangle\geq 0. \end{equation}$

因为 $ z^{k}\in P_{\bar{S}}(x^{k}) $, 所以对 $ \forall z\in\bar{S} $ 有 $ \|z^{k}-x^{k}\|^{2}\leq \|z-x^{k}\|^{2} $. 由此即得

$\begin{equation*} \langle x^{k}-z^{k}, z-z^{k}\rangle\leq \frac{1}{2}\|z-z^{k}\|^{2}= \circ(\|z-z^{k}\|). \end{equation*}$

因此, 据 $ \hat{N}_{\bar{S}}(\cdot) $ 的定义, 有

$\begin{equation} x^{k}-z^{k}\in\hat{N}_{\bar{S}}(z^{k}). \end{equation}$

再据 $ S $ 的凸性可知

$\begin{equation} x^{k}-z^{k}\in T_{S}(z^{k}), z^{k}-x^{k}\in T_{S}(x^{k}), \end{equation}$

由 (3.4) 和 (3.5) 式, 即得

$\begin{equation} x^{k}-z^{k}\in T_{S}(z^{k})\cap\hat{N}_{\bar{S}}(z^{k}). \end{equation}$

设 $ g_{k}=\frac{x^{k}-z^{k}}{\|x^{k}-z^{k}\|}(k\in K) $. 据 (3.2) 式可知存在 $ \bar{v}^{k}\in H(z^{k}) $, $ \bar{\xi}^k\in[T_{S}(z^{k})\cap\hat{N}_{\bar{S}}(z^{k})]^{\circ} $, 使得

$\begin{equation} \alpha g_{k}=\bar{v}^{k}+\bar{\xi}^{k}. \end{equation}$

据 (3.6) 和 (3.7) 式, 对 $ \forall k\in K $, 有

$\begin{equation} \alpha=\langle\bar{v}^{k},g_{k}\rangle+\langle\bar{\xi}^{k},g_{k}\rangle \leq \langle\bar{v}^{k},g_{k}\rangle. \end{equation}$

另一方面, 由 (3.1) 式可知

$\begin{equation*} 0\in\liminf_{k\in K,k\rightarrow\infty}P_{T_{S}(x^{k})}(-\partial f(x^{k}). \end{equation*}$

因此, 存在 $ \bar{u}^{k}\in\partial f(x^{k}) $ 使得

$\begin{equation} \lim_{k\in K, k\rightarrow\infty}P_{T_{S}(x^{k})}(-\bar{u}^{k})=0. \end{equation}$

这样由 (3.8) 和 (3.5) 式及投影梯度的性质 (见文献 [38,引理 3.1]), 对 $ \forall k\in K $ 有

$\begin{eqnarray*} \alpha&\leq &\langle\bar{v}^{k},g_{k}\rangle\\ &=&\langle-\bar{u}^{k},-g_{k}\rangle-\langle\bar{u}^{k}-\bar{v}^{k},g_{k}\rangle\\ &\leq &\max\{\langle-\bar{u}^{k},d\rangle\mid d\in T_{S}(x^{k}),\|d\|\leq 1\}-\langle\bar{u}^{k}-\bar{v}^{k},g_{k}\rangle\\ &=&\|P_{T_{S}(x^{k})}(-\bar{u}^{k})\|-\langle\bar{u}^{k}-\bar{v}^{k},g_{k}\rangle. \end{eqnarray*}$

根据 (3.3) 和 (3.9) 式, 由上式即得

$\begin{eqnarray*} \alpha&\leq &\liminf_{k\in K,k\rightarrow\infty}\{\|P_{T_{S}(x^{k})}(-\bar{u}^{k})\|-\langle\bar{u}^{k}-\bar{v}^{k},g_{k}\rangle\}\\ &=&-\limsup_{k\in K,k\rightarrow\infty}\langle\bar{u}^{k}-\bar{v}^{k},g_{k}\rangle\leq 0, \end{eqnarray*}$

由此引出矛盾. 证毕.

若 $ f(\cdot) $ 在 $ \mathbb{R}^n $ 上是局部 Lipschitz 的, 则 $ \partial f(x)\neq \emptyset $ 且 (1.1) 式成立. 因此由定理 3.1 即得下面推论.

推论 3.1 设在规划 (OP) 中, $ f(\cdot) $ 在 $ \mathbb{R}^n $ 上是局部 Lipschitz 的, $ \bar{S} $ 关于 $ \{x^k\}\subset S $ 是广义弱尖锐性的. 则 $ \{x^k\} $ 有限终止于 $ \bar{S} $, 当且仅当 (3.1) 式成立.

由命题 2.1 与推论 3.1 即得

推论 3.2 设在凸规划 (OP) 中, $ \bar{S}\subset S $ 是弱尖锐集, 则 $ \{x^k\}\subset S $ 有限终止于 $ \bar{S} $ 当且仅当 (3.1) 式成立.

注 3.1 推论 3.2 即是文献 [35,定理 3.1]. 后者推广并改进文献 [33,定理 4.7].

由命题 2.4 与定理 3.1 即得

推论 3.3 设在光滑最优化问题 (OP) 中, $ \bar{S}\subset S $ 与 $ \{x^k\}\subset S $ 满足 (2.8) 式, 且 $ \bar{S} $ 是弱尖锐的. 则 $ \{x^k\}\subset S $ 有限终止于 $ \bar{S} $ 当且仅当

$\begin{equation} \lim_{k\rightarrow\infty}P_{T_S(x^k)}(-\nabla f(x^k))=0. \end{equation}$

由命题 2.5 与定理 3.1 即得

推论 3.4 设在光滑规划 (OP) 中, $ \{x^k\}\subset S $. 如果 $ \{\nabla f(x^k)\} $ 有界且它的任一聚点 $ \bar{p} $ 满足 $ -\bar{p}\in {\rm int} G $, 则 $ \{x^k\} $ 有限终止于 $ \bar{S} $ 当且仅当 (eq3.10) 式成立.

由命题 2.6 与定理 3.1 即得

推论 3.5 设在光滑最优化问题 (OP) 中, $ \{x^k\}\subset S $ 有界且它的任一聚点是强非退化的, 则 $ \{x^k\} $ 有限终止于 $ \bar{S} $ 当且仅当 (3.10) 式成立.

注 3.2 推论 3.5 即是文献 [21,定理 5.3]. 后者是文献 [14,推论 3.5] 的推广.

3.2 变分不等式的情况

现在讨论变分不等式问题 (VIP) 的情况.首先注意在这种情况下, 其解集 $ \bar{S} $ 与稳定点 $ \hat{S} $ 是一致的, 即 (1.1) 式中等式成立. 这样仿照定理 3.1 的证明可得出

定理 3.2 设在变分不等式问题 (VIP) 中, $ \bar{S}\subset S $ 是一闭集, $ \bar{S} $ 关于 $ \{x^{k}\}\subset S $ 是广义弱尖锐集. 则 $ \{x^k\} $ 有限终止于 $ \bar{S} $ 当且仅当

$\begin{equation} \lim_{k\rightarrow\infty}P_{T_S(x^k)}(-F(x^k))=0. \end{equation}$

由命题 2.8 与定理 3.2 即得

推论 3.6 设在变分不等式问题 (VIP) 中, $ \bar{S}\subset S $ 是一闭集, $ \{x^{k}\}\subset S $. 如果 $ \{F(x^k)\} $ 有界且它的任一聚点 $ \bar{p} $ 满足 $ -\bar{p}\in {\rm int}G $, 则 $ \{x^k\} $ 有限终止于 $ \bar{S} $ 当且仅当 (3.11) 式成立.

注 3.3 推论 3.6 是文献 [35,定理 3.3] 的推广与改进. 因为它将文献 [35,定理 3.3] 中的锥 $ [T_S(x)\cap N_{\bar{S}}(x)]^{\circ} $ 用包含它的锥 $ [T_S(x)\cap\hat{N}_{\bar{S}}(x)]^{\circ} $ 所代替, 同时将 $ F(\cdot) $ 的连续性条件减弱为 $ \bar{S} $ 是闭集. 注意文献 [35,定理 3.3] 是文献 [12,定理 3.1] 的推广与改进.

由命题 2.9 与定理 3.2 即得

推论 3.7 设在变分不等式问题 (VIP) 中, $ F(\cdot) $ 在 $ S $ 上连续. 如果 $ \{x^k\}\subset S $ 有界且它的任一聚点是强非退化的, 则 $ \{x^k\} $ 有限终止于 $ \bar{S} $ 当且仅当 (3.11) 式成立.

3.3 实例

下面, 就最优化问题情况, 给出一个例子来验证结论的正确性.

例 3.1 最优化问题 (OP)

$\begin{equation*} \min_{x\in S} f(x)=\log (1+x_1)+\frac{1}{2}(x_2)^2, \end{equation*}$

其中

$\begin{equation*} S=\{x\in \mathbb{R}^2\mid 0\leq x_1\leq1, -1\leq x_2\leq1\}, \bar{S}=\{(0,0)\}. \end{equation*}$

这是一个光滑的非凸最优化问题, 由 $ f $ 在 $ \mathbb{R}^{n} $ 上的局部 Lipschitz 连续性可知 (1.1) 成立. 同时, $ \nabla F(x_1,x_2)=(\frac{1}{1+x_1},x_2) $, $ \nabla f(0,0)=(1,0) $, $ T_S(0,0)=\{\xi\in \mathbb{R}^2\mid\xi_1\geq0,\xi_2\in(-\infty,+\infty)\} $, $ {\hat{N}}_{\bar{S}}(0,0)=N_{\bar{S}}(0,0)=\mathbb{R}^2 $. 由上述可知

$\begin{equation} [T_S(0,0)\cap {\hat{N}}_{\bar{S}}(0,0)]^\circ=N_{S}(0,0)=\{\xi\in \mathbb{R}^2\mid\xi_1\leq0,\xi_2=0\}, \end{equation}$

由此可知, $ \bar S $ 不是一个弱尖锐集, 易验证 $ \bar S $ 对任意 $ \{x_k\}\subset S $ 是一个广义弱尖锐集.

如果 $ x^k\in \bar{S} $, 由 (1.1) 式可知, 存在 $ u^k\in f(x^k), $ 使得 $ -u^k\in N_S(x^k). $ 因此, 根据 $ S $ 的凸性与投影分解定理知 $ P_{T_S(x^k)}(-u^k)=0. $ 即 (3.1) 式成立.

如果 $ \{x^k\}\subset S $ 不是有限终止于 $ \bar{S} $, 则 $ K=\{k\mid x^k\notin\bar{S}\} $ 是一个无穷序列. 由 $ S $ 关于 $ \{x_k\}\subset S $ 的弱尖锐性, 一定存在映射 $ H: \bar{S}\rightarrow 2^{\mathbb{R}^2} $ 与常数 $ \alpha>0, $ 使得

$\begin{equation} \alpha B\subset H(z)+[T_S(z)\cap {\hat{N}}_{\bar{S}}(z)]^\circ, \forall z\in \bar{S}. \end{equation}$

由于此例中 $ \bar{S}=\{0\} $, 再由 (3.12) 式知 (3.13) 式不成立. 因此, $ \{x^k\}\subset S $ 有限终止于 $ \bar{S} $. 例 3.1 验证了定理 3.1 的正确性.

最后值得提出的是, 解集的弱尖锐性或强非退化性是许多最优化算法具有有限终止性的充分条件[9,12,14,20,22]. 在这些算法产生的可行解序列中, 要么 (3.1) 或 (3.10) 式成立[9,14,20], 要么 (3.11) 式成立[12,22]. 因此由上述定理与第 2 节中的命题可知,解集的广义弱尖锐性为这些算法的有限终止性提供了比弱尖锐性或强非退化性更弱的充分条件.

参考文献

Rockafellar R T, Wets R J B. Variational Analysis. New York: Springer Science & Business Media, 2009

[本文引用: 5]

Rockafellar R T.

Monotone operators and the proximal point algorithm

SIAM Journal on Control and Optimization, 1976, 14(5): 877-898

[本文引用: 2]

Polyak B T. Introduction to Optimization. New York: Optimization Software, 1987: 1-32

[本文引用: 1]

Ferris M C. Weak Sharp Minima and Penalty Functions in Mathematical Programming. Cambridge: University of Cambridge, 1988

[本文引用: 2]

Ansari Q H, Babu F, Yao J C.

Regularization of proximal point algorithms in Hadamard manifolds

Journal of Fixed Point Theory and Applications, 2019, 21: 1-23

[本文引用: 1]

Dinis B, Pinto P.

Metastability of the proximal point algorithm with multi-parameters

Portugaliae Mathematica, 2020, 77(3): 345-381

[本文引用: 1]

Ferris M C.

Finite termination of the proximal point algorithm

Mathematical Programming, 1991, 50: 359-366

[本文引用: 1]

Kim J L, Toulis P, Kyrillidis A.

Convergence and stability of the stochastic proximal point algorithm with momentum

Proc Machine Learn Res, 2022, 168: 1034-1047

[本文引用: 1]

Matsushita S, Xu L.

Finite termination of the proximal point algorithm in Banach spaces

Journal of Mathematical Analysis and Applications, 2012, 387(2): 765-769

[本文引用: 3]

Mokhtari A, Ozdaglar A, Pattathil S.

A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach

Proc Machine Learn Res, 2020, 108: 1497-1507

[本文引用: 1]

Nemirovski A.

Prox-method with rate of convergence $ \mathcal{O}(1/t) $ for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems

SIAM Journal on Optimization, 2004, 15(1): 229-251

[本文引用: 1]

Xiu N, Zhang J.

On finite convergence of proximal point algorithms for variational inequalities

Journal of Mathematical Analysis and Applications, 2005, 312(1): 148-158

[本文引用: 11]

Al-Khayyal F, Kyparisis J.

Finite convergence of algorithms for nonlinear programs and variational inequalities

Journal of Optimization Theory and Applications, 1991, 70(2): 319-332

[本文引用: 1]

Burke J V, Moré J J.

On the identification of active constraints

SIAM Journal on Numerical Analysis, 1988, 25(5): 1197-1211

[本文引用: 9]

Carmona R, Laurière M.

Convergence analysis of machine learning algorithms for the numerical solution of mean field control and games: II—the finite horizon case

The Annals of Applied Probability, 2022, 32(6): 4065-4105

[本文引用: 1]

Fischer A, Kanzow C.

On finite termination of an iterative method for linear complementarity problems

Mathematical Programming, 1996, 74: 279-292

[本文引用: 1]

Griewank A, Walther A.

Finite convergence of an active signature method to local minima of piecewise linear functions

Optimization Methods and Software, 2019, 34(5): 1035-1055

[本文引用: 1]

Nguyen L V, Qin X L.

Weak sharpness and finite convergence for mixed variational inequalities

Journal of Applied & Numerical Optimization, 2019, 1(1): 77-90

[本文引用: 1]

Solodov M V, Tseng P.

Some methods based on the D-gap function for solving monotone variational inequalities

Computational Optimization and Applications, 2000, 17: 255-277

[本文引用: 1]

Wang C, Liu Q, Yang X.

Convergence properties of nonmonotone spectral projected gradient methods

Journal of Computational and Applied Mathematics, 2005, 182(1): 51-66

[本文引用: 4]

Wang C, Zhao W, Zhou J, et al.

Global convergence and finite termination of a class of smooth penalty function algorithms

Optimization Methods and Software, 2013, 28(1): 1-25

[本文引用: 4]

Xiu N, Zhang J.

Some recent advances in projection-type methods for variational inequalities

Journal of Computational and Applied Mathematics, 2003, 152(1/2): 559-585

[本文引用: 4]

Zhao Z, Liu Z.

Finite-time convergence disturbance rejection control for a flexible Timoshenko manipulator

IEEE/CAA Journal of Automatica Sinica, 2020, 8(1): 157-168

[本文引用: 1]

Burke J V, Deng S.

Weak sharp minima revisited, part II: Application to linear regularity and error bounds

Mathematical Programming, 2005, 104: 235-261

[本文引用: 1]

Burke J V, Deng S.

Weak sharp minima revisited, Part III: Error bounds for differentiable convex inclusions

Mathematical Programming, 2009, 116(1/2): 37-56

[本文引用: 1]

Bonnans J F, Shapiro A. Perturbation Analysis of Optimization Problems. New York: Springer Science & Business Media, 2013

[本文引用: 1]

Fong R, Patrick M, Vedaldi A. Understanding deep networks via extremal perturbations and smooth masks//Proceedings of the IEEE/CVF International Conference on Computer Vision. 2019: 2950-2958

[本文引用: 1]

Jourani A.

Hoffman's error bound, local controllability, and sensitivity analysis

SIAM Journal on Control and Optimization, 2000, 38(3): 947-970

[本文引用: 1]

Tirer T, Huang H, Niles-Weed J. Perturbation analysis of neural collapse//International Conference on Machine Learning. 2023: 34301-34329

[本文引用: 1]

Wang C Y, Zhang J Z, Zhao W L.

Two error bounds for constrained optimization problems and their applications

Applied Mathematics and Optimization, 2008, 57: 307-328

[本文引用: 4]

Xu K, Shi Z, Zhang H, et al.

Automatic perturbation analysis for scalable certified robustness and beyond

Advances in Neural Information Processing Systems, 2020, 33: 1129-1141

[本文引用: 1]

Zheng X Y, Yang X Q.

Weak sharp minima for semi-infinite optimization problems with applications

SIAM Journal on Optimization, 2007, 18(2): 573-588

[本文引用: 1]

Burke J V, Ferris M C.

Weak sharp minima in mathematical programming

SIAM Journal on Control and Optimization, 1993, 31(5): 1340-1359

[本文引用: 10]

Marcotte P, Zhu D.

Weak sharp solutions of variational inequalities

SIAM Journal on Optimization, 1998, 9(1): 179-189

[本文引用: 5]

Zhou J, Wang C.

New characterizations of weak sharp minima

Optimization Letters, 2012, 6: 1773-1785

[本文引用: 9]

Burke J V, Ferris M C.

Characterization of solution sets of convex programs

Operations Research Letters, 1991, 10(1): 57-60

[本文引用: 2]

Rockafellar R T. Convex Analysis. Princeton: Princeton Univ Press, 1970

[本文引用: 2]

Calamai P H, Moré J J.

Projected gradient methods for linearly constrained problems

Mathematical Programming, 1987, 39(1): 93-116

[本文引用: 1]

/

〈 〉

版权所有 © 《数学物理学报》杂志社
地址： 武汉市71010号信箱(430071)　电话: 027-87199206(中文版)　027-87199087(英文版)
E-mail: actams@apm.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发