呂義勇, 趙文杰, 周光明

(湘潭大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院, 湖南 湘潭 411105)

0 引言

鞍點問題是一個非常重要的優(yōu)化問題, 可應(yīng)用于許多研究領(lǐng)域, 比如對偶理論、最大最小優(yōu)化等.目前已經(jīng)有大量研究鞍點問題的文獻(xiàn).例如, Bertsekas等[1]對鞍點問題的基本理論進行了詳細(xì)介紹.Benzi等在文獻(xiàn)[2]中提出了求解線性系統(tǒng)類型的鞍點問題的迭代方法，在文獻(xiàn)[3-7]中提出了幾種迭代方法與預(yù)處理方法來求解鞍點形式的線性系統(tǒng)問題.對于求解凸-凹型目標(biāo)函數(shù)的鞍點問題, 目前的方法主要利用梯度, 次梯度, 變分不等式[8-10].Vasilyev等[11]提出了一種外梯度方法, 用于找到線性常微分方程的受控系統(tǒng)解上定義的凸-凹函數(shù)的鞍點.郭曉等[12]對帶有簡單凸集約束的鞍點優(yōu)化問題, 提出了投影原始-對偶梯度方法, 并證明了算法的收斂性.

近年來, 在求解非凸-凹型目標(biāo)函數(shù)鞍點問題上取得了重要的進展, 多種求解該類型的鞍點問題的數(shù)值方法被提出了.2018年, 基于Lasserre松弛方法, Nie等[13]提出了一種計算多項式鞍點的數(shù)值算法, 并證明了算法的收斂性.該方法不要求目標(biāo)函數(shù)是凸-凹的, 約束集也可以是非凸的.2019年, Zhou等[14]基于Lasserre松弛方法和最優(yōu)性條件, 提出了計算一般約束下有理函數(shù)鞍點問題的數(shù)值算法, 并且通過數(shù)值實驗驗證了算法的有效性.以上文獻(xiàn)討論的鞍點都是全局鞍點, 目前, 對于局部鞍點問題的研究很少.2019年, Adolphs等[15]定義了局部鞍點.2020年, 趙文杰[16]基于最優(yōu)性條件和Lasserre半定松弛方法, 提出了一種計算無約束多項式的局部鞍點的算法.

本文將討論無約束局部鞍點的計算問題.考慮到若函數(shù)在無窮遠(yuǎn)處還有局部鞍點, 則在實際計算中,無窮遠(yuǎn)處的局部鞍點是很難計算的.因此, 為了計算方便, 在一個有界的區(qū)域(通常取盒子形狀的區(qū)域)內(nèi)討論局部鞍點.

本文在第二部分提出求解無約束局部鞍點的數(shù)值算法和驗證局部鞍點是否是全局鞍點的算法, 在第三部分對這兩個數(shù)值算法進行收斂性分析, 接著在第四部分給出一些具體的數(shù)值實驗去驗證算法的有效性, 最后對論文進行小結(jié).

1 求解局部鞍點的數(shù)值算法

先給出鞍點的定義[1], 該定義實際上也是本文所提到的全局鞍點的定義.

定義1.1令X?Rn,Y?Rm,若f(x,y)在點(x*,y*)∈X×Y處滿足

f(x*,y)≤f(x*,y*)≤f(x,y*), ?(x,y)∈X×Y,

(1)

則稱(x*,y*)為f(x,y)在X×Y上的鞍點.

下面是局部鞍點的定義[15].

定義1.2令X?Rn,Y?Rm, 若存在很小的正數(shù)γ, 在點(x*,y*)∈X×Y處滿足

f(x*,y)≤f(x*,y*)≤f(x,y*), ?(x,y)∈[X∩B(x*,γ)]×[Y∩B(y*,γ)]，

(2)

其中

(3)

則稱(x*,y*)為f(x,y)在X×Y上的局部鞍點.

設(shè)f(x,y)在Rn×Rm上是二階連續(xù)可微的, 假設(shè)定義1.1中的X=Rn,Y=Rm, 本文主要討論目標(biāo)函數(shù)f(x,y)在Rn×Rm上的局部鞍點的計算問題, 當(dāng)計算出局部鞍點之后, 若f(x,y)在Rn×Rm上存在全局鞍點,將從局部鞍點的集合中選出全局鞍點.如果目標(biāo)函數(shù)在無窮遠(yuǎn)處還有局部鞍點, 則在實際計算中, 無窮遠(yuǎn)處的局部鞍點是很難計算的.為了方便計算, 將在一個有界的區(qū)域內(nèi)討論局部鞍點.本文令定義1.1和定義1.2中的X=[l1,b1]n?Rn,Y=[l2,b2]m?Rm.其中,l1,l2,b1,b2是給定的常實數(shù).

假設(shè)f(x,y)∈C2(X×Y)在X×Y上不同的局部鞍點值只有有限個, 其大小順序排列如下:

現(xiàn)在提出求解局部鞍點的算法.

算法1

步0:給定鄰域半徑γ, 區(qū)域X=[l1,b1]n?Rn,Y=[l2,b2]m?Rm, 初始點(x0,y0)∈X×Y，令S:=?.

步1:求候選局部鞍點和對應(yīng)的函數(shù)值f*.

(a) 求解如下問題:

(c) 若C2為空集, 則目標(biāo)函數(shù)在X×Y上不存在局部鞍點, 算法終止.

(a) 給定初始點x0, 求解如下問題:

(4)

得最優(yōu)解集為Cx={x1,x2,…,xK1}; 若Cx中的點xk,k∈{1,2,…,K1}有

則進入下一步, 否則驗證下一個候選局部鞍點.

(b) 給定初始點y0, 求解如下問題:

(5)

得最優(yōu)解集為Cy={y1,y2,…,yL1}; 若Cy中的點yl,l∈{1,2,…,L1}有

(c) 當(dāng)C2中所有的候選局部鞍點驗證完畢, 若S為空集, 則目標(biāo)函數(shù)在X×Y上不存在局部鞍點, 算法終止.

該算法可以計算出f(x,y)在X×Y上的局部鞍點(x*,y*), 以及對應(yīng)的局部鞍點值f*.在X×Y上, 函數(shù)f(x,y)的局部鞍點與全局鞍點有如下的關(guān)系.

定理1.1假設(shè)f(x,y)是X×Y上的二階連續(xù)可微函數(shù), 若(x*,y*)是f(x,y)在X×Y上的全局鞍點, 則(x*,y*)為X×Y上的局部鞍點.

證明若(x*,y*)是f(x,y)在X×Y上的全局鞍點, 由定義1.1可知, 下列不等式成立:

f(x*,y)≤f(x*,y*)≤f(x,y*), ?x∈X,?y∈Y.

假設(shè)(x*,y*)不是局部鞍點, 則至少存在一點(x,y)∈[X∩B(x*,γ)]×[Y∩B(y*,γ)], 使得不等式

f(x*,y)≤f(x*,y*)≤f(x,y*)

(6)

不成立.又

[X∩B(x*,γ)]?X, [Y∩B(y*,γ)]?Y,

因此不等式(6)不成立的結(jié)論與定義1.1矛盾.從而(x*,y*)為f(x,y)在X×Y上的局部鞍點.

即驗證局部鞍點是否是全局鞍點.

算法2

(a)求解如下問題:

(7)

鞍點, 算法終止.

(a)求解如下問題

(8)

注: 在算法1和2中, 計算優(yōu)化子問題時, 本文均利用MATLAB中的求解器MultiStart(Global Optimization Toolbox)求解[17].Multistart在求解優(yōu)化子問題時, 根據(jù)給定的點(x0,y0)，先通過在區(qū)域內(nèi)生成一系列初始點, 再運用內(nèi)點法, SQP等方法來求解相應(yīng)的優(yōu)化問題.因此, 若生成的初始點在區(qū)域內(nèi)分布均勻, 并且足夠多時, 算法1步1的所有候選局部鞍點, 步2中的所有局部最小點和局部最大點, 以及算法2中的所有全局最小點和全局最大點都是可以得到的.

2 收斂性分析

設(shè)x∈Rd, 無約束優(yōu)化問題

ming(x)

(9)

具有以下一階、二階最優(yōu)性條件[18].

定理2.1(一階必要條件) 設(shè)g(x)在開集D上一階連續(xù)可微.若x*∈D是問題(5)的一個局部極小點, 則必有?g(x*)=0.

定理2.2(二階必要條件) 設(shè)g(x)在開集D上二階連續(xù)可微.若x*∈D是問題(5)的一個局部極小點, 則必有?g(x*)=0且?2g(x*)是半正定矩陣.

下面給出(x*,y*)是f(x,y)的局部鞍點的必要條件.

定理2.3假設(shè)f(x,y)是Rn×Rm上的二階連續(xù)可微函數(shù), 若(x*,y*)是f(x,y)在Rn×Rm上的局部鞍點, 則

(10)

證明若(x*,y*)是f(x,y)在Rn×Rm上的局部鞍點, 則由定義1.2可得:

f(x*,y*)≤f(x,y*), ?x∈B(x*,γ),

又由局部極小點的定義可知,x*為f(x,y*)的局部極小點.

根據(jù)定理2.1和定理2.2可得:

同理, 根據(jù)

f(x*,y)≤f(x*,y*) ?y∈B(y*,γ),

可以得到

由定理2.3可知, 若f(x,y)在X×Y上存在局部鞍點, 則通過算法1中步1, 得到滿足條件(10)的全部候選鞍點的集合C2, 且局部鞍點(x*,y*)∈C2.

證明因為f(x,y)∈C2(X×Y)在X×Y上的局部鞍點只有有限個, 算法1的初始點在X×Y上分布均勻, 并且足夠多, 領(lǐng)域半徑γ很小.則算法1中所有的候選局部鞍點的集合C2, 步2中所有的局部最小點的集合Cx與所有的局部最大點的集合Cy都是可以得到的.

f(x*,y*)≤f(x,y*),?x∈X∩B(x*,γ),

f(x*,y)≤f(x*,y*),?y∈Y∩B(y*,γ),

(11)

3 數(shù)值實驗

本節(jié)通過數(shù)值實驗來驗證算法1和2的有效性.所有的數(shù)值結(jié)果均在華碩電腦上通過MATLAB 2016b計算得到.電腦配置如下: 雙核 3.10 GHz CPU, 運行內(nèi)存為 4GB.MATLAB 通過調(diào)用MultiStart來計算候選局部鞍點集合[17], 以及求解算法1和算法2中的最小、最大化子問題.

下列所有數(shù)值實驗中, (x0,y0)表示初始點,k表示第k個局部鞍點, (x*,y*)表示局部鞍點的坐標(biāo),f*表示對應(yīng)的局部鞍點值.在以下算例的計算中, 取γ=0.01.

算例1目標(biāo)函數(shù)

給定區(qū)域(x,y)∈[-1,1]×[-1,1].利用算法1, 取初始點(x0,y0)=(0,0), 得到候選局部鞍點為(x1,y1)=(0.124 3,-0.456 4),(x2,y2)=(-0.456 5,0.573 3), 通過算法1的步2驗證出這兩個點均不是局部鞍點. 計算時間t=6.112 s.

給定區(qū)域(x,y)∈[-10,10]×[-10,10], 取初始點(x0,y0)=(0,0), 得到16個候選局部鞍點, 通過算法1的步2驗證這16個點均不是局部鞍點.

算例2目標(biāo)函數(shù)

給定區(qū)域(x,y)∈[-10,10]3×[-10,10]3.利用算法1, 取初始點(x0,y0)=(1,1,1,1,1,1), 候選局部鞍點集合為空, 即在區(qū)域[-10,10]3×[-10,10]3上不存在局部鞍點.計算時間t=8.429 s.

算例3目標(biāo)函數(shù)

給定區(qū)域(x,y)∈[-10,10]3×[-10,10]3.利用算法1, 取初始點(x0,y0)=(0,0,0,0,0,0), 得到候選局部鞍點(0,0,0,0,0,0), 通過算法1驗證后可知此點是唯一的局部鞍點, 局部鞍點值f*=0, 計算時間t1=72.751 s.

取初始點(x0,y0)=(1,1,1,1,1,1), 得到相同局部鞍點(0,0,0,0,0,0), 計算時間t2=74.185 s.又由算法2可驗證出此局部鞍點不是[-10,10]3×[-10,10]3上的全局鞍點.

算例4目標(biāo)函數(shù)

f(x,y)=e-y2-(x+1)2-e-x2+(y+1)2+ex2-y2.

給定區(qū)域(x,y)∈[-10,10]×[-10,10].利用算法1, 取初始點(x0,y0)=(1,1), 算得到候選局部鞍點(0.120 5,-0.557 3), 通過算法1驗證后可知此點是唯一的局部鞍點, 局鞍點值f*=-0.246 4.計算時間t1=12.680 s.

取初始點(x0,y0)=(5,5), 得到相同的局部鞍點(0.120 5,-0.557 3), 計算時間t2=9.931 s.又由算法2可驗證出此局部鞍點是[-10,10]×[-10,10]上的全局鞍點.

算例5目標(biāo)函數(shù)

給定區(qū)域(x,y)∈[-5,5]3×[-5,5]3.利用算法1, 取初始點(x0,y0)=(0,0,0,0,0,0),計算得到候選局部鞍點(-0.716 7,-0.716 7,-0.716 7,0.586 6,0.586 6,0.586 6).通過算法1驗證后可知此點是唯一的局部鞍點.局部鞍點值f*=1.320 8.計算時間t1=37.518 s

取初始點(x0,y0)=(1,0.5,1,1.5,2,1), 得到相同的局部鞍點, 計算時間t2=37.450 s.又由算法2可驗證出此局部鞍點不是[-5,5]3×[-5,5]3上的全局鞍點.

算例6目標(biāo)函數(shù)

f(x,y)=x4y2-x2y4+x3y-xy3+x-y.

給定區(qū)域(x,y)∈[-2,2]×[-2,2].利用算法1, 分別取初始點(x0,y0)=(0,0)與(x0,y0)=(-0.5,1.5), 計算得到的局部鞍點相同,計算時間為t1=15.081 s和t2=15.061 s.結(jié)果見表1.

表1 算例6的數(shù)值結(jié)果

從表1可以看出給定區(qū)域上有3個局部鞍點.由算法2可驗證局部鞍點(-0.695 8,-0.695 8)是[-2,2]×[-2,2]上的全局鞍點.

算例7目標(biāo)函數(shù)

f(x,y)=xcosy+ysinx.

給定區(qū)域(x,y)∈[-8,8]×[-8,8].利用算法1,分別取初始點(x0,y0)=(0,0)與(x0,y0)=(-2.5,2.5),計算得到的局部鞍點相同,計算時間為t1=15.192 s和t2=14.509s.結(jié)果見表2.

表2 算例7的數(shù)值結(jié)果

從表2可以看出在給定區(qū)域上有6個局部鞍點.由算法2可驗證這6個點均不是[-8,8]×[-8,8]上的全局鞍點.

算例8目標(biāo)函數(shù)

給定區(qū)域(x,y)∈[-5,5]3×[-5,5]3.利用算法1, 分別取初始點(x0,y0)=(0,0,0,0,0,0)與(x0,y0)=(1,1,1,1,1,1), 計算得到的局部鞍點相同, 計算時間分別為t1=73.059 s和t1=70.782 s.結(jié)果見表3.

表3 算例8的數(shù)值結(jié)果

從表3可以看出在給定區(qū)域上存在8個局部鞍點.由算法2可驗證點(-0.592 0,-0.592 0,-0.592 0,±0.490 0,±0.490 0,±0.490 0)均為[-5,5]3×[-5,5]3上的全局鞍點.

上述算例在計算中, 初始點選取在給定的區(qū)域內(nèi)即可.通過以上算例可知, 候選局部鞍點不一定為局部鞍點, 局部鞍點存在時, 全局鞍點不一定存在.由算例8可知, 如果區(qū)域上的全局鞍點存在, 全局鞍點可能不是唯一的.

以上算例的數(shù)值結(jié)果表明, 本文提出的無約束局部鞍點問題的數(shù)值算法和驗證局部鞍點是否是全局鞍點的算法是可行的.

4 總結(jié)

本文研究了無約束函數(shù)局部鞍點的計算問題,當(dāng)變量x和y限定于一些一般約束時, 本文提出的方法不再有效.因此, 如何針對帶有一般約束條件的局部鞍點問題, 提出有效的數(shù)值算法是一個值得進一步研究的問題.