約束最佳化方法
正文
尋求具有約束條件的線性或非線性規劃問題解的數值算法。假設ƒ(尣),gi(尣)(i=1,2,…,m)是n維歐幾里得空間Rn中的實值函式。所謂約束最佳化問題,是指在約束條件gi(尣)≤0(i=1,2,…,m)之下求一點


對於只有等式約束的非線性規劃,經典的拉格朗日乘子法指出,在對函式加以一定限制下,最優解可在一組函式方程的解集中去尋求,但是並未指出行之有效的算法。1951年,H.W.庫恩和A.W.塔克爾發表“論非線性規劃”一文後,隨著計算技術的迅速發展,線性約束的非線性規劃出現了不少行之有效的算法。在非線性約束規劃的研究上,近十幾年來也有相當的進展。
可行方向法 根據逐次沿可行方向求可行解點的疊代思想構造一點列{尣k},使其滿足某種給定要求的算法稱為可行方向法。假設已知可行解為尣(k),若能找到一個向量










上述線性近似型算法的收斂速度,一般都不高於超線性的。對二階可微的函式ƒ(尣),在尣(k)處若用二次函式





序貫無約束極小化法 1943年R.庫朗對於僅帶一個約束等式g(尣)=0的問題,引入參數t>0,研究函式ƒ(尣)+t【g(尣)】2的平穩點尣(t)在t→∞時與原問題的關係。對於具有不等式約束gi(尣)≤0(i=1,2,…,m)的非線性規劃問題,則作函式
;









對兼有等式和不等式約束的最最佳化問題,可結合使用罰函式與障礙函式而構造出混合型函式來求解;對兼有線性和非線性約束的最最佳化問題,可僅將非線性約束納入p(尣,t)(或B(尣,r),或L(尣,u,t)),將問題化為線上性約束下p(尣,t)(或B(尣,r),或L(尣,u,t))的極小化問題。
對於不可微的凸規劃,近十多年來有人用次梯度或差分等概念來建立算法。設ƒ為Rn中的凸函式,若矢量






贊格威爾1969年提出用統一的觀點研究算法。他的基本思想是,將算法看成是一個點到集的映像。在一些假設下由上半連續的點到集映像產生的點列 {尣(k)}收斂於最優解。從而統一了不少已有算法的收斂性的研究。這方面的工作還在不斷發展。
參考書目
M.阿弗里爾著,李元熹等譯:《非線性規劃-分析與方法》,上冊,上海科學技術出版社,上海,1979。(M.Avriel,Nonlinear Programming-Analysis and Method,Prentice-hall,Englewood Cliffs,New Jersey,1976.)
A.V.Fiacco and G.P.McCormick,Nonlinear Pro-gramming Sequential unconstrained Minimization Techiques, John Wiley & Sons, New York, 1968.