凸二次半定規(guī)劃兩個(gè)原始對(duì)偶內(nèi)點(diǎn)算法.pdf

1、本學(xué)位論文研究一類特殊的非線性半定規(guī)劃問題，即凸二次半定規(guī)劃(簡記為CQSDP).這類問題在經(jīng)濟(jì)、金融、工程設(shè)計(jì)、控制論等領(lǐng)域有著廣泛的應(yīng)用.因此，研究凸二次半定規(guī)劃問題的求解算法在理論和應(yīng)用方面都有重要的意義.
　　本學(xué)位論文提出了凸二次半定規(guī)劃問題的一個(gè)基于勢(shì)函數(shù)的原始對(duì)偶勢(shì)下降內(nèi)點(diǎn)算法和一個(gè)長步原始對(duì)偶路徑跟蹤算法.首先，根據(jù)線性半定規(guī)劃原始對(duì)偶勢(shì)下降內(nèi)點(diǎn)法的思想，基于仿射縮放(affine-scaling)方向和Neste

2、rov Todd-scaling(NT-scaling)方向以及勢(shì)函數(shù)，建立了CQSDP的一個(gè)原始對(duì)偶勢(shì)下降內(nèi)點(diǎn)算法.該算法具有以下特點(diǎn):使用原始對(duì)偶affine-scaling方向作為搜索方向且迭代點(diǎn)落在中心路徑附近時(shí)，勢(shì)函數(shù)有充分的下降性;當(dāng)?shù)c(diǎn)遠(yuǎn)離中心路徑時(shí)使用NT-scaling方向作為搜索方向也保證了勢(shì)函數(shù)的充分下降性;算法至多迭代O（√nln1/ε）可得到一個(gè)ε-最優(yōu)解.
　　其次，借鑒線性半定規(guī)劃長步原始對(duì)偶路徑跟