【摘要】：本學(xué)位論文研究一類特殊的非線性半定規(guī)劃問題,即凸二次半定規(guī)劃(簡記為CQSDP).這類問題在經(jīng)濟(jì)、金融、工程設(shè)計、控制論等領(lǐng)域有著廣泛的應(yīng)用.因此,研究凸二次半定規(guī)劃問題的求解算法在理論和應(yīng)用方面都有重要的意義.本學(xué)位論文提出了凸二次半定規(guī)劃問題的一個基于勢函數(shù)的原始對偶勢下降內(nèi)點算法和一個長步原始對偶路徑跟蹤算法.首先,根據(jù)線性半定規(guī)劃原始對偶勢下降內(nèi)點法的思想,基于仿射縮放(affine-scaling)方向和Nesterov Todd-scaling(NT-scaling)方向以及勢函數(shù),建立了 CQSDP 的一個原始對偶勢下降內(nèi)點算法.該算法具有以下特點:使用原始對偶affine-scaling 方向作為搜索方向且迭代點落在中心路徑附近時,勢函數(shù)有充分的下降性;當(dāng)?shù)c遠(yuǎn)離中心路徑時使用NT-scaling方向作為搜索方向也保證了勢函數(shù)的充分下降性;算法至多迭代O(√nln1/ε)可得到一個ε-最優(yōu)解.其次,借鑒線性半定規(guī)劃長步原始對偶路徑跟蹤法的思想,引入原始對偶對數(shù)障礙函數(shù),采用NT方向作為搜索方向,提出了凸二次半定規(guī)劃的長步原始對偶路徑跟蹤算法.該算法具有以下特點:對數(shù)障礙函數(shù)有充分的下降性;當(dāng)?shù)c落在中心路徑附近時步長1被接受;算法至多迭代O(n|lnε|)次后可得到一個ε-最優(yōu)解.最后,對本學(xué)位論文提出的兩個算法進(jìn)行了初步的數(shù)值測試,數(shù)值結(jié)果表明這兩個算法是可行并且有效的.
[Abstract]:In this dissertation, we study a class of special nonlinear semidefinite programming problems, namely convex quadratic semidefinite programming (abbreviated as CQSDP). Such problems are widely used in the fields of economy, finance, engineering design, cybernetics and so on. Therefore, it is very important to study the algorithm of convex quadratic semidefinite programming in theory and application. In this paper, we propose a potential function based original dual potential descent interior point algorithm and a long step original dual path tracking algorithm for convex quadratic semidefinite programming. Firstly, according to the idea of original dual potential descent interior point method of linear semidefinite programming, based on affine scaling (affine-scaling) direction, Nesterov Todd-scaling (NT-scaling) direction and potential function, an original dual potential descent interior point algorithm for CQSDP is established. The algorithm has the following characteristics: when the original dual affine-scaling direction is used as the search direction and the iterative point falls near the center path, the potential function has sufficient descent; When the iteration point is far from the center path, the NT-scaling direction is used as the search direction, and the sufficient descent of the potential function is also ensured, and the algorithm can obtain an 蔚 -optimal solution at most by iterating O (nln1/ 蔚). Secondly, based on the idea of long step original dual path tracking for linear semidefinite programming, the original dual logarithmic obstacle function is introduced, and the NT direction is used as the search direction, and a long step original dual path tracking algorithm for convex quadratic semidefinite programming is proposed. The algorithm has the following characteristics: the logarithmic barrier function has sufficient descent, the step size 1 is accepted when the iterative point falls near the central path, and the algorithm can obtain an 蔚 -optimal solution after iterating at most the O (n ln 蔚 times. Finally, the numerical results of the two algorithms proposed in this dissertation show that the two algorithms are feasible and effective.
【學(xué)位授予單位】：廣西大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O221

【參考文獻(xiàn)】

相關(guān)期刊論文 前6條

1 Zhi Bin ZHU;Hua Li ZHU;;A Filter Method for Nonlinear Semidefinite Programming with Global Convergence[J];Acta Mathematica Sinica(English Series);2014年10期

2 黃靜靜;王愛文;;二次半定規(guī)劃的原始對偶內(nèi)點算法的H..K..M搜索方向的存在唯一性[J];數(shù)學(xué)的實踐與認(rèn)識;2008年18期

3 康志林;張圣貴;;一類二次半定規(guī)劃問題及其內(nèi)點算法[J];福建師范大學(xué)學(xué)報(自然科學(xué)版);2008年01期

4 徐鳳敏;徐成賢;;求解二次半定規(guī)劃的原對偶內(nèi)點算法(英文)[J];工程數(shù)學(xué)學(xué)報;2006年04期

5 關(guān)秀翠,刁在筠;二次半定規(guī)劃問題及其投影收縮算法[J];高等學(xué)校計算數(shù)學(xué)學(xué)報;2002年02期

6 聶家旺,袁亞湘;A potential reduction algorithm for an extended SDP problem[J];Science in China,Ser.A;2000年01期

，

本文編號：2302520