二阶锥规划的理论与算法研究

二阶锥规划是在有限个二阶锥的笛卡儿乘积与仿射子空间的交集上求一个线性目标函数的最小值问题二阶锥规划是锥规划的一个分支，它既是线性规划的推广，又是半定规划的特例，是一种具有优美结构的对称锥规划这类规划应用广泛，比如在设施选址、图论控制优化、天线阵列设计、投资组合问题等方面以及金融、工程设计、数字信号处理、声学、力学、民航、电气等领域都有所应用因此，研究二阶锥规划问题的理论和算法具有重要的理论意义和应用价值 二阶锥规划问题的研究起源于17世纪，但直至最近十几年才进入活跃阶段，2fJfJ3年有了对其理论和算法研究的阶段性综述文章对二阶锥规划的算法研究主要分为内点法和非内点法两大类原始一对偶内点法是一类重要的内点法，包含“可行内点法”和"不可行内点法”两种，前者的初始点和迭代点均要求可行，后者的初始点和迭代点只需满足二阶锥约束可行内点法主要有原始一对偶路径跟踪算法，基于核函数的原始一对偶内点算法等不可行内点法常见的有不可行内点预估一校正算法，非精确不可行内点算法等非内点法主要有光滑牛顿法，非内点f内部)连续化方法，序列二次规划法等 在较全面了解二阶锥规划研究背景和研究进展的基础上，本文对二阶锥规划的理论和算法进行了深入的研究，并取得如下主要成果： l在12完善了综述性文章中若当代数性质一个重要定理的证明（见定理l 2 3），提出并证明了若当代数理论的三个新定理f见定理l 2 6一定理l 2 8) 2详细分析了2维f每个二阶锥约束都是2维的情形)二阶锥规划转化为线性规划的过程，给出相关的重要性质，并提出了求解2维二阶锥规划的对偶单纯形法和原始一对偶单纯形法，举例说明了算法的有效性并进行了灵敏度分析 3基于不可行内点法的优点和预估一校正算法的思想，建立了两个新的求解二阶锥规划的预估一校正算法其预估方向分别是Newton方向和Euler方向，校正方向属于Alizadeh—Haeberly一0verton㈦H0)方向的范畴算法的优点是对于初始内点和迭代内点可行或不可行的情形都适用主要创新点是构造了一个更简单的中心路径的邻域，这不仅与最优性条件切合，而且由此构造的两个新算法能处理较大规模的问题在一些假设条件下，算法具有全局收敛性、线性和二次收敛速度，并获得了0(rln（s。e）)的迭代复杂性界，其中r表示二阶锥规划问题所包含的二阶锥约束的个数数值实验结果表明提出的这两个算法是有效的 4分别提出了非光滑向量值Fische rBurmeisterfFB)函数和向量值最小函数的两个新光滑函数，并基于此建立了两个求解二阶锥规划的非内点连续化算法它们的共同优点是：初始点可任取；每次迭代只需求解一个线性方程组得到搜索方向，进行一次线搜索得到步长；在无严格互补假设下，得到算法的全局收敛性和强收敛性而且，证明了基于非光滑FB函数的光滑化算法还具有二次收敛性，并能很好地求解较大规模问题，同时证明了基于向量值最小函数的非内部连续化算法还获得超线性收敛性 全文结构如下：第一章对国内外的研究主流和发展现状进行追踪和系统分类描述，并且建立了三个有关若当代数的新定理；第二章提出2维二阶锥规划的对偶单纯形法和原始一对偶单纯形法并进行了灵敏度分析；第三章建立二阶锥规划两个新的预估一校正算法，它们对初始点和迭代点可行或不可行的情况都适用；第四章基于非光滑FB函数的一个新光滑函数建立了光滑化算法，并进行较大规模的数值实验；第五章提出向量值最小函数的一个新光滑函数并基于此建立了具有超线性收敛性的非内部连续化算法；第六章总结全文内容并展望进一步的研究工作