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

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

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