切平面在混合整数非线性规划中的应用

摘要

混合整数非线性规划（Mixed Integer Nonlinear Programming，MINLP）是一类包含连续和整数变量的非线性规划问题。MINLP是整数规划的一个重要分支，近几十年来MINLP的应用有了快速的发展，其应用领域包括流程工业、金融、工程、管理科学和运筹学等各个领域。MINLP问题的求解算法包括确定型算法和启发式算法，确定型算法是将难于求解的MINLP问题分解为相对容易求解的混合整数线性规划问题（Mixed Integer Linear Programming，MILP），其中一类分解方法是通过投影及对偶等方法将MINLP问题分解为MILP问题，另外一类是利用迭代构造切平面的方法将原问题分解为简单问题。 本文的目标是通过对求解凸MINLP问题的各种确定型算法的研究，明确切平面在确定型算法中的重要作用，利用切平面的构造方法对已知算法进行改进，并争取构造出新的算法。 本文首先给出了切平面在确定型算法中的作用，给出了切平面构造的位置和方法与各种算法收敛速度的关系，得出结论：切平面的构造影响算法的收敛速度，一般来说在非线性可行域边界上构造切平面的算法具有快的收敛速度，非线性可行域边界上构造的切平面称为支撑超平面；又MINLP问题的性质要求最优解为整数点，因此如果可以给出在整数点处快速生成支撑超平面的方法，就得到了一个简洁且收敛速度快的确定型算法。 基于此我们给出了求解MINLP问题的支撑超平面算法的一般形式，并证明了其收敛性，同时提出了三个具体支撑超平面算法，分别为平行下降支撑超平面算法，基于内点的支撑超平面算法和不基于内点的支撑超平面算法。 外逼近（Outer Approximation， OA）算法是求解MINLP问题的一个重要算法，有着很广泛的应用，该算法的缺点是需要利用两个NLP问题的求解。我们将SHP算法的思想引入到OA算法中，给出改进的OA算法，我们称新的算法为EOA（Extended Outer Approximation，EOA）算法。在EOA算法中，当第一个非线性规划问题无解时，利用Vinott's SHP算法生成一个支撑超平面，替换OA算法中通过求解第二个NLP问题生成的切平面。新算法继承了OA算法在非线性可行域边界整数点生成切平面的优势，同时减少了NLP问题的求解次数。 启发式算法和确定型算法是求解MINLP问题的两个不同类型的算法，确定型算法在求解MINLP问题时可以保证解的全局最优性，但对大规模问题的求解需要很长的计算时间，启发式方法不能保证解的全局最优，但求解问题时具有快速、简单的特点。本文我们给出了一种将启发式算法转化为确定型算法的切平面方法，新的算法继承了切平面方法全局收敛和启发式算法效率高的特点，并保证了算法的收敛速度和全局最优性，我们称这种算法为启发式切平面算法。

目录

文摘

英文文摘

声明

致谢

(1) 引言

a) 研究背景

b) 混合整数非线性规划概述

ⅰ.MINLP问题的提出及应用领域

ⅱ.求解MINLP问题的难点

c) MLNLP的研究现状

ⅰ.确定型算法的研究现状

ⅱ.启发式算法的研究现状

ⅲ.基于分枝定界的算法框架的研究现状

ⅳ.软件开发工作现状

d) 本文研究内容

e) 本文的创新点

f) 本文的组织

(2) 切平面的构造对确定型算法的影响

a) 目标函数的线性化

b) 非线性可行域线性化

c) 凸多面体对凸非线性可行域的逼近

d) 切平面生成对算法的影响

ⅰ.ECP方法

ⅱ.OA方法

2.4.3 GBD方法

2.4.4 LP/NLP based BB方法

2.4.5 Hybrid Algorithm方法

2.5 本章小结

3 支撑超平面算法及其三种特例

3.1 支撑超平面算法

3.1.1 一般SHP算法步骤

3.1.2 收敛性证明

3.2 平行下降SHP算法

3.3 基于内点的支撑超平面算法

3.4 不依赖于内点的支撑超平面算法NISHP

3.5 本章小结

4 利用SHP算法对OA算法的改进

4.1 OA算法中切平面的构造

4.2 改进的OA算法

4.3 本章小结

5 启发式算法转化为确定型算法的切平面方法

5.1 启发式方法概述

5.2 启发式切平面方法

5.3 一种启发式切平面算法

5.3.1 SR1 based SQP算法简介

5.3.2 SR1 based SQP切平面算法

5.4 本章小结

6 结论

6.1 研究成果

6.2 展望

参考文献

作者简历