帶誤差的等式約束優(yōu)化問題的BFGS-SQP-L方法分析

武 聽，周永輝

(1.貴州師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，貴州 貴陽 550025；2.貴州師范大學(xué) 大數(shù)據(jù)與計算機(jī)科學(xué)學(xué)院，貴州 貴陽 550025)

0 引言

BFGS方法是求解無約束優(yōu)化問題的擬牛頓法中最有效的方法之一，由Broyden[1]，F(xiàn)letcher[2]，Goldfarb[3]和Shanno[4]提出。其經(jīng)典的收斂分析是在假定目標(biāo)函數(shù)及其梯度是精確的情況下進(jìn)行的，結(jié)果表明該算法具有很好的數(shù)值效果和快速的收斂效果。目前BFGS被認(rèn)為是迄今最好的擬牛頓公式[5]，并成為工程師和數(shù)學(xué)家解決最優(yōu)化問題的主要方法。關(guān)于等式約束優(yōu)化問題，F(xiàn)ukushima[6]提出序列二次規(guī)劃(SQP)方法，成為解決約束優(yōu)化最有效的數(shù)值算法之一。而對于二次規(guī)劃子問題有許多求解方法，如BFGS-SQP法、Powell-SQP法、PSB-SQP法以及Salsa-SQP法等[7-8]。

但是隨著社會的發(fā)展，一些無法精確估計目標(biāo)函數(shù)和梯度的現(xiàn)實優(yōu)化難題擺在眼前，如機(jī)器學(xué)習(xí)和函數(shù)評估容易受到計算誤差影響的模型。因此，人們開始研究帶誤差問題的優(yōu)化算法及其理論性質(zhì)和實際性能。Choi等[9]和Kelley[10]針對不精確梯度的BFGS方法采用了隱式濾波法，該方法假設(shè)噪聲可以在任何迭代中隨意減小，通過確保噪聲隨著迭代接近解而衰減，保證了該方法的收斂性。Dennis等[11]和Ypma[12]研究了帶誤差的擬牛頓法的有界變差性質(zhì)和局部收斂性，當(dāng)在解附近開始時，Hessian近似接近精確的Hessian近似。Barton[13]提出了BFGS方法的一種實現(xiàn)方式，其中假設(shè)函數(shù)中的噪聲是已知的，通過適當(dāng)?shù)挠邢薏罘旨夹g(shù)來計算梯度。Berahas等[14]使用Hamming的有限差分技術(shù)估計函數(shù)中的噪聲，并使用這種估計來計算BFGS方法中的有限差分梯度，其中將噪聲考慮在內(nèi)并放寬了Armijo條件，但沒有研究噪聲對BFGS更新的影響。Xie等[15]在文獻(xiàn)[13]的基礎(chǔ)上，保留了標(biāo)準(zhǔn)的Armijo-Wolfe線搜索，提出了目標(biāo)函數(shù)和梯度存在誤差的無約束優(yōu)化問題的BFGS算法，證明了所提出的算法是局部線性收斂的。

本文在文獻(xiàn)[1-4,6-13]基礎(chǔ)上，針對目標(biāo)函數(shù)及其梯度均有誤差的等式約束優(yōu)化問題，給出BFGS-SQP-L優(yōu)化算法。其主要方法是將經(jīng)典的BFGS公式嵌入到序列二次規(guī)劃(SQP)框架，采用拉格朗日(L)步長，并應(yīng)用延長差分技術(shù)以保證算法的可行性。最后，我們將考慮目標(biāo)函數(shù)及其梯度估值的誤差是一致有界的情形，研究所提出的BFGS-SQP-L優(yōu)化迭代算法的局部收斂性。

1 等式約束優(yōu)化問題

考慮帶誤差的等式約束優(yōu)化問題(簡記為EOEP)

minΦ(x)

s.t.ci(x)=0,(i=1,2,…,m)

(1)

其中Φ，ci:Rn→R，Φ和ci是非線性的，c(x)=(c1(x),c2(x),…,cm(x))T?，F(xiàn)在目標(biāo)函數(shù)Φ∈C1及其梯度▽Φ不能直接得到，然而我們能得到Φ和▽Φ不精確(或噪聲)的表達(dá)式，分別用f(x)和g(x)表示

f(x)=Φ(x)+ε(x)

(2)

g(x)=▽Φ(x)+e(x)

其中ε(x)和e(x)為目標(biāo)函數(shù)和梯度的誤差。

2 算法

根據(jù)經(jīng)典的BFGS算法[5]，借鑒無約束優(yōu)化的帶誤差的線搜索BFGS方法[15]，結(jié)合序列二次規(guī)劃(SQP)方法[6]，我們給出EOEP的序列二次規(guī)劃-拉格朗日線搜索-BFGS方法(簡稱BFGS-SQP-L)如下：

步0 函數(shù)f(·)和g(·)；常數(shù)00；起始點x0；拉格朗日乘子λ0；對稱正定矩陣B0；對于k=1,2…直至收斂為止。

步1

xk + 1=xk+αkdk

(3)

λk+1=Λ(xk,Bk)

步2 求搜索方向dk，即解噪聲函數(shù)的二次規(guī)劃子問題：

(4)

步3 求步長α*，滿足Armijo-Wolfe條件

(5)

步4 如果步3這樣的步長存在，令αk=α*；否則，令αk=0。

步5 如果‖αkdk‖≥ρ，則令sk=αkdk，yk=▽xl(xk+1,λk+1)-▽xl(xk,λk+1)。

步6

(6)

其中函數(shù)Λ是λ的更新公式(見3.3節(jié))，式子中λk+1的一個常見選擇是與子問題的解dk相關(guān)聯(lián)的乘數(shù)，Ak=(▽c1(xk),▽c2(xk),…,▽cm(xk))。l、▽l分別是誤差函數(shù)f所對應(yīng)的拉格朗日函數(shù)和梯度，矩陣Bk是l在(xk,λk)處的Hessian矩陣或其近似。

3 收斂性分析

在這一節(jié)中，給出保證上述BFGS-SQP-L方法產(chǎn)生可接受解的條件。文中，‖·‖表示l2范數(shù)。我們的分析依賴于以下假設(shè)。

假設(shè)1 設(shè)Φ對應(yīng)的拉格朗日函數(shù)L(x,λ)是有下界的且二次連續(xù)可微的，并且有M-Lipschitz連續(xù)(M>0)梯度的，即

‖▽xL(x,λ)-▽xL(y,λ)‖≤M‖x-y‖,?x,y∈Rd

(7)

這個假設(shè)可以放寬，只要求梯度是Lipschitz連續(xù)的，取M>0簡化下面定理的證明過程。

假設(shè)2 目標(biāo)函數(shù)Φ和梯度值▽Φ中的誤差是一致有界的，即對于所有的x∈Rd，存在非負(fù)常數(shù)εf,εg:

|f(x)-Φ(x)|=|ε(x)|≤εf

‖g(x)-▽Φ(x)‖≤‖e(x)‖≤εg

假設(shè)3 設(shè)x*是EOEP的局部最優(yōu)解:

a) 存在最優(yōu)拉格朗日乘子λ*使得

▽xl(x*,λ*)=▽f(x*)+▽c(x*)λ*=0

b)A(x*)=▽c(x*)列滿秩；

c)B*對稱正定；

d)f,ci均在λ*的某個鄰域內(nèi)二次連續(xù)可微，且▽2f(x),▽2ci(x)在x*的鄰域內(nèi)李普希茲連續(xù)。

假設(shè)2見文獻(xiàn)[12]；假設(shè)3是約束優(yōu)化問題經(jīng)典的標(biāo)準(zhǔn)假設(shè)，見文獻(xiàn)[5]。以下均假定假設(shè)1，假設(shè)2和假設(shè)3成立。

3.1 Armijo-Wolfe步長的存在

Xie等[15]在應(yīng)用BFGS 求解EOEP在無等式(1)約束優(yōu)化問題時，給出了真實函數(shù)Φ滿足的Armijo-Wolfe步長條件，同時證明了誤差函數(shù)f也滿足該條件。類似地，可證明在本文有約束的情況下，這樣的步長也是存在的。滿足等式約束條件(1)和真實目標(biāo)函數(shù)Φ所對應(yīng)的拉格朗日函數(shù)及梯度分別為：

▽xL(x,λ)=▽Φ(x)-▽c(x)λ=g(x)-▽c(x)λ-e(x)=▽xl(x,λ)-e(x)

(8)

那么，存在步長αk，使得

(9)

則αk滿足

定理1和定理2表明，如果假設(shè)真實拉格朗日函數(shù)的梯度▽xLk不會太小，那么噪聲拉格朗日函數(shù)l和梯度▽xl的Armijo-Wolfe步長存在，同時滿足l的Armijo-Wolfe條件也會滿足真實拉格朗日函數(shù)L。

這2個定理的證明，完全類似文獻(xiàn)[15]定理3.4和3.5的證明過程，故略去。

3.2 延長差分參數(shù)的選擇

文獻(xiàn)[15]的定理2.1表明，運用BFGS方法處理無約束優(yōu)化時，在某些假設(shè)下，對于迭代的一部分，可以建立線性收斂。特別地，要求更新中的(sk,yk)必須滿足：

(10)

因此，在處理EOEP時，還需要作出以下附加假設(shè)。

假設(shè)4 真實拉格朗日函數(shù)L是m-強(qiáng)凸的，0

其中M由式(7)給出。

以下均假定假設(shè)4成立。注意，即使所給假設(shè)成立，仍然不足以支撐條件(10)成立。因此，和文獻(xiàn)[15]一樣，我們這里也采用延長差分的方法，在執(zhí)行BFGS更新之前增加差分間隔并重新計算梯度，即在BFGS-SQP-L算法中

要求延長差分參數(shù)ρ滿足：

以使得條件(10)成立。

3.3 子問題的解和λ乘子估計

為了便于研究算法的收斂性，下面我們給出子問題的解和λ乘子估計[6]。

令N(▽c(x)T)表示▽c(x)T的零空間。N(▽c(x)T)的投影矩陣記為

P(x)=I-▽c(x)[▽c(x)T▽c(x)]-1▽c(x)T

又設(shè)x*,λ*分別為(1)的一個局部最優(yōu)解和相應(yīng)的拉格朗日乘子，即l(x*,λ*)=0。

噪聲函數(shù)的二次規(guī)劃子問題

的解為

dk=hk+vk

其中

其中λk+1為拉格朗日乘子。

又由Newrton公式有

3.4 迭代的收斂

下面，分3步來研究迭代的收斂性。

1)說明BFGS-SQP-L算法搜索方向為目標(biāo)函數(shù)的下降方向，即BFGS-SQP-L算法的搜索方向和真實函數(shù)的搜索方向之間成銳角。事實上，真實的二次規(guī)劃子問題求解的方向

從而，

2)考慮部分好的迭代。固定標(biāo)量p∈(0,1)，設(shè)

(11)

(12)

根據(jù)文獻(xiàn)[15]的定理2.1，有相應(yīng)的結(jié)果，證明略去。

|Jk|≥pk

(13)

定理3表明，如果滿足更新條件(10)，當(dāng)p選擇接近1時，就可以認(rèn)為大部分的迭代都是好的迭代。

3)可以證明，由BFGS-SQP-L算法生成的迭代的一部分產(chǎn)生了與其拉格朗日梯度成比例的真實拉格朗日函數(shù)的下降，以至于真實目標(biāo)函數(shù)值的下降。

(14)

其中

B=max

則存在一個步長αk，滿足參數(shù)(c1,c2)的(l,▽xl)的Armijo-Wolfe條件，即

且

L(xk+αkdk,λk+1)-L(xk,λk+1)≤

(15)

證明取k∈J，顯然有cosθk≥β1，得

同時，

L(xk+αkdk,λk+1)-L(xk,λk+1)

(16)

常數(shù)A,B以及(15)中的常數(shù)不取決于目標(biāo)函數(shù)或噪聲，而僅取決于參數(shù)c1,c2。

4 結(jié)束語

本文提出了目標(biāo)函數(shù)和梯度均帶有界誤差的等式約束優(yōu)化問題(EOEP)，針對該問題提出了BFGS-SQP-L算法。

受經(jīng)典文獻(xiàn)啟發(fā)，我們首先給出Armijo-Wolfe線搜索條件，然后選擇合適的延長差分參數(shù)，其次求解SQP子問題的搜索方向以及拉格朗日乘子迭代公式，最后給出可接受解的必要條件，使得在這些條件下，誤差函數(shù)對應(yīng)的拉格朗日函數(shù)的Armijo-Wolfe線搜索在目標(biāo)函數(shù)對應(yīng)的拉格朗日函數(shù)中產(chǎn)生足夠的下降，以至目標(biāo)函數(shù)也產(chǎn)生下降。由于誤差總是存在的，因此我們考慮可行性僅側(cè)重于一小部分的迭代收斂。

注意，在目標(biāo)函數(shù)對應(yīng)的拉格朗日的梯度比誤差大得多的情況下，經(jīng)典的BFGS方法盡管表現(xiàn)良好，但誤差仍有可能破壞Hessian更新，導(dǎo)致拉格朗日線搜索給出帶有沖突的信息。本文中的BFGS-SQP-L算法是采用拉格朗日線搜索L步長，嵌入SQP框架，對BFGS方法的簡單修改，結(jié)果發(fā)現(xiàn)誤差本身對約束的影響并不大，從而繼承了沒有誤差時BFGS經(jīng)典方法的良好性能。