文档介绍：半定规划的灵敏度分析
学位申请人李光荣
导师姓名及职称成央金教授
学院名称数学与计算科学学院
学科专业运筹学与控制论
研究方向半定规划及其应用
学位申请级别理学硕士
学位授予单位湘潭大学
论文提交日期 2011-4-20
Sensitivity analysis in semideﬁnite Programming
Candidate Guangrong Li
Supervisor and Rank Cheng
College Mathematics putational Science
Program Operational Research and ics
Specialization Semideﬁnite Programming and Its Applications
Degree Master of Science
University Xiangtan University
Date April 20th, 2011
湘潭大学
学位论文原创性声明
本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究
所取得的研究成果. 除了文中特别加以标注引用的内容外, 本论文不包
含任何其他个人或集体已经发表或撰写的成果作品. 对本文的研究做
出重要贡献的个人和集体, 均已在文中以明确方式标明. 本人完全意识
到本声明的法律后果由本人承担.
作者签名: 日期: 年月日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定, 同
意学校保留并向国家有关部门或机构送交论文的复印件和电子版, 允许
论文被查阅和借阅. 本人授权湘潭大学可以将本学位论文的全部或部分
内容编入有关数据库进行检索, 可以采用影印、缩印或扫描等复制手段
保存和汇编本学位论文.
涉密论文按学校规定处理.
作者签名: 日期: 年月日
导师签名: 日期: 年月日
摘要
半定规划是线性规划的推广,是数学规划方面相对较新的研究方向。随着
线性规划的内点算法成功的推广到半定规划上,近年来半定规划的理论和算法都
取得了重要进展,并在组合优化,控制论,系统论,移动通信等领域得到了广泛
的应用。
本文分为五章:第一章介绍了半定规划的发展历史和应用领域,并总结了目
前求解半定规划的主要思想和方法;第二章给出了本文要用到的数学知识,包括
半定规划的相关概念,半定规划的对偶理论和内点算法,以及线性规划的灵敏度
分析;第三章讨论了基于内点算法的半定规划的灵敏度分析,并重点研究了三种
方向的情形;第四章对半定规划的𝜀灵敏度分析进行了讨论;第五章对本文内容
进行了小结和展望。
关键词:半定规划;对偶理论;内点算法;灵敏度分析
I
Abstract
Semideﬁnite programming(SDP) is an extension of linear programming, It is
a new research ﬁeld in mathematical programming. In recent years,the interior
point method was extended to the ﬁled of semideﬁnite programming, the theory
and algorithm for SDP have developed greatly, and its numerous applications
are found binatorial optimization, ics, system engineering, mobile
communications.
This paper is divided into ﬁve parts. In the ﬁrst part, We introduce the
development and application of the semideﬁnite programming, summarize some
main thoughts and methods on solving semideﬁnite programming. In the second
chapter, We introduce some knowledge which we’ll use after, including relevant
concepts, duality theory and interior point algorithm on semideﬁnite program-