凸二次規(guī)劃的一種寬鄰域內(nèi)點(diǎn)算法研究及拓展.pdf

1、內(nèi)點(diǎn)算法是求解線性規(guī)劃的有效的算法之一，它具有多項(xiàng)式復(fù)雜性，實(shí)際計(jì)算性能也可以與單純型法媲美，尤其對(duì)大規(guī)模問(wèn)題更顯高效性.第一個(gè)具有實(shí)用性的多項(xiàng)式復(fù)雜性內(nèi)點(diǎn)算法是由Karmarkar于1984年提出.此后20年，經(jīng)過(guò)眾多優(yōu)化專家的共同努力，對(duì)內(nèi)點(diǎn)算法的研究取得了豐碩成果：不僅建立了完善的理論體系，而且開(kāi)發(fā)出了高效的數(shù)值軟件.如今，內(nèi)點(diǎn)算法被成功推廣到求解凸規(guī)劃、互補(bǔ)問(wèn)題、半定規(guī)劃、二階錐優(yōu)化等.本文的研究工作主要在于對(duì)線性規(guī)劃寬鄰域內(nèi)點(diǎn)

2、算法的推廣，將其應(yīng)用到凸二次規(guī)劃和線性互補(bǔ)問(wèn)題，不僅設(shè)計(jì)了新的算法，完成了新算法的多項(xiàng)式迭代復(fù)雜性的證明，而且新算法的數(shù)值實(shí)驗(yàn)表明算法是有效的.本文共分四章,第一章介紹了相關(guān)基本知識(shí)及研究背景；第二章提出了凸二次規(guī)劃的基于鄰近度量函數(shù)最小值的寬鄰域預(yù)估-校正算法，并證明了算法的收斂性，用數(shù)值實(shí)驗(yàn)驗(yàn)證了新算法是可行的；第三章為線性互補(bǔ)問(wèn)題設(shè)計(jì)了一個(gè)Mehrotra型預(yù)估-校正算法并給出了多項(xiàng)式迭代復(fù)雜性的證明，進(jìn)行了數(shù)值實(shí)驗(yàn)；第四章是對(duì)全