基于局部Self-Concordant障礙函數(shù)的內(nèi)點算法.pdf

1、1994年數(shù)學(xué)規(guī)劃專家Yurii Nesterov教授和Arkadi Nemirovskii教授首次提出了self-concordance(SC)函數(shù)以及SC障礙函數(shù)的理論，并基于SC障礙函數(shù)設(shè)計了統(tǒng)一求解一般凸優(yōu)化問題的內(nèi)點算法，給出了算法復(fù)雜性的統(tǒng)一分析。這個研究工作是前沿性和高度有影響的，2006年Arkadi Nemirovski教授被邀請在西班牙數(shù)學(xué)家大會做了一小時報告. 對SC函數(shù)以及SC障礙函數(shù)的研究由C.Roos

2、教授領(lǐng)導(dǎo)的研究團隊進行了推廣.2006年，他們首次提出了局部SC(LSC)障礙函數(shù)的概念，試圖將已有的基于核函數(shù)的障礙函數(shù)和SC障礙函數(shù)統(tǒng)一起來.在這幾位研究者工作的基礎(chǔ)上，本文研究了兩個由核函數(shù)確定的障礙函數(shù)的LSC障礙性質(zhì).這兩個函數(shù)的LSC障礙性質(zhì)的體現(xiàn)主要是通過對它們的兩個重要參數(shù)的計算，由于這兩個重要參數(shù)與優(yōu)化問題的維數(shù)有關(guān)，因此也與算法的計算復(fù)雜性有關(guān).其次，本文設(shè)計了求解自對偶線性規(guī)劃問題(SP) min{qTx:Mx≥-

3、q，x≥0}的純Newton步內(nèi)點算法.其中，M為斜對稱矩陣(即MT=-M)，0≤q∈Rn，x∈Rn.我們分析了算法的復(fù)雜性，得到此算法具有多項式時間算法復(fù)雜性的結(jié)論.最后，我們給出了一個數(shù)值計算實例來說明LSC障礙函數(shù)的參數(shù)對算法復(fù)雜性的影響. 全文共分為六章：第一章是緒論，綜述了內(nèi)點法和SC函數(shù)、SC障礙函數(shù)的歷史發(fā)展，介紹了內(nèi)點法的基本思想及分類.第二章介紹了SC函數(shù)和SC障礙函數(shù)的概念和性質(zhì)，給出了解線性規(guī)劃問題的純Ne