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

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

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

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