文档介绍：A Dissertation Submitted in Partial Fulfillment of the Requirements for
the Degree of Master of Science
General Central Path Following Algorithm for Convex
Programming and Its Extension
Graduate Student: Chen Donghai
Major: Applied Mathematics
Supervisor: Prof. Zhang Mingwang
China Three Gorges University
Yichang, 443002,
May, 2011
三峡大学硕士学位论文
三峡大学学位论文原创性声明
本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立进行研究工
作所取得的成果,除文中已经注明引用的内容外,本论文不含任何其他个人或集体
中以明确方式标明,本人完全意识到本声明的法律后果由本人承担.
学位论文作者签名:
日期:
I
三峡大学硕士学位论文
内容摘要
内点算法是求解线性规划的有效算法之一,它具有多项式复杂性,实际计算性
能也可以与单纯型法媲美,尤其对大规模问题更显高效. 第一个具有实用性的多项
式复杂性内点算法是由 Karmarkar 于 1984 年提出的. 此后 20 多年,经过众多优化
专家的共同努力,对内点算法的研究取得了丰硕成果:不仅建立了完善的理论体系,
而且开发出了高效的数值软件. 如今,内点算法被成功推广到求解凸规划、互补问
题、半定规划、二阶锥优化等领域.
本文的研究成果有以下两个方面: 其一,基于 Gonzaga,艾文宝等人的思想,
对水平线性互补问题提出了一种新的广义中心路径跟踪算法. 算法从任意原始-对
偶可行内点出发,在每步迭代中取“仿射步”与“中心步”的凸组合为新的迭代方
向,围绕一条广义中心路径趋于问题的最优解. 通过对仿射步、中心步迭代方向及
其交叉项上界的估计,证明了算法的多项式迭代复杂性. 其二,基于 ,
, 等学者近期的工作,构造了一个新的核函数,设计了一类求解
P* )( 线性互补问题的内点算法. 该算法用核函数的障碍函数替代以往原始-对偶
算法所依赖的经典对数障碍函数,得到了新算法下大步校正方法和小步校正方法的
多项式迭代复杂性界.
本文共分四章,第一章介绍了相关基本知识及研究背景;第二章提出了水平线
性互补问题的广义中心路径跟踪算法,并证明了算法的多项式收敛性;第三章为
P* )( 线性互补问题设计了一个基于新核函数的内点算法,分别给出了大步校正和
小步校正下的多项式迭代复杂性界;第四章是对全文的总结和展望.
关键词:水平线性互补问题内点算法 P* )( 线性互补问题多项式复杂性
II
三峡大学硕士学位论文
Abstract
Interior point algorithm is one of the most efficient algorithms for solving linear
programming,it not only has plexity,but also can be used to solve large
scale linear programming problems as the simplex methods. The first practical interior
point algorithm with plexity was presented by Karmarkar in 1984. Since
then with the optimization experts’ works, a large amount of research results were
produced: the theoretical system has been founded and some efficient softwares have
been developed. Now, interior point algorithm is extended to Convex Programming,
Complementarity Problems , Second Order Cone Optimization, Semidefinite
Pro