帶一般約束無導數優化問題的改進信賴域算法

盧曉寧, 劉紅衛, 楊善學, 劉澤顯,3, 劉 梅

(1. 西安電子科技大學 數學與統計學院, 西安 710126； 2. 西安財經學院 統計學院, 西安 710100；3. 賀州學院 數學與計算機學院, 廣西 賀州 542899)

目標函數導數信息不可利用的無導數優化問題在資源分配、 工程預算等領域應用廣泛. 本文考慮如下帶有一般約束的無導數優化問題：

(1)

其中:f:n→為導數不易求得的光滑函數;hi:n→,gj:n→, 且hi,gj為連續可微的函數;l∈n;u∈n.

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

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

1 改進的TRDF算法

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

1.1 模型構造

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

(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乘子的修正

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

(9)

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

分析表明, 迭代中可能出現下列3種情況：

(10)

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

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

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

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

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

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

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

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

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

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

(11)

1.4 算法描述

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

算法1改進的TRDF算法.

算法步驟如下:

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

5) 模型更新:

③ 若ρk≤ε則算法終止； 否則轉④;

算法結束.

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

1.5 收斂性分析

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

(12)

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

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

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

(13)

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

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

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

2 數值試驗

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

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

表1 改進TRDF算法和傳統TRDF算法處理不同維數函數的數值結果

續表1

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

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

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

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

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

[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] 劉加會, 劉紅衛, 楊善學. 基于自適應Barzilai-Borwein步長的直接搜索共軛梯度法 [J]. 吉林大學學報(理學版), 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] 劉亞君, 劉新為. 無約束最優化的信賴域BB法 [J]. 計算數學, 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] 陳寶林. 最優化理論與算法 [M]. 北京: 清華大學出版社, 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]. 計算機工程與應用, 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.)