求解非线性规划问题的原始对偶内点算法

发布时间：2018-06-03 14:44

本文选题：原始对偶内点算法 + 非线性规划　；参考：《吉林大学》2017年硕士论文

【摘要】：非线性规划问题来源于生产流程安排、过程最优设计、质量控制、库存控制、系统自动化控制、管理科学和预报等诸多领域,并且与各个领域间发展的相关性日益密切,非线性规划问题的最优理论和求解算法的研究备受关注。自1984年,Karmarkar首次提出求解优化问题的内点算法以来,人们又相继提出了更多的原始对偶内点算法,原始对偶内点算法发展为求解非线性规划问题的有效算法之一,原始对偶内点算法是通过构造一类值函数,来寻找下降方向。我们首先综述现有的原始对偶内点算法,随后给出带参数扰动的原始对偶内点算法求解非线性规划问题,并给出算法收敛性的证明以及具体数值算例。初始点的选择对于原始对偶内点算法的计算效率而言有着至关重要的作用,目前大部分算法的初始点均在可行域内部选择。当可行域较复杂时,便很难做到在可行域内部寻找合适的初始点,有必要扩大初始点的选择范围,从而提高原始对偶内点算法的计算效率,我们给出一种带参数扰动的原始对偶内点算法,通过对约束函数进行适当的摄动,得到一个参数化的规划问题,进而在参数化的非线性规划问题基础上,得到其Lagrange函数以及对应的障碍惩罚函数。进一步通过构造参数化的非线性规划问题的值函数来寻找下降方向,并用修正牛顿法进行迭代来计算下降方向。通过摄动参数的引入,极大的改进了原始对偶内点算法,利用参数控制初始点选择的可行域,扩大了初始点的选择范围,进一步提高收敛速度。当摄动参数变为1时,得到比原规划问题可行域大的新可行域,初始点在新的扩大的可行域内选择;当摄动参数变为0时,扩大的可行域会收敛到原规划问题的可行域,进而找到原规划问题的KKT点。数值算例表明带参数扰动的原始对偶内点算法是有效可行的。
[Abstract]:Nonlinear programming problems come from many fields, such as production flow arrangement, process optimal design, quality control, inventory control, system automation control, management science and forecast, and are closely related to the development of various fields. The study of optimal theory and algorithm for nonlinear programming has attracted much attention. Since 1984 when Karmarkar first proposed interior point algorithm for solving optimization problems, more and more original dual interior point algorithms have been put forward. The original dual interior point algorithm has been developed into one of the effective algorithms for solving nonlinear programming problems. The original dual interior point algorithm is to find the descent direction by constructing a class of value functions. We first summarize the existing primal dual interior point algorithm, then we give the original dual interior point algorithm with parameter perturbation to solve the nonlinear programming problem, and prove the convergence of the algorithm and give a numerical example. The selection of initial points plays an important role in the computational efficiency of the original dual interior point algorithm. At present, most of the initial points of the algorithm are selected within the feasible region. When the feasible domain is more complex, it is difficult to find a suitable initial point within the feasible domain. It is necessary to expand the selection range of the initial point so as to improve the computational efficiency of the original dual interior point algorithm. We give a primal dual interior point algorithm with parameter perturbation. By proper perturbation of the constraint function, we obtain a parameterized programming problem, which is based on the parameterized nonlinear programming problem. The Lagrange function and the corresponding obstacle penalty function are obtained. Furthermore, the descent direction is found by constructing the value function of parameterized nonlinear programming problem, and the descent direction is calculated by iterating the modified Newton method. Through the introduction of perturbation parameters, the original dual interior point algorithm is greatly improved. By using parameters to control the feasible region of initial point selection, the range of initial point selection is expanded, and the convergence rate is further improved. When the perturbation parameter becomes 1, a new feasible region is obtained, which is larger than that of the original programming problem, and the initial point is selected in the new extended feasible region, and when the perturbation parameter becomes 0, the expanded feasible region converges to the feasible region of the original programming problem. Then the KKT point of the original programming problem is found. Numerical examples show that the original dual interior point algorithm with parameter perturbation is effective and feasible.
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O221.2

【参考文献】