双层规划求解的思想是什么？_摩根-摩根娱乐集团空调售卖站

当前位置：首页 > 新闻动态 > 企业新闻

企业新闻

双层规划求解的思想是什么？

发布时间：2024-04-07 23:09:37浏览次数：

当双层优化中，上、下层优化问题中目标函数是非线性的，且约束条件也是非线性时，求解其全局最优解的数学思想是什么？其求解很难的具体原因是什么？

同问。。

深夜失眠，扫到这个问题，谈下自己的理解。解决双层规划，首先要搞明白俩个事情，一是为什么要双层规划?二是如何求解?

广义上来说，双层规划就是下层函数的解是上层函数的计算参数，但这个定义不准确，因为任何最优化问题其实都可以理解成是双层规划，只要将自变量理解为无约束的规划即可，那么问题就是如何判断一个问题是一个双层问题呢?

方法很简单，就是看下层的自变量与上层模型的关系能否用解析式表达出来，如果能，那么就可以直接表达成一个约束做成单层函数求解，如果不能就是双层问题了。

一般能写成单层尽量不要双层，因为optimal solution很难保证，往往只能得到strong stationary solution，而且求解过程很复杂。一个特殊的情况就是变分不等式，由于变分不等式往往是不等式组，作为单层约束来看也非常难解，所以可以考虑写成双层问题。

如果明确了双层规划的内涵，就可以很好的选择方法了，基本上分为两大类(许多书中写五类，三类的也有，就是角度问题)。为什么是两大类呢?这里的两种方法分别是解析法和启发式算法，顾明思意，解析法就是直接算出解析节，这种方法的逻辑大都使用KKT，对偶，罚函数等将双层规划转化成单层，然后利用单层的方法求解。另一种启发式算法(也有类启发式，就是解析和启发的结合)，这种方式的特点就是:有方向的迭代，一般来说给一个初始可行解然后按照实际问题确定一个下降方向，不断搜索直到gap满足精度要求，但这里必须注意，启发式算法很有可能得到的不是最优解，一定要对结果进行论证。除搜索法外，启发式算法中，还有包括active-set，trust region等方法，更有特色，也各有前提，需要实际问题实际分析。

题主提到了非线性的条件，非线性确实是双层规划中最难的问题，目前许多方法也颇受争议，主要的问题是无法确定集的凹凸性，就使得很多解法不能适用。当然，对于一些问题还是有迹可循的，例如函数和约束都可导的话可以结合sqp将原问题近似为二次问题，然后进一步求解。再不济可以用分段线性拟合，将原问题转化成线性问题，不过这些方法虽然适用性还可以但是收敛性特征却很不明显导致迭代次数较大，计算容量不够。

最后就是不知道题主的实际问题，有些问题其实可以直接用GAMS等平台solver解的，算法也比较成熟，可以考虑。

手机码字，不方便加公式和图，见谅。有些比较好的书籍和文章以后有机会可以推荐给你。

最近正在做一些关于OD estimation的东西，所以接触到bilevel，双层规划，结合自己读的一些paper谈谈自己的认识，说的不对的地方请批评指正。

双层规划简单来说就是有一个主问题x=argmin: F1(x,x')+F2(y(x),y'), 而子问题就是主问题的约束项subject to y(x)=A(x)x

这里面主函数里首先根据初始值得到一个x，然后把这个x作为parameter输入到子问题中去求解出对应的y然后传回主问题求解此时主题的optimal。

总的来说，对于子问题而言，本身就是一个parametric问题。但是现实情况中，A(x)往往是非线性的，随之而来就导致整个bilevel问题的inner其实是非凸的。具体来说就是y(x)中使得A(x)最优的optimal不一定同时是主问题中使得整个objective function达到最优的optimal的取值。

对于这类问题的求解，总体上的思路还是通过KKT之类的手段把双层问题转化为单层问题，就是说把constraint通过KKT写成单层形式再求解。

给出一篇参考的文献，有兴趣的可以读读，个人觉得分析得还比较到位：

https://arxiv.org/pdf/1705.06270.pdf

其实你的问题提的太大了，因为不同的bi-level opt的解法并不共通。具体而言，你可以读一下最近的A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization，这篇论文对bi-level opt的类型做了比较详细的阐述。我自己最近一个课题涉及bi-level MILP，这类问题因为下层问题包含integer variables，无法转化为single level MILP。如果你看最近5年的bi-level MILP的文章，会发现求解思路就是如何利用任意找到的high-point problem point （HPP）去得到更多的原问题的信息。

基于branch-and-bound或者branch-and-cut的方法的核心是利用HPP去估计原问题的upper-bound，lower-bound，并对higher-level problem的integer variable进行branching。

另一类方法的最近文献是A note on linearized reformulations for a class of bilevel linear integer problems，核心思想是bender decomposition，即每一次我尝试一个HPP之后，在high-level problem做variable and constraints generation去避免一部分我不想要的解。

其实还有第三类方法是基于no-good-cut的，具体可以参考Bilevel mixed-integer linear programs and the zero forcing set。

总体而言，我的理解是，这类问题的难点在于如何不去branching所有的high-level integer variables，因为这对于大规模问题是难以想象的。所以我是不看好branch-and-bound或者branch-and-cut的方法。

解法的核心在于如何迭代的添加constraints甚至variable到high-level problem中去逼近feasible region。

在研究城市交通网络的交通流量优化问题时，涉及到三层规划的优化模型，但是在搜索三层规划的相关内容时发现较为匮乏，因此将自己近期学习到的相关知识整理成文，也帮助自己理清思路。首先三层规划可以看作两个双层规划的嵌套，也是研究三层规划的基础，所以这篇文章是有关下层模型为用户均衡的双层规划的部分。下一篇文章将关于三层规划的内容展开。

本文的主要内容为：1、双层规划模型的范式 2、双层规划的求解算法 3、交通方向的双层规划例子

其中1和2的内容来源于李高西的博士毕业论文《几类层次优化问题理论及算法研究》，3的内容来源于祝进城的博士毕业论文《福利经济学视角下考虑交通行为的出租车收费研究》。

双层规划（BP）模型是指上下层之间具有嵌套结构，可用于描述具有主从关系的两个决策者决策博弈的过程，上层决策者（leader）首先做出决策，然后下层决策者（follower）做出最优决策并反馈给上层。双层规划模型，用数学语言描述出来，上层模型如下：

其中 $\\psi(x)$ 是下述参数优化问题的最优解集：

这里 $F,f$ 是 $R^{n}\ imes R^{m}$ 上的实值连续函数。 $X$ 和 $K(x)$ 分别代表上层和下层约束集可定义为：

$X:={\\left\\{ x\\in R^{n}: G(x)\\leq0\\right\\}}\\\\ K(x):={}{\\left\\{y\\in R^{m}: g(x,y)\\leq0 \\right\\}}$

其中 $G: R^{n}\\rightarrow R^{k},g: R^{n}\ imes R^{m}$ ，这里“ $min_{x}$ ”加上引号是因为当下层最优解集 $\\psi(x)$ 不止一个元素是，若 $y$ 取 $\\psi(x)$ 中的不同值，则 $F(x,y)$ 关于 $x$ 的极小化问题面临不同选择。据此，可以将双层规划分为悲观双层规划和乐观双层规划。