基于值函数内点罚方法的双层规划问题研究

Research on Bi-Level Programming Problem Based on Value-Function-Based Interior-Point Penalty Method

摘要: 本文考虑了一个在实际中有很多应用的双层规划问题，其下层问题带有多个不等式约束。为了开发有效的数值算法，通常需要将双层规划转化为单层优化问题。本文首先提出了罚函数，然后利用罚函数将下层问题的约束函数罚到目标函数得到逼近下层问题的无约束优化问题，并证明该无约束优化问题的最优值函数逼近于原下层问题的最优值函数，从而利用该逼近最优值函数将双层规划问题近似为一系列单层优化问题，并证明该一系列单层优化问题的解收敛于原双层规划的最优解。

Abstract: In this paper, we consider a bi-level programming with many applications in practice, where the lower-level problem comes with multiple inequality constraints. In order to develop efficient nu-merical algorithms, it is often necessary to transform the bi-level programming into a single-level optimization problem. In this paper, we first propose a penalty function, and then use the penalty function to penalize the constraint function of the lower-level problem to the objective function to obtain an unconstrained optimization problem that approximates the lower-level problem. And we prove that the optimal value function of this unconstrained optimization problem approximates the optimal value function of the original lower-level problem. The bi-level programming problem is approximated to a series of single-level optimization problems by using the approximate optimal value function, and the solutions of the series of single-level optimization problems are proved to converge to the optimal solutions of the original bi-level programming.

1. 引言

双层规划问题是一类具有上下两层结构的数学优化问题，它在工程设计、经济均衡、交通运输等方面有着广泛的应用。双层规划问题最初由德国经济学家Stackelberg [1] 于1952年提出，经济学中的委托代理模型(Principal Agent Model)是该问题的一个典型应用。1973年，Bracken和McGill [2] 提出了双层规划问题的数学模型。随后，Candler和Norton [3] 给出了多层规划问题和双层规划问题的正式定义。双层规划是一种具有二层递阶结构的系统优化问题，上层问题和下层问题都有各自的决策变量。双层系统优化研究的是具有两个层次系统的规划与管理问题。上层决策者只是通过自己的决策去指导下层决策者，并不直接干涉下层的决策；而下层决策者只需要把上层的决策作为参数，它可以在自己的可能范围内自由决策。这种决策机制使得每层决策者制定的决策都会互相影响。最终使得每层决策者都得到自己的最优目标值。

上世纪80年代之后，国内外学者开始研究双层规划问题，使双层规划问题在理论、求解算法方面都取得了较大的发展，并且得到了广泛的应用，特别是城市道路交通 [4] [5] [6] [7] 、工程问题 [8] [9] [10] 、经济管理 [11] [12] 以及其他应用领域 [13] [14] 。目前，双层规划问题已成为管理学、数学、经济学等众多领域所关注的一项热门课题。关于双层规划的理论、求解算法和应用等方面的研究工作可以参见一些专著 [15] [16] [17] 和综述性文章 [18] [19] [20] 。

本文考虑如下形式的积极双层规划问题(BP)：

$\begin{array}{l}\left(\text{BP}\right)\text{min}F\left(x,y\right)\\ \text{s}\text{.t}\text{.}y\in S\left(x\right),\\ x\in X,\end{array}$

其中 $S\left(x\right)$ 表示下层问题：

$\begin{array}{l}\left(P_x\right)\text{min}f\left(x,y\right)\\ \text{s}\text{.t}\text{.}y\in Y(\; x\; )\end{array}$

的最优解集， $Y\left(x\right)=\left\{y:g_i\left(x,y\right)\le 0,i=1,2,\cdots ,m,y\in Y\right\}$ ，X和Y分别是 ${ℝ}^{n_1}$ 和 ${ℝ}^{n_2}$ 中的紧子集。 $F,f,g_i\left(i=1,2,\cdots ,m\right):{ℝ}^{n_1}\times {ℝ}^{n_2}\to ℝ$ 是连续可微的函数。令x和y分别表示上层决策者和下层决策者的决策变量。双层规划问题(BP)代表的是两个决策者之间博弈的一种积极形式，其中下层决策者被假定是合作的并且愿意选取 $S\left(x\right)$ 中任意的解作为其决策值。另一种消极方式假定下层决策者不是一定会合作，因此上层决策者要考虑最坏的情况，则产生消极双层规划模型。参见 [21] [22] [23] [24] [25] 了解更多关于积极和消极双层规划模型的细节。

由于分层结构，双层规划问题很难求解，即使是线性情况，双层规划问题也被证明是强NP难的。从连续优化的角度来看，要发展有效的数值算法，通常需要将双层规划转化为单层优化问题。沿着这个方向，学者们提出了几种双层规划的转换方法，其中包括：基于下层解函数的转换、基于下层最优性条件的转换、基于下层最优值函数的转换、基于下层拉格朗日对偶的转换。

基于下层解函数的转换方法要求下层问题的解函数是已知的，在这种情况下，即使上层问题和下层问题都是可微的和凸的，双层规划问题通常即不是可微的，也不是凸的。基于下层最优性条件转换得到的是带有互补约束的数学规划(Mathematical Program with Equilibrium Constraint, MPEC)，然而问题MPEC具有非凸的组合结构，理论上MPEC在任何可行点都不满足MFCQ (Mangasarian-Fromovitz Constraint Qualification)，因此一般的非线性规划理论不能直接应用于MPEC问题。基于下层最优值函数的转换利用下层最优值函数将双层规划问题转换为单层优化问题，但最优值函数没有解析表达式，一般很难评估，并且最优值函数是非光滑的，该转换模型在其所有可行点都不满足非光滑的MFCQ，因此求解相对困难。基于下层拉格朗日对偶的转换方法使用了正则约束拉格朗日对偶函数，但它存在一些缺点，基于对偶的转换中使用的正则约束拉格朗日对偶函数是通过极小化某个强凸函数来定义的，因此一般没有解析表达式。

本文所考虑的是下层问题带有多个不等式约束的双层规划问题，所以针对下层问题采用了内点罚方法来逼近下层问题。首先提出了罚函数 $\varphi \left(x,y\right):={\displaystyle \underset{i=1}{\overset{m}{\sum }}{g}_i\left(x,y\right)\ln \left\{-g_i\left(x,y\right)\right\}}$ 。然后利用罚函数 $\varphi \left(x,y\right)$ 将下

层问题的约束函数罚到目标函数得到逼近下层问题的无约束优化问题，并证明该无约束优化问题的最优值函数逼近于原下层问题的最优值函数，从而利用该逼近最优值函数将双层规划问题近似为一系列单层规划问题，并证明该一系列单层规划问题的解收敛于原双层规划问题的最优解。

本文组织如下，在第2节中，将介绍一些双层规划转换为单层规划的方法。在第3节中，探讨了用基于值函数内点罚方法得到的逼近双层规划问题的单层优化问题，并证明了该单层优化问题的解收敛于原双层规划问题的解。最后是结论和展望。

2. 双层规划的转换方法

本节将详细介绍一些现有的双层规划转换为单层规划的方法。

2.1. 基于下层解函数的转换

如果对任意给定的 $x\in X$ ，下层规划问题( $P_x$ )有唯一的最优解 $y\left(x\right)$ ，那么双层规划问题(BP)可以被等价地转化为单层优化问题(SP)：

$\begin{array}{l}\left(\text{SP}\right)\text{min}F\left(x,y\left(x\right)\right)\\ \text{s}\text{.t}\text{.}x\in X.\end{array}$

这种转换需要严格的条件，以确保下层最优解的存在性。在下层问题解函数 $y\left(x\right)$ 已知的情况下，即使下层问题和上层问题都是可微和凸的，上述问题中的目标函数一般即不可微也不凸。因此这种方法通常难以应用于求解双层规划。

2.2. 基于下层最优性条件的转换

当下层问题关于变量y是凸问题时，常用的方法是用下层问题的Karush-Kuhn-Tucker (KKT)条件替换下层问题的最优解集，得到带有互补约束的数学规划问题(Mathematical Program with Equilibrium Constraints，简称MPEC)：

$\begin{array}{l}\left(\text{KP}\right)\text{min}F\left(x,y\right)\\ \text{s}\text{.t}\text{.}x\in X,\\ \text{0}\le u\perp g\left(x,y\right)\le 0,\\ {\nabla }_{y}f\left(x,y\right)+{\nabla }_{y}g\left(x,y\right)u=0.\end{array}$

由于问题(KP)的约束中带有互补约束，因此它属于MPEC问题。

一方面，尽管原双层规划问题(BP)的全局最优解与其对应的问题(KP)的全局最优解重合，但在下层规划存在多个乘子的情况下，它们的局部最优解可能不相同 [26] 。此外，Ye [27] 给出了一个实例，揭示了原双层规划的最优解甚至可能不是其对应问题(KP)的一个稳定点。

另一方面，MPEC不是一个普通的约束优化问题，因为它的可行域具有组合结构，而且它在任何可行点上都不能满足MFCQ，这意味着非线性规划中成熟的优化算法在求解MPEC时可能并不稳定。在过去的几十年里，人们提出了许多求解MPEC的逼近算法，包括松弛和光滑算法、罚函数算法、内点算法、隐式规划算法、非光滑算法等。读者可参考 [28] - [33] 和其中的参考文献，以获得关于MPEC理论和数值算法的最新发展的更多细节。

2.3. 基于下层最优值函数的转换

另一种方法是利用下层最优值函数 $v\left(x\right):=\underset{y\in Y\left(x\right)}{\min }f\left(x,y\right)$ ，将双层规划问题(BP)转换为单层优化问题(VP)：

$\begin{array}{l}\left(\text{VP}\right)\text{min}F\left(x,y\right)\\ \text{s}\text{.t}\text{.}f\left(x,y\right)-v\left(x\right)\le 0,\\ x\in X,y\in Y\left(x\right).\end{array}$

该转换首次被Outrata [34] 提出，在通常情况下，该转换利用的值函数 $v\left(x\right)$ 是非光滑函数，Mordukhovich等人 [35] 研究了值函数 $v\left(x\right)$ 的局部利普希茨连续性，并建立了最优性条件。Ye等人 [36] 以及Dempe等人 [21] [37] 利用下层最优值函数对双层规划问题研究了各种最优性条件和约束规范。尽管问题(VP)是一个单层优化问题，但由于下层最优值函数 $v\left(x\right)$ 没有解析表达式，一般不可微，显然问题(VP)不是一个正常的约束优化问题。此外，问题(VP)中的不等式约束实际上是一个等式约束，因此非光滑MFCQ在每个可行点上都不满足( [36] ，命题3.2)。因此，不能用现有的优化算法直接求解问题(VP)。受半无限规划研究的激励，Xu等人 [38] [39] 考虑了一个具有紧下层可行域的简单双层规划，并提出了一些利用积分熵函数逼近下层最优值函数的逼近方法。

值函数模型的最优性理论相对完备，然而由于其所有可行点都不满足非光滑的MFCQ，因此求解相对困难，算法大多集中在特殊问题的求解上，例如线性问题、凸问题等。Ye和Zhu [40] 结合MPEC模型和值函数模型，将最优解集 $S\left(x\right)$ 替换为：

$S\left(x\right)=\left\{y\in Y:\begin{array}{c}f\left(x,y\right)-v\left(x\right)\le 0\\ g\left(x,y\right)\le 0,\exists u\ge 0,\text{s}\text{.t}.\langle g\left(x,y\right),u\rangle =0\end{array}\right\},$

得到了更容易满足部分平稳性条件的联合模型(CP)：

$\begin{array}{l}\left(\text{CP}\right)\text{min}F\left(x,y\right)\\ \text{s}\text{.t}\text{.}f\left(x,y\right)-v\left(x\right)\le 0,\\ {\nabla }_{y}f\left(x,y\right)+u{\nabla }_{y}g\left(x,y\right)=0,\\ g\left(x,y\right)\le 0,u\ge 0,\langle g\left(x,y\right),u\rangle =0,\\ x\in X,y\in Y.\end{array}$

求解问题(CP)的好处有两个。一方面，由于约束条件 $f\left(x,y\right)-v\left(x\right)\le 0$ 的出现，问题(BP)的局部最优解一定是问题(CP)的KKT点，但不一定是问题(KP)的KKT点。另一方面，由于一阶条件 ${\nabla }_{y}f\left(x,y\right)+u{\nabla }_{y}g\left(x,y\right)=0$ 的出现，问题(CP)的最优性必要条件要比问题(VP)更容易成立，这是因为其乘子有更多的选择。

2.4. 基于下层对偶问题的转换

该方法是利用下层问题的对偶问题将双层规划问题转换为单层问题，最近Ouattara和Aswani [41] 针对下层问题为凸规划的双层规划问题，构造了可微的对偶函数 $\nu \left(x,u\right)$ ：

$\nu \left(x,u\right):=\underset{y}{\min }\left\{f\left(x,y\right)+u^{{\rm T}}g\left(x,y\right):y\in \bar{Y}\right\},$

并展示了下面的基于对偶的转换：

$\begin{array}{l}\left(\text{LDP}\right)\text{min}F\left(x,y\right)\\ \text{s}\text{.t}\text{.}f\left(x,y\right)\le \nu \left(x,u\right),\\ g\left(x,y\right)\le 0,u\ge 0,\\ x\in X.\end{array}$

然后证明了(LDP)与原双层规划的等价性，并引入了正则项 ${\nu }_{\delta }\left(x,u\right):=\underset{y}{\min }\left\{\delta {\Vert y\Vert }^2+f\left(x,y\right)+u^{{\rm T}}g\left(x,y\right):y\in \bar{Y}\right\}$ ，来确保约束规范成立。

2021年Li等人 [42] 利用下层问题( $P_x$ )的Wolfe对偶问题：

$\begin{array}{l}\left({\text{WD}}_x\right)\underset{z,u}{\max }L\left(x,z,u\right)\\ \text{s}\text{.t}\text{.}{\nabla }_{z}L\left(x,z,u\right)=0,\\ u\ge 0.\end{array}$

将双层规划问题转化为单层问题(WDP)：

$\begin{array}{l}\left(\text{WDP}\right)\text{min}F\left(x,y\right)\\ \text{s}\text{.t}\text{.}f\left(x,y\right)-L\left(x,z,u\right)\le 0,\\ {\nabla }_{z}L\left(x,z,u\right)=0,u\ge 0,\\ x\in X,y\in Y\left(x\right).\end{array}$

其中 $L\left(x,z,u\right):=f\left(x,z\right)+u^{{\rm T}}g\left(x,z\right)$ 。并且证明了(WDP)与原双层规划的全局解等价，在满足某种约束规范的条件下局部解也是等价的。

3. 双层规划的近似问题

在本节中，假设值函数 $v\left(x\right)$ 是利普希茨连续的。有很多文献已经研究了值函数的利普希茨连续性，下面的命题3.1是Clarke ( [43] , Theorem 6.5.2)的一个特例，在文献 [44] 中可以找到值函数利普希茨连续性的其他较弱的充分条件以及其次微分的估计。

命题3.1：假设集值映射 $Y\left(x\right)$ 在 $x^{*}$ 附近一致有界，即存在 $x^{*}$ 的邻域U使得集合 ${\displaystyle {\cup }_{x\in U}Y\left(x\right)}$ 是有界的。如果MFCQ成立在y对任意 $y\in S\left(x^{*}\right)$ ，那么最优值函数 $v\left(x\right)$ 在 $x^{*}$ 附近利普希茨连续。

为了证明结论，给出下面的假设。

假设3.1：对于 $x\in X$ ，至少存在一个 $y\left(x\right)\in S\left(x\right)$ 使得 $g_i\left(x,y\left(x\right)\right)<0,i=1,2,\cdots ,m$ 。

为了处理包含约束函数的下层规划，我们定义了下面的内点罚函数：

$\varphi \left(x,y\right)={\displaystyle \underset{i=1}{\overset{m}{\sum }}{g}_i\left(x,y\right)\ln }\left\{-g_i\left(x,y\right)\right\},$

考虑下层问题的罚问题：

$\begin{array}{l}\left({\text{LPP}}_x\right)\text{min}{\theta }^{\epsilon }\left(x,y\right)\\ \text{s}\text{.t}\text{.}y\in Y,\end{array}$

其中 ${\theta }^{\epsilon }\left(x,y\right):=f\left(x,y\right)-\epsilon {\displaystyle \underset{i=1}{\overset{m}{\sum }}{g}_i\left(x,y\right)\ln \left(-g_i\left(x,y\right)\right)}$ 。注意我们假设 $t\ln t=\infty$ 当 $t\le 0$ 。令 $v^{\epsilon }\left(x\right)$ 是 ${\theta }^{\epsilon }\left(x,y\right)$ 在 $y\in Y$ 上的最优值，即

$v^{\epsilon }\left(x\right):=\underset{y\in Y}{\inf }{\theta }^{\epsilon }\left(x,y\right),$

$S^{\epsilon }\left(x\right)$ 是 ${\theta }^{\epsilon }\left(x,y\right)$ 在 $y\in Y$ 上的最优解集，即 $v^{\epsilon }\left(x\right)={\theta }^{\epsilon }\left(x,y^{\epsilon }\left(x\right)\right),y^{\epsilon }\left(x\right)\in S^{\epsilon }\left(x\right)$ 。注意到下层问题的罚问题( ${\text{LPP}}_x$ )的可行域是 $Y^o\left(x\right)=\left\{y\in Y:g_i\left(x,y\right)<0,i=1,2,\cdots ,m\right\}\subseteq Y\left(x\right)$ 。于是有 $v^{\epsilon }\left(x\right)=\underset{y\in Y^o\left(x\right)}{\inf }{\theta }^{\epsilon }\left(x,y\right)$ 。

定理3.1：在假设3.1成立的条件下，对任意的 $x\in X$ 以及任意的 $\epsilon >0$ ，存在正的常数N使得

$v\left(x\right)-mN\epsilon \le v^{\epsilon }\left(x\right)\le v\left(x\right)+mN\epsilon$ (1)

成立。此外，如果下层规划( $P_x$ )对任意的 $y\in S\left(x\right)$ 都满足MFCQ，有

$\underset{\epsilon \to 0,z\to x}{\lim }{v}^{\epsilon }\left(z\right)=v\left(x\right)$ (2)

成立。

证：对任意 $x\in X$ 和 $y\in Y$ ，根据函数 $g_i\left(x,y\right)$ 在紧集 $X\times Y$ 上的连续性，存在正的常数N使得对任意 $i\in \left\{1,2,\cdots ,m\right\}$ 满足 $g_i\left(x,y\right)<0$ 的 $\left(x,y\right)\in X\times Y$ ，有

$\left|-g_i\left(x,y\right)\ln \left(-g_i\left(x,y\right)\right)\right|\le N$ (3)

成立。根据条件(3)，得到对于满足 $g_i\left(x,y\right)<0$ 的任意 $\left(x,y\right)\in X\times Y$ ，有

$f\left(x,y\right)-mN\epsilon \le {\theta }^{\epsilon }\left(x,y\right)=f\left(x,y\right)+\epsilon {\displaystyle \underset{i=1}{\overset{m}{\sum }}\left(-g_i\left(x,y\right)\right)\ln \left(-g_i\left(x,y\right)\right)}\le f\left(x,y\right)+mN\epsilon$ (4)

成立。一方面，我们得到条件(1)的左边，因为

$\begin{array}{l}{v}^{\epsilon }\left(x\right):=\underset{y\in Y^{\circ }(x)}{\inf }{\theta }^{\epsilon }\left(x,y\right)\\ \ge \underset{y\in Y\left(x\right)}{\inf }\left\{f\left(x,y\right)-mN\epsilon \right\}\\ =v\left(x\right)-mN\epsilon .\end{array}$

另一方面，根据条件(4)和假设3.1，得到

$\begin{array}{l}{v}^{\epsilon }\left(x\right)\le \underset{y\in Y^{\circ }\left(x\right)}{\inf }\left\{f\left(x,y\right)+mN\epsilon \right\}\\ =v\left(x\right)+mN\epsilon .\end{array}$

于是条件(1)得证。

根据命题3.1知，最优值函数 $v\left(x\right)$ 是利普希茨连续的，因此对任意的 $x\in X$ 有 $\underset{z\to x}{\lim }v\left(z\right)=v\left(x\right)$ 成立。那么根据夹逼原则，有条件(2)成立。证毕。

定理3.2：在假设3.1成立的条件下，如果下层规划( $P_x$ )对任意的 $y\in S\left(x\right)$ 都满足MFCQ，则对任意的 $x\in X$ ，有

$\underset{\epsilon \to 0,z\to x}{\lim \sup }{S}^{\epsilon }\left(z\right)\subseteq S(\; x\; )$

成立。

证：对任意的 $y^{\epsilon }\left(z\right)\in S^{\epsilon }\left(z\right)$ ，根据Y的紧性，不失一般性，假设 $\underset{\epsilon \to 0,z\to x}{\lim }{y}^{\epsilon }\left(z\right)=\bar{y}\in Y$ 。因为 $y^{\epsilon }\left(z\right)\in S^{\epsilon }\left(z\right)$ ，那么对任意的 $i\in \left\{1,2,\cdots ,m\right\}$ ，有 $g_i\left(z,y^{\epsilon }\left(z\right)\right)<0$ 。根据函数 $g_i\left(i\in \left\{1,2,\cdots ,m\right\}\right)$ 的连续性，得到

$\underset{\epsilon \to 0,z\to x}{\lim }{g}_i\left(z,y^{\epsilon }\left(z\right)\right)=g_i\left(x,\bar{y}\right)\le 0,\forall i\in \left\{1,2,\cdots ,m\right\}.$

根据条件(3)，对于满足 $g_i\left(x,y\right)<0$ 的任意 $\left(x,y\right)\in X\times Y$ ， ${\displaystyle \underset{i=1}{\overset{m}{\sum }}-g_i\left(x,y\right)\ln \left(-g_i\left(x,y\right)\right)}$ 是有界的。于是 $\underset{\epsilon \to 0,z\to x}{\lim }\epsilon {\displaystyle \underset{i=1}{\overset{m}{\sum }}-g_i\left(z,y^{\epsilon }\left(z\right)\right)\ln \left(-g_i\left(z,y^{\epsilon }\left(z\right)\right)\right)}=0$ 。

根据定理3.1，得到

$\begin{array}{l}v\left(x\right)=\underset{\epsilon \to 0,z\to x}{\lim }{\theta }^{\epsilon }\left(z,y^{\epsilon }\left(z\right)\right)\\ =\underset{\epsilon \to 0,z\to x}{\lim }f\left(z,y^{\epsilon }\left(z\right)\right)+\epsilon {\displaystyle \underset{i=1}{\overset{m}{\sum }}-g_i\left(z,y^{\epsilon }\left(z\right)\right)}\ln \left(-g_i\left(z,y^{\epsilon }\left(z\right)\right)\right)\\ =\underset{\epsilon \to 0,z\to x}{\lim }f\left(z,y^{\epsilon }\left(z\right)\right)+\underset{\epsilon \to 0,z\to x}{\lim }\epsilon {\displaystyle \underset{i=1}{\overset{m}{\sum }}-g_i\left(z,y^{\epsilon }\left(z\right)\right)}\ln \left(-g_i\left(z,y^{\epsilon }\left(z\right)\right)\right)\\ =f\left(x,\bar{y}\right).\end{array}$

因此由 $v\left(x\right)=f\left(x,\bar{y}\right),g_i\left(x,\bar{y}\right)\le 0,\forall i\in \left\{1,2,\cdots ,m\right\}$ 以及 $\bar{y}\in Y$ ，得到 $\bar{y}\in S\left(x\right)$ 。证毕。

逼近问题(VP)用问题( ${\text{VP}}^{\epsilon }$ )：

$\begin{array}{l}\left({\text{VP}}^{\epsilon }\right)\text{min}F\left(x,y\right)\\ \text{s}\text{.t}\text{.}f\left(x,y\right)-v^{\epsilon }\left(x\right)\le {\epsilon }^{\prime }\text{,}\\ g_i\left(x,y\right)\le 0,i=1,2,\cdots ,m,\\ \left(x,y\right)\in X\times Y.\end{array}$

令 ${\epsilon }^{\prime }>mN\epsilon$ ，并且 $\epsilon \to 0$ 时， ${\epsilon }^{\prime }\to 0$ 。

定理3.3：在假设3.1成立的条件下，对每个 $\epsilon >0$ 和 $\delta >0$ ，如果 $\left(x_{\delta }^{\epsilon },y_{\delta }^{\epsilon }\right)$ 是问题( ${\text{VP}}^{\epsilon }$ )的一个 $\delta$ -解，即对于问题( ${\text{VP}}^{\epsilon }$ )的任意可行点 $\left(x,y\right)$ ， $F\left(x,y\right)$ 不小于 $F\left(x_{\delta }^{\epsilon },y_{\delta }^{\epsilon }\right)-\delta$ 。则当 $\epsilon$ 和 $\delta$ 趋于0时，序列 $\left\{\left(x_{\delta }^{\epsilon },y_{\delta }^{\epsilon }\right)\right\}$ 的任意聚点是双层规划(BP)的最优解。

证：不失一般性，假设 $\underset{\epsilon \searrow 0,\delta \searrow 0}{\lim }\left(x_{\delta }^{\epsilon },y_{\delta }^{\epsilon }\right)=\left(x^{*},y^{*}\right)$ 。因为 $\left(x_{\delta }^{\epsilon },y_{\delta }^{\epsilon }\right)$ 对于问题( ${\text{VP}}^{\epsilon }$ )是可行的，于是有

$f\left(x_{\delta }^{\epsilon },y_{\delta }^{\epsilon }\right)-v^{\epsilon }\left(x_{\delta }^{\epsilon }\right)\le {\epsilon }^{\prime },\left(x_{\delta }^{\epsilon },y_{\delta }^{\epsilon }\right)\in \left(X\times Y\right),g_i\left(x_{\delta }^{\epsilon },y_{\delta }^{\epsilon }\right)<0,i\in \left\{1,2,\cdots ,m\right\}.$

对上述条件取极限 $\epsilon \searrow 0,\delta \searrow 0$ ，得到 $f\left(x^{*},y^{*}\right)-v\left(x^{*}\right)\le 0,\left(x^{*},y^{*}\right)\in \left(X\times Y\right)$ 。根据函数 $g_i\left(i\in \left\{1,2,\cdots ,m\right\}\right)$ 的连续性，对任意的 $i\in \left\{1,2,\cdots ,m\right\}$ ，有 $g_i\left(x^{*},y^{*}\right)\le 0$ 成立。于是 $\left(x^{*},y^{*}\right)$ 是问题(VP)的可行点。

假设 $\left(x^{*},y^{*}\right)$ 不是问题(VP)的一个最优解，则一定存在一个可行点 $\left(\bar{x},\bar{y}\right)\ne \left(x^{*},y^{*}\right)$ 使得

$F\left(\bar{x},\bar{y}\right)<F\left(x^{*},y^{*}\right)$ (5)

成立。因为 $\left(\bar{x},\bar{y}\right)$ 是问题(VP)的可行点，因此有 $f\left(\bar{x},\bar{y}\right)=v\left(\bar{x}\right)$ 。根据(1)，得到

$f\left(\bar{x},\bar{y}\right)-v^{\epsilon }\left(\bar{x}\right)\le f\left(\bar{x},\bar{y}\right)-v\left(\bar{x}\right)+mN\epsilon =mN\epsilon \le {\epsilon }^{\prime }.$

于是 $\left(\bar{x},\bar{y}\right)$ 是问题( ${\text{VP}}^{\epsilon }$ )的可行点。

因为 $\left(x_{\delta }^{\epsilon },y_{\delta }^{\epsilon }\right)$ 是问题( ${\text{VP}}^{\epsilon }$ )的一个 $\delta$ -解， $\left(\bar{x},\bar{y}\right)$ 是问题( ${\text{VP}}^{\epsilon }$ )的可行点，于是有

$F\left(\bar{x},\bar{y}\right)\ge F\left(x_{\delta }^{\epsilon },y_{\delta }^{\epsilon }\right)-\delta$

成立。令 $\epsilon$ 和 $\delta$ 趋于0，得到

$F\left(\bar{x},\bar{y}\right)\ge F\left(x^{*},y^{*}\right).$

这与(5)式矛盾，因此 $\left(x^{*},y^{*}\right)$ 是问题(VP)的一个最优解。证毕。

4. 结论与展望

本文考虑了一类下层问题带有多个不等式约束的双层规划问题。本文首先利用罚函数将下层问题的约束函数罚到目标函数得到逼近下层问题的无约束优化问题，并证明该无约束优化问题的最优值函数逼近于原下层问题的最优值函数，从而利用该逼近最优值函数将双层规划问题近似为一系列单层规划问题，最后得到该一系列单层规划问题的解收敛于原双层规划的最优解。从而可以通过求解该逼近双层规划的单层优化问题进而求解双层规划问题，因此之后对该问题的求解方法方面可以进入深入研究。

基金项目

国家自然科学基金：(11901556, 12071342)；河北省自然科学基金：(A2020202030)。