半定规划信赖域算法的研究

论文摘要

半定规划（SDP）是线性规划的一种推广,它是在满足约束“对称矩阵的仿射组合半正定”的条件下使线性目标函数极大（极小）化的问题.这个约束是非线性、非光滑、凸的,因而半定规划是一个非光滑凸优化问题.最近几十年来,由于半定规划的理论和算法的研究取得了很大的进展,并且半定规划在控制论、电子工程、组合优化等领域得到了广泛的应用,因此它已发展成为数学规划领域中一个非常活跃的研究方向.本文首先就半定规划的产生与发展做了一个比较详细的概述,介绍了半定规划最初的产生过程以及最近几十年来学术界关于半定规划算法研究的发展情况.接着又给出了半定规划的基本概念、半定规划的对偶理论、半定规划的主要算法介绍以及半定规划的实际应用背景等.本文的主要部分给出了求解半定规划的信赖域算法.首先利用互补松弛条件求出了原半定规划与其对偶问题的最优性条件,即KKT-条件.通过最优性条件,就把求解半定规划问题转化成了一个求解非线性不可微方程组的解问题.接着,利用推广的Fischer-Burmeister光滑函数,将不可微的方程组转化成一个非线性可微的方程组.然后又把这个非线性可微的方程组转化成了一个无约束的优化问题.最后利用最小二乘原理,定义了一个效益函数,因此求解原来的半定规划问题就转化为了求解无约束最小优化问题.最后,本文利用信赖域算法求出了上述无约束最小优化问题的近似解,即为原半定规划问题的最优解,并分析了该算法的有效性、适定性,还给出了算法的收敛性证明,表明该算法是切实可行的.

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 半定规划的产生与发展
• 1.2 半定规划的研究现状及意义
• 1.3 本文的主要工作和内容安排
• 第2章 基本理论
• 2.1 半定规划的基本概念
• 2.1.1 半定规划
• 2.1.2 对偶理论
• 2.2 半定规划的主要算法介绍
• 2.3 半定规划的应用
• 2.3.1 二次锥规划
• 2.3.2 二次约束二次凸规划
• 2.3.3 特征值优化问题
• 2.3.4 图的最大割问题
• 第3章 半定规划的信赖域算法
• 3.1 引言
• 3.2 半定规划的转化
• 3.3 定义函数的相关性质
• 3.3.1 定义函数的Lipschitzian连续性
• 3.3.2 定义函数的可微性
• 3.4 半定规划的信赖域算法
• 3.4.1 信赖域方法的基本思想
• 3.4.2 算法的步骤
• 3.4.3 算法的适定性
• 3.5 算法的收敛性分析
• 第4章 总结与展望
• 参考文献
• 致谢
• 附录