改进参数选择的内点法求解线性规划问题

发布时间：2020-07-22 10:04

【摘要】：内点法是目前求解优化问题最有效算法之一,不仅在理论方面保证了多项式复杂度,在实际操作中也取得了良好的效果.自1984年Karmarkar提出第一个多项式时间的内点法以来,经过三十多年不断的发展,如今已经取得了丰硕成果.现在,内点法已成功应用于很多优化问题,如:线性规划,凸规划,互补问题,半定规划等.研究者们开发了许多基于内点算法的优化软件包并得到广泛应用.用内点法解线性规划问题时,需要找到下一步迭代方向和步长,首先通过解牛顿方程来确定方向,如何简便有效地解这个方程组显得尤为重要.现有直接法和迭代法,直接法如高斯消去法,Cholesky分解等,但这些方法存储量大,CPU时间长,且解决大型问题时会遇到稠密或病态系数矩阵,被迫停机等问题.本文提出的算法采用迭代法求解,首先通过预估步和校正步得出下一步迭代方向,再通过极小化度量函数找到使目标函数下降的最优步长,进而得到下一步迭代点,算法产生一系列迭代点最终收敛至最优点.本文不仅在理论方面得到了线性收敛速率,还进行了大量的数值实验,得到了较好的实验结果,证明该算法的可行性.本文共分为四章:第一章描述本文所考虑问题的背景、国内外研究现状和全文的框架结构;第二章提出问题并给出解决问题的算法;第三章分析算法的收敛性及复杂度;第四章分析数值实验结果并总结全文.
【学位授予单位】：北京工业大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O221.1

【相似文献】