一种求解线性二层规划 ε-全局最优解的方法

吕一兵，陈 忠

(长江大学信息与数学学院，湖北 荆州 434023)

一种求解线性二层规划 ε-全局最优解的方法

吕一兵，陈 忠

(长江大学信息与数学学院，湖北 荆州 434023)

以得到的线性二层规划的局部最优解构造约束条件，并将其添加到所构造的线性二层规划的罚问题中，得到相应的单层规划问题。通过对单层规划问题的分析，设计了一种求解线性二层规划ε-全局最优解的算法，并以算例验证了算法的可行性。

线性二层规划；最优性条件；ε-全局最优解

考虑线性二层规划问题：

(1)

式中，c1,x∈Rn1；c2,b,y∈Rn2；a∈Rm；A1∈Rm×n1；A2∈Rm×n2。

对于线性二层规划模型(1)，一种经典的转化方法是以下层问题的K-T最优性条件代替下层问题，即将问题(1)转化为如下单层规划问题：

(2)

式中，u∈Rm，v∈Rn2为松弛变量。基于上述转化方法，一些学者提出了求解线性二层规划问题的分支定界法[1]、罚函数法[2]以及平衡点法[3]等。最近，Lv等[4]以问题(2)的互补条件为罚项，构造了线性二层规划问题(1)的如下罚问题：

(3)

式中,k∈R+为充分大的罚因子。通过严格的理论分析，Lv等[4]设计了一种只需要求解一系列线性规划就可以得到线性二层规划问题(1)的最优解的算法，然而文献[4]中的算法只能保证得到问题(1)的局部最优解。

下面，笔者对文献[4]中的算法进行改进，以得到问题(1)的ε-全局最优解。

假设(x′,y′)为问题(1)的局部最优解，且相应的目标函数值为：

考虑将新的约束条件：

添加到问题(3)中，构造如下单层规划问题：

(4)

循环求解问题(4)，可得到问题(1)的ε-全局最优解。

1 理论分析

假设线性二层规划问题(1)的约束域：

S′={(x,y):A1x+A2y≤a,x≥0,y≥0}

为非空紧集。在此假设条件下，由文献[5]可知，线性二层规划问题(1)必存在最优解。

记：

Xv={多面体X的顶点}

对于(u,v)∈S以及k∈R+，令：

证明首先证明函数Qk(u,v)为凸函数。令(u1,v1),(u2,v2)∈S以及λ∈(0,1)，则有：

这就表明Qk(u,v)为凸函数。

又由于S为多面体，则在多面体上极大化凸函数，其最优解必在多面体的顶点处取得，即最优解(u*,v*)∈Sv。

对于单层问题(4)的最优解，可以得到如下结论。

定理2令k∈R+，且假设条件成立，则问题(4)的最优解必在Zv×Sv处取得。

所以(x*,y*,u*,v*)∈Zv×Sv为问题(4)的最优解。

定理3假设{(xk,yk,uk,vk)}为问题(4)的最优解序列，且假设条件成立，则存在有限的k1gt;0，对于所有的k≥k1，均有：

证明假设(x*,y*)∈Z为线性二层规划问题(1)的最优解，则存在(u*,v*)∈S使得下层问题的互补条件得到满足：

(u*)T(a-A1x*-A2y*)+(v*)Ty*=0

对于(xk,yk,uk,vk)∈arg max[fk(x,y,u,v):(x,y)∈Z,(u,v)∈S]，有：

从而：

式中，m为常数。

又由于：

且Zv×Sv为有限点集，则存在有限的kgt;0，对于所有的k≥k1，均有：

定理3表明，存在有限的罚因子k1gt;0，当kgt;k1时，由问题(4)所求得的最优解满足问题(1)的下层问题的最优性条件。这就表明通过求解问题(4)可以得到问题(1)的最优解。

2 算 法

基于以上认识，笔者设计如下求解线性二层规划问题(1)的ε-全局最优解的算法。

步0 选择kgt;0(较大)，θ=-∞，εgt;0(较小)以及λgt;0,i=0。

步1 求解问题(4)：

3 算 例

为了验证算法的可行性，考虑如下线性二层规划问题[6]：

LOOP1

步0 选择k=100，θ=-∞，ε=0.5以及λ=10,i=0。

步1 求解如下规划问题：

LOOP2

步1 求解如下规划问题：

LOOP3

步1. 求解如下规划问题：

上述结果与文献相符合，这就表明设计的算法是可行的。

4 结 语

设计了求解线性二层规划ε-全局最优解的算法，理论分析以及数值试验均表明所设计的算法是可行的。由于与线性二层规划所对应的罚函数为精确罚函数，因此所设计的算法具有有限终止性，并具有良好的计算前景。

[1]Hansen P, Jaumard B, Savard G.New branch-and-bound rules for linear bilevel programming[J]. SIAM.Journal on science and statistical computing, 1992, 13:1194～1217.

[2]Ishizuka Y,Aiyoshi E.Double penalty method for bilevel optimization problems[J]. Annals of Operations Research, 1992,34:73～88.

[3]Campelo M,Scheimberg S. A study of local solutions in linear bilevel programming[J]. Journal of optimization theory and application, 2005, 125 (1): 63～84.

[4]Lv Y. A penalty function method based on Kuhn-Tucker condition for linear bilevel programming[J]. Applied Mathematics and Computation, 2007,188:808～813.

[5]Shi C,Zhang G,Lu J. On the definition of linear bilevel programming solution[J]. Applied Mathematics and Computation, 2005, (160):169～176.

[6]Bard J F. Practical Bilevel Optimization Algorithm and Applicatiom[M]. Kluwer Academic Publishers, USA, 1998.

[编辑] 洪云飞

2009-08-12

国家自然科学基金项目(10926168；70771080)。

吕一兵(1979-)，男，2002年大学毕业，博士，讲师，现主要从事最优化理论与算法等方面的教学与研究工作。

O224

[MR(2000)主题分类号]90C33

A

1673-1409(2009)04-N001-04