基于增廣Lagrange函數(shù)的約束優(yōu)化問題的一個信賴域方法

柳顏,賀素香

(武漢理工大學理學院,湖北 武漢430070)

1.引言

不等式約束優(yōu)化問題是一類傳統(tǒng)的優(yōu)化問題,其廣泛應用于經濟學、工程學、運輸科學、數(shù)學規(guī)劃等諸多領域,因此對其理論及方法的研究也具有重要的意義.本文主要研究下述形式的不等式約束優(yōu)化問題:

其中x ∈Rn,f(x):Rn→R,ci(x):Rn→R都是二階連續(xù)可微函數(shù).

目前已有許多解決不等式約束優(yōu)化問題(1.1)的方法,如拉格朗日-牛頓法、罰函數(shù)法、可行方向法、逐步二次規(guī)劃方法、有效集法、增廣Lagrange方法、信賴域法等[1?3].其中罰函數(shù)法是過去幾十年發(fā)展起來的一種解決約束優(yōu)化問題的重要方法.罰函數(shù)方法的重要思想是通過添加罰因子,在目標函數(shù)上加上由約束函數(shù)組成的一個懲罰項,來迫使迭代點逼近可行域,從而將約束優(yōu)化問題轉化為無約束優(yōu)化問題.常用的罰函數(shù)是不帶有乘子的罰函數(shù)和l∞罰函數(shù)及帶有乘子的增廣Lagrange函數(shù),而l1罰函數(shù)和l∞罰函數(shù)是非光滑的,可能會導致Maratos效應[4],而且其子問題也是非光滑的,導致該子問題不容易解決.基于Bertsekas[5]構造的指數(shù)型增廣Lagrange函數(shù)光滑性的優(yōu)點,本文將應用該函數(shù)來研究問題(1.1)的求解方法.

增廣Lagrange方法是解決問題(1.1)的重要方法之一.在傳統(tǒng)的增廣Lagrange方法的第二步中,即在第k次迭代時,通過精確求解以增廣Lagrange函數(shù)為目標函數(shù)的無約束子問題以獲得問題(1.1)的解,但是精確求解該子問題時所需的計算工作量比較大.在文[6]中Conn提出一類方法來解決以增廣Lagrange函數(shù)為目標函數(shù)的無約束子問題,其中他們考慮了該子問題的一階臨界條件滿足給定的一個精度范圍內,并且當該精度收斂到0時,由這種方法產生的序列點收斂到KKT點或者Fritz-John 點.但是,在實際問題中,當目標函數(shù)可能高度非線性和精度非常小時,這會造成相應程序非常復雜,計算代價會很大.

信賴域方法是從Levenberg(1944)和Marguart(1963)解決無約束優(yōu)化問題的工作開始的,之后許多學者對這類方法有了更深入的研究.Fletcher[7]和Powell[8]等人的工作表明了很好的收斂性和有效的計算性是信賴域方法的主要特性.目前信賴域方法的研究在等式約束優(yōu)化問題[9?11]和線性不等式約束優(yōu)化問題[12?13]中都有重要進展.WANG和YUAN14]針對等式約束優(yōu)化問題提出了一個增廣Lagrange信賴域方法.該方法考慮在每步迭代中只需要在相應信賴域中極小化經典增廣Lagrange函數(shù)的二次近似,從而使得計算子問題的難度降低,并且通過對信賴域子問題的求解得到等式約束優(yōu)化問題的近似解.鑒于目前還沒有學者采用上述方法思想研究不等式約束優(yōu)化問題,基于Bertsekas[5]構造的指數(shù)型增廣Lagrange函數(shù),本文將用信賴域方法去解決以指數(shù)型增廣Lagrange函數(shù)為目標函數(shù)的無約束子問題,并建立相應的信賴域算法.在一定的假設條件下,本文將證明算法的全局收斂性,并最后給出相應經典算例的數(shù)值實驗結果以驗證算法的有效性.

2.基礎知識

定義2.1設問題(1.1)的可行域為F,并在后文中假設F是非空集.對x ∈F,定義在可行點x處的緊約束的指標集I(x)為:

定義2.2定義問題(1.1)的Lagrange函數(shù)為L(x,λ)=f(x)?其中λ=(λ1...λm)T為Lagrange乘子.

定理2.1[15](KKT條件)設x?是問題(1.1)的局部極小點,f(x),ci(x)(x ∈D)在x?點處可微.若向量組 {?ci(x?)(i ∈Ix?))}線性無關,則存在向量λ?=(λ1?...λm?)T使得下式成立

此時稱(x?,λ?)為問題(1.1)的KKT解對,并且稱x?為問題(1.1)的KKT點.

記ci?(x)=min {ci(x),0}(i ∈D),則問題(1.1)中ci(x)≥0等價于ci?(x)=0,記c?(x)=(c1?(x),...,cm?(x))T.

3.一種信賴域方法

本文將主要用到Bertsekas[5]構造的基于不等式約束優(yōu)化問題的指數(shù)型增廣Lagrange函數(shù),其形式如下:

其中λ是Lagrange乘子,σ >0是罰因子.在傳統(tǒng)的增廣Lagrange方法的第二步中,求解如下子問題：

為了減少精確求解該子問題的計算量,本文將采用信賴域方法解決該子問題.

在第k次迭代時定義增廣Lagrange函數(shù)(3.1)的二次近似函數(shù)：

其中?k是信賴域半徑.

記dk是問題(3.3)的解.為了判別dk能否被接受,定義如下比值

其中Aredk是問題(3.2)中目標函數(shù)(3.1)的真實下降量,Predk是問題(3.2)中目標函數(shù)(3.1)的預估下降量.

下面給出基于增廣Lagrange函數(shù)(3.1)的求解問題(1.1)的信賴域算法.

算法3.1步0 給定初始點x0∈Rn,λ0∈Rm,σ0>0,?0>0,δ0>0,ε ≥0,k:=0.

步2 求解子問題(3.3),得到dk;

步3 按式(3.4)計算ρk.若ρk >η,則xk+1=xk+dk,轉步4;

否則xk+1=xk,?k+1=/4,k=k+1,轉步2.

步4 更新Lagrange乘子和罰因子：

如果Predk <δkσkmin {?k,},則σk+1=2σkδk+1=δk/4；

否則σk+1=σkδk+1=δk.

步5 更新信賴域半徑：

更新矩陣Bk得到Bk+1；k:=k+1,轉步1.

4.收斂性分析

本節(jié)首先對問題(1.1)作出一些假設條件,然后在這些假設條件下,證明算法3.1的全局收斂性.

設 {xk},{Bk}是由算法3.1產生的序列,下面給出證明中需要用到的一些假設條件:

(A1)f(x),ci(x)i ∈D是二階連續(xù)可微函數(shù);

(A2)序列 {xk},{Bk}是有界的.

引理4.1假設(A1)成立,則?x(xk+1,λk,σk)=?xL(xk+1,λk+1).

證由(3.1)和(3.5)計算得

引理4.2記Hk=?x(xk,λk,σk).設dk是問題(3.3)解,并且則有

證定義其中α ∈[0,1].由于則是問題(3.3)的可行點.

從而有

故結合(4.3)式可知(4.2)式成立.

即引理4.2得證.

定理4.3假設(A1)-(A2)成立,則

證首先證明

假設(4.4)式不成立,則對任意的k,存在一個正常數(shù)v使得

如果對充分大的k有σk=σ,則由算法3.1中的步4可知對充分大的有

然而對于充分大的k,由假設條件(A2),即 {Bk}是有界的,則存在常數(shù)N >0,使得||Bk||≤N.由(3.4)式可得

即當k→∞時,ρk→1.此時由算法3.1的步5有?k+1≥?k,這與?k→0矛盾.故(4.4)式成立.

記U是所有成功迭代對應的指標所構成的集合.下面證明||c?(xk)||收斂到0.用反證法.假設存在指標集mj ?U及常數(shù)τ >0使得

其中c?i是由c?i(xk)(i ∈mj)組成的列向量.

由(4.4)式可知,存在子列nj ?U使得

對于mj ≤u ≤nj,由引理4.2可知

可知Aredk是有下界的.

對充分大的k,有

其中ζ為一正數(shù).由Aredk的有界性,因此

0(k→∞).

基于(4.6)式,對充分大的u,都有有這與(4.5)式相矛盾,因此定理得證.

定理4.4假設(A1)-(A2)成立,dk設是問題(3.3)解,并設是序列 {xk}的聚點.如果向量組線性無關且滿足互補松弛條件,則x是問題(1)的KKT點.

證首先需要證明記即證0.

由(3.4)可知

即 {L(xk,λk,σk)}單調下降且下有界,從而

由算法3.1的步3和引理4.2可知

當k→∞時,則根據(4.7)式可知?k→0.從另一個方面可得

以及

從而可得

因此有

根據(4.8)式表明:當時k→∞,有?k+1≥?k,這與?k→0矛盾.故有

假設對所有的k,λk是有界的,由定理4.3,則序列 {xk}存在一個聚點和 {λk}存在一個聚點,使得向量組?ci()(i ∈I)線性無關且聚點x滿足互補松弛條件,由引理4.1可得,

即定理4.4得證.

5.數(shù)值實驗

下面利用算法3.1和傳統(tǒng)的增廣Lagrange算法[15]分別對附錄中的不等式約束優(yōu)化問題進行實驗,并對數(shù)值實驗結果進行分析.

測試環(huán)境：所有實驗均在聯(lián)想R720筆記本電腦上運行,操作系統(tǒng)為Windows10,處理器為Intel酷睿四核處理器,2.5GHz,8G內存.本文的程序代碼都是用Matlab語言編寫的,并在Matlab R2016a平臺上運行.

初始值的選取：兩種算法中的初始點,初始Lagrange乘子都是相同的.算法3.1中用到的部分參數(shù)定義如下：

實驗結果中用n表示附錄問題中的變量個數(shù),m表示附錄問題中的約束函數(shù)個數(shù),k表示迭代次數(shù).表5.1列出了兩種算法處理不同維度的不等式約束優(yōu)化問題的實驗結果.

表5.1 算法3.1和傳統(tǒng)的增廣Lagrange算法的數(shù)值比較結果

由表5.1可以看出,對于不同維度的測試問題,算法3.1在迭代次數(shù)和迭代時間上均少于傳統(tǒng)的增廣Lagrange算法,這說明本文提出的基于信賴域方法思想的算法減少了求解問題(1.1)的計算量; 同時表5.1給出的數(shù)值實驗結果驗證了算法3.1的有效性.

附錄

問題1[15]

最優(yōu)解和最優(yōu)值：x?=(1,0)T,f(x?)=0.

初始點和初始Lagrange乘子：x0=(0,0)T,λ0=(1,1)T.

問題2Beale問題[16]

最優(yōu)解和最優(yōu)值：x?=(4/3,7/9,4/9)T,f(x?)=1/9.

初始點和初始Lagrange乘子：x0=(0,0,0)T,λ0=(1,1,1)T

問題3Rosen-Suzuki問題[16]

最優(yōu)解和最優(yōu)值：x?=(0,1,2,?1)T,f(x?)=?44.

初始點和初始Lagrange乘子：x0=(2,2,2,2)T,λ0=(1,1,1,1)T.

問題4Wong問題(1)[16]

最優(yōu)解和最優(yōu)值：x?=(2.3305,1.9514,?0.4775,44.3657,?0.62449,1.0381,1.5942)T,f(x?)=680.630

初始點和初始Lagrange乘子：x0=(1,2,0,4011)T,λ0=(1,1,1,1)T.