求解雙層凸優(yōu)化問(wèn)題的Forward-Backward分裂算法及其應(yīng)用

唐　玥，郭　科，趙世蓮

(西華師范大學(xué) 數(shù)學(xué)與信息學(xué)院,四川 南充　637009)

0　引　言

在本文中，我們考慮如下的雙層優(yōu)化問(wèn)題

(1)

其中，H是實(shí)Hilbert空間，A∶H→2H，B∶H→2H是集值單調(diào)映射，ω∶H→R是強(qiáng)凸函數(shù)。外層優(yōu)化問(wèn)題是指如下的凸極小化問(wèn)題：

其中，ω是可微強(qiáng)凸函數(shù)。這里假定X*≠?，而X*是下述內(nèi)層優(yōu)化問(wèn)題的最優(yōu)解集，

0∈Ax+Bx。

(2)

特別地，當(dāng)A為連續(xù)可微凸函數(shù)f的梯度f(wàn)，B為下半連續(xù)凸函數(shù)g的次微分?g時(shí)，問(wèn)題(2)就退化為：

0∈f(x)+?g(x)。

(3)

易知，(3)為下述凸極小化問(wèn)題的最優(yōu)性條件：

(4)

上述優(yōu)化問(wèn)題(4)通常稱為復(fù)合凸優(yōu)化問(wèn)題，在稀疏優(yōu)化、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)學(xué)習(xí)中有重要的應(yīng)用。 對(duì)于下列最小范數(shù)解問(wèn)題：

(5)

問(wèn)題(5)正是(1)式的特殊情況，所以雙層優(yōu)化問(wèn)題包括了最小范數(shù)解問(wèn)題。

算子分裂方法[1-4]是最優(yōu)化理論和方法中比較重要的方法，它主要用于解決最優(yōu)化與最優(yōu)控制領(lǐng)域中一類(lèi)比較重要的問(wèn)題——單調(diào)包含問(wèn)題。本文的主要目的是用Forward-Backward分裂算法[5-7]來(lái)求解雙層凸優(yōu)化問(wèn)題(1)，證明算法所產(chǎn)生的序列的收斂性，然后將該算法應(yīng)用于求解變分不等式約束的雙層優(yōu)化問(wèn)題。

1　預(yù)備知識(shí)

首先我們回顧一些相關(guān)的概念和結(jié)論。

定義1設(shè)映射T:H→2H，稱T是單調(diào)算子，若它滿足：

〈x-y，w-v〉≥0，?x,y∈H,?w∈T(x),v∈T(y)，

稱T是極大單調(diào)算子，若T單調(diào)且對(duì)任意的x,y∈H，它滿足：

〈x-y,w-v〉≥0,w∈T(x)?v∈T(y)。

定義2設(shè)映射T:H→2H，稱T是α-強(qiáng)單調(diào)算子，若存在α>0，使它滿足：

〈v1-v0,x1-x0〉≥α‖x1-x0‖2,?v0∈T(x0),v1∈T(x1),?x0,v1∈H。

定義3設(shè)T:D→H，其中D是H的非空子集，

(i)T是β-壓縮映射，若存在β>0使它滿足：

‖Tx-Ty‖β‖x-y‖，?x,y∈D。

特別地，當(dāng)β=0時(shí)，稱T是非擴(kuò)張的。

(ii)T是穩(wěn)定非擴(kuò)張的，若它滿足：

‖Tx-Ty‖2+‖(I-T)x-(I-T)y‖2‖x-y‖2，?x,y∈D。

(iii)T是β-余強(qiáng)制的，若存在β>0使它滿足：

〈Tx-Ty,x-y〉≥β‖Tx-Ty‖2，?x,y∈D。

定義4稱映射T:H→H為α-平均映射,若T能寫(xiě)成T=(1-α)I+αS，其中α∈(0,1)，S:H→H是非擴(kuò)張的。

定義5稱函數(shù)f:H→H為強(qiáng)凸的，若存在α>0使它滿足：

f(tx-(1-t)y)?x,y∈H,?t∈(0,1)。

定義6 設(shè)極大單調(diào)算子T:H→2H，常數(shù)r>0，則

JrT(x)∶=(I+rT)-1(x),x∈H,

稱為T(mén)的預(yù)解算子。

命題1[8]設(shè)極大單調(diào)算子T:H→2H，r>0，則JrT是單值非擴(kuò)張映射。

命題2[8]設(shè)T:D→H，其中D是H的非空子集，

(i)如果T是均值映射，則它是非擴(kuò)張映射；

命題5[9]在Hilbert空間H中，C是H的閉凸子集，設(shè)S:C→C是α-壓縮的，

T:C→C是非擴(kuò)張的，令P∶=Fix(T)≠?，x0∈H，下列算法：

xn+1=αnSxn+(1-αn)Txn，

〈x-x*,Sx*-x*〉0,x∈P。

(6)

命題6[8]設(shè)T:H→H是非擴(kuò)張的，α∈[0,1]，則Id+αT是極大單調(diào)算子。

2　主要結(jié)果

為了證明方便我們先給出下面兩個(gè)假設(shè):

假設(shè)1：ω是一個(gè)連續(xù)可微函數(shù)的σ-強(qiáng)凸函數(shù)，其中σ∈R++，ω是Lω-Lipschitz 連續(xù)的。

定理1假設(shè)A是極大單調(diào)算子，B是ρ-余強(qiáng)制的，Ker(A+B)≠?，令x0∈H，ρ∈R++，我們給出如下算法:

(7)

注1特別地，在該算法中，若是預(yù)解算子JrT變成鄰近梯度則正是Sabach和Shimrit在文獻(xiàn)[10]中提出的BiG-SAM算法。

3　算法的應(yīng)用

變分不等式約束的雙層優(yōu)化問(wèn)題

(8)

其中，C={x|〈F(x),y-x〉≥0,?y∈Ω}。 變分不等式的模型是指：尋找x∈Ω，使得：

〈F(x),y-x〉≥0,?y∈Ω，

(9)

其中，F(xiàn)是一個(gè)Rn→Rn的單值映射，Ω是Rn中的非空閉凸集，設(shè)SOL(Ω，F(xiàn))是變分不等式(9)的解集。

稱NΩ(x)∶={d∈Rn:〈d,y-x〉≤0,?y∈Ω}為Ω在x處的法錐，其中Ω是Rn中的非空閉凸集，F(xiàn):Ω→Rn是一個(gè)映射。則自然成立的一個(gè)關(guān)系為：

x∈SOL(Ω,F)?-F(x)∈NΩ(x)

?0∈F(x)+NΩ(x)，

由此可見(jiàn)，經(jīng)典的變分不等式可以寫(xiě)成兩個(gè)算子和的包含問(wèn)題。特別地，如果令

由命題6我們很容易知道A∶=NΩ是極大單調(diào)算子，接著我們將定理1的結(jié)論應(yīng)用于求解問(wèn)題(8)，得到如下的推論成立。

(10)

4　結(jié)　論

本文用Forward-Backward分裂算法來(lái)求解雙層優(yōu)化問(wèn)題，證明了算法的收斂性，推廣了Sabach和Shimrit在文獻(xiàn)[10]中的結(jié)果，并且給出了算法的一個(gè)應(yīng)用，將算法應(yīng)用于研究變分不等式約束的雙層問(wèn)題，給出了收斂性。在今后的工作中將考慮用更多的分裂方法來(lái)求解雙層優(yōu)化問(wèn)題，并且比較他們的差異性。

參考文獻(xiàn)：

[1]LIONS P L，MERCIER B.Splitting algorithms for the sum of two nonlinear operators[J].SIAM Journal on Numerical Analysis,1979,16(6):964-979.

[2]DOUGLAS J,RACHFORD H H.On the numerical solution of heat conduction problems in two and three space variables[J].Transactions of the American Mathematical Society.1956,82(2):421-439.

[3]董玉達(dá).Splitting methods for monotone inclusions[D].南京：南京大學(xué),2003.

[4]LORENZO R,SILVIA V,BANG C V.Stochastic forward-backward splitting for monotone inclusions[J].Journal of Optimization Theory and Applications，2016，169(2):388-406.

[5]PASSTY G B.Ergodic convergence to a zero of the sum of monotone operators in Hilbert space[J].Journal of Mathematical Analysis and Applications,1979,72(2):383-390.

[6]KUZNETSOV I V.Entropy solutions to a second order forward-backward parabolic differential equation[J].Siberian Mathematical Journal,2005,46(3):467-488.

[7]COMBETTES P L,WAJS V R.Signal recovery by proximal forward-backward splitting[J].Siam Journal on Multiscale Modeling & Simulation,2005,4(4):1168-1200.

[8]BAUSCHKE H H,COMBETTES P L.Convex analysis and monotone operator theory in Hilbert spaces[M].New York:CMS Booka Math,Springer,2011.

[9]XU H K.Viscosity approximation methods for nonexpansive mappings[J].Journal of Mathematical Analysis,2004,298(1):279-29.

[10]SHOHAM S,SHIMRIT S.A first order method for solving convex bilevel optimization problems[J].SIAM Journal on Optimization,2017,27(2):640-660.