【摘要】：內(nèi)點(diǎn)法是目前求解優(yōu)化問題最有效算法之一,不僅在理論方面保證了多項式復(fù)雜度,在實(shí)際操作中也取得了良好的效果.自1984年Karmarkar提出第一個多項式時間的內(nèi)點(diǎn)法以來,經(jīng)過三十多年不斷的發(fā)展,如今已經(jīng)取得了豐碩成果.現(xiàn)在,內(nèi)點(diǎn)法已成功應(yīng)用于很多優(yōu)化問題,如:線性規(guī)劃,凸規(guī)劃,互補(bǔ)問題,半定規(guī)劃等.研究者們開發(fā)了許多基于內(nèi)點(diǎn)算法的優(yōu)化軟件包并得到廣泛應(yīng)用.用內(nèi)點(diǎn)法解線性規(guī)劃問題時,需要找到下一步迭代方向和步長,首先通過解牛頓方程來確定方向,如何簡便有效地解這個方程組顯得尤為重要.現(xiàn)有直接法和迭代法,直接法如高斯消去法,Cholesky分解等,但這些方法存儲量大,CPU時間長,且解決大型問題時會遇到稠密或病態(tài)系數(shù)矩陣,被迫停機(jī)等問題.本文提出的算法采用迭代法求解,首先通過預(yù)估步和校正步得出下一步迭代方向,再通過極小化度量函數(shù)找到使目標(biāo)函數(shù)下降的最優(yōu)步長,進(jìn)而得到下一步迭代點(diǎn),算法產(chǎn)生一系列迭代點(diǎn)最終收斂至最優(yōu)點(diǎn).本文不僅在理論方面得到了線性收斂速率,還進(jìn)行了大量的數(shù)值實(shí)驗,得到了較好的實(shí)驗結(jié)果,證明該算法的可行性.本文共分為四章:第一章描述本文所考慮問題的背景、國內(nèi)外研究現(xiàn)狀和全文的框架結(jié)構(gòu);第二章提出問題并給出解決問題的算法;第三章分析算法的收斂性及復(fù)雜度;第四章分析數(shù)值實(shí)驗結(jié)果并總結(jié)全文.
【學(xué)位授予單位】：北京工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O221.1

【相似文獻(xiàn)】

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

1 黃沁鋮;周玉榮;;預(yù)測校正對偶內(nèi)點(diǎn)法在實(shí)時電價的應(yīng)用研究[J];攀枝花學(xué)院學(xué)報;2015年05期

2 王淑華,劉三陽,穆學(xué)文,遲曉妮;半定規(guī)劃的一種非精確不可行內(nèi)點(diǎn)法[J];應(yīng)用數(shù)學(xué);2004年S1期

3 許諾,黃民翔;原對偶內(nèi)點(diǎn)法與定界法在無功優(yōu)化中的應(yīng)用[J];電力系統(tǒng)及其自動化學(xué)報;2000年03期

4 單明;周步祥;張彥軍;陳世君;付浩;;基于原-對偶內(nèi)點(diǎn)法的無功優(yōu)化不可行問題研究[J];電網(wǎng)技術(shù);2006年S2期

5 樂秀t

本文編號：2765669