一類線性約束下非光滑非線性規劃問題的優化研究

張 鵬

(武漢科技大學管理學院,湖北武漢,430081)

關于線性約束下的非線性規劃問題有過很多的研究。Zangw ill提出了次優化方法,其原理是將規劃問題轉化為一系列含等式約束的子問題,通過尋找最優解所在的流形使用無約束規劃的方法求解原問題[1];Spedicato等運用ABS算法分別求解含線性等式約束和含線性不等式約束的非線性規劃問題[2];Linderoth運用DC函數和雙線性函數的線性下界函數提出求解非凸二次約束的非凸規劃問題的分支定界算法[3];Vandenbussche等運用分支定界法求解具有箱形約束的非凸二次規劃問題[4];Li提出分解算法求解大規模二次規劃問題[5];Achache擴展了內點算法,提出了原始對偶路徑依賴法求解凸二次規劃問題[6];王永麗等提出濾子內點算法求解正定二次規劃問題[7];高岳林等提出了求解凹二次規劃問題的一個融合割平面方法的分支定界混合算法,并證明了算法是收斂的[8];趙敏等采用序列二次規劃方法,將非線性規劃轉化為一系列二次子規劃求解,并用信賴域二次規劃的方法求解子規劃問題,一定程度上降低了算法的復雜程度[9];夏少剛等提出了一種新的簡易算法求解具有箱形約束的二次規劃問題,并討論了算法的有限步收斂性[10];張鵬等結合序列二次規劃法和不等式組的旋轉算法求解線性約束連續可微的凸規劃問題[11-12]。上述問題的目標函數均是光滑的。

本文提出了一類線性約束下非光滑非線性規劃問題,采用分塊法和不等式組的旋轉算法對該問題進行求解,同時還證明該算法的收斂性和有效性。

1 線性約束下連續不可微的非線性規劃模型

1.1 模型描述

設非光滑的非線性規劃模型為

式中:H為正定或半正定矩陣;gi=(gi1,…,gin),i=1,…,n;f(x)為非光滑的非線性函數,其決策變量的交叉項為二次,非交叉項由線性函數和凹函數構成。ci(xi)為非光滑的凹函數,如圖1所示。

圖1 非光滑凹函數Fig.1 Nonsmooth concave function

1.2 模型分析

ci(xi)為非光滑的凹函數,可用線性函數加以擬合,如圖2所示。

圖2 非光滑凹函數的線性擬合Fig.2 L inear denotation of the nonsmooth concave function

圖2中,OB為ki(xi)=kixi,ki=ci(ai)/ai。用ki(xi)代替ci(xi),則模型(1)可以轉化為以下模型:

定理1 當x分別為模型(1)和模型(2)的可行解,則

證明:因為ci(xi)為凹函數,所以ci(xi)≥kixi,則

即

證畢。

假設模型(2)的最優解為x0=(x10,…,xn0)T,如果

證明:由于x0為模型(2)的最優解,則x0是模型(1)的可行解;又因為x＊為模型(1)的最優解,所以f(x＊)≤f(x0)。x＊是模型(2)的可行解,根據定理1可知,g0(x＊)≤f(x＊),因此

即模型(1)的解是收斂的。證畢。

若式(4)不成立,則對ci(xi)與kixi差額最大變量進行分枝。設

令

cs(xs)可通過cs1(xs1)和cs2(xs2)線性擬合,如圖3所示。

圖3 非光滑凹函數分段線性擬合Fig.3 Subsection linear denotation of the nonsmooth concave function

圖3中,直線OA為cs1(xs1),斜率ks1=cs(xs1/2)/(xs1/2);直線AB為cs2(xs2),斜率ks2=(cs(as)-cs(as/2))/(as/2)。則模型(2)可轉化為下列兩個模型:

和

定理3 若x1為模型(9)的最優解,則有

證明:由于x1為模型(9)的最優解,則x1為模型(2)的可行解。又由于所以

由于x＊為模型(2)的最優解,則x1為模型(2)的可行解,故有

由式(12)和式(13)可知

證畢。

由定理3可知,用cs1(xs1)和cs2(xs2)代替cs(xs)以后,目標函數將變大。若為任意小的正數,則x1為模型(1)的近似最優解。

2 算法的基本步驟

2.1 模型(1)的計算步驟

步驟2 如果P={φ},那么轉步驟9,否則轉步驟3。

步驟3 選擇一個問題(Pk)犘

步驟4 讓ki(xi)近似估計ci(xi),且Xk=下述數學規劃問題可轉化為

并轉步驟3

步驟9 停止計算就是模型(1)的最優解。

3 結語

提出了一類線性約束下非光滑非線性規劃問題,運用分塊法和不等式組的旋轉算法對該問題進行了求解,同時證明了該算法的收斂性和有效性。

[1] Zangwill WI.A decomposable nonlinear programming approach[J].Operations Research,1967,15(6):1 068-1 087.

[2] Spedicato E,Xia Z Q,Zhang L W.ABS algorithms for linear equations and optimization[J].Journal of Computational and Applied Mathematics,2000,124(12),155-170.

[3] Linderoth J.A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs[J].Math Programming,2005,103(2):251-282.

[4] Vandenbussche D,Nemhauser G L.A branch-andcut algo rithm fo r solving nonconvex quadratic prograMS with box constraints[J].Math Programming,2005,102(3):559-575.

[5] Li H M,Zhang K C.A decomposition algorithm for solving large-scale quadratic programming problems[J].Appli Math Comput.2006,173(1):394-403.

[6]Achache M.A new primal-dual path-following method for convex quadratic programming[J].Computational and Applied Mathematics,2006,25(1):97-110.

[7] 王永麗,賀國平,王鑫.求解正定二次規劃的一個全局收斂的濾子內點算法[J].數學的實踐與認識,2008,21:127-133.

[8] 高岳林,鄧光智.凹二次規劃問題的一個融合割平面方法的分支定界混合算法[J].工程數學學報,2008(4):589-596.

[9] 趙敏,李少遠.基于信賴域二次規劃的非線性模型預測控制優化算法[J].控制理論與應用,2009(6):634-640.

[10]夏少剛,費威.具有箱形約束的二次規劃的一種簡易算法[J].運籌與管理,2008(4):6-10.

[11]張鵬.不允許賣空情況下均值-方差和均值-VaR投資組合比較研究[J].中國管理科學,2008,16(4):7-11.

[12]張鵬,張忠楨,岳超源.基于效用最大化的投資組合旋轉算法研究[J].財經研究,2005(12):117-126.

[13]張鵬,張忠楨,曾永泉.限制性賣空的均值-方差投資組合優化[J].數理統計與管理,2008(1):124-129.

[14]張鵬,張忠楨,岳超源.限制性賣空的均值-半絕對偏差投資組合模型及其旋轉算法研究[J].中國管理科學,2006,14(2):7-11.