双层优化入门(1)—基本原理与求解方法(附matlab代码)

1.介绍

        双层优化问题(Bilevel Programming Problems)，也被称为双层规划，最早由Stackelberg与1934年在经济学相关研究中提出，因此也被称为Stackelberg问题。

        双层规划问题一般具有层次性、独立性、冲突性、优先性和自主性等特点：

        1）层次性

        优化时是分层管理的形式，下层优化服从上层优化，但下层优化有相对的自主权。

        2）独立性

        各层决策者各自控制一部分决策变量，以优化各自的目标。

        3）冲突性

        各层决策者有目标函数各不相同，且这些目标往往是相互矛盾的。

        4）优先性

        上层决策者优先做出决策，下层决策者在选择策略时，不能改变上层的决策。
        5）自主性

        上层的决策可能影响下层的行为，因而部分地影响下层目标的实现，但上层不能完全控制下层的选择行为，在上层决策允许范围内,下层有自主决策权。
        按照上下层优化的形式不同又可以分为线性双层优化以及非线性双层优化问题。当双层优化问题中所有目标函数和约束条件均为线性时，即为线性双层优化，否则就是非线性双层优化问题。其中双层优化的基本形式可描述为：

        其中，x和y是上层优化的决策变量，但x在下层优化中是参数。所以，双层优化模型是一个优化问题受制于另一个优化问题的模型。

2.问题分析

        下面是一个简单的线性双层优化问题：

matlab代码：

%% 清空
clc
clear
close all
warning off
%% 采用迭代方法进行求解
x=sdpvar(1);
y=sdpvar(1);
Constraints1=[2*x-3*y >= -12 , x+y <= 14 , x>=0 , y>=0];
objective1=-x-2*y;
objective2=-y;
ops=sdpsettings('verbose', 0 , 'solver', 'cplex');
result=optimize(Constraints1,objective1,ops);
if result.problem==0
    disp(['第一次迭代最优解：x=',num2str(value(x)),',y=',num2str(value(y))])
    disp(['第一次迭代最优函数值=',num2str(value(objective1))])
end
x_dot=zeros(1,100);
y_dot=zeros(1,100);
x_dot(1)=value(x);
for k=1:10
    Constraints2=[-3*x+y <= -3 , 3*x+y <= 30 , x==x_dot(k) , x>=0 , y>=0];
    result=optimize(Constraints2,objective2,ops);
    y_dot(k)=value(y);
    Constraints1=[2*x-3*y >= -12 , x+y <= 14 , y==y_dot(k) , x>=0 , y>=0];
    result1=optimize(Constraints1,objective1,ops);
    x_dot(k+1)=value(x);
    if result1.problem || result.problem
        disp('迭代无法收敛')
        break
    end
end

        运行结果：

 3.双层优化求解方法

定义拉格朗日函数为：

以上面提到的线性双层优化问题为例，其下层优化的拉格朗日函数为： 

KKT 方程组如下：

        对于该问题，可以分三种情况讨论：

        1） u1 =0，模型可以简化为：

        2） u1∈(0,1)∪(1,+∞)，模型可以简化为：

         3） u1=1，模型可以简化为：

matlab代码： 

%% 清空
clc
clear
close all
warning off
%% u1=0
x=sdpvar(1);
y=sdpvar(1);
Constraints1=[2*x-3*y >= -12 , x+y <= 14 , x>=0 , y>=0 , -3*x+y <= -3 , 3*x+y == 30 ,];
objective=-x-2*y;
ops=sdpsettings('verbose', 0 , 'solver', 'cplex');
result1=optimize(Constraints1,objective,ops);
disp('***********u1=0时的最优解和最优函数值************')
if result1.problem==0
    disp(['最优解：x=',num2str(value(x)),',y=',num2str(value(y))])
    disp(['最优函数值=',num2str(value(objective))])
else
    disp('无最优解')
end

%% u1∈(0,1)∪(1,+∞)
x=sdpvar(1);
y=sdpvar(1);
Constraints1=[2*x-3*y >= -12 , x+y <= 14 , x>=0 , y>=0 , -3*x+y == -3 , 3*x+y == 30 ,];
objective=-x-2*y;
ops=sdpsettings('verbose', 0 , 'solver', 'cplex');
result2=optimize(Constraints1,objective,ops);
disp('****u1∈(0,1)∪(1,+∞)时的最优解和最优函数值*****')
if result2.problem==0
    disp(['最优解：x=',num2str(value(x)),',y=',num2str(value(y))])
    disp(['最优函数值=',num2str(value(objective))])
else
    disp('无最优解')
end

%% u1=1
x=sdpvar(1);
y=sdpvar(1);
Constraints1=[2*x-3*y >= -12 , x+y <= 14 , x>=0 , y>=0 , -3*x+y == -3 , 3*x+y <= 30 ,];
objective=-x-2*y;
ops=sdpsettings('verbose', 0 , 'solver', 'cplex');
result2=optimize(Constraints1,objective,ops);
disp('***********u1=1时的最优解和最优函数值************')
if result2.problem==0
    disp(['最优解：x=',num2str(value(x)),',y=',num2str(value(y))])
    disp(['最优函数值=',num2str(value(objective))])
else
    disp('无最优解')
end

运行结果：

        这样就完成了对上述简单线性双层优化问题的求解。通过下层优化的KKT条件将双层优化转换为单层优化是最常用的方法，但不是唯一的方法，后面我将继续更新这个系列，和大家一起学习双层优化问题。

参考文献：

[1] Bilevel Programming Problems