http://www.ma-xy.com
目录
第一章 多级规划 1
1.1 问题的引入与分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 模型规范化和基本理论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 规范化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 研究背景与现状 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 二层单目标线性规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4
二层线性规划的有效解
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.1 最优解的有效化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 下层多追随二层线性规划 (有效极点法) . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 二层非线性规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.7 一般二层非线性规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7.1 二层非线性规划更一般的模型 . . . . . . . . . . . . . . . . . . . . . . . . . 13
1
http://www.ma-xy.com
第一章 多级规划
1.1 问题的引入与分析
价格控制问题是一类具有实际背景的二层规划，其模型如下
max a
T
x + b
T
y
s.t. x ⩾ 0
y为如下问题解
max
y
x
T
y
s.t. Ax + By ⩽ p
y ⩾ 0
其中：a, x, b, y ∈ R
n
, p ∈ R
m
，A, B ∈ R
m×n
。
上面模型的意义是：(1) 上级决策者决定下级决策者的目标函数 x
T
y 中的价值函数 x，以
优化自己的目标函数 a
T
x + b
T
y；(2) 下级决策者决定变量 y，在上级决策者决定了价格策略 x
后，优化自己的目标函数 x
T
y，而上级决策者根据下级作出的反应进一步调查，以使自己的目标
a
T
x + b
T
y 最小。
1
http://www.ma-xy.com
1.2 模型规范化和基本理论 第一章 多级规划
1.2 模型规范化和基本理论
1.2.1 规范化
根据上面的价格控制问题，写出多级规划 (GMLP) 的一般形式
min f
1
(x
1
, x
2
, · · · , x
l
)
s.t. x = (x
1
, x
2
, · · · , x
l
) ∈ X
1
, 且(x
2
, x
3
, · · · , x
l
)解
min f
2
(x
1
, x
2
, · · · , x
l
)
s.t. x ∈ X
2
, 且(x
3
, x
4
, · · · , x
l
)解
· · ·
min f
l
(x
1
, x
2
, · · · , x
l
)
s.t. x ∈ X
l
当目标函数 f
1
, f
2
, · · · , f
l
中含有向量值函数时，相应的问题为多层多目标规划问题。特别地，
l = 2 时，上述问题称为二层 (双级) 规划 (bilevel programming)。当 f
1
, f
2
为线性函数且 X
1
, X
2
为多面体时，GMLP 称为线性二层规划。类似于单层规划，根据目标函数 f
1
, f
2
为向量值函数或
者单值函数，二层规划可分为：上层为单目标而下层为多目标的二层规划；上层为多目标而下层
为单目标；或者上下层均为多目标的二层规划模型。
1.2.2 研究背景与现状
1977 年 Candler 在研究奶制品工业模型和墨西哥农业模型的报告中首次提出了多层规划这
一术语。其实早在 1973 年 Bracken 和 Mcqill 就提出了二层规划和多层规划的模型，并讨论了此
类问题的性质和求解，这种讨论为二层线性规划几何性质的研究和算法设计提供了理论基础。上
世纪 70 年代，德国经济学家 StaCkelberg 提出了寡头市场模型—StaCkelberg 模型
¬
，在该模型
中，决策是贯序的，主导产业先走一步，因而占有优势。
上世纪 80 年代末，许多学者对多层规划进行了较深入的研究，得到了一些较好的结论。如：
当没有上层约束条件时，二层规划问题的可行集是闭连通集，且最优解在约束区域的某个极点达
到。并且有文献指出，求解一个线性二层规划问题 (包括验证一个局部最优解是否是全局最优解)
是一个 NP-难问题。利用这些性质，人们提出了许多解线性二次规划问题的算法。
90 年代，二层规划横向、纵向问题的研究也更加深入：下层有多个子问题的二层规划、多层
规划、多层混合整数规划，下层以最优值反应上层的二层规划、二层多目标规划及有平衡约束的
数学规划等方向都取得了许多成果。
在国内，多层规划的研究在 90 年代初才引起关注。较早从事研究的单位有：东南大学、中
科院系统所和自动化所、湘潭大学、西南交大、天津大学和西安电子科技大学等。
但是，目前为止，研究较多的仍为二层规划。多层规划问题本质上的非凸非可微使得其研究
较为困难。就二层规划而言，其几何性质比熟知的单层数学规划复杂得多，主要表现在：1、约束
¬
它是三个经典的寡头市场模型之一
http://www.ma-xy.com 2 http://www.ma-xy.com
http://www.ma-xy.com
第一章 多级规划 1.3 二层单目标线性规划
的嵌套本性；2、可行集一般不具备凸性和闭性，有上层约束时还可能不连通；3、内在的非光滑
性因下层问题含有参数，其最优解以参数为自变量形成的映射一般非 F r´echet 可微，由此导致二
层规划的非光滑性质；4、下层问题的多解性加大了二层规划的研究难度 5.NP-难的计算复杂性。
因而，对多层规划研究大多局限于二层规划。下面，介绍一些不同类型二层规划的求解理论。
1.3 二层单目标线性规划
考虑如下的二层线性规划 (BLP)
max
x
F (x, y) = a
T
x + b
T
y
s.t. y为如下问题解
max
y
f(x, y) = c
T
x + d
T
y
s.t. Ax + By ⩽ r
x, y ⩾ 0
其中：F (x, y), f (x, y) 分别为 BLP 的上层和下层目标函数。x, a, c ∈ R
n
1
，y, b, d ∈ R
n
2
，A ∈ R
m×n
1
，
B ∈ R
m×n
2
，r ∈ R
m
。x, y 分别是上、下层的决策变量 (优化变量)。
首先，我们给出二层线性规划 BLP 的一些基本概念：
定义 BLP 的约束域为
Ω = {(x, y)|Ax + By ⩽ r, x ⩾ 0, y ⩾ 0}
定义 BLP 下层规划问题的约束域为
Ω = {y|By ⩽ r − Ax, y ⩾ 0, ∀x ⩾ 0}
定义 BLP 约束域在上层决策中的投影为
S = {x|∃y ⩾ 0, s.t.Ax + By ⩽ r, x ⩾ 0}
定义 ∀x ⩾ 0，BLP 的下层规划问题的合理反应集 M (x) = {y|y ∈ arg max{f(x, y), y ∈
Ω(x)}}
定义 BLP
的诱导域：
IR
=
{
(
x, y
)
|
(
x, y
)
∈
Ω
, y
∈
M
(
x
)
}
为了保证优化问题有解，假定 Ω 和 IR 是非空有界的。从二层线性规划的模型来看，其优化
策略应该是：首先，上层对下层宣布自己的决策 x，该决策直接影响下层规划的可行集和目标函
数，下层在此基础上优化，直到上层的目标函数值 F (x, y) 最优为止 (当然，也可能是将 f(x, y)
传递给上层)。
值得注意的是，虽然上下层皆为线性，但由于上层的目标函数决定于下层的解函数。一般来
说，这个解函数不是线性的且不可微。进一步，Bialas 和 Karwan 以实例论证了上层问题的非凸
http://www.ma-xy.com 3 http://www.ma-xy.com
http://www.ma-xy.com
1.3 二层单目标线性规划 第一章 多级规划
性，在研究二层线性规划时，为了给出二层线性规划良好的解的定义，通常假定二层规划的下层
规划问题的解是唯一的。
对于给定的上层决策变量 x ∈ S，下层线性规划 f (x, y) 的求解可以用下式代替为：
max
y
f(x, y) = d
T
y
s.t. By ⩽ r − Ax
y ⩾ 0
(1.1)
而上式 (1.1) 的对偶问题为：
min
u
(r − Ax)
T
u
s.t. B
T
u ⩾ d
u ⩾ 0
由此可知式 (1.1) 存在最优解的充分必要条件是：
By ⩽ r − Ax
B
T
u ⩾ d
(r − Ax)
T
u = d
T
y
y, µ ⩾ 0
有可行解，并且 y 的取值就是 (1.1) 式的最优解。
因此，对于给定的上层决策变量 x ∈ S，下层线性规划解的充分必要条件如上所述。这样，
就把 BLP 转化为如下等价形式的单层规划
max
x,y,u
F (x, y) = a
T
x + b
T
y
s.t.
By ⩽ r − Ax
B
T
u ⩾ d
(r − Ax)
T
u = d
T
y
x, y, u ⩾ 0
记 V
e
= {u|B
T
u ⩾ d, u ⩾ 0} 为下层规划问题的对偶问题的可行解集，根据线性规划理论可
知 V
e
至多存在有限个极点，所以我们可以用单纯性法求得 V
e
的所有极点，记所有极点集为
V = {u
1
, u
2
, · · · , u
l
}。这样，可以把 BLP 转化为如下一系列的线性规划问题：fori = 1, 2, . . . , l
max F (x, y) = a
T
x + b
T
y
s.t.
By ⩽ r − Ax
(r − Ax)
T
u
i
= d
T
y
x, y ⩾ 0
http://www.ma-xy.com 4 http://www.ma-xy.com
http://www.ma-xy.com
第一章 多级规划 1.4 二层线性规划的有效解
可以利用单纯形法求解上述问题。因为假定 Ω 和 IR 是非空有界的，所以对 i ∈ {1, 2, . . . , l}，
上述问题有最优解或者没有可行解。令 I = {1, 2, . . . , l}，如果原 BLP 有最优解，则必存在 i ∈ I，
使得上述问题有最优解，因此 I = ϕ。对于 i ∈ I，令 (x
i
, y
i
) 为上述问题的最优解，则 BLP 的
最优解为使 F (x
k
, y
k
) = max{F (x
i
, y
i
), i ∈ I} 的 (x
k
, y
k
)。
1.4 二层线性规划的有效解
一个双目标规划称为一个二层规划相应的双目标规划，是指该双目标规划的两个目标函数分
别为二层规划的上、下层目标函数，其可行解为二层规划的容许集。如果二层规划的最优解是相
应的双目标规划的 Pareto 有效解，称该最优解为有效最优解。值得一提的是：即使是线性二层
规划，最优解也可能不是有效解。
考虑如下二层线性规划问题
max
x
F (x, y) = a
T
x + b
T
y
s.t. y ∈ arg max{f (x, y) = c
T
x + d
T
y|Ax + By ⩽ r, x, y ⩾ 0}
其中：F (x, y), f (x, y) 为目标函数。上式相应的双目标规划为
max
x,y
(F (x, y), f (x, y))
s.t. Ax + By ⩽ r
x, y ⩾ 0
记 S = {(x, y)|Ax + By ⩽ r, x, y ⩾ 0} 为 BLP 的约容许集，令 S(x) = {y|By ⩽ r −
Ax, 当 x 固定}，记 S
′
= {(¯x, ¯y) ∈ S|f (¯x, ¯y) ⩾ f (¯x, y), ∀y ∈ S(x)} 为 BLP 的可行集。记 S
′′
=
{(¯x, ¯y) ∈ S
′
|F (¯x, ¯y) ⩾ F (¯x, y), ∀(x, y) ∈ S
′
} 为 BLP 的最优解集。(¯x, ¯y ) ∈ S 是双目标规划的
Pareto 有效解 ⇔ 不存在 (x, y) ∈ S 使 F (x, y) ⩾ F (¯x, ¯y)，f (x, y) ⩾ f(¯x, ¯y) 且至少有一个是严格
不等式。
假设 1：容许集 S 有界；假设 2：线性二层规划存在有效最优解。如果 BLP 存在有效最优
解，则其有效最优解可在容许集 S 的顶点达到。
max F (x)
s.t. x ∈ X
y ∈ arg max{f(y)|g(x, y) ⩽ 0, y ∈ Y }
其中：F (x), f (y), g(x, y) 为各个自变量的线性函数，X, Y 为多面体。
命题 (1) 上述问题存在最优解是 Pareto 有效解
。
刘红英. 多层规划的理论与算法研究. 西电. 博文
http://www.ma-xy.com 5 http://www.ma-xy.com
http://www.ma-xy.com
1.4 二层线性规划的有效解 第一章 多级规划
命题 (2) 设 x
∗
∈ D，则 x
∗
是多目标规划 max{f
1
(x), · · · , f
p
(x)|x ∈ D} 有效解的充要条件
是 x
∗
是如下规划的最优解
max
p
∑
i=1
f
i
(x)
s.t.
f
i
(x) ⩾ f
i
(x
∗
)
i = 1, 2, . . . , p
x ∈ D
下面来讨论：当已知一个最优解时，在假设 2 下如何求解有效最优解。记 (¯x, ¯y) 为所得最优
解，利用 Kth-best 算法思想，给出有效最优解的求解算法：
step1. 判断 (¯x, ¯y) 是否为多目标的有效解，若是，输出 (¯x, ¯y)；否则，转到 step2。
step2. 判断 (¯x, ¯y) 是否为 S 的极点，若是，转到 step4；否则，求一个极点最优解，仍记为 (¯x, ¯y)。
step3. 判断 (¯x, ¯y) 是否为多目标规划的有效解，若是，输出 (¯x, ¯y) 并停止；否则，转到 step4。
step4. 记 (x
0
, y
∗
0) = (¯x, ¯y ) 令 i = 0, w = {(x
i
, y
i
)}，T = ϕ
i
。
step5.(更新) 令 w
i
为 (x
i
, y
i
) 的邻接极点集，且满足 F (¯x, ¯y) = F (x
i
, y
i
)，(x, y) ∈ w
i
，令
T = T ∪ {(x
i
, y
i
)}, w = (w ∪ w
i
)/T 。
step6. 令 i = i + 1，取 (x
i
, y
i
) ∈ w 转到 step7。
step7.(可行性检验) 判断 (x
i
, y
i
) 是否为二级规划的可行解，若是，转到 step8；否则，转到 step5。
step8.(有效性检验) 判断 (x
i
, y
i
) 是否为多目标的有效解，若是，输出 (x
i
, y
i
)，且停止；否则，转
到 step5。
以上算法的实质是隐枚举所有使上层目标值等于最优值的约束集 S 的极点，直到搜索到一
个极点是可行的、有效的。其中，step8 的有效性检验利用命题 (2) 的结果来完成。
1.4.1 最优解的有效化
二层规划的可行集 S
′
中存在有效集。对于一个二层规划问题，我们自然希望求得最优解，
如果不易求出，也应该首先考虑在其可行域上，求满足一定条件的次优解。考虑次优解的满足条
件可以为：(1) 次优解是多目标规划的有效解。(2) 次优解是二层规划的可行解。(3) 在所有满足
(1)(2) 的点中求使上层目标值最大的解。对于线性二层规划来说，bard 的有效点算法满足以上条
件。因而，第一种有效点方法采用 bard 的算法。下面，考虑第二种有效化方法。
记
ˆ
S = {(x, y) ∈ S|f (x, y) ⩾ f (¯x, ¯y), ∀(x, y) ∈ S}，其中 (¯x, ¯y) 为二层规划的最优解。
max F (x, y)
s.t. (x, y) ∈
ˆ
S
上述问题的解中存在一点是多目标规划的有效解。取上述问题的解与多目标规划的有效解的
交集中的点作为有效化结果，称之为第二种有效化方法，记 N S = {(x, y)|(x, y) ∈ S, F (x, y) ⩾
F (¯x, ¯y), f (x, y) ⩾ f (¯x, ¯y), }，其中 (¯x, ¯y) 为二层规划的最优解。
http://www.ma-xy.com 6 http://www.ma-xy.com
http://www.ma-xy.com
第一章 多级规划 1.5 下层多追随二层线性规划 (有效极点法)
1.5 下层多追随二层线性规划 (有效极点法)
考虑如下二层规划问题：
max
x
F (x, y
1
, y
2
, · · · , y
n
) = a
T
x +
n
∑
i=1
b
T
i
y
i
s.t. Ax +
n
∑
i=1
B
i
y
i
⩽ s
y
i
(i = 1, 2, . . . , n)是下面问题的解
max
y
i
f
i
(x, y
i
) = c
T
i
x + d
T
i
y
i
s.t. C
T
i
x + D
i
y
i
⩽ t
i
x, y
i
⩾ 0
其中：F (x, y
1
, y
2
, · · · , y
n
) 是上层目标函数，f
i
(x, y) 为下层目标函数，表示多个下层决策者。x, a ∈
R
n
，b
i
, y
i
∈ R
n
i
，s ∈ R
p
i
，t
i
∈ R
q
i
，c
i
∈ R
n
，d
i
∈ R
n
i
，B
i
∈ R
p
i
×n
i
，C
i
∈ R
q
i
×n
，D
i
∈ R
q
i
×n
i
，
A ∈ R
n×n
。x, y
i
分别是上、下层的决策变量。
经过和 BLP(二级线性规划) 相似的处理，我们可以将多追随二层线性规划问题转化为如下
的单层线性规划问题：当上层决策变量 x ∈ S 给定后，下层问题解存在唯一性的充分必要条件为
C
i
x + D
i
y
i
⩽ t
i
w
T
i
D
i
⩾ d
i
w
T
i
(t
i
− C
i
x) ⩾ d
T
i
y
i
w
i
⩾ 0
y
i
⩾ 0
i = 1, 2, . . . , n
有可行解，并且取值 (y
1
, y
2
, . . . , y
n
) 为下层问题的最优解。
多追随二层线性规划的等价单层线性规划问题：
max
x,y
1
,y
2
,··· ,y
n
w
1
,w
2
,··· ,w
n
F (x, y
1
, y
2
, · · · , y
n
) = a
T
x +
n
∑
i=1
b
T
i
y
i
s.t.
Ax +
n
∑
i=1
B
i
y
i
⩽ s
i
C
i
x + D
i
y
i
⩽ t
i
w
T
i
D
i
⩾ d
i
w
T
i
(t
i
− C
i
x) ⩾ d
T
i
y
i
x ⩾ 0, w
i
⩾ 0, y
i
⩾ 0
i = 1, 2, . . . , n
http://www.ma-xy.com 7 http://www.ma-xy.com
http://www.ma-xy.com
1.6 二层非线性规划 第一章 多级规划
记上述问题的下层第 i 个规划的对偶可行解集为 W
t
i
= {w
i
|w
T
i
D
i
⩾ d
i
, w
i
⩾ 0}。下层第 i
个规划的对偶可行解集极点集为 w
i
(含有限个点)。
定义 存在 n 个下层规划的对偶可行解集极点集 w
1
, w
2
, . . . , w
n
，则 w
1
, w
2
, . . . , w
n
的笛卡尔
积定义为：
W = w
1
× w
2
× · · · × w
n
= {w
j
|j = 1, 2, . . . , t}
其中：w
j
= ( w
j
1
, w
j
2
, . . . , w
j
n
)，且 w
j
i
∈ W
i
(i = 1, 2, . . . , n)。
根据线性规划理论可知，下层 n 个规划的对偶可行解集 w
t
i
(i = 1, 2, . . . , n) 分别至多存在有
限个极点，同时，可以利用线性规划方法求解出它们所有极点。于是，可得上述问题的对偶可行解
极点集 w
1
, w
2
, . . . , w
n
的笛卡尔积 W 。又因为 LP 在可行域非空的情况下，若线性规划存在有限
最优解，则目标函数的最优值在某极点上达到。假设 W 中有 t 个元素，即 W = (w
1
, w
2
, · · · , w
t
)，
根据 w
1
, w
2
, . . . , w
n
的笛卡尔积定义，可以把上述问题转化为 t 个单层线性规划问题：for j = 1,
2, ..., t
max
x,y
1
,y
2
,··· ,y
n
F (x, y
1
, y
2
, · · · , y
n
) = a
T
x +
n
∑
i=1
b
T
i
y
i
s.t.
Ax +
n
∑
i=1
B
i
y
i
⩽ S
i
C
i
x + D
i
y
i
⩽ t
i
w
jT
i
(t
i
− C
i
x) = d
T
i
y
i
w
j
i
⩾ 0, y
i
⩾ 0
i = 1, 2, . . . , n
因为假定 Ω 和 IR(BLP 定义下的推广) 是非空有界的，所以对于 j ∈ {1, 2, . . . , t}，上述
问题有最优解或者没有可行解。令 I ∈ {1, 2, . . . , t}，上述问题有最优解或者没有可行解。令
I = {1, 2, . . . , l}，如果原多追随二层规划有最优解，则必存在 j ∈ I，使得上述问题有最优解。因
此 I = ϕ。对于 j ∈ I，令 (x
j
, y
j
) 为上述问题的最优解，则下层多追随二层线性规划的最优解为
使 F (x
k
, y
k
) = max{F (x
j
, y
j
), j ∈ I} 的 (x
k
, y
k
)。
1.6 二层非线性规划
首先讨论二层规划上层为非线性目标，下层为线性规划的二层非线性规划问题。利用罚函数
法进行求解。其次，对一般的非线性规划做简单介绍，利用 KKT 条件和 Lagrange 函数，把二
层非线性规划等价转化为一个单层非线性规划，然后进行求解。
http://www.ma-xy.com 8 http://www.ma-xy.com
http://www.ma-xy.com
第一章 多级规划 1.6 二层非线性规划
考虑如下二层非线性规划
min
x
F (x, y)
s.t. G(x, y) ⩽ 0
x ⩾ 0
y是如下规划问题的解
min
y
f(x, y) = c
T
2
x + d
T
2
y
s.t. Ax + By ⩽ b
y
⩾
0
其中：x ∈ X ⊂ R
n
, y ∈ Y ⊂ R
m
是决策变量。F : X ×Y → R 为非线性可微函数，f : X ×Y → R
为线性函数，b ∈ R
p
，d
1
, d
2
∈ R
m
，c
T
1
, c
T
2
∈ R
n
，G : R
n
× R
m
→ R
k
，上述问题的下层规划等价
于
min
y
f(x, y) = d
T
2
y
s.t. By ⩽ b − Ax
y ⩾ 0
上述问题的对偶问题 (D) 可以表示为
min
u
(Ax − b)
T
u
s.t. − B
T
u ⩽ d
2
u ⩾ 0
其中：u ∈ R
p
。
记上述对偶问题的可行域为 U = {u ∈ R
p
| − B
T
u ⩽ d
2
, u ⩾ 0}。于是原规划问题等价于
min
x,y,u
F (x, y)
s.t.
G(x, y) ⩽ 0
d
T
2
y − (Ax − b)
T
u = 0
Ax + By ⩽ b
− B
T
u ⩽ d
2
x, y, u ⩾ 0
http://www.ma-xy.com 9 http://www.ma-xy.com
http://www.ma-xy.com
1.6 二层非线性规划 第一章 多级规划
把上述规划和等式约束作为罚项构造到目标函数中，有
min
x,y,u
g(x, y, u) = F (x, y) + M
(
d
T
2
y − (Ax − b)
T
u
)
(1.2)
s.t.
G(x, y) ⩽ 0
Ax + By ⩽ b
− B
T
u ⩽ d
2
x, y, u ⩾ 0
其中：M 属于 R
++
的惩罚因子或罚权重。
定理 如果 (x
0
, y
0
) ∈ S 是原问题的最优解，且上述 (1.2) 存在最优解，则 ∃M ∈ R
++
, u
0
∈ U，
当且仅当 M ⩾ M
1
时，(x
0
, y
0
, u
0
) 是 (1.2) 式的最优解。
仔细观察式 (1.2)，不难发现，上层目标函数 F (x, y) 是一个连续、可微凸函数，而 M
(
d
T
2
y − (Ax − b)
T
u
)
则不一定是凸函数。值得一提的是，u 和 x, y 是没有关系的。于是我们猜想这个非凸函数是否可
以进一步简化，得到一个凸函数或者更特殊的函数。我们构造下列函数
min
x
0
,y
0
,u
g(x, y, u) = F (x
0
, y
0
) + M
(
d
T
2
y
0
− (Ax
0
− b)
T
u
)
(1.3)
s.t.
− B
T
u ⩽ d
2
u ⩾ 0
其中：(x
0
, y
0
) 是原问题的最优解。
定理 设式 (1.2) 的最优解为 (x
0
, y
0
, u
0
)，当且仅当 u
0
是上述问题的最优解。
由于
x, y
与
u
无关，所以先固定
x, y
，再来求解
u
。仔细观察会发现，上述问题是一个单
层线性规划，其最优解可能在约束域极点处找到，于是我们求解出上述问题的约束域极点，记为
U
D
= {u
j
, j = 1, 2, . . . , s}，构造如下问题：
min
x,y,u
g(x, y, u
j
) = F (x, y) + M
(
d
T
2
y − (Ax − b)
T
u
j
)
(1.4)
s.t.
G(x, y) ⩽ 0
Ax + By ⩽ b
u
j
∈ U
D
, j = 1, 2, . . . , s
x, y ⩾ 0
定理 如果 (x
0
, y
0
) 是原问题的最优解，则 ∃M
1
∈ R
++
，u
j
∈ U
D
，当且仅当 M ⩾ M
1
时，
(x
0
, y
0
, u
j
) 是问题 (1.2) 的最优解。
由此，求解原问题时，我们可以先任意固定一个 u
j
∈ U
D
，然后求问题 (1.4) 的最优解
(j = 1, 2, . . . , s)。
http://www.ma-xy.com 10 http://www.ma-xy.com
http://www.ma-xy.com
第一章 多级规划 1.7 一般二层非线性规划
假设求出问题 (1.4) 的最优解为 (x
j
, y
j
)，并且满足 d
T
2
y
j
(Ax
j
− b)
T
u
j
= 0，那么，可以确
定 (x
j
, y
j
) 是原问题的最优解，于是问题 (1.3) 则转化为一个凸函数在相应约束域中求得最优的
问题：
step1. 用单纯性法求问题 (1.3) 的约束域极点，记 U
D
= {u
j
, j = 1, 2, . . . , s} 给定初始搜索条件.
step2. 给定初始搜索条件 M = 1, δ = 5, k = 1, u
k
和容许误差 ε 的极点，若是，转到 step2；否
则，求一个极点最优解，仍记为 (¯x, ¯y)
step3. 求解问题 (1.4)，记最优解为 (x
k
, y
k
, u
k
).
step4. 如果 h(x
k
, y
k
, u
k
) ⩽ ε，则终止计算，输出 (x
k
, y
k
)；否则，转到 step5.
step5. 如果 k < s，则令 k := k + 1 返回 step3；否则，令 k = 1, M = δM 返回 step3.
1.7 一般二层非线性规划
考虑如下二层非线性规划问题
min
x
F (x, y)
s.t. G(x, y) ⩽ 0
x ⩾ 0
y为如下问题解
min
y
f(x, y)
s.t. f(x, y) ⩾ 0
其中：F, f : R
n
×R
m
→ R 分别是上下层目标函数，上下层规划的向量值函数 G : R
n
×R
m
→ R
q
，
g
:
R
n
× R
m
→ R
p
，x ∈ X ⊂ R
n
，y ∈ Y ⊂ R
m
为决策变量。
假设 F, f, G, g 为连续可微的凸函数，我们利用 KKT 条件和 Lagrange 函数将二层规划转化
为单层规划，再利用罚函数法求解单层规划，以此来近似原二层规划最优解。
假设下层规划是一个凸规划问题，对于每个 x ∈ S(x)，满足MFCQ 约束条件，则可以等价
为以下 KKT 条件：
∇
y
L(x, y, λ) = ∇
y
f(x, y) + λ
T
∇
y
g(x, y) = 0
g(x, y) ⩽ 0
λ
T
g(x, y) = 0
λ ⩾ 0
其中：下层规划问题的 Lagrange 函数形式为
L(x, y, λ) = f (x, y) + λ
T
g(x, y)
http://www.ma-xy.com 11 http://www.ma-xy.com
http://www.ma-xy.com
1.7 一般二层非线性规划 第一章 多级规划
定理 如果 (x, y) ∈ S，则 (x, y) ∈ IR 的一个充分必要条件为：存在一个 λ ⩾ 0，使得 (x, y, λ)
满足 KKT 条件。
最后，用 KKT 条件来代替原问题的下层规划，则可以把原问题转化为如下单层规划
min
x,y,λ
F (x, y)
s.t.
G(x, y) ⩽ 0
∇
y
f(x, y) + λ
T
g(x, y) = 0
g(x, y) ⩽ 0
λ
T
g(x, y) ⩽ 0
x ∈ X, y ∈ Y, λ ⩾ 0
定理 (x
∗
, y
∗
) 是原问题的最优解的充要条件是存在 λ
∗
⩾ 0，使 (x
∗
, y
∗
, λ
∗
) 是上述问题的最
优解。
计算上述问题等价于
min
x,y,λ
F (x, y)
s.t.
G(x, y) ⩽ 0
∇
y
f(x, y) + λ
T
∇
y
g(x, y)
= 0
g(x, y) ⩽ 0
λ
T
g(x, y)
= 0
x ∈ X, y ∈ Y, λ ⩾ 0
将等式约束代入目标函数，有
min
x,y,λ
F (x, y) + M (
∇
y
f(x, y) + λ
T
∇
y
g(x, y)
+ |λ
T
g(x, y)|)
s.t.
G(x, y) ⩽ 0
g(x, y) ⩽ 0
x ∈ X, y ∈ Y, λ ⩾ 0
于是求解二层非线性规划问题等价于求上述问题
http://www.ma-xy.com 12 http://www.ma-xy.com
http://www.ma-xy.com
第一章 多级规划 1.7 一般二层非线性规划
1.7.1 二层非线性规划更一般的模型
(1) 下层以最优解为最佳反应的二层非线性规划更一般的模型如下
min
x,y
F (x, y)
s.t. G(x, y) ⩽ 0
x ∈ R
n
⩾ 0
y是如下规划问题的解
y = arg min
y
f(x, y)
s.t. g(x, y) ⩽ 0
其中：F, G, f, g 中至少有一个为非线性函数。
(2) 下层以目标函数值为最佳反应的二层非线性规划的一般形式如下
min F (x, f )
s.t. G(x, y) ⩽ 0
x ∈ R
n
⩾ 0
f = min f (x, y)
s.t. g(x, y) ⩽ 0
y ∈ R
m
⩾ 0
http://www.ma-xy.com 13 http://www.ma-xy.com
