一类非线性二层规划的Frank-Wolfe方法

张涛,吕一兵

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

0 引言

二层规划是一种具有递阶结构的系统优化问题，其数学模型可以表示为:

其中，x∈Rn1,y∈Rn2分别为上层决策变量及下层决策变量.F(x,y),f(x,y)分别称为上层目标函数以及下层目标函数.

对二层规划的求解是比较困难的，即使最简单的情况即所有的函数为线性函数，也是NP-难问题.求解非线性二层规划就更加困难了，目前求解非线性二层规划的方法主要包括分支定界法[1]、下降方法[2]以及信赖域方法[3]等.事实上，由于非线性二层规划的复杂性质[4]，其算法设计一般针对的是具有某种特殊结构的非线性二层规划问题.

在本文中，考虑如下形式的二层二次规划问题:

(1)

其中F(x,y),f(x,y)1分别为上层和下层的目标函数，c1,c2∈Rn1,d1,d2∈Rn2,b∈Rm均为已知向量，R,Q∈R(n1+n2)×(n1+n2)为对称矩阵，A∈Rm×n1,B∈Rm×n2.x∈Rn1,y∈Rn2分别为上层、下层规划问题的决策变量.

对于二层二次规划问题(1)，考虑以下层问题的K-T最优性条件代替下层问题，同时取互补条件为罚项，从而得到该类非线性二层规划的相应单层规划问题.由于相应的单层规划为二次规划问题，因此考虑用Frank-Wolfe方法进行求解.在本文接下来的内容中，首先介绍相关的概念以及算法的理论基础;然后，设计二层二次规划问题(1)的Frank-Wolfe方法，并以数值实验验证算法的可行性;最后对本文进行小结.

1 主要结果

令

其中Q0∈Rn2×n2,Q1∈Rn2×n1,Q2∈Rn1×n1,则下层目标函数f(x,y),即为:

定义1 称集合S={(x,y)|Ax+By≤b}为二层二次规划问题的约束域.

定义2 称集合P={x|存在y,使得(x,y)∈S}是上层决策变量x的可行域.

为了讨论方便，我们假设S是非空紧的.假设Q0是负定矩阵.因此对每个给定的上层决策变量x∈P，下层规划问题存在唯一的解，不妨记为y(x)，而且下层问题存在最优解[6].

定义3 称集合IR={(x,y)|(x,y)∈S,y=y(x)}为二层二次规划问题的可行域.

尽管约束域S是一个凸多面体，但二层二次规划问题的可行域IR一般不再是凸集，因此二层二次规划问题是非凸规划问题.下面给出二层二次规划问题的最优性条件，这也是求解二层二次规划算法的理论基础.

定理1[1](x*,y*)∈S为二层二次规划问题最优解的充分必要条件是存在w*∈Rm,u*∈Rm,v*∈Rn1≥0,使得(x*,y*,w*,u*,v*)是下面规划问题的解.

(2)

在问题(2)的约束条件中除互补外，其余均为线性约束，笔者考虑以互补条件为罚项，用精确罚函数的方法求解.即问题(2)转化为:

(3)

其中:M>0为罚因子.

对于模型(2)与(3)，Liu等[5]证明了如下的定理.

定理2 如果问题(2)的可行域非空，且对于某个M0>0,问题(3)有解，则必存在M*≥M0使得对于所有的M≥M*，问题(2)与(3)有相同的非空最优解集.

从定理2可以看出欲求解非线性规划(2)，只需求解相应的单层规划(3)，而模型(3)的求解方法建立在如下命题的基础上.为叙述方便，不妨记模型(3)的目标函数为F′(z),其中:z=(x1…xn1,y1…yn2,u1…um,v1…vn2,w1…wm)T，则相应的约束条件记为:

A′z=α,z≥0.

其中A′,α为如下分块矩阵:

此时模型(3)等价的记为:

minF′(z),s.t. A′z=α,z≥0

(4)

假设z(k)为问题(4)的任一可行点，在z(k)处取F′(z)的一阶Taylor展开，则问题(4)转换为:

(5)

对于问题(4)与(5)之间的关系有如下的命题.

定理3 设问题(5)有最优解y(k)，则有如下结果:

则有

又因为

则

因为y(k)为问题(5)的最优解，故对于问题(4)与(5)的任一可行点z(k)有:

即:

这就证明了y(k)-z(k)为问题(4)的一个下降方向，同时y(k)-z(k)为问题(4)的可行方向是显然的.

并取z(k+1)=z(k)+ak(y(k)-z(k)).

以上就是传统的Frank-Wolfe步骤.

2 算法及数值实验

基于上述讨论，可形成如下求解问题(1)的算法，具体的算法步骤如下.

算法:Step1. 给定罚因子M，以及误差限ε>0;

Step2. 将二层二次规划(BQP)转化为(2)式;

Step3. 将(2)式中的互补松弛条件取为罚项，得到如下单层规划

(6)

Step4. 将规划(6)的目标函数在可行域的点zk=(xk,yk,uk,wk,vk)处线性展开得到:

(7)

为验证本算法的可行性，我们考虑如下二层二次规划问题[3-4]:

(8)

文献中最优解x=0.843 8,y=(0.765 7,0).

将(8)式的下层问题用其KT条件代替同时取互补松弛条件为罚项得到如下单层规划:

(9)

从数值实验我们可以看出求解二层二次规划的Frank-Wolfe方法是可行的，同时如果误差限取的更小，则得到的解将更加逼近原最优解.

3 小结

从算法的收敛性及算例实现的过程可知从非线性二层规划的任何一个可行点，利用本文中的算法都可以得到相应的局部最优解.如何将本文中的算法进行改进，得到问题的全局最优解值得继续研究.

参考文献：

[1] Bard J F. Practical bilevel optimization algorithms and application[M].London:Kluwer Academic Publishers,1998.

[2] Vicente L, Savard G, Judice J.Decent approaches for quadratic bilevel programming[J].Journal of Optimization Theory and Applications, 1994,81(2):379-399.

[3] 刘国山，韩继业，汪寿阳. 双层优化问题的信赖域算法[J].科学通报, 1998,43(4):383-387.

[4] Deng X. Complexity issues in bilevel linear programming[M].London:Kluwer Academic Publishers,1998:149-164.

[5] Dempe S. Foundation of bilevel programming[M].London:Kluwer Academic Publishers,2002.

[6] Shi C, Zhang G, Lu J.On the definition of linear bilevel programming solution[J].Applied Mathematics and Computation,2005,160:169-173.