半定规划的全牛顿步不可行内点算法研究

发布时间：2021-11-03 02:16

　　半定规划（SDP）作为线性规划（LP）的一种推广,被广泛应用于许多科学和工程领域,如组合优化、控制理论和模式识别等。近年来,许多求解LP的内点算法被成功推广到了SDP上,使得SDP逐渐受到学者们的关注。内点算法（IPM）是目前求解SDP问题最有效的算法,根据初始点是否可行分为可行内点算法（FIPM）和不可行内点算法（IIPM）。全牛顿步不可行内点算法因在迭代过程中仅使用牛顿步,不需要线搜索,可以降低算法的计算量而成为研究热点之一。全牛顿步不可行内点算法一般包含两个迭代过程:可行步和中心步。其中,可行步是为了得到新的扰动问题的一个严格可行点,并且该迭代点位于扰动问题中心路径的二次收敛区间内;中心步是以新的扰动问题的严格可行点作为初始点进行迭代,进而得到下一个扰动问题的可行点。本文基于新的可行步搜索方向提出一种全牛顿步不可行内点算法;其次,对Wang等人^[45]所提算法的理论分析进行改进,简化了算法的分析过程。主要成果如下:1.基于Liu和Sun^[35]提出的核函数,构造了一种新的全牛顿步不可行内点算法。新算法采用该核函数代替可行步搜索方向中的原... 

【文章来源】：西安电子科技大学陕西省 211工程院校 教育部直属院校

【文章页数】：66 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
符号对照表
缩略语对照表
第一章 绪论
    1.1 半定规划的研究背景及意义
    1.2 半定规划的基本理论
        1.2.1 半定规划的基本概念
        1.2.2 半定规划对偶理论
    1.3 半定规划的主要算法
        1.3.1 内点法
        1.3.2 非内点法
    1.4 全牛顿步不可行内点算法的研究现状
    1.5 本文的主要工作和内容安排
第二章 基于特定核函数的全牛顿步不可行内点算法
    2.1 引言
    2.2 预备知识
        2.2.1 扰动问题和它的中心路径
        2.2.2 经典牛顿搜索方向
    2.3 基于核函数的可行步搜索方向
    2.4 全牛顿步不可行内点算法
        2.4.1 算法的迭代
        2.4.2 不可行内点算法
    2.5 算法分析
        2.5.1 (?)的上界
        2.5.2 Tr(X+S)的上界
    2.6 小结
第三章 改进算法分析的全牛顿步不可行内点算法
    3.1 引言
    3.2 基础知识
    3.3 全牛顿步不可行内点算法
        3.3.1 中心近似函数
        3.3.2 算法的迭代
        3.3.3 算法框架
    3.4 算法分析
        3.4.1 可行步的作用
        3.4.2 (?)的上界
        3.4.3 Tr(XS)的上界
    3.5 小结
第四章 总结和展望
    4.1 总结
    4.2 展望
参考文献
致谢
作者简介


【参考文献】：
期刊论文
[1]Karmarkar算法——一种新的线性规划多项式算法[J]. 李跃明.  南京邮电学院学报. 1987(02)

博士论文
[1]线性规划和互补问题的宽邻域内点算法研究[D]. 马晓珏.西安电子科技大学 2017
[2]桁架结构拓扑优化的理论与应用研究[D]. 高阁.中国科学院大学(中国科学院长春光学精密机械与物理研究所) 2017

硕士论文
[1]半定规划的不可行内点算法[D]. 吴岳.西安电子科技大学 2015



本文编号：3472843