论文部分内容阅读
二阶锥规划(SOCP)是一类基于仿射集和有限个二阶锥的笛卡尔乘积的交集上极大化或极小化一个线性函数的凸优化问题.它作为线性规划(LP)的推广及半正定规划(SDP)的特例,有着广泛的应用.为此,许多数学规划问题都通过转化成二阶锥规划进行求解. 本文主要讨论二阶锥规划的数值解法-原始-对偶内点算法,具体包括以下几部分内容: 第一章:二阶锥规划简介及研究进展. 第二章:提出一个新的二次核函数,并分析该函数的性质,进而基于该函数给出二阶锥规划的原始-对偶内点算法.通过探讨算法的复杂性,求出基于该二次核函数的大步校正法的理论迭代界为O(r3/4 logr/(ε)),此迭代界略好于基于对数障碍函数的理论迭代界O(r logr/(ε)).此外,我们通过数值实验表明了本章算法是可行有效的. 第三章:用对数核函数φ(t)=t2-1/2-log(t)及核函数φ(t)=1/2(t-1/t)2的凸组合,构造了另一个新核函数.在证明了该核函数的性质的基础上给出了二阶锥规划的原始-对偶内点算法.通过研究算法的复杂性,求出了基于该凸组合核函数的大步校正算法的理论迭代界为O(r2/3log r/(ε),该界与基于核函数φ(t)=1/2(t-1/t)2的理论迭代界一致. 第四章:对本文的总结.