求解無約束函數(shù)局部鞍點(diǎn)的數(shù)值算法

呂義勇, 趙文杰, 周光明

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

0 引言

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

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

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

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

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

先給出鞍點(diǎn)的定義[1], 該定義實(shí)際上也是本文所提到的全局鞍點(diǎn)的定義.

定義1.1令X?Rn,Y?Rm,若f(x,y)在點(diǎn)(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上的鞍點(diǎn).

下面是局部鞍點(diǎn)的定義[15].

定義1.2令X?Rn,Y?Rm, 若存在很小的正數(shù)γ, 在點(diǎn)(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上的局部鞍點(diǎn).

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

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

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

算法1

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

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

(a) 求解如下問題:

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

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

(4)

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

則進(jìn)入下一步, 否則驗(yàn)證下一個(gè)候選局部鞍點(diǎn).

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

(5)

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

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

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

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

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

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

假設(shè)(x*,y*)不是局部鞍點(diǎn), 則至少存在一點(diǎn)(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上的局部鞍點(diǎn).

即驗(yàn)證局部鞍點(diǎn)是否是全局鞍點(diǎn).

算法2

(a)求解如下問題:

(7)

鞍點(diǎn), 算法終止.

(a)求解如下問題

(8)

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

2 收斂性分析

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

ming(x)

(9)

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

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

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

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

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

(10)

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

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

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

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

同理, 根據(jù)

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

可以得到

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

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

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

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

(11)

3 數(shù)值實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

算例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, 取初始點(diǎn)(x0,y0)=(1,1), 算得到候選局部鞍點(diǎn)(0.120 5,-0.557 3), 通過算法1驗(yàn)證后可知此點(diǎn)是唯一的局部鞍點(diǎn), 局鞍點(diǎn)值f*=-0.246 4.計(jì)算時(shí)間t1=12.680 s.

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

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

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

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

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

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

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

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

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

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

f(x,y)=xcosy+ysinx.

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

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

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

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

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

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

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

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

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

4 總結(jié)

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