帶一般約束無導(dǎo)數(shù)優(yōu)化問題的改進信賴域算法

盧曉寧, 劉紅衛(wèi), 楊善學(xué), 劉澤顯,3, 劉 梅

(1. 西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院, 西安 710126； 2. 西安財經(jīng)學(xué)院 統(tǒng)計學(xué)院, 西安 710100；3. 賀州學(xué)院 數(shù)學(xué)與計算機學(xué)院, 廣西 賀州 542899)

目標函數(shù)導(dǎo)數(shù)信息不可利用的無導(dǎo)數(shù)優(yōu)化問題在資源分配、 工程預(yù)算等領(lǐng)域應(yīng)用廣泛. 本文考慮如下帶有一般約束的無導(dǎo)數(shù)優(yōu)化問題：

(1)

其中:f:n→為導(dǎo)數(shù)不易求得的光滑函數(shù);hi:n→,gj:n→, 且hi,gj為連續(xù)可微的函數(shù);l∈n;u∈n.

直接搜索算法和信賴域算法是處理這些無導(dǎo)數(shù)優(yōu)化問題的主要方法. 信賴域方法先確定步長, 后確定下降方向, 無導(dǎo)數(shù)信賴域(TRDF)算法能保證算法的整體收斂性, 且不需要目標函數(shù)的任何導(dǎo)數(shù)信息, 是一種有效且常用的方法. 目前的信賴域算法主要是對模型及子問題的求解進行研究: Conn等[1]和Powell[2]給出了利用信賴域算法求解無導(dǎo)數(shù)優(yōu)化問題的收斂性證明; Marazzi等[3]利用楔形信賴域方法精確二次插值模型, 然后求解無約束優(yōu)化問題, 使二次模型更近似原函數(shù), 更精確求解原問題的全局極小點; Grapiglia等[4]改進了求解復(fù)合非光滑優(yōu)化問題的二次模型. 序列二次規(guī)劃法[5]和Barzilai-Borwein(BB)法[6]是處理無導(dǎo)數(shù)優(yōu)化問題的重要方法, 劉亞君等[7]提出了無約束優(yōu)化的信賴域BB法, 利用BB步長近似二次模型的Hessian陣, 加快了算法的收斂速度; Powell[8]結(jié)合截斷共軛梯度法和有效集法, 提出了求解界約束問題的BOBYQA算法(bound optimization by quadratic approximation algorithm), 該算法利用幾何方法構(gòu)造插值點集, 確保了插值點集的均衡性; Audet等[9]利用進步欄閾法(PB策略)進行探測搜索, 提出了求解兩個信賴域子問題的進步欄閾無導(dǎo)數(shù)信賴域(TRDF)算法; Conejo等[10]利用增廣Lagrange函數(shù)法對一般約束問題進行處理, 提出了有效的TRDF算法(傳統(tǒng)TRDF算法), 該算法主要分為內(nèi)循環(huán)和外循環(huán)兩個循環(huán)迭代: 在內(nèi)循環(huán)中, 利用增廣Lagrange函數(shù)法求解二次模型, 得到局部解; 在外循環(huán)中, 利用信賴域算法框架求解目標函數(shù)的全局極小點. 增廣Lagrange函數(shù)法是求解帶有一般約束優(yōu)化問題的有效算法, 它能合理地將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題. 但傳統(tǒng)TRDF算法忽略了模型近似更新和初始增廣Lagrange乘子的關(guān)系, 且每次迭代乘子都從初始值開始, 增加了乘子更新的計算量. 同時, 通過對傳統(tǒng)TRDF算法迭代過程的觀察發(fā)現(xiàn)： 在迭代中, 多數(shù)測試函數(shù)會先搜索到性質(zhì)較好的點, 該點有的是離插值點較近的點, 有的就是插值點集中的點. 傳統(tǒng)TRDF算法并未充分利用插值點集中點的信息.

本文對傳統(tǒng)TRDF算法存在的不足進行如下改進： 在求解子問題前, 先利用PB策略對迭代點進行篩選, 采用Powell[11]提出的最小F-范數(shù)法更新模型; 然后通過分析算法迭代間模型的更新情況與下一次迭代初始乘子的關(guān)系, 修正求解子問題的初始增廣Lagrange乘子, 以降低算法的迭代次數(shù)和迭代時間.

1 改進的TRDF算法

傳統(tǒng)的信賴域算法先由給定的初始點構(gòu)造原問題的近似模型(子問題), 然后在信賴域中求解子問題, 從而找到原問題的全局極小點. 本文算法主要從以下兩方面進行改進： 1) 構(gòu)造約束函數(shù)的違和函數(shù), 利用PB策略對插值點集進行篩選, 找到性質(zhì)較好的迭代點, 以加快函數(shù)值的下降速度； 2) 針對傳統(tǒng)TRDF算法迭代中初始增廣Lagrange乘子返回初值的不足進行修正, 以降低求解子問題的時間.

1.1 模型構(gòu)造

在進行第k次迭代前, 需先給定初始點xb∈n, 然后利用BOBYQA算法構(gòu)造插值點集和模型. 即以xb為中心構(gòu)造m個插值點, 這里m∈[2n+1,(n+1)(n+2)/2][10]. 令以為中心、ρ為半徑, 先構(gòu)造插值點：

(2)

剩余(m-2n-1)個插值點為

其中:

(3)

這里:ck∈;gk∈n;2Qk∈n×n. 由插值條件Qk(Yk)=f(Yk)[10]可得：

(4)

1.2 改進TRDF算法對迭代點的選取

(5)

(6)

(7)

此時子問題(7)可化為下列等價形式：

(8)

這里q=p′+2n.

1.3 改進TRDF算法對初始增廣Lagrange乘子的修正

傳統(tǒng)TRDF算法在求解子問題時會返回初值重新計算乘子, 而未對上一次迭代輸出的乘子信息進行合理利用. 針對該不足, 本文改進TRDF算法將具體分析迭代間可能出現(xiàn)的3種模型更新情況, 充分利用已有的乘子信息, 對子問題增廣Lagrange函數(shù)的初始乘子進行修正, 使求解模型更簡便. 首先給出子問題(8)的增廣Lagrange函數(shù)[12]為：

(9)

其中:μ∈p,λ∈q為增廣Lagrange乘子;β≥0為罰因子.

分析表明, 迭代中可能出現(xiàn)下列3種情況：

(10)

從而不僅減少了求解子問題時λ的更新迭代次數(shù), 使求解子問題(8)的函數(shù)值充分下降, 同時也找到了較好的(k+1)次迭代點, 加快了算法的收斂速度.

2) 模型不更新, 插值點集也不更新. 即

Qk+1=Qk,Yk+1=Yk.

插值點集Yk滿足均衡性, 但第k次迭代目標函數(shù)下降不充分, 即0

μk+1=μold,λk+1=λold,

作為第(k+1)次迭代求解模型Qk+1的較好初始乘子, 然后減少信賴域半徑, 求解子問題.

3) 重新構(gòu)造插值點集和模型. 此時插值點集Yk不滿足均衡性, 且第k次迭代目標函數(shù)下降不充分, 甚至f(x+)>f(xk)(即求解子問題得出x+的函數(shù)值比迭代點的函數(shù)值大), 需以當(dāng)前迭代點xk為中心, 令xb=xk重新構(gòu)造插值點集和模型. 求解子問題的初始乘子回歸初值, 即

μk+1=μ0,λk+1=λ0,

這種情況下求解子問題的初始乘子和傳統(tǒng)TRDF算法相同.

信賴域半徑Δk通過計算比值r更新, 即

(11)

1.4 算法描述

通過不斷更新迭代, 算法會產(chǎn)生一個{xk}序列, 最終得到的全局極小點為可行點. 每個點xk為當(dāng)前信賴域中二次模型的嚴格局部最優(yōu)解, 且為使目標函數(shù)值最小的點, 或者是使目標函數(shù)充分下降的點.

算法1改進的TRDF算法.

算法步驟如下:

4) 如果‖x+-xk‖∞>0.5ρk, 則轉(zhuǎn)5)； 否則, 如果ρk≤ε, 則算法終止； 如果ρk>ε, 則轉(zhuǎn)6)；

5) 模型更新:

③ 若ρk≤ε則算法終止； 否則轉(zhuǎn)④;

算法結(jié)束.

改進的TRDF算法利用BOBYQA算法構(gòu)造模型, 同時采用最小F-范數(shù)法對模型進行更新, 確保了插值點集的均衡性, 使模型的構(gòu)造更簡便. 改進算法利用PB策略對迭代點進行有效的篩選, 修正子問題的初始增廣Lagrange乘子, 有效地降低了算法的迭代時間和迭代次數(shù).

1.5 收斂性分析

新算法利用PHR增廣Lagrange函數(shù)法求解子問題, 是在PH算法的基礎(chǔ)上對不等式約束引入輔助變量, 將其轉(zhuǎn)化為等式約束優(yōu)化問題, 再將輔助變量消去轉(zhuǎn)化為式(9)的增廣Lagrange函數(shù)形式. 下面給出改進算法的收斂性分析. 子問題(8)的廣義Lagrange函數(shù)的一階必要條件[12]為

(12)

改進算法采用的PHR方法需要先對子問題(8)的不等式約束引入輔助變量yj≥0(j=1,2,…,q), 將子問題(8)中的不等式約束轉(zhuǎn)化為等式約束形式, 即

gj(x)-yj=0,j=1,2,…,q.

此時子問題(8)可轉(zhuǎn)化為下面等價的僅有等式約束的優(yōu)化問題形式：

(13)

然后利用增廣Lagrange函數(shù)法對其進行求解. 利用增廣Lagrange函數(shù)法求解問題(13)的收斂性證明參見文獻[12], 本文通過消去輔助變量可將問題(13)的增廣Lagrange函數(shù)轉(zhuǎn)化為式(9)的等價形式, 從而得出利用增廣Lagrange函數(shù)法求解子問題(8)的收斂性定理:

hi(x)=0,i=1,2,…,p,

gj(x)≥0,j=1,2,…,q,

2 數(shù)值試驗

下面利用改進的TRDF算法和傳統(tǒng)TRDF算法選擇文獻[13]中測試函數(shù)1～43進行試驗, 并對試驗結(jié)果進行分析.

測試環(huán)境： 所有試驗均在聯(lián)想E49筆記本電腦上運行, MATLAB R2010b環(huán)境, 操作系統(tǒng)為Windows7, 處理器為Intel(R) B950 2.10 GHz, 2 GB內(nèi)存. 初始取值： 兩種算法初始點相同, 取內(nèi)部信賴域半徑ρ=1,ε=10-4,γ=0.05,s=10. 終止條件[10]： 在運行過程中, 當(dāng)‖x+-xk‖∞≤0.5ρk且ρ<ε時, 二次模型不再下降, 算法終止, 或算法迭代次數(shù)超過1 000次時終止. 表1列出了兩種算法處理不同維數(shù)測試函數(shù)的試驗結(jié)果, 表2列出了兩種算法迭代次數(shù)和迭代時間的比較(比較準則參照文獻[14]).

表1 改進TRDF算法和傳統(tǒng)TRDF算法處理不同維數(shù)函數(shù)的數(shù)值結(jié)果

續(xù)表1

表2 兩種算法迭代次數(shù)和迭代時間的比較

由表1和表2可見： 對于不同維數(shù)的測試函數(shù), 改進TRDF算法與傳統(tǒng)TRDF算法在迭代次數(shù)上的勝出比為28∶10, 相同次數(shù)為5次, 改進算法在迭代次數(shù)上優(yōu)勢明顯; 在迭代時間上, 兩種算法的勝出比為29∶11, 相同次數(shù)為3次, 改進算法明顯縮短了迭代所需的時間, 整體實驗效果更好. 以函數(shù)5為例分析表明, 改進TRDF算法不僅在迭代次數(shù)上明顯降低了1/2, 且迭代時間也縮短為原來的1/2, 說明改進TRDF算法更高效.

兩種算法求解不同維數(shù)測試函數(shù)的函數(shù)值隨迭代次數(shù)增加的變化趨勢如圖1所示. 由圖1可見, 改進TRDF算法更快地搜索到了問題的全局極小點, 在迭代次數(shù)和迭代時間上明顯優(yōu)于傳統(tǒng)TRDF算法.

圖1 測試函數(shù)10(A)和測試函數(shù)34(B)的函數(shù)值隨迭代次數(shù)的變化趨勢Fig.1 Change trend of function values of test function 10 (A) and test function 34 (B) with number of iterations

綜上所述, 本文在傳統(tǒng)TRDF算法的基礎(chǔ)上, 給出了一種改進TRDF算法, 并給出了其收斂性的證明. 改進TRDF算法利用PB策略對迭代點進行篩選, 減少了求解子問題的時間, 通過分析模型的更新, 修正求解子問題的初始增廣Lagrange乘子, 使每次迭代能從較好的初始乘子出發(fā), 更快找到目標函數(shù)充分下降的迭代點. 數(shù)值實驗結(jié)果驗證了改進算法的有效性.

[1] Conn A R, Scheinberg K, Vicente L N. Introduction to Derivative-Free Optimization [M]. Philadelphia, PA: Mathematical Programming Society, 2009.

[2] Powell M J D. On the Convergence of Trust Region Algorithms for Unconstrained Minimization without Derivatives [J]. Comput Optim Appl, 2012, 53(2): 527-555.

[3] Marazzi M, Nocedal J. Wedge Trust Region Methods for Derivative Free Optimization [J]. Math Program, 2002, 91(2): 289-305.

[4] Grapiglia G N, YUAN Jinyun, YUAN Yaxiang. A Derivative-Free Trust-Region Algorithm for Composite Nonsmooth Optimization [J]. Comput Appl Math, 2016, 35(2): 475-499.

[5] Tr?ltzsch A. A Sequential Quadratic Programming Algorithm for Equality-Constrained Optimization without Derivatives [J]. Optim Lett, 2016, 10(2): 383-399.

[6] 劉加會, 劉紅衛(wèi), 楊善學(xué). 基于自適應(yīng)Barzilai-Borwein步長的直接搜索共軛梯度法 [J]. 吉林大學(xué)學(xué)報(理學(xué)版), 2017, 55(3): 571-576. (LIU Jiahui, LIU Hongwei, YANG Shanxue. Direct Search Conjugate Gradient Method Base on Adaptive Barzilai-Borwein Step-Size [J]. Journal of Jilin University (Science Edition), 2017, 55(3): 571-576.)

[7] 劉亞君, 劉新為. 無約束最優(yōu)化的信賴域BB法 [J]. 計算數(shù)學(xué), 2016, 38(1): 96-112. (LIU Yajun, LIU Xinwei. Trust Region BB Methods for Unconstrained Minimization [J]. Mathematica Numerica Sinica, 2016, 38(1): 96-112.)

[8] Powell M J D. The BOBYQA Algorithm for Bound Constrained Optimization without Derivatives [R/OL]. 2009-08. http://www.damtp.cam.ac.uk/user/na/NA_papers/NA2009_06.pdf.

[9] Audet C, Conn A R, Digabel S Le, et al. A Progressive Barrier Derivative-Free Trust-Region Algorithm for Constrained Optimization [R/OL]. 2016-06-28. http://www.optimization-online.org/DB_FILE/2016/06/5515.pdf.

[10] Conejo P D, Karas E W, Pedroso L G. A Trust-Region Derivative-Free Algorithm for Constrained Optimization [J]. Optim Methods Softw, 2015, 30(6): 1126-1145.

[11] Powell M J D. Least Frobenius Norm Updating of Quadratic Models That Satisfy Interpolation Conditions [J]. Math Program, 2004, 100(1): 183-215.

[12] 陳寶林. 最優(yōu)化理論與算法 [M]. 北京: 清華大學(xué)出版社, 1989. (CHEN Baolin. Optimization Theory and Algorithm [M]. Beijing: Tsinghua University Press, 1989.)

[13] Hock W, Schittkowski K. Test Examples for Nonlinear Programming Codes [M]. New York: Springer-Verlag, 1981.

[14] 耿燕, 周慶華, 王熙照, 等. 用改進的信賴域方法求解二次插值模型 [J]. 計算機工程與應(yīng)用, 2011, 47(35): 28-31. (GENG Yan, ZHOU Qinghua, WANG Xizhao, et al. Improved Trust Region Method for Quadratic Interpolation Models [J]. Computer Engineering and Application, 2011, 47(35): 28-31.)