一類線性約束下非光滑非線性規(guī)劃問題的優(yōu)化研究

張 鵬

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

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

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

1 線性約束下連續(xù)不可微的非線性規(guī)劃模型

1.1 模型描述

設(shè)非光滑的非線性規(guī)劃模型為

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

圖1 非光滑凹函數(shù)Fig.1 Nonsmooth concave function

1.2 模型分析

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

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

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

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

證明:因?yàn)閏i(xi)為凹函數(shù),所以ci(xi)≥kixi,則

即

證畢。

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

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

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

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

令

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

圖3 非光滑凹函數(shù)分段線性擬合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)可轉(zhuǎn)化為下列兩個(gè)模型:

和

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

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

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

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

證畢。

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

2 算法的基本步驟

2.1 模型(1)的計(jì)算步驟

步驟2 如果P={φ},那么轉(zhuǎn)步驟9,否則轉(zhuǎn)步驟3。

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

步驟4 讓ki(xi)近似估計(jì)ci(xi),且Xk=下述數(shù)學(xué)規(guī)劃問題可轉(zhuǎn)化為

并轉(zhuǎn)步驟3

步驟9 停止計(jì)算就是模型(1)的最優(yōu)解。

3 結(jié)語(yǔ)

提出了一類線性約束下非光滑非線性規(guī)劃問題,運(yùn)用分塊法和不等式組的旋轉(zhuǎn)算法對(duì)該問題進(jìn)行了求解,同時(shí)證明了該算法的收斂性和有效性。

[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] 王永麗,賀國(guó)平,王鑫.求解正定二次規(guī)劃的一個(gè)全局收斂的濾子內(nèi)點(diǎn)算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2008,21:127-133.

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

[9] 趙敏,李少遠(yuǎn).基于信賴域二次規(guī)劃的非線性模型預(yù)測(cè)控制優(yōu)化算法[J].控制理論與應(yīng)用,2009(6):634-640.

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

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

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

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

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