论文部分内容阅读
二阶锥规划是一个凸优化问题,它是在一个仿射子空间和有限个二阶锥的笛卡尔乘积的交集上极大化或极小化一个线性函数.许多数学规划问题,如线性规划、凸二次规划和二次约束的凸二次规划等,都可转化为二阶锥规划求解.近年来,由于其在工程、控制与设计、机器学习、组合优化等诸多领域的广泛应用,二阶锥规划已成为数学规划领域的一个重要的研究方向.本文主要研究求解二阶锥规划的内点算法和光滑算法.全文共分八章.首先在第一章,我们简要介绍二阶锥规划的模型,研究背景、意义和现状,并概述了本文的主要工作.第二章,给出一个求解二阶锥规划的非精确不可行内点算法.算法不要求初始点及其迭代点的可行性,只要求每次迭代产生的点位于不可行中心路径的某个邻域内.通过选取适当的步长,证明了算法是全局收敛的多项式时间算法.第三章,给出了一个新的增长项是线性的核函数.基于此核函数给出了一个求解二阶锥规划的原始-对偶内点算法,分析了算法的复杂性,并得到了一个关于大步校正方法的迭代界O(rlogr/s),这里r表示二阶锥规划中二阶锥的个数.这个界与典型的基于对数障碍函数的原始-对偶内点算法的界相同.此外,我们还给出了一个数值例子,并探讨了核函数中的参数对算法运行的影响.第四章,将求解线性规划的加权路径跟踪内点算法推广求解二阶锥规划.该方法在每步迭代时采用完全牛顿步,不需要做任何线搜索,并且具有局部二次收敛速度和目前所知的最好的多项式时间算法复杂性.第五章,通过对称扰动Fischer-Burmeister函数,给出一个新的光滑函数.基于该光滑函数,把二阶锥规划问题转化成一个参数化的光滑方程组,并给出了一个非内部连续化算法.该算法对初始点的选取没有任何限制,不要求初始点及所产生的迭代点严格可行.算法在每步迭代中只需解一个线性方程组并进行一次线性搜索.即使不满足严格互补假设条件,所给算法也具有全局收敛和局部二阶收敛性.数值试验表明新算法是有效的.第六章,提出一类含有单参数的光滑函数,它包含一些已知的光滑函数作为特殊情况.基于此类光滑函数,给出一个求解二阶锥规划的光滑牛顿法,在较弱条件下证明了算法具有全局和局部二阶收敛性.此外,我们还利用随机产生的一些二阶锥规划问题做数值试验.数值结果不但表明算法是有效的,还表明光滑函数中的参数在算法的运行过程中起着重要作用.第七章,基于一个非对称扰动的Fischer-Burmeister光滑函数,给出了一个新的求解二阶锥规划的光滑算法.该算法所产生的迭代点列的任何聚点都是二阶锥规划的解.进一步,算法产生的迭代点列有界,因此至少有一个聚点.在一致非奇异条件下证明了所给算法具有局部二阶收敛性.数值试验验证了算法的可行性和有效性.第八章,总结了本文的主要工作,并提出了一些有待进一步研究的课题.