DOI: 10.12677/aam.2024.139393, PDF, HTML, XML,  被引量   
作者: 路斯文：长沙理工大学数学与统计学院，湖南 长沙
关键词: 最小约束违背优化问题；MPCC；W-稳定点；增广拉格朗日方法；Least Constraint Violation； MPCC； W-Stationary Point； Augmented Lagrangian Method

文章引用：路斯文. 最小约束违背非线性凸优化[J]. 应用数学进展, 2024, 13(9): 4119-4128. https://doi.org/10.12677/aam.2024.139393

1. 引言

关于非线性规划问题，已有不少不可行稳定点和算法。例如Byrd，Curtis与Nocedal [1]提出了SQP算法，在一组条件下可以保证算法超线性收敛到一个 $l_1$ -范数度量的不可行稳定点。Burke，Curtis与Wang [2]考虑具有等式和不等式约束的一般非线性规划问题，证明了他们所提的SQP算法可以全局并且快速收敛到KKT点，或者超线性或二次收敛到 $l_1$ -范数度量的不可行稳定点。Dai，Liu与Sun [3]提出了一个原始–对偶内点方法，并证明了该内点方法当原始问题可行时，在一定条件下超线性或二次收敛到问题的KKT点；当问题不可行时，则超线性或二次收敛到 $l_2$ -范数度量的不可行稳定点。

这些算法都是求解约束条件不可行性度量的某个稳定点，这样的稳定点与原问题的目标函数没有任何关系，并不是最小约束违背优化问题的解[4]。因此有必要考虑在最小约束违背的点集上极小化目标函数。Dai和Zhang [5]依据Lipschitz连续优化的最优性理论，提出了L-稳定点的概念，并构造了求解最小约束违背的非线性凸规划问题的惩罚函数方法和用于求解最小约束违背的非线性凸优化问题等价MPCC问题的光滑Fischer-Burmeister函数方法。

然而，惩罚函数方法并不是精确的，当惩罚参数较大时，惩罚函数方法会出现计算困难，并且光滑函数方法只能收敛到问题的L-稳定点。由于约束规范不同导致无法确定L-稳定点和S-稳定点之间的关系。为了克服惩罚函数方法和光滑函数方法在求解最小约束违背优化问题的局限性，对最小约束违背凸优化问题值得重新考虑新的理论和算法。Chiche和Gilbert [6]的研究为我们提供了有价值的线索，他们证明了增广拉格朗日方法可以处理一个不可行的凸二次规划问题，这促使我们考虑用增广拉格朗日方法来处理最小约束违背的非线性凸优化问题。

本文采用增广拉格朗日方法求解最小约束违背优化等价的MPCC问题，进而达到求解最小约束违背优化问题的目的，并证明了增广拉格朗日方法生成的点列收敛到该等价MPCC问题的W-稳定点。

2. 基于不可行性度量的数学规划模型

本节考虑如下形式的非线性规划问题

$\begin{array}{l}\text{min }f\left(x\right)\\ \text{s}\text{.t}\text{. }h\left(x\right)=0,\\ g\left(x\right)\ge 0,\end{array}$ (2.1)

其中用 $f:R^n\to R$ ， $h:R^n\to R^q$ ， $g:R^n\to R^p$ 。记问题(2.1)的可行域：

$\Phi =\left\{x\in R^n:h\left(x\right)=0,g\left(x\right)\ge 0\right\}.$

基于上述非线性规划问题，为后续讨论需要，引入问题的不可行性度量。

定义2.1 [5]函数 $\theta :R^n\to R$ 称为约束 $\left(h\left(x\right),g\left(x\right)\right)\in \left\{0_q\right\}\times R_{+}^p$ 的不可行度量，如果存在递增连续函数 $\rho :R_{+}\to R_{+}$ 满足 $\rho \left(0\right)=0$ ，使得

$\theta \left(x\right)=\rho \left(\mathrm{dist}\left(\left(h\left(x\right),g\left(x\right)\right),\left\{0_q\right\}\times R_{+}^p\right)\right),$

其中

$\mathrm{dist}\left(\left(h\left(x\right),g\left(x\right)\right),\left\{0_q\right\}\times R_{+}^p\right)=\inf \left\{\Vert h\left(x\right),y-g\left(x\right)\Vert :y\in R_{+}^p\right\}$

是由 $\left(h\left(x\right),g\left(x\right)\right)$ 到 $\left\{0_q\right\}\times R_{+}^p$ 在 $R^q\times R^p$ 的范数 $\Vert \cdot \Vert$ 下的距离。

显然， $\theta \left(x\right)$ 依赖于函数 $\rho (\cdot )$ 和范数 $\Vert \cdot \Vert$ 。本文中采用 $\rho \left(t\right)=\frac{1}{2}{t}^2$ ，范数 $\Vert \cdot \Vert$ 采用标准的欧式范数，即 $l_2$ -范数。

在上述不可行性度量下，引入在具有最小约束违背点集上极小化目标函数 $f\left(x\right)$ 的数学模型。

定义2.2 [5]对于约束 $\left(h\left(x\right),g\left(x\right)\right)\in \left\{0_q\right\}\times R_{+}^p$ 的一个不可行度量 $\theta \left(x\right)$ ，与 $\theta$ 相联系的最小约束违背的极小化目标函数 $f\left(x\right)$ 的数学模型定义为

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{. }x\in \mathrm{Arg}\underset{z}{\min }\theta \left(z\right).\end{array}$ (2.2)

显然，如果可行域 $\Phi$ 非空，那么 $\underset{z}{\min }\theta \left(z\right)=0$ ， $\mathrm{Arg}\underset{z}{\min }\theta \left(z\right)=\Phi$ ，问题(2.2)恰好就是原始问题(2.1)。因此，问题(2.2)可以被视为原始问题(2.1)的拓广。

在定义2.2中，没有阐述 $\mathrm{Arg}\underset{z}{\min }\theta \left(z\right)$ 的含义，要看具体情况如何约定。如果 $\theta \left(z\right)$ 是凸函数，显然这一集合就是全局极小点的集合。然而，如果 $\theta \left(z\right)$ 是非凸函数(比如问题是可行的，当 $\Phi$ 是非凸时就是这一情形)。 $\mathrm{Arg}\underset{z}{\min }\theta \left(z\right)$ 可以理解为局部极小点，甚至是稳定点集。在非凸优化的情形，不可行性检测是非常难的问题。

对 $\rho \left(t\right)=\frac{1}{2}{t}^2$ ， $t\ge 0$ ，约束的最小违背定义为下述问题的最优值

$\begin{array}{l}\min \frac{1}{2}{\Vert \left(h\left(x\right),y\right)\Vert }^2\\ \text{s}\text{.t}\text{. }g\left(x\right)+y\ge 0_p.\end{array}$ (2.3)

最小约束违背的点集定义为

$S=\left\{x:\left(x,y\right)求解问题\left(2.3\right)\right\}.$

在S上极小化f的问题是

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{. }\left(x,y\right)求解\end{array}$ (2.4)

$\{\begin{array}{l}\underset{w,z}{\min }\frac{1}{2}{\Vert h\left(w\right)\Vert }^2+{\Vert z\Vert }^2\\ \text{s}\text{.t}\text{. }g\left(w\right)+z\ge 0.\end{array}$

用 $\left(P_L\right)$ 记问题(2.4)的下层问题，即

$\left(P_L\right)$ $\{\begin{array}{l}\underset{w,z}{\min }\left[\frac{1}{2}{\Vert h\left(w\right)\Vert }^2+{\Vert z\Vert }^2\right]\\ \text{s}\text{.t}\text{. }g\left(w\right)+z\ge 0.\end{array}$

利用与 $\rho \left(t\right)$ 的关系，有

$\theta \left(w\right)=\frac{1}{2}{\Vert h\left(x\right)\Vert }^2+\underset{z}{\min }\left\{\frac{1}{2}{\Vert z\Vert }^2:g\left(w\right)+z\ge 0\right\}=\frac{1}{2}\left[{\Vert h\left(w\right)\Vert }^2+{\Vert {\left[g\left(w\right)\right]}_{-}\Vert }^2\right],$

其中 ${\left[z\right]}_{-}={\left({\left[z_1\right]}_{-},\cdots ,{\left[z_p\right]}_{-}\right)}^{\text{T}}$ ， $z\in R^p$ ，其中 ${\left[t\right]}_{-}=\min \left\{0,t\right\}$ ， $t\in R$ 。容易验证， $\theta \left(w\right)$ 是问题(2.1)的一个不可行性度量。问题 $\left(P_L\right)$ 的最优解可表示为

$\mathrm{Arg}\min \left(P_L\right)=\mathrm{Arg}\underset{x}{\min }\theta \left(x\right)=\mathrm{Arg}\underset{x}{\min }\frac{1}{2}\left[{\Vert h\left(x\right)\Vert }^2+{\Vert {\left[g\left(x\right)\right]}_{-}\Vert }^2\right].$

所以，问题(2.4)可等价地表示为

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{. }x\in \mathrm{Arg}\underset{w}{\min }\frac{1}{2}\left[{\Vert h\left(w\right)\Vert }^2+{\Vert {\left[g\left(w\right)\right]}_{-}\Vert }^2\right].\end{array}$ (2.5)

容易验证，如果h和g是可微的，则 $\theta \left(x\right)$ 是可微的，且满足

$\nabla \theta =Jh{\left(x\right)}^{\text{T}}h\left(x\right)+Jg{\left(x\right)}^{\text{T}}{\left[g\left(w\right)\right]}_{-}.$ (2.6)

以下讨论最小约束违背的非线性凸优化问题，将从模型(2.5)出发，并利用公式(2.6)解决该问题。

3. 最小约束违背非线性凸优化

3.1. 最小约束违背非线性凸优化等价的MPCC问题

考虑下述非线性凸优化问题

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{. }Ax-b=0,\\ g\left(x\right)\ge 0,\end{array}$ (3.1)

其中f是一光滑的凸函数， $A\in R^{q\times n}$ ， $b\in R^q$ ，且每一个 $g_i\left(i=1,\cdots ,p\right)$ 都是凹的光滑函数。此种情况下，函数 $\theta \left(x\right)$ 是凸函数，从而问题(2.5)是凸优化问题，可被简化为

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{. }{A}^{\text{T}}\left(Ax-b\right)+Jg{\left(x\right)}^{\text{T}}{\left[g\left(x\right)\right]}_{-}=0.\end{array}$ (3.2)

尽管问题(3.2)是一个凸优化问题，其约束处理并不容易，因为这些约束是非光滑的等式，需要将约束转化为光滑约束，构造数值算法。通过引入辅助向量 $y\in R^p$ ，可将(3.2)中的约束表示为

$A^{\text{T}}\left(Ax-b\right)+Jg{\left(x\right)}^{\text{T}}y=0,$

$0\le y\perp g\left(x\right)+y\ge 0.$

为讨论方便，定义 $z=g\left(x\right)+y$ ，上述系统可以表示为

$F\left(x,y,z\right)=0,\left(y,z\right)\in \Omega ,$

其中

$F\left(x,y,z\right)=\left(\begin{array}{c}{A}^{\text{T}}\left(Ax-b\right)+Jg{\left(x\right)}^{\text{T}}y\\ g\left(x\right)+y-z\end{array}\right),$

$\Omega =\left\{\left(y,z\right)\in R^p\times R^q:0\le y\perp z\ge 0\right\}.$ (3.3)

因此，问题(2.5)等价地表示为

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{. }F\left(x,y,z\right)=0,\left(y,z\right)\in \Omega .\end{array}$ (3.4)

映射F在 $\left(x,y,z\right)$ 的Jacobian矩阵具有形式

$JF\left(x,y,z\right)=\left(\begin{array}{ccc}{A}^{\text{T}}A-{\displaystyle \underset{j=1}{\overset{p}{\sum }}{y}_i}{\nabla }^2{g}_i\left(x\right)& -Jg{\left(x\right)}^{\text{T}}& 0\\ Jg\left(x\right)& I_p& -I_p\end{array}\right).$ (3.5)

为后续讨论方便，我们记 $H\left(x,y\right)=A^{\text{T}}A-{\displaystyle \underset{j=1}{\overset{p}{\sum }}{y}_i}{\nabla }^2{g}_i\left(x\right)$ ， $G\left(x\right)=Jg\left(x\right)$ 。

用 $\Phi$ 记问题(3.4)的可行域，即

$\Phi =\left\{\left(x,y,z\right)\in R^n\times \Omega :F\left(x,y,z\right)=0\right\}.$

那么问题(3.4)可被简化为如下的MPCC问题

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{. }\left(x,y,z\right)\in \Phi .\end{array}$ (3.6)

3.2. 等价MPCC问题的必要性最优性条件

本节主要讨论MPCC (3.6)的最优性条件，下面我们首先来回顾一些符号和定理。定义下述指标集合

$\alpha :=\left\{i|y_i=0,z_i>0\right\},$

$\beta :=\left\{i|y_i=0,z_i=0\right\},$

$\gamma :=\left\{i|y_i>0,z_i=0\right\}.$

为了得到 $N_{\Phi }\left(\bar{x},\bar{y},\bar{z}\right)$ 的显示表达式，我们首先给出抽象约束集合的切锥、法锥形式。

定理3.1 [7]设 ${\Omega }_i=\left\{\left(y_i,z_i\right)\in R^2|y_i\ge 0,z_i\ge 0,y_i{z}_i=0\right\}$ ，则对 $\forall \left(y_i,z_i\right)\in {\Omega }_i$ ，有

$T_{{\Omega }_i}\left(y_i,z_i\right)=\{\begin{array}{ll}\left\{0\right\}\times R,\hfill & y_i=0,z_i>0,\hfill \\ R\times \left\{0\right\},\hfill & y_i>0,z_i=0,\hfill \\ {\Omega }_i,\hfill & y_i=0,z_i=0,\hfill \end{array}$

$N_{{\Omega }_i}\left(y_i,z_i\right)=\{\begin{array}{ll}R\times \left\{0\right\},\hfill & y_i=0,z_i>0,\hfill \\ \left\{0\right\}\times R,\hfill & y_i>0,z_i=0,\hfill \\ \left(R_{-}\times R_{-}\right)\cup \left(\left\{0\right\}\times R\right)\cup \left(R\times \left\{0\right\}\right),\hfill & y_i=0,z_i=0,\hfill \end{array}$

${\hat{N}}_{{\Omega }_i}\left(y_i,z_i\right)=\{\begin{array}{ll}R\times \left\{0\right\},\hfill & y_i=0,z_i>0,\hfill \\ \left\{0\right\}\times R,\hfill & y_i>0,z_i=0,\hfill \\ \left(R_{-}\times R_{-}\right),\hfill & y_i=0,z_i=0.\hfill \end{array}$

进而有

${\hat{N}}_{R^n\times \Omega }\left({\bar{x}}_i,{\bar{y}}_i,{\bar{z}}_i\right)=\left\{0\right\}\times {\otimes }_{i=1}^m{\hat{N}}_{{\Omega }_{\text{i}}}\left({\bar{y}}_i,{\bar{z}}_i\right)=\left\{\left(0,d_i{}^a,d_i^b\right):d_{\alpha }^b=0,d_{\gamma }^a=0,d_{\beta }^a\le 0,d_{\beta }^b\le 0\right\}.$

$\begin{array}{c}{N}_{R^n\times \Omega }\left({\bar{x}}_i,{\bar{y}}_i,{\bar{z}}_i\right)=\left\{0\right\}\times {\otimes }_{i=1}^m{N}_{{\Omega }_{\text{i}}}\left({\bar{y}}_i,{\bar{z}}_i\right)\\ =\left\{\left(0,d_i{}^a,d_i^b\right):d_{\alpha }^b=0,d_{\gamma }^a=0,d_{\beta }^a\le 0,d_{\beta }^b\le 0\text{or}{d}_{\beta }^a=0\text{or}{d}_{\beta }^b=0\right\}.\end{array}$

在基本约束规范成立的条件下，抽象约束集合的切锥、法锥形式具体如下：

定理3.2 [8] MPCC (3.6)的可行域为 $\Phi =\left\{\left(x,y,z\right)\in R^n\times \Omega :F\left(x,y,z\right)=0\right\}$ ，其中 $R^n\times \Omega \subset R^{n+2m}$ 是一个闭集合， $F:R^{2n}\to R^p$ 是一个光滑连续可微映射， $F={\left(g_1,\cdots ,g_m,h_1,\cdots ,h_m\right)}^{\text{T}}$ ， $p=2m$ ，则：

1) $\begin{array}{c}{\hat{N}}_{\Phi }\left(\bar{x},\bar{y},\bar{z}\right)\supset \left\{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\lambda }_i\nabla g_i\left(\bar{x}\right)}+{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\lambda }_i\nabla h_i\left(\bar{x}\right)}+d|\left({\lambda }^g,{\lambda }^h\right)\in R^{2m},d\in {\hat{N}}_D\left(\bar{x},\bar{y},\bar{z}\right)\right\}\\ =JF{\left(\bar{x},\bar{y},\bar{z}\right)}^{\text{T}}{R}^p+{\hat{N}}_D\left(\bar{x},\bar{y},\bar{z}\right)\end{array}$.

2) 如果基本约束规范在 $\left(\bar{x},\bar{y},\bar{z}\right)$ 处成立，即：

$\{\begin{array}{l}y\in R^p\\ 0\in JF{\left(\bar{x},\bar{y},\bar{z}\right)}^{\text{T}}y+N_{R^n\times \Omega }\left(\bar{x},\bar{y},\bar{z}\right)\end{array}\to y={\left(0,\cdots ,0\right)}^{\text{T}}$

则 $N_{\Phi }\left(\bar{x},\bar{y},\bar{z}\right)\subset JF{\left(\bar{x},\bar{y},\bar{z}\right)}^{\text{T}}{R}^p+N_D\left(\bar{x},\bar{y},\bar{z}\right)$。

3) 当 $\beta =\varnothing$ 时， $D=R^n\times \Omega$ 在 $\left(\bar{x},\bar{y},\bar{z}\right)$ 处正则， ${\left\{0\right\}}^p$ 在 $F\left(\bar{x},\bar{y},\bar{z}\right)$ 处正则，则 $\Phi$ 在 $\left(\bar{x},\bar{y},\bar{z}\right)$ 处正则，得 ${\hat{N}}_{\Phi }\left(\bar{x},\bar{y},\bar{z}\right)=N_{\Phi }\left(\bar{x},\bar{y},\bar{z}\right)=JF{\left(\bar{x},\bar{y},\bar{z}\right)}^{\text{T}}{R}^p+N_D\left(\bar{x},\bar{y},\bar{z}\right)$。

下面给出在基本约束规范成立的条件下，MPCC问题的W-稳定点概念。

定理3.3 设 $\bar{x}$ 为MPCC (3.6)的局部最优解，且该点处基本约束规范成立，当 $\beta =\varnothing$ 时，严格互补松弛条件成立，则 $\bar{x}$ 为W-稳定点。即存在 $\left({\lambda }^H,{\lambda }^G\right)\in R^{q+p}$ ，满足

$\nabla f\left(\bar{x}\right)+{\displaystyle \underset{i\in \alpha \cup \beta }{\sum }{\lambda }_i^H}H\left(\bar{x}\right)+{\displaystyle \underset{i\in \beta \cup \gamma }{\sum }{\lambda }_i^G}G\left(\bar{x}\right)=0,$

${\lambda }_{\gamma }^H=0,{\lambda }_a^G=0.$

证明 由定理3.2可知，MPCC问题的可行域集合的法锥形式如下：

$\begin{array}{c}{N}_{\Phi }\left(\bar{x},\bar{y},\bar{z}\right)\subseteq JF{\left(\bar{x},\bar{y},\bar{z}\right)}^{\text{T}}{R}^p+N_D\left(\bar{x},\bar{y},\bar{z}\right)\\ \subseteq \left(\begin{array}{c}H{\left(\bar{x}\right)}^{\text{T}}{\lambda }^H+G{\left(\bar{x}\right)}^{\text{T}}{\lambda }^G\\ -{\lambda }^H\\ -{\lambda }^G\end{array}\right)+\left(\begin{array}{c}0\\ d^H\\ d^G\end{array}\right)\\ =\left(\begin{array}{c}H{\left(\bar{x}\right)}^{\text{T}}{\lambda }^H+G{\left(\bar{x}\right)}^{\text{T}}{\lambda }^G\\ -{\lambda }^H+d^H\\ -{\lambda }^G+d^G\end{array}\right).\end{array}$

因为 ${\hat{N}}_{\Phi }\left(\bar{x},\bar{y},\bar{z}\right)\subset N_{\Phi }\left(\bar{x},\bar{y},\bar{z}\right)$ ，由基本最优性条件可得

$\begin{array}{c}0\in \nabla f\left(\bar{x}\right)+{\hat{N}}_{\Phi }\left(\bar{x},\bar{y},\bar{z}\right)\\ \in \nabla f\left(\bar{x}\right)+N_{\Phi }\left(\bar{x},\bar{y},\bar{z}\right)\\ \in \left(\begin{array}{c}\nabla f\left(\bar{x}\right)\\ 0\\ 0\end{array}\right)+\left(\begin{array}{c}H{\left(\bar{x}\right)}^{\text{T}}{\lambda }^H+G{\left(\bar{x}\right)}^{\text{T}}{\lambda }^G\\ -{\lambda }^H+d^H\\ -{\lambda }^G+d^G\end{array}\right)\\ =\left(\begin{array}{c}\nabla f\left(\bar{x}\right)+H{\left(\bar{x}\right)}^{\text{T}}{\lambda }^H+G{\left(\bar{x}\right)}^{\text{T}}{\lambda }^G\\ -{\lambda }^H+d^H\\ -{\lambda }^G+d^G\end{array}\right).\end{array}$

所以存在 ${\lambda }^H,{\lambda }^G$ ，有

$0=\nabla f\left(\bar{x}\right)+H{\left(\bar{x}\right)}^{\text{T}}{\lambda }^H+G{\left(\bar{x}\right)}^{\text{T}}{\lambda }^G,$

$0=-{\lambda }^H+d^H,$

$0=-{\lambda }^G+d^G.$

由定理3.1可知，当 $i\in \gamma$ 时，我们有 $d_{\gamma }^H=0$ ，那么如果 $0=-{\lambda }_{\gamma }^H+d_{\gamma }^H$ ，有 ${\lambda }_{\gamma }^H=0$ ；当 $i\in \alpha$ 时，我们有 $d_{\alpha }^G=0$ ，那么如果 $0=-{\lambda }_{\alpha }^G+d_{\alpha }^G$ ，有 ${\lambda }_{\alpha }^G=0$ 。

由此可知 $\bar{x}$ 是W-稳定点。

4. 增广拉格朗日方法

对于等式约束优化问题

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{. }g\left(x\right)=0,x\in R^n.\end{array}$

对这一等式约束优化问题，Powell [9]、Hestenes [10]在1969年提出用增广拉格朗日方法来求解，首先将上述问题转化为

$\min f\left(x\right)+{\lambda }^{\text{T}}g\left(x\right)+c{\Vert g\left(x\right)\Vert }^2$

的无约束优化问题，这里 $c>0$ 是罚参数， $\lambda$ 是增广拉格朗日乘子的近似。该方法可以通过对 $\lambda$ 进行迭代，得到近似最优解。

本节首先将问题(3.6)中的互补约束表示为拉格朗日函数的形式，它的拉格朗日函数 $L:R^n\times R^p\times R^p\to R$ 为

$L\left(x,y,z,\lambda \right)=f\left(x\right)+{\lambda }^{\text{T}}F\left(x,y,z\right),$ (4.1)

其中关于 $x,y,z$ 的梯度和Hessian矩阵如下：

${\nabla }_{x}L\left(x,y,z,\lambda \right)=\nabla f\left(x\right)+J_{x}F{\left(x,y,z\right)}^{\text{T}}\lambda ,$

${\nabla }_{y}L\left(x,y,z,\lambda \right)=J_{y}F{\left(x,y,z\right)}^{\text{T}}\lambda ,$

${\nabla }_{z}L\left(x,y,z,\lambda \right)=J_{z}F{\left(x,y,z\right)}^{\text{T}}\lambda .$

问题(3.6)的增广拉格朗日函数 $L_c:R^n\times R^p\times R^p\to R$ 为

$L_c\left(x,y,z,\lambda \right)=f\left(x\right)+{\lambda }^{\text{T}}F\left(x,y,z\right)+\frac{c}{2}{\Vert F\left(x,y,z\right)\Vert }^2,$ (4.2)

其中 $c>0$ 是一个罚参数， $\Vert \cdot \Vert$ 表示欧几里得 $l_2$ -范数。则上述增广拉格朗日对偶问题为

$\underset{\lambda }{\max }\left\{\underset{\left(x,y,z\right)}{\inf }{L}_{c^k}\left(x,y,z,{\lambda }^k\right)\right\}.$ (4.3)

求解该对偶问题的增广拉格朗日方法迭代格式如下：

$\left(x^{k+1},y^{k+1},z^{k+1}\right)\in \underset{\left(x,y,z\right)\in \Omega }{\arg \max }{L}_{c^k}\left(x,y,z,{\lambda }^k\right),$

${\lambda }^{k+1}={\lambda }^k+c^{k}F\left(x^{k+1},y^{k+1},z^{k+1}\right).$

定理4.1 [11]设 $\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)$ 为 $L\left(x,y,z,\lambda \right)$ 的一个稳定点，则对任意的 $c>0$ ， $\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)$ 也是 $L_c\left(x,y,z,\lambda \right)$ 的一个稳定点，而且 $L_c\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=L\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)$ 。反之也成立。

证明 $L_c\left(x,y,z,\lambda \right)$ 的梯度表达式为

${\nabla }_x{L}_c\left(x,y,z,\lambda \right)=\nabla f\left(x\right)+J_{x}F{\left(x,y,z\right)}^{\text{T}}\lambda +c{J}_{x}F{\left(x,y,z\right)}^{\text{T}}F\left(x,y,z\right),$ (4.4)

${\nabla }_y{L}_c\left(x,y,z,\lambda \right)=J_{y}F{\left(x,y,z\right)}^{\text{T}}\lambda +c{J}_{y}F{\left(x,y,z\right)}^{\text{T}}F\left(x,y,z\right),$ (4.5)

${\nabla }_z{L}_c\left(x,y,z,\lambda \right)=J_{z}F{\left(x,y,z\right)}^{\text{T}}\lambda +c{J}_{z}F{\left(x,y,z\right)}^{\text{T}}F\left(x,y,z\right),$ (4.6)

${\nabla }_{\lambda }{L}_c\left(x,y,z,\lambda \right)=F\left(x,y,z\right).$ (4.7)

如果 $\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)$ 是 $L\left(x,y,z,\lambda \right)$ 的一个稳定点，那么有

${\nabla }_{x}L\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=0,{\nabla }_{y}L\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=0,{\nabla }_{z}L\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=0,F\left(x,y,z\right)=0.$

因此，由(4.4) (4.5) (4.6) (4.7)可知，对任意的 $c>0$ ，有

${\nabla }_x{L}_c\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=\nabla f\left(x\right)+J_{x}F{\left(x,y,z\right)}^{\text{T}}\lambda +c{J}_{x}F{\left(x,y,z\right)}^{\text{T}}F\left(x,y,z\right)=0,$

${\nabla }_y{L}_c\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=J_{y}F{\left(x,y,z\right)}^{\text{T}}\lambda +c{J}_{y}F{\left(x,y,z\right)}^{\text{T}}F\left(x,y,z\right)=0,$

${\nabla }_z{L}_c\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=J_{z}F{\left(x,y,z\right)}^{\text{T}}\lambda +c{J}_{z}F{\left(x,y,z\right)}^{\text{T}}F\left(x,y,z\right)=0,$

${\nabla }_{\lambda }{L}_c\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=F\left(x,y,z\right)=0.$

即 $\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)$ 是 $L_c\left(x,y,z,\lambda \right)$ 的一个稳定点。进一步，把 $F\left(\bar{x},\bar{y},\bar{z}\right)=0$ 代入(4.2)即得

$L_c\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=L\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)$ 。

同样的，当

${\nabla }_x{L}_c\left(\bar{x},\bar{y},\bar{z},\lambda \right)=0,{\nabla }_y{L}_c\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=0,{\nabla }_z{L}_c\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=0,{\nabla }_{\lambda }{L}_c\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=0,$

有

${\nabla }_{x}L\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=0,{\nabla }_{y}L\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=0,{\nabla }_{z}L\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=0,F\left(\bar{x},\bar{y},\bar{z}\right)=0$ 。

这说明 $\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)$ 是 $L\left(x,y,z,\lambda \right)$ 的一个稳定点。把 $F\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=0$ 代入(4.2)就可以得到

$L_c\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right)=L\left(\bar{x},\bar{y},\bar{z},\bar{\lambda }\right).$

最后，我们证明采用增广拉格朗日方法用于求解该等价MPCC问题所生成的点列收敛到该等价问题的W-稳定点。

定理4.2 设 $\left\{\left(x^k,y^k,z^k\right)\right\}$ 为增广拉格朗日对偶问题(4.3)的KKT稳定点序列，假设 $\left(\bar{x},\bar{y},\bar{z}\right)\in \Phi$ 是它的聚点，在 $\bar{x}$ 处MPCC-LICQ成立，则当 $\left\{c_k\right\}\to 0$ 时， $\bar{x}$ 是问题MPCC (3.6)的W-稳定点。

证明 因为 $\left\{\left(x^k,y^k,z^k\right)\right\}$ 为问题(4.3)的KKT稳定点序列，那么

${\nabla }_x{L}_{c^k}\left(x^k,y^k,z^k,{\lambda }^k\right)=\nabla f\left(x^k\right)+J_{x^k}F{\left(x^k,y^k,z^k\right)}^{\text{T}}{\lambda }^k+c^k{J}_{x^k}F{\left(x^k,y^k,z^k\right)}^{\text{T}}F\left(x^k,y^k,z^k\right)=0.$

记 ${\lambda }^k=\left({\lambda }_H^k,{\lambda }_G^k\right)$ ，

${\nabla }_x{L}_{c^k}\left(x^k,y^k,z^k,{\lambda }^k\right)=\nabla f\left(x^k\right)+{\left(\begin{array}{c}H\left(x^k\right)\\ G\left(x^k\right)\end{array}\right)}^{\text{T}}{\lambda }^k+c^k\left(H{\left(x^k\right)}^{\text{T}}G{\left(x^k\right)}^{\text{T}}\right)\left(\begin{array}{c}{\text{A}}^{\text{T}}\left(\text{Ax}-\text{b}\right)+J\text{g}{\left(\text{x}\right)}^{\text{T}}\text{y}\\ \text{g}\left(\text{x}\right)+\text{y}-\text{z}\end{array}\right)=0.$

可以推出

$\nabla f\left(x^k\right)+H{\left(x^k\right)}^{\text{T}}{\lambda }_H^k+G{\left(x^k\right)}^{\text{T}}{\lambda }_G^k+c^k\left(H{\left(x^k\right)}^{\text{T}}\left({\text{A}}^{\text{T}}\left(\text{Ax}-\text{b}\right)+J\text{g}{\left(\text{x}\right)}^{\text{T}}\text{y}\right)+G{\left(x^k\right)}^{\text{T}}\left(\text{g}\left(\text{x}\right)+\text{y}-\text{z}\right)\right)=0.$

由上式可得

$\begin{array}{c}-\nabla f\left(x^k\right)=H{\left(x^k\right)}^{\text{T}}{\lambda }_H^k+G{\left(x^k\right)}^{\text{T}}{\lambda }_G^k+c^k\left(H{\left(x^k\right)}^{\text{T}}\left({\text{A}}^{\text{T}}\left(\text{Ax}-\text{b}\right)+J\text{g}{\left(\text{x}\right)}^{\text{T}}\text{y}\right)+G{\left(x^k\right)}^{\text{T}}\left(\text{g}\left(\text{x}\right)+\text{y}-\text{z}\right)\right)\\ =H{\left(x^k\right)}^{\text{T}}\left({\lambda }_H^k+c^k\left({\text{A}}^{\text{T}}\left(\text{Ax}-\text{b}\right)+J\text{g}{\left(\text{x}\right)}^{\text{T}}\text{y}\right)\right)+G{\left(x^k\right)}^{\text{T}}\left({\lambda }_G^k+c^k\left(\text{g}\left(\text{x}\right)+\text{y}-\text{z}\right)\right).\end{array}$

令

$a^k={\lambda }_H^k+c^k\left({\text{A}}^{\text{T}}\left(\text{Ax}-\text{b}\right)+J\text{g}{\left(\text{x}\right)}^{\text{T}}\text{y}\right),b^k={\lambda }_G^k+c^k\left(\text{g}\left(\text{x}\right)+\text{y}-\text{z}\right),$ (4.8)

即

$-\nabla f\left(x^k\right)=H{\left(x^k\right)}^{\text{T}}{a}^k+G{\left(x^k\right)}^{\text{T}}{b}^k={\displaystyle \underset{i=1}{\overset{p}{\sum }}{a}_i^k}H\left(x^k\right)+{\displaystyle \underset{i=1}{\overset{p}{\sum }}{b}_i^k}G\left(x^k\right).$ (4.9)

下证式(4.8)中的乘子序列 $\left\{a^k,b^k\right\}$ 有界。如果 $\left\{a^k,b^k\right\}$ 无界，那么存在一个子集K，对任意的 $k\in K$ ， $k\to \infty$ ，有 $\frac{\left(a^k,b^k\right)}{\Vert \left(a^k,b^k\right)\Vert }\to \left(a^{\prime },b^{\prime }\right)$ 。(4.9)式两边同时除以 $\Vert \left(a^k,b^k\right)\Vert$ 并取极限，当 $k\to \infty$ 时，有

${\displaystyle \underset{i\in \alpha \cup \beta }{\sum }{a^{\prime }}_i}H\left(\bar{x}\right)+{\displaystyle \underset{i\in \beta \cup \gamma }{\sum }{b^{\prime }}_i}G\left(\bar{x}\right)=0.$

当 $i\in \gamma$ 时，

$\underset{k\to \infty }{\lim }{a}^k={\lambda }_H^k+c^k\left({\text{A}}^{\text{T}}\left(\text{Ax}-\text{b}\right)+J\text{g}{\left(\text{x}\right)}^{\text{T}}\text{y}\right)=0.$

当 $i\in \alpha$ 时，

$\underset{k\to \infty }{\lim }{b}^k={\lambda }_G^k+c^k\left(\text{g}\left(\text{x}\right)+\text{y}-\text{z}\right)=0.$

因为 $\left(a^{\prime },b^{\prime }\right)\ne 0$ 与在 $\bar{x}$ 处满足MPCC-LICQ矛盾，所以 $\left\{\left(a^k,b^k\right)\right\}$ 有界。

不失一般性，设 $\left\{\left(a^k,b^k\right)\right\}$ 收敛于 $\left(\bar{a},\bar{b}\right)$ 设

$\underset{k\to \infty }{\lim }{a}_i^k={\bar{a}}_i,\underset{k\to \infty }{\lim }{b}_i^k={\bar{b}}_i,i=1,\cdots ,m.$

当 $i\in \gamma$ 时， ${\lambda }_H^k=0$ ， $k\to \infty$ ， $c^k\to 0$ 时，即 ${\bar{a}}_i=0$ 。同理，当 $i\in \alpha$ 时，可得 ${\bar{b}}_i=0$ 。由H，G连续可微，对(4.9)取极限，得

$-\nabla f\left(\bar{x}\right)={\displaystyle \underset{i\in \alpha \cup \beta }{\sum }{\bar{a}}_i}H\left(\bar{x}\right)+{\displaystyle \underset{i\in \beta \cup \gamma }{\sum }{\bar{b}}_i}G\left(\bar{x}\right)$ ，

$\nabla f\left(\bar{x}\right)=0.$

即证得 $\bar{x}$ 是问题MPCC(3.6)的W-稳定点。

5. 结论

本文主要针对约束不相容的凸优化问题建立了最小约束违背优化模型。当约束相容时，模型退化为原始问题。当约束不相容时，模型可被重新表述为MPCC问题。并证明了该等价MPCC问题的W-稳定性。将增广拉格朗日方法用于求解该等价问题，证明了该方法生成的点列收敛到该等价问题的W-稳定点。

对于最小约束违背优化，还有许多问题值得研究。当不知道可行域是否为空集时，最小约束违背优化问题总是可行的，这是它的优点。如果约束问题是可行的，那么问题涉及的不可行性度量 $\theta \left(x\right)$ 通常是光滑的，但不是二次可微的，这会带来计算上的困难。本文只处理了最小约束违背的凸优化问题，增广拉格朗日方法能否处理最小约束违背的非凸优化问题需要继续思考和研究。

参考文献

[1]	Byrd, R.H., Curtis, F.E. and Nocedal, J. (2010) Infeasibility Detection and SQP Methods for Nonlinear Optimization. SIAM Journal on Optimization, 20, 2281-2299. https://doi.org/10.1137/080738222
[2]	Burke, J.V., Curtis, F.E. and Wang, H. (2014) A Sequential Quadratic Optimization Algorithm with Rapid Infeasibility Detection. SIAM Journal on Optimization, 24, 839-872. https://doi.org/10.1137/120880045
[3]	Dai, Y., Liu, X. and Sun, J. (2020) A Primal-Dual Interior-Point Method Capable of Rapidly Detecting Infeasibility for Nonlinear Programs. Journal of Industrial & Management Optimization, 16, 1009-1035. https://doi.org/10.3934/jimo.2018190
[4]	戴彧虹, 张立卫. 最小约束违背优化[M]. 北京: 科学出版社, 2023: 223-253.
[5]	Dai, Y.-H. and Zhang, L. (2021) Optimization with Least Constraint Violation. CSIAM Transactions on Applied Mathematics, 2, 551-584. https://doi.org/10.4208/csiam-am.2020-0043
[6]	Chiche, A. and Gilbert, J.C.H. (2016) How the Augmented Lagrangian Algorithm Can Deal with An Infeasible Convex Quadratic Optimization Problem. Journal of Convex Analysis, 23, 425-459.
[7]	Rockafellar, R.T. and Wets, R.J.-B. (1998) Variational Analysis. Springer-Verlag.
[8]	张立卫, 吴佳, 张艺. 变分分析[M]. 北京: 科学出版社, 2013: 100-101.
[9]	Powell, M.J.D. (1969) A Method for Nonlinear Constraints in Minimization Problems. In: Fletcher, R., Ed., Optimization, Academic Press, 283-298.
[10]	Hestenes, M.R. (1969) Multiplier and Gradient Methods. Journal of Optimization Theory and Applications, 4, 303-320. https://doi.org/10.1007/bf00927673
[11]	刘昶. 互补约束优化问题的增广拉格朗日方法[D]: [硕士学位论文]. 大连: 大连理工大学, 2022.