二次锥规划的算法研究

论文摘要

二次锥规划是一类十分重要的非光滑凸规划问题,它是在有限个二次锥的笛卡儿乘积的仿射子空间的交集上极小化或极大化一个线性函数,许多数学问题都可转化成二次锥规划求解,如线性规划和凸二次规划等。由于其在工程、控制、金融等领域的广泛应用,近年来二次锥规划问题备受关注。本文主要研究了二次锥规划的一些不可行内点算法和光滑方法,并探讨了二次锥互补函数的几种光滑函数及其性质。具体内容如下:1.为了克服内点算法中要求初始点严格可行这一缺点,提出二次锥规划的三种不可行内点算法—原对偶不可行内点算法、基于价值函数的不可行内点法和预估校正不可行内点算法。不可行内点算法不要求初始点及其迭代点的可行性,只要它们位于中心路径的某个不可行邻域内即可。通过恰当选取步长,证明了不可行内点算法是全局收敛的多项式时间算法。2.将线性规划中求解搜索方向的非精确技巧引入到二次锥规划,给出求解二次锥规划的三种非精确不可行内点算法。算法允许运用非精确搜索方向,且不要求初始点和迭代点位于严格可行解集内。非精确搜索方向在计算时可以有适度的误差,特别当求解大规模二次锥规划问题时可节省计算时间和内存,同时证明了这三种算法的全局收敛性。3.给出Chen-Harker-Kanzow-Smale（CHKS）光滑函数和光滑Fischer-Burmeister函数的一些性质;提出两种新的向量值函数,讨论其利普希茨连续、强半光滑和可微性质,给出其雅可比公式,并证明它们分别是最小值函数的光滑函数和Fischer—Burmeister函数的光滑函数,上述工作将在二次锥规划光滑方法的设计及收敛性分析中起到重要作用。4.提出二次锥规划的五种带光滑参数的光滑牛顿法,基于最小值函数或Fischer-Burmeister函数,将二次锥规划问题转化为一个非线性方程组,用牛顿法求解该方程组的扰动,且在迭代过程中恰当选取光滑参数,从而得到二次锥规划问题的最优解,算法对初始点的选取没有任何限制且是全局收敛的。5.给出二次锥规划的五种带光滑变量的光滑牛顿法并证明了其全局收敛性.基于二次锥互补函数的光滑函数构造一个等价于最优性条件的非线性方程组,该方程组不含任何显式的不等式约束,如x∈K,s∈K或x∈K0,s∈K0。然后用牛顿法求解这一非线性方程组,得到二次锥规划问题的最优解。这五种算法都将光滑函数中的参数视作变量,因而每一步迭代只需求解一个线性方程组,并进行一次线性搜索。算法对初始点的选取都没有任何限制,且其收敛性分析不依赖一致非奇异假设。

论文目录

• 符号说明
• 摘要
• ABSTRACT
• 第一章 绪论
• §1.1 二次锥规划简介
• §1.2 预备知识
• §1.3 本文内容安排
• 第二章 二次锥规划的不可行内点算法
• §2.1 严格可行内点算法
• §2.2 原-对偶不可行内点算法
• §2.3 基于价值函数的不可行内点法
• §2.4 预估-校正不可行内点算法
• §2.5 非精确不可行内点算法Ⅰ
• §2.6 非精确不可行内点算法Ⅱ
• §2.7 非精确不可行内点算法Ⅲ
• 第三章 二次锥互补函数的光滑函数
• §3.1 二次锥互补函数
• §3.2 CHKS光滑函数
• §3.3 最小值函数的新光滑函数
• §3.4 光滑Fischer-Burmeister函数
• §3.5 Fischer-Burmeister函数的新光滑函数
• 第四章 二次锥规划的带光滑参数的光滑方法
• §4.1 全局收敛的光滑方法
• §4.2 预估-校正光滑方法
• §4.3 非内部连续化算法
• §4.4 二阶收敛的非内部连续化算法
• §4.5 二阶收敛的光滑牛顿法
• 第五章 二次锥规划的带光滑变量的光滑方法
• §5.1 全局收敛的光滑牛顿法
• §5.2 超线性收敛的非内部连续化算法
• §5.3 一步光滑牛顿法
• §5.4 次二阶收敛的光滑牛顿法
• §5.5 次二阶收敛的非内部连续化算法
• 结束语
• 致谢
• 参考文献
• 在读博士期间撰写（发表）的论文
• 在读博士期间参加的科研项目