matlab求解⾮线性整数规划_拉格朗⽇松弛求解整数规划浅析 （附Python代码实例）...
拉格朗⽇松弛是⼀种常见的求解⼤规模整数规划/混合整数规划的有效⽅法。⽬前⽹络上关于拉格朗⽇松弛的解读多数是从拉格朗⽇松弛求解⾮线性规划问题的⾓度着⼿，很少有关于拉格松弛求解整数规划的内容。另⼀⽅⾯在实践层⾯上拉格朗⽇松弛⽅法 有着诸多需要注意的问题，⽽教科书理论证明往往为了proof的漂亮很少讨论这些缺陷和问题。 我在博⼠阶段先后两次修了Nonlinear programming的课程，主讲⽼师是Peter Luh⽼师（陆宝森⽼师）。陆⽼师是研究拉格朗⽇松弛求解整数规划领域的前驱者，我⼗分有幸和陆⽼师讨论交流过很多问题，后边⾃⼰也动⼿实践过拉格朗⽇松弛算法，并发表了相关的paper，因此这⾥我把⼀些经验分享出来。
0 ⼤规模整数规划/混合整数规划的 decomposition method 简介
由于⼤规模整数规划/混合整数规划往往是NP-hard的，所以我们很难直接对这些问题求解。每当遇到这些复杂问题的时候，⼀个基本思路就是对复杂的优化问题进⾏分解（decomposition）。谈到整数规划问题的分解主流的就三种⽅法：
1 Benders decomposition (主要思想是⾏⽣成+割平⾯⽅法)
2 Dantzig-Wolfe decomposition (主要思想其实就是列⽣成)
3 Lagrangian decomposition (主要思想是 Lagrangian relaxation)
前两种⽅法今天不是我们的主⾓，下⾯我们主要介绍 Lagrangian relaxation
1 拉格朗⽇松弛求解整数规划问题基本思想回顾
企业内部控制基本规范1.1 把约束放到⽬标上去 达到化繁为简的⽬的
这个我们就不具体讲了，因为基本上教科书上都会讲到。
1.2 尽量松弛掉linked/coupling constraints 让不可分问题变为可分问题
有如下优化问题
(A1)
(A2)
(A3)
决策变量有两⼤类
，
约束（A1）和约束（A2）分别只和
有关，⽽约束（A3）是⼀个linked/coupling constraints，它把
两类变量耦合在了⼀起。
若采⽤Lagrangian relaxation 把约束（A3）松弛到⽬标函数得到松弛问题：
(B1)
(B2)
此时由于linked/coupling constraints被处理掉了，因此在松弛问题中决策变量
实现了解耦可以分为两个⼦问题分别对
求优化
⼦问题1：
⼦问题2：
对偶函数：
对偶问题：
2 为什么要⽤拉格朗⽇松弛？
1 拉格朗⽇松弛之后得到的问题下界要⼤于等于 直接将0,1整数变量松弛为[0,1]连续变量的下界。⼀⾔以蔽之就是 拉格朗松弛得到的解的质量要好。
2 采⽤拉格朗⽇松弛之后我们会得到拉格朗⽇乘⼦，拉格朗⽇乘⼦反应了对偶的信息，那么⽤这个这个对偶信息可以做很多很多事情（此处省略⼀万字）。
3 如果问题具有linked/coupling constraints那么采⽤拉格朗⽇松弛之后可以使得问题被分解，进⽽⼤⼤简化原问题。
3 拉格朗⽇迭代算法及收敛性分析
拉格朗⽇松弛求解整数规划问题的主要包括两⼤模块，1是松弛后的⼦问题求解；2是拉格朗⽇乘⼦的更新（对偶问题求解）
1松弛后的⼦问题求解
松弛后的⼦问题求解，⼀般要根据⼦问题的具体性质来确定求解⽅式。在整数规划问题中采⽤拉格朗⽇松弛后的⼦问题⼀般最好不要是NP-hard的或者⼀般问题规模很⼩可以进⾏暴⼒求解，否则⼦问题的求解还需要进⼀步特殊处理。所以⼀般我们求解⼦问题可以直接让求解器（GurobiCplex等）直接求解即可，也可以根据具体情况采⽤动态规划，线性规划等⼿段帮助求解。
2拉格朗⽇乘⼦更新
拉格朗⽇乘⼦更新本质上是要求 对偶问题。由于对偶问题是⼀个⾮光滑凸优化问题，我们这⾥采⽤次梯度算法来更新拉格朗⽇乘⼦。
(1)
其中
为乘⼦，
分别为第k步迭代的步长和次梯度⽅向。其步长选取公式为
（2）
次梯度选取公式为（次梯度的选择不唯⼀，这⾥只给出常见的⼀种）
（3）
想具体了解次梯度的可参考
函数的次梯度如何理解？w ww.zhihu
松弛后的⼦问题求解和拉格朗⽇乘⼦更新分别反复迭代进⾏下去就构成了算法的流程。如下图所⽰：
只要按照公式（1-3）的⽅式选择步长和乘⼦迭代⽅向就可以保证收敛性，相关收敛性证明过程可以参考⽂献[3]的476页。
4 拉格朗⽇松弛迭代算法需要注意的问题
4.1 次梯度算法步长公式有⼤学问
公式（2）给出的步长选取范围
其中
是对偶问题最优解，实际上
是⼀个未知的量。我们整个算法就是为了求唐建华简历
啊，那在求解过程中怎么会知道
的值呢。所以这个步长范围的公式看似美丽实际上不太实⽤，同时步长的选择其实对最终的求解效果有着举⾜轻重的影响。
快思图⽬前已经有很多很多的paper着⼒于改进这个问题。⼀个思路是想办法估计
，另⼀个思路就是Surrogate Lagrangian Relaxation，具体可以参考⽂献[1].
4.2 尽量少松弛约束
平常在讲解拉格朗⽇松弛理论的时候是习惯把所有约束放到⽬标函数上去，以⽅便推导和讲解的过程，但是在实操过程中，松弛约束条件的做法实际上是没有办法的办法。能不松弛还是尽量还是不要松弛，能少松弛就少松弛⼀点。千万不要看着教科书上都是给全松弛了就⼀股脑全松弛掉约束条件，那样肯定不会得到⾼质量的解的。
4.3 松弛后的⼦问题要尽量简单
就像之前提到的拉格朗⽇松弛后的⼦问题⼀般最好不要是NP-hard的或者是问题规模很⼩即使是NP-hard也可以暴⼒求解的。
所以如果松弛后的⼦问题还是规模⽐较⼤的NP-hard问题，那么就需要⼀些特殊⽅法来进⼀步处理，那么有可能这个优化问题难度是⽐较⼤的，采⽤Lagrangian Relaxation未必能得到好的效果。
4.4 松弛后的问题尽量保证具备可分性
有线电视技术⾯对整数规划问题的求解很重要的⼀个思想就是通过decomposition来降低问题规模。如果所求解的优
化问题没有 linked/coupling constraints 这种特性，可以在松弛linked/coupling constraints后将优化问题变成可分的性质的话，则该优化问题不推荐直接使⽤拉格朗⽇松弛来求解。
4.5 拉格朗⽇松弛得到的是⼀个最优解的下界（很可能是不可⾏解）
值得注意的是拉格朗⽇松弛得到的同样是⼀个原问题的下界，即不可⾏解。所以在完成拉格朗⽇松弛算法后我们还需要⼀个启发式算法把得到的这个不可⾏解修复为可⾏解。
5 拉格朗⽇松弛算法求解应⽤实例高处作业吊篮
要求解的简单⼆次整数规划问题实例，本例⼦来⾃于参考⽂献[1]的第⼀个实验：
将两个约束松弛到⽬标函数上来可得
代码主流程如下所述：
max_itertimes = 30
for i in range(max_itertimes):
外蒙古
subproblempute_obj(dualproblem.lamd)
subproblem.solve()
dualproblempute_subgradients(subproblem)
dualproblempute_stepsize(subproblem)
dualproblem.update_lamd()
print("optimal solution = ", subproblem.opt_solution)
print("subgradients = ", dualproblem.subgradients)
subproblem为松弛问题⼦问题的对象，dualproblem为对偶问题的对象，然后我们先求解松弛问题 subproblem.solve()，然后再求解对偶问题，求解对偶包括 计算次梯度（compute_subgradients），计算步长(compute_stepsize)和更新乘⼦(update_lamd)
我们（⼀作我师妹，三作是我，我主要负责了代码开发）最近也做了⼀个关于Surrogate Lagrangian r
elaxation求解⽣产调度的问题见参考⽂献[2]，后期我们也会把代码开源供⼤家学习参考。
参考⽂献：
【1】Bragin M A, Luh P B, Yan J H, et al. Convergence of the Surrogate Lagrangian Relaxation Method[J]. Journal of Optimization Theory and Applications, 2015, 164(1): 173-201.
【2】Cui H, Luo X, Wang Y, et al. Scheduling of steelmaking-continuous casting process using deflected surrogate Lagrangian relaxation approach and DC algorithm[J]. Computers & Industrial Engineering, 2020.
【3】Bertsekas D P. ⾮线性规划[J]. 清华⼤学出版社，2013.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议