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

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

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