原始對偶內(nèi)點法的幾點研究.pdf

1、原始對偶內(nèi)點法是優(yōu)化算法中的一個熱點課題，長期以來一直受到廣泛的關(guān)注并取得了很大的進展。內(nèi)點法不但具有多項式復雜性，而且在實踐中也是很有效的。不可行內(nèi)點法起始于分量都為正的一個任意點，隨著最優(yōu)性的達到可行性也隨之達到。許多著名的軟件都是使用不可行內(nèi)點法，因而很有必要給予繼續(xù)關(guān)注。
　　 本文第一章主要研究求解線性規(guī)劃問題的full-Newton步不可行內(nèi)點算法，該算法使用的是full-Newton步，它的多項式復雜度跟現(xiàn)有的不可

2、行內(nèi)點法的復雜度保持一致。每次迭代由一個可行步(用于改善可行性)和幾個中心步(用于拉回到中心路徑)構(gòu)成。這個算法由Roos2006年最先提出，為了保持整個文章的可讀性，在1.2節(jié)我們簡單介紹Roos提出的full-Newton步不可行內(nèi)點法。我們提出在full-Newton步不可行內(nèi)點算法中引入kernel函數(shù)，將經(jīng)典的Newton方向延伸到一個更普遍的情況。
　　 第二章中，我們使用Nesterov-Todd方向?qū)⒌谝徽轮薪饩€

3、性規(guī)劃的原始對偶內(nèi)點法延伸到半定規(guī)劃。眾所周知，線性規(guī)劃的原始對偶可行的內(nèi)點法通過使用Nesterov-Todd方向很容易延伸到半定規(guī)劃。本文考慮的是不可行問題，在Roos的線性規(guī)劃問題基礎(chǔ)上，我們利用對數(shù)障礙函數(shù)的一些特性，成功地將算法延伸到半定規(guī)劃。
　　 最后我們涉足非線性規(guī)劃的內(nèi)點法.在第三章我們在Ulbrich的工作的基礎(chǔ)上，結(jié)合內(nèi)點方法提出一個3維的filter算法.該算法與原有算法相比，充分利用了filter框架的