凸规划的广义中心路径跟踪算法及其拓展

摘要

内点算法是求解线性规划的有效算法之一,它具有多项式复杂性,实际计算性能也可以与单纯型法媲美,尤其对大规模问题更显高效.第一个具有实用性的多项式复杂性内点算法是由 Karmarkar于1984年提出的.此后20多年,经过众多优化专家的共同努力,对内点算法的研究取得了丰硕成果:不仅建立了完善的理论体系,而且开发出了高效的数值软件.如今,内点算法被成功推广到求解凸规划、互补问题、半定规划、二阶锥优化等领域.
　　本文的研究成果有以下两个方面:其一,基于Gonzaga,艾文宝等人的思想,对水平线性互补问题提出了一种新的广义中心路径跟踪算法.算法从任意原始-对偶可行内点出发,在每步迭代中取“仿射步”与“中心步”的凸组合为新的迭代方向,围绕一条广义中心路径趋于问题的最优解.通过对仿射步、中心步迭代方向及其交叉项上界的估计,证明了算法的多项式迭代复杂性.其二,基于J.Peng, T.Terlaky, Y.Q.Bai等学者近期的工作,构造了一个新的核函数,设计了一类求解P线性互补问题的内点算法.该算法用核函数的障碍函数替代以往原始-对偶算法所依赖的经典对数障碍函数,得到了新算法下大步校正方法和小步校正方法的多项式迭代复杂性界.* k)(
　　本文共分四章,第一章介绍了相关基本知识及研究背景;第二章提出了水平线性互补问题的广义中心路径跟踪算法,并证明了算法的多项式收敛性;第三章为P线性互补问题设计了一个基于新核函数的内点算法,分别给出了大步校正和小步校正下的多项式迭代复杂性界;第四章是对全文的总结和展望.

目录

封面

声明

中文摘要

英文摘要

目录

引 言

1 绪论

1.1 基本概念

1.2 内点算法产生的背景

1.3 内点算法的研究现状

1.4 基本符号

2 水平线性互补问题的广义中心路径跟踪算法

2.1 线性互补问题

2.2 广义中心路径

2.3 算法的描述

2.4 算法的收敛性

2.5 小结

3 *( )P ? 线性互补问题基于新核函数的内点算法

3.1 算法的描述

3.2 核函数及其增长性

3.3 内迭代中障碍函数的减少

3.4 迭代复杂性

3.5 小结

4 总结与展望

参考文献

后 记

附录：攻读硕士学位期间发表的部分学术论著