存零约束优化问题的目标罚函数法

Objective Penalty Function Method for Mathematical Program with Switching Constraints

摘要: 存零约束优化问题是一类特殊的约束优化问题。若x¯是该问题的最优解，由于存零约束，导致通常的约束规范在x¯处不成立，因此有些算法不能直接应用于求解存零约束优化问题。本文在求解传统非线性规划的目标罚函数方法的基础上，提出了一种求解存零约束优化问题的目标罚函数方法，在一定的条件下证明了目标罚函数的局部最优解是原问题的局部最优解，以及目标罚函数算法产生的迭代点列的极限点是原问题的弱稳定点。数值算例表明，本文所提出的目标罚函数方法是有效的。

Abstract: The mathematical program with switching constraints is a special type of constrained optimization problem. Ifx¯is the optimal solution of the problem, due to the switching constraints, the usual constraint specification does not hold atx¯, so some algorithms cannot be directly applied to solve the mathematical program with switching constraints. On the basis of solving the objective penalty function method for traditional nonlinear programming, this article proposes an objective penalty function method for solving mathematical program with switching constraints. Under certain conditions, it is proved that the local optimal solution of the objective penalty function is the local optimal solution of the original problem, and the limit point of the iterative point sequence generated by the objective penalty function algorithm is the weakly stationary point of the original problem. Numerical examples show that the objective penalty function method proposed in this paper is effective.

1. 引言

考虑如下存零约束优化问题

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{.}{g}_i\left(x\right)\le 0,i=1,\cdots ,m,\\ h_j\left(x\right)=0,j=1,\cdots ,p,\\ G_s\left(x\right)H_s\left(x\right)=0,s=1,\cdots ,l,\end{array}$ (1.1)

其中$f,h_1,\cdots ,h_p,g_1,\cdots ,g_m,G_1,\cdots ,G_l,H_1,\cdots ,H_l:R^n\to R$ 都是连续可微的。$f\left(x\right)$ 为目标函数，

$g_i\left(x\right)\le 0,i=1,\cdots ,m,h_j\left(x\right)=0,j=1,\cdots ,p,$

称为一般约束条件，

$G_s\left(x\right)H_s\left(x\right)=0,s=1,\cdots ,l,$ (1.2)

称为存零约束条件。记问题(1.1)的可行域为

$X:=\{x\in R^n|g_i\left(x\right)\le 0,i=1,\cdots ,m;h_j(x)=0,j=1,\cdots ,p;G_s{H}_s\left(x\right)=0,s=1,\cdots ,l\},$

我们称这样的问题(1.1)为存零约束优化问题(Mathematical Program with Switching Constraints)，简称MPSC。

2019年，Mehlitz [1]首次引入MPSC，该问题与互补约束优化问题[2] [3] (简称MPCC)、消失约束优化问题[4] [5] (简称MPVC)、析取约束优化问题(简称MPDC) [6] [7]等密切相关。MPSC具有特殊结构，它不满足一些常见的约束规范，故需要建立适用于MPSC的稳定点概念和约束规范。因此，Mehlitz [1]引入一些适用于MPSC的稳定点概念(例如弱稳定点、Mordukhovich-稳定点(简称M-稳定点)和强稳定点等)，并给出一些MPSC的约束规范(例如MPSC Mangasarian-Fromovitz约束规范(简称MPSC-MFCQ)、MPSC线性独立约束规范(简称MPSC-LICQ)等)。

Liang等人[6]将MPSC表述为MPDC，结合近年来MPDC的约束规范和最优性条件，将其应用于MPSC，并且推导出MPSC的局部误差界和精确惩罚结果的充分条件。Mehlitz [7]在MPDC的线性无关约束规范成立的情况下，推导MPDC的一阶、二阶最优性条件，并且将其应用于MPSC，得到MPSC的二阶最优性条件。Li等人[8]证明了在MPSC Guignard约束规范(简称MPSC-GCQ)成立时，MPSC的局部极小点是Bouligand-稳定点(简称B-稳定点)。并且Li等人[8]扩展非线性规划中的一些约束规范应用于MPSC。这些约束规范都严格弱于MPSC-MFCQ和MPSC-LICQ，当约束规范成立时，MPSC的局部极小点是M-稳定点。

存零约束条件的存在使得非线性规划的算法不能直接应用于求解MPSC. Kanzow等人[9]引入松弛因子，将几种常用的MPCC松弛方法应用于求解MPSC。Kanzow等人[9]指出，虽然Scholtes的方法、Steffensen和Ulbrich的松弛方法在一定条件下产生的迭代点列收敛到MPSC的弱稳定点，但在合理的假设条件下，Kanzow和Schwartz的松弛方法产生的迭代点列能够收敛到MPSC的M-稳定点。张婷婷等人[10]将存零约束作为罚项加入到目标函数中，提出部分罚函数方法，证明了在MPSC-LICQ成立的情况下，部分罚函数问题的迭代点列的聚点是MPSC的弱稳定点。罗美玲等人[11]针对MPSC，提出Wolfe型对偶模型，在凸性和严格凸性假设下，给出MPSC的Wolfe对偶问题的弱、强、逆、限制逆和严格逆对偶结果。Jinman等人[12]研究含非Lipschitz项的存零约束优化问题，给出了求解非Lipschitz项MPSC的一种近似方法，利用局部Lipschitz函数来近似非Lipschitz项，并证明了该近似方法生成的迭代点列的聚点在MPSC-MFCQ约束规范成立时是MPSC的弱稳定点，在二阶必要条件和MPSC-MFCQ约束规范成立时是MPSC的强稳定点。

本文，我们将罚参数与目标函数、约束函数结合，基于互补约束优化目标罚函数方法，提出存零约束优化问题的目标罚函数方法。本文将在第2节介绍基本概念。第3节讨论原问题与罚函数问题在最优解方面的关系，同时给出目标罚函数算法，分析算法迭代点列的收敛性。第4节给出算法的数值实验结果。最后，第5节对全文进行总结。

2. 基本概念及目标罚函数方法

首先，为了便于符号标注，我们定义了在MPSC任意一个可行点$\overline{x}\in R^n$ 处的指标集：

$\begin{array}{l}{I}^h\left(\overline{x}\right):=\left\{1,2,\cdots ,p\right\},\\ I^g\left(\overline{x}\right):=\left\{i\in \left\{1,2,\cdots ,m\right\}|g_i\left(\overline{x}\right)=0\right\},\\ I^G\left(\overline{x}\right):=\left\{s\in \left\{1,2,\cdots ,l\right\}|G_s\left(\overline{x}\right)=0\wedge H_s\left(\overline{x}\right)\ne 0\right\},\\ I^H\left(\overline{x}\right):=\left\{s\in \left\{1,2,\cdots ,l\right\}|G_s\left(\overline{x}\right)\ne 0\wedge H_s\left(\overline{x}\right)=0\right\},\\ I^{GH}\left(\overline{x}\right):=\left\{s\in \left\{1,2,\cdots ,l\right\}|G_s\left(\overline{x}\right)=0\wedge H_s\left(\overline{x}\right)=0\right\},\end{array}$

其中，$I^G\left(\overline{x}\right)$ ，$I^H\left(\overline{x}\right)$ ，$I^{GH}\left(\overline{x}\right)$ 是$\left\{1,2,\cdots ,l\right\}$ 的互不相交的分区。

接下来，我们给出关于MPSC的弱稳定点概念。

定义2.1 [1]设$\overline{x}\in R^n$ 是问题(1.1)的一个可行点，如果存在乘子$\left(\lambda ,\rho ,\mu ,\nu \right)\in R^m\times R^p\times R^l\times R^l$ 使得

$\begin{array}{c}0=\nabla f\left(\overline{x}\right)+{\displaystyle \sum _{i\in I^g\left(\overline{x}\right)}{\lambda }_i\nabla g_i\left(\overline{x}\right)}+{\displaystyle \sum _{j\in I^h\left(\overline{x}\right)}{\rho }_j\nabla h_j\left(\overline{x}\right)}+{\displaystyle \sum _{s=1}^l\left({\mu }_s\nabla G_s\left(\overline{x}\right)+{\nu }_s\nabla H_s\left(\overline{x}\right)\right)},\\ \forall i\in I^g\left(\overline{x}\right):{\lambda }_i\ge 0,\forall s\in I^H\left(\overline{x}\right):{\mu }_s=0,\forall s\in I^G\left(\overline{x}\right):{\nu }_s=0,\end{array}$(2.1)

成立，则$\overline{x}$ 是弱稳定点。

由于MPSC问题中的存零约束，使得通常的约束规范不满足。本文考虑将罚参数放入目标函数，先定义函数

$P\left(x\right)={\displaystyle \sum _{j=1}^p{h}_j^2\left(x\right)}+{\displaystyle \sum _{i=1}^m\max {\left\{g_i\left(x\right),0\right\}}^2}+{\displaystyle \sum _{s=1}^l{\left(G_s\left(x\right)H_s\left(x\right)\right)}^2,}$ (2.2)

$\forall x\in R^n$ ，有$P\left(x\right)\ge 0$ 。当$\forall \overline{x}\in X$ ，有$P\left(\overline{x}\right)=0$ 。

同时构造目标罚函数

$F\left(x,M\right)=\max {\left\{f\left(x\right)-M,0\right\}}^2+M^{2}P\left(x\right),$

其中M是罚参数，并且$M<0$ 。$\forall x\in R^n$ ，有$F\left(x,M\right)\ge 0$ 。

由此构造如下无约束优化罚问题

$\begin{array}{cc}\min & F\left(x,M\right)\\ \text{s}\text{.t}.& x\in R^n.\end{array}$ (2.3)

本文接下来讨论存零约束优化问题与无约束优化罚问题在最优解方面的关系，同时给出该问题的算法框架，分析目标罚函数方法最优解点列的收敛性。

3. 算法及主要理论结果

我们先考虑问题(1.1)与问题(2.3)之间最优解方面的关系。

定理3.1 ${\widehat{x}}_M$ 是问题(2.3)的局部最优解，M是一个常数，$M<f\left({\widehat{x}}_M\right)$ 。如果点${\widehat{x}}_M$ 是问题(1.1)的可行点，则${\widehat{x}}_M$ 是问题(1.1)的局部最优解。

证明：如果${\widehat{x}}_M$ 是问题(1.1)的可行点，我们有${\widehat{x}}_M\in X$ ，$P\left({\widehat{x}}_M\right)=0$ ，

$F\left({\widehat{x}}_M,M\right)=\max {\left\{f\left({\widehat{x}}_M\right)-M,0\right\}}^2,$ (3.1)

由${\widehat{x}}_M$ 是问题(2.3)的局部最优解，则对任意的$x\in R^n$ ，

$F\left({\widehat{x}}_M,M\right)\le F\left(x,M\right),$ (3.2)

此外，存在某常数$\delta >0$ ，$x^{\prime }\in B\left({\widehat{x}}_M,\delta \right)=\left\{x\in R^n|{\Vert x-{\widehat{x}}_M\Vert }_2\le \delta \right\}$ ，由(3.1)，(3.2)及$M<f\left({\widehat{x}}_M\right)$ ，可得$\forall x^{\prime }\in B\left({\widehat{x}}_M\right)\cap X$ ，

$0<\max {\left\{f\left({\widehat{x}}_M\right)-M,0\right\}}^2=F\left({\widehat{x}}_M,M\right)\le F\left(x^{\prime },M\right)=\max {\left\{f\left(x^{\prime }\right)-M,0\right\}}^2,$

因此，我们有$f\left({\widehat{x}}_M\right)-M\le f\left(x^{\prime }\right)-M$ 。

由此可得$\forall x^{\prime }\in B\left({\widehat{x}}_M\right)\cap X$ ，$f\left({\widehat{x}}_M\right)\le f\left(x^{\prime }\right)$ 。${\widehat{x}}_M$ 是问题(1.1)的局部最优解。

基于上面的讨论，我们给出一种求解问题(1.1)的局部最优解的算法，我们称之为MPSC的目标罚函数算法，其步骤如下：

算法3.1

步1 任选$x_0\in R^n$ 和$M_1<0$ ，$N>1$ ，$k=1$ 。

步2 以$x_{k-1}$ 为初始点，求解

$x_k\in \arg {\min }_{x\in R^n}\left\{F\left(x,M_k\right)\right\}$ 。

步3 如果$x_k$ 是问题(1.1)的可行点，且$M_k<f\left(x_k\right)$ ，则停止。

步4 令$M_{k+1}:=N{M}_k$ ，$k:=k+1$ ，转步2。

注1 本算法中步2出现的最优解是指局部最优解。

注2 为了使算法可行，假设罚函数$F\left(x,M_k\right)$ 有局部最优解。

关于算法3.1的收敛性，我们有如下结果。

定理3.2 假设f，$g_i\left(i\in \left\{1,2,\cdots ,m\right\}\right)$ ，$h_j\left(j\in \left\{1,2,\cdots ,p\right\}\right)$ ，$G_s,H_s\left(s\in \left\{1,2,\cdots \right\}\right)$ 在$R^n$ 上连续，且$\underset{\Vert x\Vert \to \infty }{\lim }f\left(x\right)=+\infty$ 。$\left\{x_k\right\}$ 是算法3.1得到的点列。

1) 如果$\left\{x_k\right\}\left(k=1,2,\cdots ,\overline{k}\right)$ 是有限点列。即算法3.1在第$\overline{k}$ 次迭代终止，则$x_{\overline{k}}$ 是问题(1.1)的最优解。

2) 如果$\left\{x_k\right\}$ 是无限点列，$\left\{f\left(x_k\right)\right\}$ 是有界的，并且满足

$\underset{k\to +\infty }{\lim }\frac{F\left(x_k,M_k\right)}{M_k^2}=0$ ，

则$\left\{x_k\right\}$ 是有界的，$\left\{x_k\right\}$ 的任意极限点$\overline{x}$ 是问题(1.1)的可行点且是问题(1.1)的弱稳定点。

证 1) 如果算法3.1在第$\overline{k}$ 次迭代终止，则有$x_{\overline{k}}$ 是问题(1.1)的可行点，且$M_{\overline{k}}<f\left(x_{\overline{k}}\right)$ 。由定理3.1，可得$x_{\overline{k}}$ 是问题(1.1)的最优解。

2) 首先，我们注意到$\left\{f\left(x_k\right)\right\}$ 是有界的，又因为$\underset{\Vert x\Vert \to \infty }{\lim }f\left(x\right)=+\infty$ ，有$\left\{x_k\right\}$ 是有界的。不失一般性，假设当$k\to +\infty$ ，$x_k\to \overline{x}$ ，我们有

$\begin{array}{c}\nabla F\left(x_k,M_k\right)=2\max \left\{f\left(x_k\right)-M_k,0\right\}\nabla f\left(x_k\right)+M_k^2{\displaystyle \sum _{i=1}^{m}2\max \left\{g_i\left(x_k\right),0\right\}\nabla g_i\left(x_k\right)}\\ +M_k^2{\displaystyle \sum _{s=1}^{l}2G_s\left(x_k\right)H_s\left(x_k\right)\left(G_s\left(x_k\right)\nabla H_s\left(x_k\right)+H_s\left(x_k\right)\nabla G_s\left(x_k\right)\right)}\\ +M_k^2{\displaystyle \sum _{j=1}^{q}2h_j\left(x_k\right)\nabla h_j}\left(x_k\right),\end{array}$ (3.3)

展开，

$\begin{array}{c}\nabla F\left(x_k,M_k\right)=2\max \left\{f\left(x_k\right)-M_k,0\right\}\nabla f\left(x_k\right)+M_k^2{\displaystyle \sum _{i=1}^{m}2\max \left\{g_i\left(x_k\right),0\right\}\nabla g_i\left(x_k\right)}\\ +M_k^2{\displaystyle \sum _{j=1}^{q}2\max \left\{h_j\left(x_k\right),0\right\}\nabla h_j\left(x_k\right)}-M_k^2{\displaystyle \sum _{j=1}^{q}2\max \left\{-h_j\left(x_k\right),0\right\}\nabla h_j\left(x_k\right)}\\ +M_k^2{\displaystyle \sum _{s=1}^{l}2H_s^2\left(x_k\right)}\max \left\{G_s\left(x_k\right),0\right\}\nabla G_s\left(x_k\right)\\ -M_k^2{\displaystyle \sum _{s=1}^{l}2H_s^2\left(x_k\right)}\max \left\{-G_s\left(x_k\right),0\right\}\nabla G_s\left(x_k\right)\\ +M_k^2{\displaystyle \sum _{s=1}^{l}2G_s^2\left(x_k\right)}\max \left\{H_s\left(x_k\right),0\right\}\nabla H_s\left(x_k\right)\\ -M_k^2{\displaystyle \sum _{s=1}^{l}2G_s^2\left(x_k\right)}\max \left\{-H_s\left(x_k\right),0\right\}\nabla H_s\left(x_k\right),\end{array}$

其中$k=1,2,\cdots$ 。

$\left\{x_k\right\}$ 是无限点列，因为$M_{k+1}=N{M}_k$ ，且$N>1$ ，$M_k<0$ ，可得$M_k\to -\infty$ 。由于$\left\{f\left(x_k\right)\right\}$ 是有界的，这意味着存在一个常数$k^{\prime }>0$ ，$\forall k>k^{\prime }$ ，我们有$M_k<f\left(x_k\right)$ ，从而

$\begin{array}{c}{\omega }_k=2\max \left\{f\left(x_k\right)-M_k,0\right\}+M_k^2{\displaystyle \sum _{i=1}^{m}2\max \left\{g_i\left(x_k\right),0\right\}}\\ +M_k^2{\displaystyle \sum _{j=1}^{q}2\max \left\{h_j\left(x_k\right),0\right\}}+M_k^2{\displaystyle \sum _{j=1}^{q}2\max \left\{-h_j\left(x_k\right),0\right\}}\\ +M_k^2{\displaystyle \sum _{s=1}^{l}2H_s^2\left(x_k\right)}\max \left\{G_s\left(x_k\right),0\right\}+M_k^2{\displaystyle \sum _{s=1}^{l}2H_s^2\left(x_k\right)}\max \left\{-G_s\left(x_k\right),0\right\}\\ +M_k^2{\displaystyle \sum _{s=1}^{l}2G_s^2\left(x_k\right)}\max \left\{H_s\left(x_k\right),0\right\}+M_k^2{\displaystyle \sum _{s=1}^{l}2G_s^2\left(x_k\right)}\max \left\{-H_s\left(x_k\right),0\right\},\end{array}$

因此，$\forall k>k^{\prime }$ ，${\omega }_k>0$ 。

特别，$\forall k>k^{\prime }$ ，令

$\begin{array}{l}{\alpha }^k=\frac{2\max \left\{f\left(x_k\right)-M_k,0\right\}}{{\omega }_k},\\ {\lambda }_i^k=\frac{2M_k^2}{{\omega }_k}\max \left\{g_i\left(x_k\right),0\right\},i=1,2,\cdots ,m,\\ {\rho }_j^{k_1}=\frac{2M_k^2}{{\omega }_k}\max \left\{h_j\left(x_k\right),0\right\},j=1,2,\cdots ,p,\\ {\rho }_j^{k_2}=\frac{2M_k^2}{{\omega }_k}\max \left\{-h_j\left(x_k\right),0\right\},j=1,2,\cdots ,p,\\ {\mu }_s^{k_1}=\frac{2M_k^2}{{\omega }_k}{H}_s^2\left(x_k\right)\max \left\{G_s\left(x_k\right),0\right\},s=1,2,\cdots ,l,\\ {\mu }_s^{k_2}=\frac{2M_k^2}{{\omega }_k}{H}_s^2\left(x_k\right)\max \left\{-G_s\left(x_k\right),0\right\},s=1,2,\cdots ,l,\\ {\nu }_s^{k_1}=\frac{2M_k^2}{{\omega }_k}{G}_s^2\left(x_k\right)\max \left\{H_s\left(x_k\right),0\right\},s=1,2,\cdots ,l,\\ {\nu }_s^{k_2}=\frac{2M_k^2}{{\omega }_k}{G}_s^2\left(x_k\right)\max \left\{-H_s\left(x_k\right),0\right\},s=1,2,\cdots ,l,\end{array}$

我们有

${\alpha }^k+{\displaystyle \sum _{i=1}^m{\lambda }_i^k}+{\displaystyle \sum _{j=1}^p{\rho }_j^{k_1}}+{\displaystyle \sum _{j=1}^p{\rho }_j^{k_2}}+{\displaystyle \sum _{s=1}^l{\mu }_s^{k_1}}+{\displaystyle \sum _{s=1}^l{\mu }_s^{k_2}}+{\displaystyle \sum _{s=1}^l{\nu }_s^{k_1}}+{\displaystyle \sum _{s=1}^l{\nu }_s^{k_2}}=1,\forall k>k^{\prime },$ (3.4)

${\alpha }^k>0,{\lambda }_i^k,{\rho }_j^{k_1},{\rho }_j^{k_2},{\mu }_s^{k_1},{\mu }_s^{k_2},{\nu }_s^{k_1},{\nu }_s^{k_2}\ge 0,\forall k>k^{\prime },$

显然，当$k\to +\infty$ ，序列$\left\{{\alpha }^k,{\lambda }_i^k,{\rho }_j^{k_1},{\rho }_j^{k_2},{\mu }_s^{k_1},{\mu }_s^{k_2},{\nu }_s^{k_1},{\nu }_s^{k_2}\right\}$ 是收敛的。则当$k\to +\infty$ ，有

$\begin{array}{l}{\alpha }^k\to \alpha >0,{\lambda }_i^k\to {\lambda }_i\ge 0,i=1,2,\cdots ,m,\\ {\rho }_j^{k_1}\to {\rho }_j^1\ge 0,{\rho }_j^{k_2}\to {\rho }_j^2\ge 0,j=1,2,\cdots ,p,\\ {\mu }_s^{k_1}\to {\mu }_s^1\ge 0,{\mu }_s^{k_2}\to {\mu }_s^2\ge 0,s=1,2,\cdots ,l,\\ {\nu }_s^{k_1}\to {\nu }_s^1\ge 0,{\nu }_s^{k_2}\to {\nu }_s^2\ge 0,s=1,2,\cdots ,l,\end{array}$

根据$\underset{k\to +\infty }{\lim }\frac{F\left(x_k,M_k\right)}{M_k^2}=0$ ，且$F\left(x_k,M_k\right)=\max {\left\{f\left(x_k\right)-M_k,0\right\}}^2+M_k^{2}P\left(x_k\right)\ge 0$ ，则当$k\to +\infty$ ，$x_k\to \overline{x}$ ，有$P\left(\overline{x}\right)=0$ 。因此，点$\overline{x}$ 是问题(1.1)的可行点。

考虑$\forall i\notin I^g\left(\overline{x}\right)$ ，有$g_i\left(\overline{x}\right)<0$ 。由于

${\lambda }_i^k=\frac{2M_k^2}{{\omega }_k}\max \left\{g_i\left(x_k\right),0\right\},i=1,2,\cdots ,m,$

则当k充分大时，$\forall i\notin I^g\left(\overline{x}\right)$ ，${\lambda }_i^k=0$ 。因此，我们有$\forall i\notin I^g\left(\overline{x}\right)$ ，${\lambda }_i=0$ 。又因为${\lambda }_i^k\to {\lambda }_i\ge 0$ ，$i=1,2,\cdots ,m$ ，则$\forall i\in I^g\left(\overline{x}\right)$ ，${\lambda }_i\ge 0$ 。

当$k\to +\infty$ ，令

$\begin{array}{l}{\rho }_j^k={\rho }_j^{k_1}-{\rho }_j^{k_2}\to {\rho }_j={\rho }_j^1-{\rho }_j^2,j=1,2,\cdots ,p,\\ {\mu }_s^k={\mu }_s^{k_1}-{\mu }_s^{k_2}\to {\mu }_s={\mu }_s^1-{\mu }_s^2,s=1,2,\cdots ,l,\\ {\nu }_s^k={\nu }_s^{k_1}-{\nu }_s^{k_2}\to {\nu }_s={\nu }_s^1-{\nu }_s^2,s=1,2,\cdots ,l,\end{array}$

现在我们考虑证明$\forall s\in I^G\left(\overline{x}\right)$ ，$\underset{k\to \infty }{\lim }{\nu }_s^k$ 存在，有${\nu }_s=\underset{k\to \infty }{\lim }{\nu }_s^k=0$ 。同理当$\forall s\in I^H\left(\overline{x}\right)$ ，$\underset{k\to \infty }{\lim }{\mu }_s^k$ 存在，有${\mu }_s=\underset{k\to \infty }{\lim }{\mu }_s^k=0$ 。

反证法，$\forall s\in I^G\left(\overline{x}\right)$ ，假设$\underset{k\to \infty }{\lim }{\nu }_s^k$ 不存在。即假设存在一个正数$a>0$ 和$\left\{{\nu }_s^k\right\}$ 的子序列(不失一般性，用序列本身代替)，当k充分大时，使得$\left|{\nu }_s^k\right|\ge a$ 。则

$\begin{array}{c}\frac{\left|{\nu }_s^k\right|}{\left|{\mu }_s^k\right|}=\frac{\left|2M_k^2{G}_s^2\left(x_{k+1}\right)\left(\max \left\{H_s\left(x_{k+1}\right),0\right\}-\max \left\{-H_s\left(x_{k+1}\right),0\right\}\right)\right|}{\left|2M_k^2{H}_s^2\left(x_{k+1}\right)\left(\max \left\{G_s\left(x_{k+1}\right),0\right\}-\max \left\{-G_s\left(x_{k+1}\right),0\right\}\right)\right|}\\ =\frac{\left|2M_k^2{G}_s^2\left(x_{k+1}\right)H_s\left(x_{k+1}\right)\right|}{\left|2M_k^2{H}_s^2\left(x_{k+1}\right)G_s\left(x_{k+1}\right)\right|},\end{array}$

$\forall s\in I^G\left(\overline{x}\right)$ ，当$k\to +\infty$ ，有

$\frac{\left|{\nu }_s^k\right|}{\left|{\mu }_s^k\right|}=\frac{\left|G_s\left(x_{k+1}\right)\right|}{\left|H_s\left(x_{k+1}\right)\right|}\to 0,\left|{\mu }_s^k\right|\to +\infty ,$ (3.5)

同理，$\forall s\in I^H\left(\overline{x}\right)$ ，假设$\underset{k\to \infty }{\lim }{\mu }_s^k$ 不存在。即假设存在一个正数$b>0$ 和$\left\{{\mu }_s^k\right\}$ 的子序列(不失一般性，用序列本身代替)，当k充分大时，使得$\left|{\mu }_s^k\right|\ge b$ 。则

$\begin{array}{c}\frac{\left|{\mu }_s^k\right|}{\left|{\nu }_s^k\right|}=\frac{\left|2M_k^2{H}_s^2\left(x_{k+1}\right)\left(\max \left\{G_s\left(x_{k+1}\right),0\right\}-\max \left\{-G_s\left(x_{k+1}\right),0\right\}\right)\right|}{\left|2M_k^2{G}_s^2\left(x_{k+1}\right)\left(\max \left\{H_s\left(x_{k+1}\right),0\right\}-\max \left\{-H_s\left(x_{k+1}\right),0\right\}\right)\right|}\\ =\frac{\left|2M_k^2{H}_s^2\left(x_{k+1}\right)G_s\left(x_{k+1}\right)\right|}{\left|2M_k^2{G}_s^2\left(x_{k+1}\right)H_s\left(x_{k+1}\right)\right|},\end{array}$

$\forall s\in I^H\left(\overline{x}\right)$ ，当$k\to +\infty$ ，有

$\frac{\left|{\mu }_s^k\right|}{\left|{\nu }_s^k\right|}=\frac{\left|H_s\left(x_{k+1}\right)\right|}{\left|G_s\left(x_{k+1}\right)\right|}\to 0,\left|{\nu }_s^k\right|\to +\infty ,$ (3.6)

由等式(3.4)，可得当$k\to +\infty$ ，序列$\left\{{\mu }_s^{k_1},{\mu }_s^{k_2},{\nu }_s^{k_1},{\nu }_s^{k_2}\right\}$ 是收敛的，这与上式(3.5)，(3.6)矛盾。

因此，有$\forall s\in I^G\left(\overline{x}\right)$ ，$\underset{k\to \infty }{\lim }{\nu }_s^k$ 存在，且${\nu }_s=\underset{k\to \infty }{\lim }{\nu }_s^k=0$ 。$\forall s\in I^H\left(\overline{x}\right)$ ，$\underset{k\to \infty }{\lim }{\mu }_s^k$ 存在，且${\mu }_s=\underset{k\to \infty }{\lim }{\mu }_s^k=0$ 成立。

此外，由等式(3.3)，当$k\to +\infty$ ，存在$\alpha >0$ ，${\rho }_j\left(j\in I^h\left(\overline{x}\right)\right)$ ，${\lambda }_i\ge 0\left(i\in I^g\left(\overline{x}\right)\right)$ ，${\lambda }_i=0\left(i\notin I^g\left(\overline{x}\right)\right)$ ，${\mu }_s=0\left(s\in I^H\left(\overline{x}\right)\right)$ ，${\nu }_s=0\left(s\in I^G\left(\overline{x}\right)\right)$ 有

$\alpha \nabla f\left(\overline{x}\right)+{\displaystyle \sum _{j\in I^h\left(\overline{x}\right)}{\rho }_j\nabla h_j\left(\overline{x}\right)}+{\displaystyle \sum _{i\in I^g\left(\overline{x}\right)}{\lambda }_i\nabla g_i\left(\overline{x}\right)}+{\displaystyle \sum _{s=1}^l\left({\mu }_s\nabla G_s\left(\overline{x}\right)+{\nu }_s\nabla H_s\left(\overline{x}\right)\right)}=0$

同除以$\alpha$ ，令

$\begin{array}{l}\frac{{\lambda }_i}{\alpha }={\tilde{\lambda }}_i,i=1,2,\cdots ,m,\frac{{\rho }_j}{\alpha }={\tilde{\rho }}_j,j=1,2,\cdots ,p,\\ \frac{{\mu }_s}{\alpha }={\tilde{\mu }}_s,s=1,2,\cdots ,l,\frac{{\nu }_s}{\alpha }={\tilde{\nu }}_s,s=1,2,\cdots ,l,\end{array}$

可得

$\begin{array}{c}0=\nabla f\left(\overline{x}\right)+{\displaystyle \sum _{i\in I^g\left(\overline{x}\right)}{\tilde{\lambda }}_i\nabla g_i\left(\overline{x}\right)}+{\displaystyle \sum _{j\in I^h\left(\overline{x}\right)}{\tilde{\rho }}_j\nabla h_j\left(\overline{x}\right)}+{\displaystyle \sum _{s=1}^l\left({\tilde{\mu }}_s\nabla G_s\left(\overline{x}\right)+{\tilde{\nu }}_s\nabla H_s\left(\overline{x}\right)\right)},\\ \forall i\in I^g\left(\overline{x}\right):{\tilde{\lambda }}_i\ge 0,\forall s\in I^H\left(\overline{x}\right):{\tilde{\mu }}_s=0,\forall s\in I^G\left(\overline{x}\right):{\tilde{\nu }}_s=0,\end{array}$

由定义2.1，则点$\overline{x}$ 是问题(1.1)的弱稳定点成立。

4. 数值实验

本文对算法3.1，通过数值计算的角度，检验其数值效果及其可行性。为了使算法可行，在算法3.1中的无约束优化问题求解局部极小点时可以采用BFGS、梯度下降法等无约束算法。我们将用MATLAB R2022b来求解MPSC相关文献的例子，并将算法3.1中的条件$x_k$ 是问题(1.1)的可行点用$P\left(x_k\right)\le \epsilon$ 代替，取$\epsilon ={\text{e}}^{-10}$ ，求解存零约束优化问题的近似局部最优解。

例1 [10]

$\begin{array}{l}\min f\left(x\right)={\left(x_1+1\right)}^2+x_2^2\\ \text{s}\text{.t}\text{.}-x_1+x_2\le 0,\\ x_1^2-x_2\le 0,\\ x_1{x}_2=0,\end{array}$ (4.1)

考虑目标罚函数

$F\left(x,M\right)=\max {\left\{{\left(x_1+1\right)}^2+x_2^2-M,0\right\}}^2+M^2\left[\max {\left\{-x_1+x_2,0\right\}}^2+\max {\left\{x_1^2-x_2,0\right\}}^2+{\left(x_1{x}_2\right)}^2\right],$

其中约束优化问题(4.1)的最优解为$\left(0,0\right)$ ，最优值为1。

选取初始点$x_0=\left(2,5\right)$ ，$N=2$ ，由不同的罚参数$M_1$ 得到的计算结果如表1所示。

Table 1. The calculation results of different penalty parameters M₁ in Example 1

表1. 例1不同罚参数M₁的计算结果

$M_1$	$x_k$	$f\left(x_k\right)$	$M_k$	$P\left(x_k\right)$	k
−2	(1.0e−05*−0.7631, 1.0e−05*−0.3814)	1.0000	−524,288	2.9115e−11	18
−5	(1.0e−04*−0.1221, 1.0e−04*−0.0610)	1.0000	−327,680	7.4506e−11	16
−27	(1.0e−05*−0.9045, 1.0e−05*−0.4516)	1.0000	−442,368	4.0909e−11	14
−41	(1.0e−04*−0.1191, 1.0e−04*−0.0596)	1.0000	−335,872	7.0894e−11	13
−79	(1.0e−04*−0.1236, 1.0e−04*−0.0618)	1.0000	−323,584	7.6384e−11	12
−113	(1.0e−05*−0.8640, 1.0e−05*−0.4324)	1.0000	−462,848	3.7327e−11	12

选取初始点$x_0=\left(2,5\right)$ ，$M_1=-5$ ，由不同的迭代因子N得到的计算结果如表2所示。

Table 2. The calculation results of different iteration factors N in Example 1

表2. 例1不同迭代因子N的计算结果

N	$x_k$	$f\left(x_k\right)$	$M_k$	$P\left(x_k\right)$	k
2	(1.0e−04*−0.1221, 1.0e−04*−0.0610)	1.0000	−327,680	7.4506e−11	16
3	(1.0e−04*−0.1355, 1.0e−04*−0.0677)	1.0000	−295,245	9.1782e−11	10
4	(1.0e−04*−0.1220, 1.0e−04*−0.0611)	1.0000	−327,680	7.4482e−11	8
7	(1.0e−05*−0.6800, 1.0e−05*−0.3399)	1.0000	−588,245	2.3121e−11	6
11	(1.0e−05*−0.4968, 1.0e−05*−0.2482)	1.0000	−805,255	1.2343e−11	5
13	(1.0e−05*−0.2154, 1.0e−05*−0.1079)	1.0000	−1,856,465	2.3192e−12	5

选取罚参数$M_1=-5$ ，$N=2$ ，不同初始点x₀得到的计算结果如表3所示。

Table 3. The calculation results of different initial points x₀ in Example 1

表3. 例1不同初始点x₀的计算结果

$x_0$	$x_k$	$f\left(x_k\right)$	$M_k$	$P\left(x_k\right)$	k
(42, 11)	(1.0e−04*−0.1221, 1.0e−04*−0.0610)	1.0000	−327,680	7.4506e−11	15
(−35, 29)	(1.0e−04*−0.1221, 1.0e−04*−0.0610)	1.0000	−327,680	7.4506e−11	13
(12, −87)	(1.0e−04*−0.1221, 1.0e−04*−0.0610)	1.0000	−327,680	7.4506e−11	11
(25, 57)	(1.0e−04*−0.1221, 1.0e−04*−0.0610)	1.0000	−327,680	7.4506e−11	11
(61, 123)	(1.0e−04*−0.1221, 1.0e−04*−0.0610)	1.0000	−327,680	7.4506e−11	10

例2 [9]

$\begin{array}{l}\min f\left(x\right)=x_1{x}_2-x_1-x_2\\ \text{s}\text{.t}.x_1^2+x_2^2-1\le 0,\\ x_1{x}_2=0,\end{array}$ (4.2)

考虑目标罚函数

$F\left(x,M\right)=\max {\left\{x_1{x}_2-x_1-x_2-M,0\right\}}^2+M^2\left[\max {\left\{x_1^2+x_2^2-1,0\right\}}^2+{\left(x_1{x}_2\right)}^2\right],$

其中约束优化问题(4.2)的最优解为$\left(1,0\right)$ 和$\left(0,1\right)$ ，最优值为−1。

选取初始点$x_0=\left(3,5\right)$ ，$N=2$ ，由不同的罚参数$M_1$ 得到的计算结果如表4所示。

Table 4. The calculation results of different penalty parameters M₁ in Example 2

表4. 例2不同罚参数M₁的计算结果

$M_1$	$x_k$	$f\left(x_k\right)$	$M_k$	$P\left(x_k\right)$	k
−2	(−0.0000, 1.0000)	−1.0000	−65536	5.83e−11	15
−5	(−0.0000, 1.0000)	−1.0000	−81920	3.72e−11	14
−7	(−0.0000, 1.0000)	−1.0000	−57344	7.61e−11	13
−13	(−0.0000, 1.0000)	−1.0000	−53248	8.80e−11	12
−57	(−0.0000, 1.0000)	−1.0000	−58368	7.33e−11	10
−83	(−0.0000, 1.0000)	−1.0000	−84992	3.46e−11	10
−117	(−0.0000, 1.0000)	−1.0000	−59904	6.97e−11	9

选取初始点$x_0=\left(3,5\right)$ ，$M_1=-5$ ，由不同的迭代因子N得到的计算结果如表5所示。

Table 5. The calculation results of different iteration factors N in Example 2

表5. 例2不同迭代因子N的计算结果

N	$x_k$	$f\left(x_k\right)$	$M_k$	$P\left(x_k\right)$	k
2	(−0.0000, 1.0000)	−1.0000	−81920	3.72e−11	14
3	(−0.0000, 1.0000)	−1.0000	−98415	2.58e−11	9
4	(−0.0000, 1.0000)	−1.0000	−81920	3.72e−11	7
7	(−0.0000, 1.0000)	−1.0000	−84035	3.54e−11	5
11	(−0.0000, 1.0000)	−1.0000	−73205	4.67e−11	4
13	(0.0000, 1.0000)	−1.0000	−142805	1.22e−11	4
29	(−0.0000, 1.0000)	−1.0000	−121945	1.68e−11	3

选取罚参数$M_1=-5$ ，$N=2$ ，不同初始点$x_0$ 得到的计算结果如表6所示。

Table 6. The calculation results of different initial points x₀ in Example 2

表6. 例2不同初始点x₀的计算结果

$x_0$	$x_k$	$f\left(x_k\right)$	$M_k$	$P\left(x_k\right)$	k
(−12, 57)	(−0.0000, 1.0000)	−1.0000	−81920	3.72e−11	14
(41, 23)	(1.0000, −0.0000)	−1.0000	−81920	3.72e−11	14
(37, −81)	(1.0000, −0.0000)	−1.0000	−81920	3.72e−11	14
(122, 67)	(1.0000, −0.0000)	−1.0000	−81920	3.72e−11	14
(187, 3)	(−0.0000, 1.0000)	−1.0000	−81920	3.72e−11	14
(29, 74)	(−0.0000, 1.0000)	−1.0000	−81920	3.72e−11	14

从以上的数据实验中看出，$\left|M_k\right|$ 越大，$x_k$ 越接近原问题的最优解，$P\left(x_k\right)$ 越接近0，$f\left(x_k\right)$ 越接近原问题的最优值。在选取$M_1$ 时，发现当$\left|M_1\right|$ 越大时，迭代次数越小，但是$\left|M_k\right|$ 并不会随之越大。从表1、表4中可知，当初始点$x_0$ 和迭代因子N固定时，在[−5, −2]范围内选取的罚参数$M_1$ ，更有可能使最后迭代的$\left|M_k\right|$ 越大。从表2、表5中可知，当初始点$x_0$ 和罚参数$M_1$ 固定时，在[7, 13]范围选取的迭代因子N，更有可能使最后迭代的$\left|M_k\right|$ 越大。从表3、表6中看出，当罚参数$M_1$ 和迭代因子N固定时，初始点$x_0$ 的选取对求解存零约束优化问题影响较小，可以任意选取初始点$x_0$ 。

5. 结论

存零约束优化问题因存零约束的存在，导致现有算法不能直接应用于该优化问题。本文基于互补约束优化目标罚函数方法，构建存零约束优化问题的目标罚函数方法，进一步讨论原问题和目标罚函数问题在最优解方面的关系，以及分析最优解点列的收敛性。最后，本文通过数值结果表明了目标罚函数法的可行性。数据试验表明，目标罚函数算法是求解存零约束优化问题的有效算法，并且初始点的选取对求解存零约束优化问题影响较小。