【摘要】：眾所周知,原-對(duì)偶內(nèi)點(diǎn)算法是求解線性規(guī)劃問(wèn)題最有效的算法之一。2001年以前,幾乎所有的原-對(duì)偶內(nèi)點(diǎn)算法都是采用牛頓方向作為搜索方向,這種搜索方向和原-對(duì)偶對(duì)數(shù)障礙函數(shù)有密切聯(lián)系。通過(guò)替換對(duì)數(shù)障礙函數(shù)為新的核函數(shù)障礙函數(shù),可以得到新的搜索方向并設(shè)計(jì)核函數(shù)內(nèi)點(diǎn)算法�；诤撕瘮�(shù)的e-凸性在設(shè)計(jì)大步可行內(nèi)點(diǎn)算法中大大簡(jiǎn)化算法分析的作用,本文將核函數(shù)的e-凸性引入線性規(guī)劃的全牛頓步可行算法設(shè)計(jì),接著給出線性規(guī)劃基于核函數(shù)的全牛頓步不可行內(nèi)點(diǎn)算法,并推廣到半正定規(guī)劃,就設(shè)計(jì)新算法和復(fù)雜性分析進(jìn)行研究。首先,給出了線性規(guī)劃基于有限障礙核函數(shù)的全牛頓步可行算法。不僅僅將核函數(shù)用來(lái)確定搜索方向,更為重要的是,將核函數(shù)的性質(zhì)特別是e-凸性用于全牛頓步內(nèi)點(diǎn)算法分析,簡(jiǎn)化了算法復(fù)雜性分析過(guò)程,并且算法得到了同迄今為止可行內(nèi)點(diǎn)算法最好的復(fù)雜性一致的結(jié)果。接著,根據(jù)大步核函數(shù)內(nèi)點(diǎn)算法框架研究了所討論核函數(shù)的特點(diǎn),明確指出其不可用于大步內(nèi)點(diǎn)算法設(shè)計(jì)。實(shí)際上,此類(lèi)核函數(shù)剛好可以用于設(shè)計(jì)全牛頓步內(nèi)點(diǎn)算法,并且具有巨大的優(yōu)勢(shì)。為得到更好的數(shù)值表現(xiàn),對(duì)核函數(shù)確定的搜索方向進(jìn)行改進(jìn),定義新的寬鄰域,結(jié)合經(jīng)典寬鄰域內(nèi)點(diǎn)算法,給出了基于核函數(shù)的寬鄰域內(nèi)點(diǎn)算法。雖然理論復(fù)雜度較全牛頓步內(nèi)點(diǎn)算法有所提高,但是數(shù)值實(shí)驗(yàn)顯示了其優(yōu)越性,彌補(bǔ)了核函數(shù)全牛頓步內(nèi)點(diǎn)算法在數(shù)值表現(xiàn)上的不足。其次,基于簡(jiǎn)單的核函數(shù)設(shè)計(jì)了線性規(guī)劃的新的不可行內(nèi)點(diǎn)算法。傳統(tǒng)的全牛頓步不可行內(nèi)點(diǎn)算法理論上有優(yōu)勢(shì),但是所采用的傳統(tǒng)牛頓方向和臨近度量使得算法分析復(fù)雜。新的簡(jiǎn)單核函數(shù)不僅僅用于構(gòu)造搜索方向和二次收斂域,其性質(zhì)特別是e-凸性的引入使得全牛頓步不可行內(nèi)點(diǎn)算法的復(fù)雜性分析大大簡(jiǎn)化,并且算法得到了線性規(guī)劃同迄今為止最好的不可行內(nèi)點(diǎn)算法復(fù)雜性一致的結(jié)果。進(jìn)一步,借助于核函數(shù)矩陣函數(shù)的定義以及矩陣分析工具,將求解線性規(guī)劃問(wèn)題基于簡(jiǎn)單函數(shù)的全牛頓步不可行內(nèi)點(diǎn)算法推廣到求解半正定規(guī)劃問(wèn)題中,在保持同迄今為止最好的不可行內(nèi)點(diǎn)算法復(fù)雜性一致的結(jié)果的同時(shí)同樣大大簡(jiǎn)化了傳統(tǒng)半正定規(guī)劃全牛頓步不可行內(nèi)點(diǎn)算法的復(fù)雜性分析。最后,借助于在執(zhí)行可行步之后尋找更低的臨近度量的估計(jì),用來(lái)簡(jiǎn)化全牛頓步不可行內(nèi)點(diǎn)算法復(fù)雜性分析,即去除中心步的思想,針對(duì)半正定規(guī)劃問(wèn)題,對(duì)核函數(shù)所確定的搜索方向進(jìn)行改進(jìn),使得可行步跟蹤下一擾動(dòng)問(wèn)題的障礙參數(shù)更新后的中心路徑,設(shè)計(jì)了新的全牛頓步不可行內(nèi)點(diǎn)算法.該算法只需要執(zhí)行可行步,不需要任何中心步,復(fù)雜性分析簡(jiǎn)化的同時(shí)得到了和線性規(guī)劃問(wèn)題不可行內(nèi)點(diǎn)算法迄今為止最好的復(fù)雜性一致的結(jié)果。數(shù)值實(shí)驗(yàn)表明采用新的改進(jìn)方向后,算法的臨近度量值顯著降低,并且優(yōu)于傳統(tǒng)半正定規(guī)劃全牛頓步不可行內(nèi)點(diǎn)算法。
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2018
【分類(lèi)號(hào)】：O221.1

【相似文獻(xiàn)】

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

1 溫春燕;烏彩英;;二階錐規(guī)劃基于核函數(shù)凸組合的內(nèi)點(diǎn)算法[J];內(nèi)蒙古大學(xué)學(xué)報(bào)(自然科學(xué)版);2017年02期

2 馮增哲;張西學(xué);劉建波;房亮;;半定規(guī)劃的一個(gè)新的寬鄰域非可行內(nèi)點(diǎn)算法[J];運(yùn)籌學(xué)學(xué)報(bào);2014年02期

3 張維泉;張圣貴;;基于新函數(shù)下的半定規(guī)劃原始對(duì)偶內(nèi)點(diǎn)算法的復(fù)雜度分析[J];福建師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年02期

4 龔小玉;王先甲;胡振鵬;;基于核函數(shù)求解線性互補(bǔ)問(wèn)題的不可行內(nèi)點(diǎn)算法[J];數(shù)學(xué)雜志;2013年03期

5 陳飛翔;劉金魁;武忠祥;張輝;;半定規(guī)劃的一種修正原對(duì)偶內(nèi)點(diǎn)算法研究[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2011年01期

6 張鋒;段余平;邱軍;馮小琴;;基于粒子群算法與內(nèi)點(diǎn)算法的無(wú)功優(yōu)化研究[J];電力系統(tǒng)保護(hù)與控制;2010年13期

7 陳飛翔;張輝;武忠祥;;凸二次規(guī)劃的原-對(duì)偶內(nèi)點(diǎn)算法數(shù)值實(shí)驗(yàn)初步[J];科學(xué)技術(shù)與工程;2009年01期

8 楊春艷;雍龍泉;;求解凸二次規(guī)劃的一種改進(jìn)的原-對(duì)偶內(nèi)點(diǎn)算法[J];長(zhǎng)江大學(xué)學(xué)報(bào)(自然科學(xué)版)理工卷;2009年02期

9 王永麗;王鑫;賀國(guó)平;;求解半定規(guī)劃的原始對(duì)偶勢(shì)下降內(nèi)點(diǎn)算法研究[J];山東科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年06期

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

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

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

2 王國(guó)強(qiáng);錢(qián)忠根;;凸二次規(guī)劃的新的原始-對(duì)偶內(nèi)點(diǎn)算法[A];數(shù)學(xué)·力學(xué)·物理學(xué)·高新技術(shù)研究進(jìn)展——2006（11）卷——中國(guó)數(shù)學(xué)力學(xué)物理學(xué)高新技術(shù)交叉研究會(huì)第11屆學(xué)術(shù)研討會(huì)論文集[C];2006年

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

4 朱志斌;張可村;;非凸非線性規(guī)劃一個(gè)全局收斂的可行內(nèi)點(diǎn)算法[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（下卷）[C];2004年

5 王曉敏;劉靈;;半定規(guī)劃的原始-對(duì)偶不可行內(nèi)點(diǎn)算法[A];2006年中國(guó)運(yùn)籌學(xué)會(huì)數(shù)學(xué)規(guī)劃分會(huì)代表會(huì)議暨第六屆學(xué)術(shù)會(huì)議論文集[C];2006年

6 韋化;陽(yáng)育德;;微分-代數(shù)方程約束的電力系統(tǒng)最優(yōu)化問(wèn)題——模型與現(xiàn)代內(nèi)點(diǎn)算法[A];2006年中國(guó)運(yùn)籌學(xué)會(huì)數(shù)學(xué)規(guī)劃分會(huì)代表會(huì)議暨第六屆學(xué)術(shù)會(huì)議論文集[C];2006年

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

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

9 楊國(guó)梁;黃思明;;應(yīng)用內(nèi)點(diǎn)算法求解效用函數(shù)意義下證券組合有效選擇問(wèn)題[A];2002年中國(guó)管理科學(xué)學(xué)術(shù)會(huì)議論文集[C];2002年

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

1 馬曉玨;線性規(guī)劃和互補(bǔ)問(wèn)題的寬鄰域內(nèi)點(diǎn)算法研究[D];西安電子科技大學(xué);2017年

2 汪威威;錐規(guī)劃的核函數(shù)全牛頓步內(nèi)點(diǎn)算法研究[D];西安電子科技大學(xué);2018年

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

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

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

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

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

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

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

10 楊林峰;計(jì)及機(jī)組啟停的動(dòng)態(tài)最優(yōu)潮流問(wèn)題研究[D];廣西大學(xué);2012年

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

1 王亞丹;半定規(guī)劃的全牛頓步不可行內(nèi)點(diǎn)算法研究[D];西安電子科技大學(xué);2018年

2 徐志宇;基于二階錐規(guī)則的投資追蹤問(wèn)題[D];南京大學(xué);2018年

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

4 溫春燕;二階錐規(guī)劃的內(nèi)點(diǎn)算法研究[D];內(nèi)蒙古大學(xué);2017年

5 劉金倩;半定規(guī)劃的不可行內(nèi)點(diǎn)算法研究[D];西安電子科技大學(xué);2017年

6 李思琦;半定規(guī)劃原始對(duì)偶內(nèi)點(diǎn)算法的復(fù)雜度分析[D];渤海大學(xué);2015年

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

8 李秀峰;錐規(guī)劃基于寬鄰域的內(nèi)點(diǎn)算法[D];西安電子科技大學(xué);2014年

9 鐘兆偉;半定規(guī)劃的內(nèi)點(diǎn)算法[D];西安電子科技大學(xué);2010年

10 張博;原-對(duì)偶內(nèi)點(diǎn)算法用于優(yōu)化問(wèn)題的研究及其在風(fēng)險(xiǎn)投資領(lǐng)域的應(yīng)用[D];西安電子科技大學(xué);2005年

，

本文編號(hào)：2640284