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

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

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

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