半定規(guī)劃（SDP）作為線性規(guī)劃（LP）的一種推廣,被廣泛應(yīng)用于許多科學(xué)和工程領(lǐng)域,如組合優(yōu)化、控制理論和模式識(shí)別等。近年來,許多求解LP的內(nèi)點(diǎn)算法被成功推廣到了SDP上,使得SDP逐漸受到學(xué)者們的關(guān)注。內(nèi)點(diǎn)算法（IPM）是目前求解SDP問題最有效的算法,根據(jù)初始點(diǎn)是否可行分為可行內(nèi)點(diǎn)算法（FIPM）和不可行內(nèi)點(diǎn)算法（IIPM）。全牛頓步不可行內(nèi)點(diǎn)算法因在迭代過程中僅使用牛頓步,不需要線搜索,可以降低算法的計(jì)算量而成為研究熱點(diǎn)之一。全牛頓步不可行內(nèi)點(diǎn)算法一般包含兩個(gè)迭代過程:可行步和中心步。其中,可行步是為了得到新的擾動(dòng)問題的一個(gè)嚴(yán)格可行點(diǎn),并且該迭代點(diǎn)位于擾動(dòng)問題中心路徑的二次收斂區(qū)間內(nèi);中心步是以新的擾動(dòng)問題的嚴(yán)格可行點(diǎn)作為初始點(diǎn)進(jìn)行迭代,進(jìn)而得到下一個(gè)擾動(dòng)問題的可行點(diǎn)。本文基于新的可行步搜索方向提出一種全牛頓步不可行內(nèi)點(diǎn)算法;其次,對Wang等人^[45]所提算法的理論分析進(jìn)行改進(jìn),簡化了算法的分析過程。主要成果如下:1.基于Liu和Sun^[35]提出的核函數(shù),構(gòu)造了一種新的全牛頓步不可行內(nèi)點(diǎn)算法。新算法采用該核函數(shù)代替可行步搜索方向中的原... 

【文章來源】：西安電子科技大學(xué)陜西省 211工程院校 教育部直屬院校

【文章頁數(shù)】：66 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
符號(hào)對照表
縮略語對照表
第一章 緒論
    1.1 半定規(guī)劃的研究背景及意義
    1.2 半定規(guī)劃的基本理論
        1.2.1 半定規(guī)劃的基本概念
        1.2.2 半定規(guī)劃對偶理論
    1.3 半定規(guī)劃的主要算法
        1.3.1 內(nèi)點(diǎn)法
        1.3.2 非內(nèi)點(diǎn)法
    1.4 全牛頓步不可行內(nèi)點(diǎn)算法的研究現(xiàn)狀
    1.5 本文的主要工作和內(nèi)容安排
第二章 基于特定核函數(shù)的全牛頓步不可行內(nèi)點(diǎn)算法
    2.1 引言
    2.2 預(yù)備知識(shí)
        2.2.1 擾動(dòng)問題和它的中心路徑
        2.2.2 經(jīng)典牛頓搜索方向
    2.3 基于核函數(shù)的可行步搜索方向
    2.4 全牛頓步不可行內(nèi)點(diǎn)算法
        2.4.1 算法的迭代
        2.4.2 不可行內(nèi)點(diǎn)算法
    2.5 算法分析
        2.5.1 (?)的上界
        2.5.2 Tr(X+S)的上界
    2.6 小結(jié)
第三章 改進(jìn)算法分析的全牛頓步不可行內(nèi)點(diǎn)算法
    3.1 引言
    3.2 基礎(chǔ)知識(shí)
    3.3 全牛頓步不可行內(nèi)點(diǎn)算法
        3.3.1 中心近似函數(shù)
        3.3.2 算法的迭代
        3.3.3 算法框架
    3.4 算法分析
        3.4.1 可行步的作用
        3.4.2 (?)的上界
        3.4.3 Tr(XS)的上界
    3.5 小結(jié)
第四章 總結(jié)和展望
    4.1 總結(jié)
    4.2 展望
參考文獻(xiàn)
致謝
作者簡介


【參考文獻(xiàn)】：
期刊論文
[1]Karmarkar算法——一種新的線性規(guī)劃多項(xiàng)式算法[J]. 李躍明.  南京郵電學(xué)院學(xué)報(bào). 1987(02)

博士論文
[1]線性規(guī)劃和互補(bǔ)問題的寬鄰域內(nèi)點(diǎn)算法研究[D]. 馬曉玨.西安電子科技大學(xué) 2017
[2]桁架結(jié)構(gòu)拓?fù)鋬?yōu)化的理論與應(yīng)用研究[D]. 高閣.中國科學(xué)院大學(xué)(中國科學(xué)院長春光學(xué)精密機(jī)械與物理研究所) 2017

碩士論文
[1]半定規(guī)劃的不可行內(nèi)點(diǎn)算法[D]. 吳岳.西安電子科技大學(xué) 2015



本文編號(hào)：3472843