1、重庆大学硕士学位论文 英文摘要 II ABSTRACT This thesis mainly studies the penalty function method for the vector bilevel programming problem and the mathematical program with vector variational inequality constraints. Firstly, we describe the development and current researches on the topic of the bilevel programmi
2、ng， the mathematical program with equilibrium constraints and the penalty function method for the mathematical programs with constraints. Then, we give the main research work of this thesis. And we introduce some basic notions, definitions, and propositions, which will be used in this thesis. For th
3、e nonlinear bilevel optimization problem, where the upper level is a scalar optimization problem and the lower level is a vector optimization problem, we have given that by defining a new function, which can indicate whether a feasible solution is an efficient solution for the lower level problem or
4、 not, and appending it to the upper level objective function, we can establish the penalty problem of the original problem. We give the algorithm which can be used to solve the original problem and have proved the convergence property of it. For the optimization problem with weak vector variational
5、inequality, by introducing an adequate gap function, we establish the penalty problem of it and we study the property of the solution for the penalty problem. We give the algorithm to solve the original problem and have proved the convergence property of it. Under certain conditions, a vector optimi
6、zation problems solution is equivalent to the solution of an optimization problem with variational inequality constraints. So with some appropriate hypotheses, we apply the results to the vector bilevel programming problem. At last, the results of this thesis are summarized. And some problems which
7、are thought over in the future are put forward. Keywords：Bilevel programming, Variational inequality, Gap function, Penalty function method, (Weak) Efficient solution 重庆大学硕士学位论文 目 录 III 目 录 中文摘要 .I 英文摘要 . II 1 绪 论 .1 1.1 二层规划问题和均衡约束问题的国内外研究现状 .1 1.2 约束优化问题罚函数方法的国内外研究现状 .4 1.3 论文的写作动机和主要内容 .7 2 预备知识
8、.8 3 一类半向量二层规划问题的罚函数法 . 11 3.1 引言 . 11 3.2 解的存在性及罚问题的建立 .12 3.3 算法及收敛性证明 .15 4 含向量变分不等式约束的优化问题的罚函数方法 .18 4.1 基本模型及概念 .18 4.2 含参弱向量变分不等式的间隙函数 .19 4.3 罚函数方法 .21 4.4 应用到二层规划问题 .26 5 总结与展望 .28 5.1 全文总结 .28 5.2 本课题的后期研究展望 .28 致 谢 .29 参考文献 .30 附 录 .34 A. 作者在攻读硕士学位期间发表的论文目录 .34 重庆大学硕士学位论文 1 绪 论 1 1 绪 论 1.1
9、 二层规划问题和均衡约束问题的国内外研究现状 二层规划 (Bilevel Programming, BP)是一种具有二层递阶嵌套结构的数学规划问题，其一般的数学模型为： ,min ( , ). ( , ) 0,min ( , ). ( , ) 0.xyxXyYFxyst G x yxyfxyst g x y其中对每个固定的 是下面规划问题的解， (1.1) 其中 ,:,:,:n m nm nm u nm lx XRyYRFfR RGR RgR R+ + (n， m ， u ，lN+ )。称 ,min ( , ). ( , ) 0.xyxXFxyst G x y(1.2) 为上层规划问题，称 m
10、in ( , ). ( , ) 0.yYfxyst g x y(1.3) 为下层规划问题。上层的领导者和下层的跟随者拥有各自的目标函数和约束条件，领导者先给出一个决策变量的值，各个跟 随者就把这个决策变量作为参变量，并根据自己的目标函数和约束条件，在允许 的范围内求得一个最优值，然后将自己取得的最优结果传达给领导者，领导者再 在跟随者反馈来的最优结果的基础上在容许的范围内求得整个系统的最优解。 记 :2mnRSR 为下层问题 (1.3)的最优解集映射。如果上层领导者爱冒险，这时他会认为下层跟随者会从下层最优解集 中选择一个对上层来讲是最好的解，这样就得到了乐观模型： min min ( , )
11、. ( , ) 0,().xX yYFxyst G x yySx(1.4) 如果上层领导者是保守型的，这时他会认 为下层跟随者可能会做出最不利于自己的选择，于是他便作出最坏的打算，这样就得到了悲观模型： 重庆大学硕士学位论文 1 绪 论 2 min max ( , ). ( , ) 0,().xX yYFxyst G x yySx (1.5) 1934 年，为了对现实社会中的经济模型给予更好的描述，德国经济学家Stackelberg 在他的专著 1中首次提出了层次规划的概 念。第二次世界大战期间纳粹德国采取反竞争的经济政策致使二层规划问 题在那时没能引起人们过多的注意。后来直到 1973 年，
12、 Bracken 和 McGill 在他们的文章 2中才提出了二层规划的模型，二层规划和多层规划 (Multilevel Programming, MP)这两个名词正式出现是在Candler 和 Norton 于 1977 年做的科技报告 3中，这些问题才开始逐渐受到它们本该有的关注，一些学者对二层规划问题开 始了集中而深刻地研究，从而促进了二层规划问题在理论和应用上的不断繁荣与发展。 二层规划是一个非凸不可微的优化问题。 对于最为常见且形式最为简单的线性二层规划问题 ,Jeroslow4和 Bard5已经证明了是 NP-难问题。与一般的数学规划不同，即使当 (1.1)中的所有函数 F ， f
13、 ， G ， g 都是连续的，并且集合 X 和 Y 是紧集， 二层规划问题 (1.1)仍然可能没有最优解。 当上层规划问题给定一个决策变量后，如果下层规划问题的最优解不唯一，将会 导致整个二层规划问题的求解困难，甚至无法保证能求得原二层规划问题的最优解。 对二层规划第一个方面的研究内容是如何根据具体问题建立具体的数学模型。通过对二层规划一般的数学模型 (1.1)向不同的方向推广可以得到不同类型的二层规划问题。 对二层规划研究的第二个方面是基础理论 的研究，即解的存在性和最优性条件等方面的研究。数学规划问题的最优解 所满足的条件被称为是最优性条件。它是优化算法研究的重点，也是算法设计的基础。 B
14、onnel7首次把上层为标量优化下层为多目标优化的二层规划问题称为 半向量二层规划问题 (Semivectorial Bilevel Programming Problem)，并给出了当下层优化问题的目标函数是凸函数时的最优性必要条件。最早是 Bard 在文献 8中对线性二层规划进行了研究，得到了一些最优性条件， 但这一最优性结论对于某些问题是不成立的， Haurie 等在文献 9和 Clarke和 Westerberg 在文献 10中分别给出了反例。根据二层规划的特点并结合最速下降方向， Savard 和 Gauvin 在文献 11中给出了一个最优性必要条件。当下层规划是严格凸二次规划时，
15、Vicente 和 Calamai 在文献 12中给出了最优性的充要条件，并证明了这个条件是单层规划的一阶 和二阶最优性条件的推广。 Dempe 在文献 13中利用非光滑分析以及 Calamai 和 Bi 在文献 14中利用二层规划与一个相关精确罚函数之间的联系，得到了一些最优性充 要条件。如果二层规划的目标函数是一致 Lipschitz 连续的， Ye 等15先将问题转化为单层优化，然后结合非光滑分析法和重庆大学硕士学位论文 1 绪 论 3 罚函数法推出了二层规划的一个广义 KKT 最优性必要条件。 Zheng 等16以及 Calvete 和 Gal17证明了问题的局部最优解在约束域的极点处
16、取得。 Mersha 和Dempe18以及 Shi 等19通过研究给出了线性二层规划的最优解的存在性以及最优性充要条件。以上的这些最优性条件，由 于对问题的条件限制太严格，特别是非线性二层规划的最优性条件，以致于在实际中很难得到应用。 对二层规划研究的第三个方面是算法的研 究，即如何对已建立的模型进行求解。二层规划在数学规划中是很有趣的并 且占据着很大的比重，尽管已经取得了一些重大的成果，但仍然是可以继续研究的一块沃土。自从 1980 年起一些专家和学者致力于研究二层规划，经过近 40 年的深入研究，已经提出了一些求解二层规划的算法。比如：极点法、 KKT 法、下降方向法、分支定界法、罚函数法
17、等，以及一些智能算法，比如：遗传算法、模拟退火算法、蚁群算法、粒子群算法 20-24等。这些智能算法都是非数值优化方法， 由于此类算法在求解二层规划时具体的参数（如编码长度、交叉概率、变异概率 等）很难确定，所以一般收敛性难以保证，在实际应用中的可解释性也不理想。 但是非数值优化算法有它独特的优点，比如：通用性强，对问题本身的性质要求比较弱等。 均衡约束数学规划 (Mathematical Program with Equilibrium Constraints, MPEC )是约束条件中含有变分不等式或互补问题的约束优化问题。 变分不等式 (Variational Inequality)，互
18、补问题 (Complementarity Problems)，均衡约束数学规划和二层规划，这几类问题关系紧密，不仅为非线性约束 优化、非线性方程组、极大极小问题和微分方程等提供了统一的理论框架，而且 在交通运输和工程设计等领域有着广泛应用。 MPEC 也是典型的非凸优化问题，鉴于其广泛的应用前景以及问题自身的挑战性，自 20 世纪 80 年代后期对其进行了大量研究。尽管关于 MPEC 的研究历史并不太长，但是与之相关的理论和算法 已经相当完善。需要指出的是，大部分有关 MPEC 的文章都是针对如下互补约束数学规划问题进行讨论 min ( ). () 0, () 0,() 0, () 0, ()
19、 () 0.Tfxst g x h xGx Hx Gx Hx = =(1.6) 其中 :,: ,: ,: (,)nnpnqnmf RRgRRhRRGHRRnpqmN+ 均为光滑映射。欧几里得空间中的向量变分不等式最先由 Giannessi25引出 ,后来有了集中的研究。 Chen 和 Craven26研究了向量变分不等式和向量优化问题之间的关系。 近年来，为进一步丰富 MPEC 理论，人们更多的开始关注 MPEC 的高阶最优性、灵敏度及稳定性分析等理论课题以及像随机 MPEC 这样更为一般化的问题。当然，随着研究的深入与发展，要做出富有创造性的成 果变得越来越困难。但是，计算机科学的进步以及最
20、优化理论与方法 的发展必将为研究 MPEC 等复杂问题提供新的工重庆大学硕士学位论文 1 绪 论 4 具。 人们面临的问题越来越复杂，描述很多问 题的数据量急剧增加，大数据时代已经来临。由于很多实际问题可以模型化 为互补与变分不等式问题，因而，大规模互补与变分不等式问题的理论与算法研究具有重要的意义和应用价值。 1.2 约束优化问题罚函数方法的国内外研究现状 罚函数法是一种处理约束优化问题的方法 ，其原理是：利用问题中的约束函数作出适当的惩罚函数加到目标函数中去 ，从而将约束优化问题的求解转化为对相应的增广目标函数的无约束非线性规划 的求解。即可以用求解无约束优化问题的方法来得到最优解。 利用
21、罚函数法能把约束优化问题转化为无 约束优化问题，或者对上层和下层优化问题中的某些约束条件运用罚函数方 法将其惩罚到目标函数上来，进而可以将二层规划问题转化为容易求解的无约束 优化问题进行求解。通过求解一系列带罚因子的无约束优化问题，如果其收敛点存在，则其收敛点就是原问题的最优解。罚函数法一般分为内点法和外点法。外点 法是让迭代点从非可行解出发慢慢移动到可行域中，内点法是让迭代点在可行域 内进行搜索，约束边界起到障碍作用，不会让迭代点跑出可行域。罚函数法的缺 点在于罚因子很难确定，取得太小不能起到惩罚作用，取得太大可能导致错误。 求解线性二层规划经典的罚函数法是 Bard27提出的基于互补松弛条
22、件和White28提出的基于下层规划问题的对偶间隙的精确罚函数法。 Calvete 和 Gal29利用对偶将问题转化为单层的并设计了精 确的罚函数法求解了上层是分式规划，下层是线性规划，约束区域是多面体的二层规划问题。 Lv 等30用基于 KKT 条件的罚函数法求解线性二层规划问题。 Li 等31将罚函数法和进化算法相结合来求解非线性规划问题。 Meng 等32提出了求解二层非线性规划问题的含有双罚因子的罚函数法， 并给出了收敛性分析。对用罚函数方法求解半 向量二层规划问题的研究大部分都集中在了线性问题，而且所采取的罚函数通常都是下层优化问题的间隙函数。 Dauer33利用罚函数的方法研究了一
23、类在线性多目 标优化问题的有效解集上极大化目标函数的问题。 鉴于外罚函数法和内罚函数法的缺点，在 现实应用中，人们通常采用将外罚函数法和内罚函数法相结合的方法，这就是下面的混合罚函数法。 处理带等式约束和不等式约束的非线性优 化问题的混合罚函数法的途径之一是对等式约束利用外罚函数法的思想，对 不等式约束利用内罚函数法的思想，构造出所谓的混合增广目标函数 重庆大学硕士学位论文 1 绪 论 5 211(, ) () () ,2()qpiiiiHx fx h xgx=+ (1.7) 或 2211(, ) () () ,2()qpiiiiHx fx h xgx=+ +(1.8) 或 2111(, )
24、() () ln ().2qpiiHx fx h x gx=+ (1.9) 从而可以根据外罚函数法或内罚函数法的 算法框架建立起相应的算法，但是对于由此建立起的算法的初始迭代点的选择仍是困难的。 第二种途径是通过引入松弛变量iy ( 1, 2, ,ip= null )， 将带等式约束和不等式约束的非线性优化问题等价地转化为： min ( ). . ( ) 0, 1, 2, ,( ) 0, 1, 2, ,iijfxst g x y i I phx j J q+ = = =nullnull(1.10) 然后构造等价问题 (1.29)的混合增广目标函数 2211 1(, , ) () () () ,
25、22qp piiiiixy fx h x g x yy= =+ + + (1.11) 或 22211 1(, , ) () () () ,22qp piiiiixy fx h x g x yy= =+ + + (1.12) 或 2211 1(, , ) () () () ln .22qp piiiiix yfx hx gxy y= =+ + + (1.13) 从而可以根据外罚函数法或内罚函数法的 算法框架建立起相应的算法，对于由此建立起来的算法的初始迭代点 (, )x y (12(, , , ) 0pyyy y= null )的选择可以是任意的。 外罚函数法、内罚函数法以及由二者相结 合产生的
26、混合罚函数法，它们都需要求解一系列无约束极小化问题，从而导 致计算工作量大、收敛速度慢，而随着需要的罚参数趋于无穷大或零导致增广目标函数的 Hesse 矩阵的病态又造成问题求解的效率差。因此，人们又构造出了另外两种类型的罚函数。 其中一种是精确罚函数，使得当罚参数在 一个取值范围内取值时，求得的罚优化问题的最优解就是原问题的最优解。 Zangwill 在 1967 年首次提出了精确罚函数： 1(, ) () max (),0.piiPx fx g x=+(1.14) 在一定条件下，存在一个有限值 0 ，使得当 时，对应的罚问题的最重庆大学硕士学位论文 1 绪 论 6 优解就是原问题的最优解。因
27、此只需求解一个罚问题就可以得到原问题的最优解。正因为如此，精确罚函数成为求解非线性 约束优化问题的重要方法。关于精确罚函数的研究，仍有新的研究成果不断问世。 下面给出经典精确罚函数，亦即发展最为成熟的1l 精确罚函数。对于非线性优化问题 min ( ). . ( ) 0, 1, 2, ,( ) 0, 1, 2, ,.ijfxst g x i I phx j J qxX = =nullnull(1.15) 其中1,: , ( , , )nnijf gh R Rx X Ri Ij Jnpq N+ 。 若假设问题 (1.15)中的集合 X 为开集，则其精确罚问题为 11min () max0, ()
28、 () .pqiixXiif xgxhx=+ +(1.16) 精确罚函数的优点是罚问题的无约束极小 点就是原问题的最优解，在确定了参数的适当精确值后，求解这样一个无约 束优化问题即可。另外，其对问题中函数性态的要求较低，只要实现恰当，就可以保证较好的收敛速度和数值稳定性。 另外一种是乘子罚函数，是在约束问题的 Lagrange 函数中增加一个惩罚项，故又称为增广 Lagrange 罚函数，相应的算法称为乘子法（或增广罚函数法） 。这种算法的原理是利用约束优化问题的近似 Lagrange 乘子所提供的信息，在对罚参数的值进行有限次的调整后即可使它保持不 变，在每次的迭代过程中用某种乘子修正公式对
29、 Lagrange 乘子向量进行修正，通过求解一系列乘子罚函数的无约束极小化问题来找到原约束优化问题的最优解， 从而不需要使罚因子无限地趋于无穷大或零。 Bonnel 和 Morgan34在 2006 年首次将上层为标量优化下层为多目标优化的二层规划问题称为半向量二层规划问题，不 仅给出了当下层问题的目标函数是凸函数时的最优性必要条件，而且将这个结果 应用到了下层问题的目标函数是线性函数的情形 2009 年 Ankhili 和 Mansouri35研究了一类上层和下层问题均为线性规划的半向量二层规划问题。作者通过边际函 数建立其罚函数，提出了求解该问题的精确罚函数法，不仅给出了算法的收敛性 分
30、析，而且通过数值算例研究了所有的线性情形。 2011 年 Zheng 和 Wan36借助下层问题的对偶问题并通过引入两个罚参数构建了一类上层为标量优化下层为多目 标线性优化的半向量二层规划问题，并给出了相应的算法，用数值算例说明了算法的可行性。 重庆大学硕士学位论文 1 绪 论 7 1.3 论文的写作动机和主要内容 受以上学者研究内容的启发，我们考虑研 究一类数学模型更为一般的半向量二层规划问题的罚函数方法，同时又考虑 到很多实际问题都可以模型化为比二层规划问题更为广泛的均衡约束数学规划问 题，所以我们也对带有弱向量变分不等式的优化问题的罚函数法进行了一些研究。 本文主要研究一类半向量二层规划
31、问题和 含弱向量变分不等式约束优化问题的罚函数方法。论文的主要工作如下： 第三章研究了一类上层是标量优化下层是多目标优化的非线性二层规划问题的罚函数法。通过定义一个可以判断 下层问题的可行解是否为其有效解的函数，并把它附加到上层问题的目标函数中 ，我们构造出了原问题的罚问题，并给出了求解原问题的算法，证明了算法的收敛性。 第四章研究的是含弱向量变分不等式约束条件的优化问题 (OPVVIC)的罚函数方法。通过引入 (OPVVIC)的间隙函数构造出其罚问题。然后研究了罚问题解的性质，并给出了通过罚问题求解 (OPVVIC)的算法，证明了算法的收敛性。考虑到在一定条件下多目标优化问题的解与向 量变分
32、不等式问题的解等价，我们在适当的假设条件下，将前面的研究结果应用到了半向量二层规划问题。 重庆大学硕士学位论文 2 预备知识 8 2 预备知识 关于二层规划的数学模型 (1.1)，其相关集合和定义如下： 定义 2.1 搜索空间： (, ) ,x yxXyY= | 。 约束域： (, ) (, ) 0, (, ) 0Sxy Gxy gxy= | 。 对于固定的 x，下层规划问题的可行域： () (, ) 0Sx y Y gxy= | 。 S 在上层决策空间的投影： () ,(,)SX x X y Y xy S= | 。 对于 ()x Sx ，下层规划问题的合理反应集： () argmin (,
33、) ()yPx fxy y Sx=|。 诱导域 (或可行域 )： (, )(, ) , ()IRxyxySyPx=| 。 在 S 为非空紧集， IR 为非空集的假设下，二层规划问题 (1.1)可以写成如下形式： ,min ( , ). ( , ) .xyFxyst x y IR(2.1) 定义 2.2 若 (, )x yIR ，则称 (, )x y 为二层规划问题 (2.1)的可行解。 定义 2.3 若*(, )x yIR ，对任意 (, )x yIR ，都有*(, ) (,)Fx y Fxy ，则称*(, )x y为二层规划问题 (2.1)的最优解。 定义 2.4 若*(, )xy ，对任意
34、 (, )xy ，都有*(, ) (,)Fx y Fxy 和*(, ) (,)f xy fxy ， 则称*(, )x y 为二层规划问题 (2.1)的完全最优解。 然而，对于二层规划问题 (1.1)，同时使上层目标函数和下层目标函数达到最优的完全最优解不一定存在。借助多目标规划中 Pareto 最优解的概念37，给出如下定义。 定义 2.5 设*(, )x yS ，若不存在 (, )xy ，使得*(, ) ( , )Fxy Fx y ，*(, ) (,)f xy fxy 且*(, ) ( , )Fxy Fx y ，*(, ) ( , )f xy fx y 成立，则称*(, )x y 为二层规划问题 (1.1)的 Pareto 最优解。 定义 2.6 设集合nSR 。如果对任意的 0,1 都有 1212(1 ) , , .x xSxxS + 则称 S 是凸集或 S 是凸的。 定义 2.7 以nx R 为球心 , 0r 为半径的球记为 (,)nB xr y R y x r= | ，使得 (,)B xr S ，则称 S 为开集。 定义 2.8 包含点nx R 的开集称为 x的一个邻域。
