本文選題：原始對偶內(nèi)點(diǎn)算法 + 非線性規(guī)劃��； 參考：《吉林大學(xué)》2017年碩士論文

【摘要】：非線性規(guī)劃問題來源于生產(chǎn)流程安排、過程最優(yōu)設(shè)計(jì)、質(zhì)量控制、庫存控制、系統(tǒng)自動化控制、管理科學(xué)和預(yù)報(bào)等諸多領(lǐng)域,并且與各個(gè)領(lǐng)域間發(fā)展的相關(guān)性日益密切,非線性規(guī)劃問題的最優(yōu)理論和求解算法的研究備受關(guān)注。自1984年,Karmarkar首次提出求解優(yōu)化問題的內(nèi)點(diǎn)算法以來,人們又相繼提出了更多的原始對偶內(nèi)點(diǎn)算法,原始對偶內(nèi)點(diǎn)算法發(fā)展為求解非線性規(guī)劃問題的有效算法之一,原始對偶內(nèi)點(diǎn)算法是通過構(gòu)造一類值函數(shù),來尋找下降方向。我們首先綜述現(xiàn)有的原始對偶內(nèi)點(diǎn)算法,隨后給出帶參數(shù)擾動的原始對偶內(nèi)點(diǎn)算法求解非線性規(guī)劃問題,并給出算法收斂性的證明以及具體數(shù)值算例。初始點(diǎn)的選擇對于原始對偶內(nèi)點(diǎn)算法的計(jì)算效率而言有著至關(guān)重要的作用,目前大部分算法的初始點(diǎn)均在可行域內(nèi)部選擇。當(dāng)可行域較復(fù)雜時(shí),便很難做到在可行域內(nèi)部尋找合適的初始點(diǎn),有必要擴(kuò)大初始點(diǎn)的選擇范圍,從而提高原始對偶內(nèi)點(diǎn)算法的計(jì)算效率,我們給出一種帶參數(shù)擾動的原始對偶內(nèi)點(diǎn)算法,通過對約束函數(shù)進(jìn)行適當(dāng)?shù)臄z動,得到一個(gè)參數(shù)化的規(guī)劃問題,進(jìn)而在參數(shù)化的非線性規(guī)劃問題基礎(chǔ)上,得到其Lagrange函數(shù)以及對應(yīng)的障礙懲罰函數(shù)。進(jìn)一步通過構(gòu)造參數(shù)化的非線性規(guī)劃問題的值函數(shù)來尋找下降方向,并用修正牛頓法進(jìn)行迭代來計(jì)算下降方向。通過攝動參數(shù)的引入,極大的改進(jìn)了原始對偶內(nèi)點(diǎn)算法,利用參數(shù)控制初始點(diǎn)選擇的可行域,擴(kuò)大了初始點(diǎn)的選擇范圍,進(jìn)一步提高收斂速度。當(dāng)攝動參數(shù)變?yōu)?時(shí),得到比原規(guī)劃問題可行域大的新可行域,初始點(diǎn)在新的擴(kuò)大的可行域內(nèi)選擇;當(dāng)攝動參數(shù)變?yōu)?時(shí),擴(kuò)大的可行域會收斂到原規(guī)劃問題的可行域,進(jìn)而找到原規(guī)劃問題的KKT點(diǎn)。數(shù)值算例表明帶參數(shù)擾動的原始對偶內(nèi)點(diǎn)算法是有效可行的。
[Abstract]:Nonlinear programming problems come from many fields, such as production flow arrangement, process optimal design, quality control, inventory control, system automation control, management science and forecast, and are closely related to the development of various fields. The study of optimal theory and algorithm for nonlinear programming has attracted much attention. Since 1984 when Karmarkar first proposed interior point algorithm for solving optimization problems, more and more original dual interior point algorithms have been put forward. The original dual interior point algorithm has been developed into one of the effective algorithms for solving nonlinear programming problems. The original dual interior point algorithm is to find the descent direction by constructing a class of value functions. We first summarize the existing primal dual interior point algorithm, then we give the original dual interior point algorithm with parameter perturbation to solve the nonlinear programming problem, and prove the convergence of the algorithm and give a numerical example. The selection of initial points plays an important role in the computational efficiency of the original dual interior point algorithm. At present, most of the initial points of the algorithm are selected within the feasible region. When the feasible domain is more complex, it is difficult to find a suitable initial point within the feasible domain. It is necessary to expand the selection range of the initial point so as to improve the computational efficiency of the original dual interior point algorithm. We give a primal dual interior point algorithm with parameter perturbation. By proper perturbation of the constraint function, we obtain a parameterized programming problem, which is based on the parameterized nonlinear programming problem. The Lagrange function and the corresponding obstacle penalty function are obtained. Furthermore, the descent direction is found by constructing the value function of parameterized nonlinear programming problem, and the descent direction is calculated by iterating the modified Newton method. Through the introduction of perturbation parameters, the original dual interior point algorithm is greatly improved. By using parameters to control the feasible region of initial point selection, the range of initial point selection is expanded, and the convergence rate is further improved. When the perturbation parameter becomes 1, a new feasible region is obtained, which is larger than that of the original programming problem, and the initial point is selected in the new extended feasible region, and when the perturbation parameter becomes 0, the expanded feasible region converges to the feasible region of the original programming problem. Then the KKT point of the original programming problem is found. Numerical examples show that the original dual interior point algorithm with parameter perturbation is effective and feasible.
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O221.2

【參考文獻(xiàn)】

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

1 李建華;李子鵬;呂顯瑞;張慧;;帶參數(shù)擾動的原始對偶內(nèi)點(diǎn)算法求解一類非線性規(guī)劃問題[J];吉林大學(xué)學(xué)報(bào)(理學(xué)版);2015年06期

，

本文編號：1973162