半定規(guī)劃的算法研究.pdf

1、半定規(guī)劃是線性規(guī)劃的一種推廣.近年來其理論和算法取得了很大的進(jìn)展,并且在組合優(yōu)化、系統(tǒng)工程和電子工程等領(lǐng)域得到了廣泛應(yīng)用,已成為數(shù)學(xué)規(guī)劃領(lǐng)域中一個新的活躍的研究方向.本文首先介紹了半定規(guī)劃的基礎(chǔ)知識、基本理論、主要算法和研究現(xiàn)狀,然后對半定規(guī)劃的算法作了一些研究,主要內(nèi)容如下:1.將非精確算法結(jié)合到不可行內(nèi)點(diǎn)法中,給出了求解半定規(guī)劃的一種非精確不可行內(nèi)點(diǎn)法,該算法在迭代中不需要保持迭代點(diǎn)的可行性,而且使用的搜索方向僅需要達(dá)到一個相對的精

2、度.本章最后分析了其收斂性,結(jié)果表明,該算法最多可以在O(n<'2>ln(1/ε))步內(nèi)求出半定規(guī)劃的一個ε--近似解.2.引入矩陣值函數(shù)的一些相關(guān)概念,基于向量空間與矩陣空間之間的同構(gòu)關(guān)系給出了矩陣值函數(shù)的一些重要性質(zhì),并分析了常用的幾種矩陣值函數(shù)的強(qiáng)半光滑性.這在半定規(guī)劃的一些算法的構(gòu)造及收斂性分析中起關(guān)鍵作用.3.通過對半定規(guī)劃的KKT最優(yōu)性條件的等價轉(zhuǎn)化,得到一個等價的非線性方程組,其中不再含有像X≥0,Z≥或X>0,Z>0這樣