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

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

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

(1)

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

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

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

1 改進(jìn)的TRDF算法

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

1.1 模型構(gòu)造

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

(2)

剩余(m-2n-1)個(gè)插值點(diǎn)為

其中:

(3)

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

(4)

1.2 改進(jìn)TRDF算法對(duì)迭代點(diǎn)的選取

(5)

(6)

(7)

此時(shí)子問(wèn)題(7)可化為下列等價(jià)形式：

(8)

這里q=p′+2n.

1.3 改進(jìn)TRDF算法對(duì)初始增廣Lagrange乘子的修正

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

(9)

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

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

(10)

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

2) 模型不更新, 插值點(diǎn)集也不更新. 即

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

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

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

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

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

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

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

信賴域半徑Δk通過(guò)計(jì)算比值r更新, 即

(11)

1.4 算法描述

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

算法1改進(jìn)的TRDF算法.

算法步驟如下:

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

5) 模型更新:

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

算法結(jié)束.

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

1.5 收斂性分析

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

(12)

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

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

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

(13)

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

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

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

2 數(shù)值試驗(yàn)

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

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

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

續(xù)表1

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

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

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

圖1 測(cè)試函數(shù)10(A)和測(cè)試函數(shù)34(B)的函數(shù)值隨迭代次數(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ǔ)上, 給出了一種改進(jìn)TRDF算法, 并給出了其收斂性的證明. 改進(jìn)TRDF算法利用PB策略對(duì)迭代點(diǎn)進(jìn)行篩選, 減少了求解子問(wèn)題的時(shí)間, 通過(guò)分析模型的更新, 修正求解子問(wèn)題的初始增廣Lagrange乘子, 使每次迭代能從較好的初始乘子出發(fā), 更快找到目標(biāo)函數(shù)充分下降的迭代點(diǎn). 數(shù)值實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)算法的有效性.

[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] 劉加會(huì), 劉紅衛(wèi), 楊善學(xué). 基于自適應(yīng)Barzilai-Borwein步長(zhǎng)的直接搜索共軛梯度法 [J]. 吉林大學(xué)學(xué)報(bào)(理學(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] 劉亞君, 劉新為. 無(wú)約束最優(yōu)化的信賴域BB法 [J]. 計(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ìn)的信賴域方法求解二次插值模型 [J]. 計(jì)算機(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.)