本文選題：二階錐規(guī)劃 + 核函數(shù)　； 參考：《內(nèi)蒙古大學(xué)》2017年碩士論文

【摘要】：二階錐規(guī)劃(SOCP)是一類基于仿射集和有限個(gè)二階錐的笛卡爾乘積的交集上極大化或極小化一個(gè)線性函數(shù)的凸優(yōu)化問(wèn)題.它作為線性規(guī)劃(LP)的推廣及半正定規(guī)劃(SDP)的特例,有著廣泛的應(yīng)用.為此,許多數(shù)學(xué)規(guī)劃問(wèn)題都通過(guò)轉(zhuǎn)化成二階錐規(guī)劃進(jìn)行求解.本文主要討論二階錐規(guī)劃的數(shù)值解法—原始-對(duì)偶內(nèi)點(diǎn)算法,具體包括以下幾部分內(nèi)容:第一章:二階錐規(guī)劃簡(jiǎn)介及研究進(jìn)展.第二章:提出一個(gè)新的二次核函數(shù),并分析該函數(shù)的性質(zhì),進(jìn)而基于該函數(shù)給出二階錐規(guī)劃的原始-對(duì)偶內(nèi)點(diǎn)算法.通過(guò)探討算法的復(fù)雜性,求出基于該二次核函數(shù)的大步校正法的理論迭代界為O(O(r3/4logr/ε),此迭代界略好于基于對(duì)數(shù)障礙函數(shù)的理論迭代界O(rlogr/ε).此外,我們通過(guò)數(shù)值實(shí)驗(yàn)表明了本章算法是可行有效的.第三章:用對(duì)數(shù)核函數(shù)φ(t)=(t2-1)/2-log(t)及核函數(shù)φ(t)=1/2(t-1/t)~2的凸組合,構(gòu)造了另一個(gè)新核函數(shù).在證明了該核函數(shù)的性質(zhì)的基礎(chǔ)上給出了二階錐規(guī)劃的原始-對(duì)偶內(nèi)點(diǎn)算法.通過(guò)研究算法的復(fù)雜性,求出了基于該凸組合核函數(shù)的大步校正算法的理論迭代界為O(r2/3logr/ε),該界與基于核函數(shù)φ(t)=1/2(t-1/t)2的理論迭代界一致.第四章:對(duì)本文的總結(jié).
[Abstract]:Second order cone programming (SOCP) is a convex optimization problem in which a linear function is maximized or minimized on the intersection of affine sets and finite second order cones. It is widely used as a special case of linear programming (LP) and positive semidefinite programming (SDP). For this reason, many mathematical programming problems are solved by transforming them into second-order cone programming. In this paper, we mainly discuss the numerical solution of second-order cone programming, primal-dual interior point algorithm, including the following parts: chapter 1: introduction and research progress of second-order cone programming. Chapter 2: a new quadratic kernel function is proposed, and the properties of the function are analyzed. Based on this function, a primal-dual interior point algorithm for second-order cone programming is presented. By discussing the complexity of the algorithm, the theoretical iteration bound of the giant step correction method based on the quadratic kernel function is found to be O(O(r3/4logr/ 蔚, which is slightly better than the theoretical iteration bound O(rlogr/ 蔚 n based on logarithmic barrier function. In addition, numerical experiments show that the algorithm is feasible and effective. In Chapter 3, another new kernel function is constructed by using the convex combination of the logarithmic kernel function 蠁 t ~ (2) ~ (1 / 2) and the kernel function 蠁 ~ (t) ~ (1 / 2) / t ~ (1 / 1) ~ (2). On the basis of proving the properties of the kernel function, the primal-dual interior point algorithm for second-order cone programming is given. By studying the complexity of the algorithm, the theoretical iteration bound of the giant step correction algorithm based on the convex combined kernel function is obtained, which is consistent with the theoretical iteration bound based on the kernel function 蠁 / t / 2 / t ~ (-1) / t ~ (2). Chapter four: summary of this paper.
【學(xué)位授予單位】：內(nèi)蒙古大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O221

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 王國(guó)強(qiáng);白延琴;;一類關(guān)于半正定規(guī)劃的多項(xiàng)式原對(duì)偶內(nèi)點(diǎn)算法(英文)[J];Journal of Shanghai University;2006年03期

2 遲曉妮;劉三陽(yáng);穆學(xué)文;王淑華;;二次錐規(guī)劃的一種非精確不可行內(nèi)點(diǎn)算法[J];工程數(shù)學(xué)學(xué)報(bào);2006年04期

3 遲曉妮;劉三陽(yáng);;二次錐規(guī)劃的一種原-對(duì)偶不可行內(nèi)點(diǎn)算法[J];西安電子科技大學(xué)學(xué)報(bào);2007年02期

4 張艷梅;張圣貴;;基于一個(gè)新函數(shù)的二階錐規(guī)劃的原始對(duì)偶內(nèi)點(diǎn)算法分析[J];福建師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年04期

5 遲曉妮;劉三陽(yáng);李炳杰;;二次錐規(guī)劃的不可行內(nèi)點(diǎn)算法[J];蘭州大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年04期

6 劉徽;黃寬娜;;運(yùn)輸問(wèn)題求解的一種內(nèi)點(diǎn)算法[J];樂(lè)山師范學(xué)院學(xué)報(bào);2009年05期

7 宋翌;陽(yáng)彩霞;魏妮妮;;一種基于內(nèi)點(diǎn)算法的三重目標(biāo)過(guò)濾器優(yōu)化算法的研究與仿真[J];科技導(dǎo)報(bào);2013年01期

8 陳錫斌,周學(xué)良;變量帶上下界的內(nèi)點(diǎn)算法[J];武漢水利電力大學(xué)學(xué)報(bào);1993年01期

9 周學(xué)良,陳錫斌;變量帶上下界內(nèi)點(diǎn)算法的理論與實(shí)現(xiàn)[J];武漢水利電力大學(xué)學(xué)報(bào);1993年05期

10 周學(xué)良，，陳錫斌;推廣的變量帶上下界內(nèi)點(diǎn)算法及其應(yīng)用[J];武漢水利電力大學(xué)學(xué)報(bào);1994年06期

相關(guān)會(huì)議論文 前4條

1 岳玉靜;蔡新中;何冰潔;王國(guó)強(qiáng);;馬科維茨均值-方差模型的原-對(duì)偶內(nèi)點(diǎn)算法[A];第四屆全國(guó)決策科學(xué)/多目標(biāo)決策研討會(huì)論文集[C];2007年

2 張環(huán);潘平奇;;線性規(guī)劃的一個(gè)內(nèi)點(diǎn)算法[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

3 王浚嶺;;一類線性約束凸規(guī)劃問(wèn)題的內(nèi)點(diǎn)算法及其計(jì)算復(fù)雜性[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（下卷）[C];2004年

4 盛玉紅;熱西達(dá);;凸二次規(guī)劃問(wèn)題的一種內(nèi)點(diǎn)算法[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2004年

相關(guān)博士學(xué)位論文 前9條

1 劉新澤;對(duì)稱錐互補(bǔ)問(wèn)題若干內(nèi)點(diǎn)算法的復(fù)雜性研究[D];西安電子科技大學(xué);2014年

2 楊喜美;對(duì)稱錐規(guī)劃的寬鄰域內(nèi)點(diǎn)算法研究[D];西安電子科技大學(xué);2014年

3 馬鵬飛;旋轉(zhuǎn)錐互補(bǔ)函數(shù)及旋轉(zhuǎn)錐規(guī)劃內(nèi)點(diǎn)算法研究[D];上海大學(xué);2015年

4 王言金;最優(yōu)化的不可行內(nèi)點(diǎn)算法研究[D];武漢大學(xué);2004年

5 張立溥;錐規(guī)劃的全牛頓步不可行內(nèi)點(diǎn)算法[D];上海大學(xué);2011年

6 劉長(zhǎng)河;錐規(guī)劃中若干內(nèi)點(diǎn)算法的復(fù)雜性研究[D];西安電子科技大學(xué);2012年

7 遲曉妮;二次錐規(guī)劃的算法研究[D];西安電子科技大學(xué);2008年

8 張景;基于自協(xié)調(diào)指數(shù)核函數(shù)的原始—對(duì)偶內(nèi)點(diǎn)算法[D];上海大學(xué);2014年

9 羅自炎;Lyapunov-type對(duì)稱錐規(guī)劃[D];北京交通大學(xué);2010年

相關(guān)碩士學(xué)位論文 前10條

1 田文娟;半定規(guī)劃的原對(duì)偶內(nèi)點(diǎn)算法[D];西安電子科技大學(xué);2014年

2 張慧;求解非線性規(guī)劃問(wèn)題的原始對(duì)偶內(nèi)點(diǎn)算法[D];吉林大學(xué);2017年

3 王雪;勢(shì)函數(shù)下降內(nèi)點(diǎn)算法的研究[D];武漢大學(xué);2005年

4 劉萬(wàn)香;含自由變量?jī)?yōu)化問(wèn)題的內(nèi)點(diǎn)算法研究[D];曲阜師范大學(xué);2010年

5 遲曉妮;二次錐規(guī)劃的內(nèi)點(diǎn)算法及光滑牛頓法[D];西安電子科技大學(xué);2005年

6 柏欽璽;預(yù)估校正內(nèi)點(diǎn)算法研究[D];武漢大學(xué);2005年

7 孫曉靜;線性約束優(yōu)化的仿射尺度內(nèi)點(diǎn)算法[D];蘇州大學(xué);2009年

8 羅艾花;組合同倫內(nèi)點(diǎn)算法的研究[D];武漢大學(xué);2005年

9 王英妮;關(guān)于廣義互補(bǔ)問(wèn)題的內(nèi)點(diǎn)算法研究[D];曲阜師范大學(xué);2009年

10 李敬華;線性規(guī)劃的不可行內(nèi)點(diǎn)算法研究[D];西安電子科技大學(xué);2014年

本文編號(hào)：1927408