求解雙層凸優化問題的Forward-Backward分裂算法及其應用

唐　玥，郭　科，趙世蓮

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

0　引　言

在本文中，我們考慮如下的雙層優化問題

(1)

其中，H是實Hilbert空間，A∶H→2H，B∶H→2H是集值單調映射，ω∶H→R是強凸函數。外層優化問題是指如下的凸極小化問題：

其中，ω是可微強凸函數。這里假定X*≠?，而X*是下述內層優化問題的最優解集，

0∈Ax+Bx。

(2)

特別地，當A為連續可微凸函數f的梯度f，B為下半連續凸函數g的次微分?g時，問題(2)就退化為：

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

(3)

易知，(3)為下述凸極小化問題的最優性條件：

(4)

上述優化問題(4)通常稱為復合凸優化問題，在稀疏優化、機器學習、統計學習中有重要的應用。 對于下列最小范數解問題：

(5)

問題(5)正是(1)式的特殊情況，所以雙層優化問題包括了最小范數解問題。

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

1　預備知識

首先我們回顧一些相關的概念和結論。

定義1設映射T:H→2H，稱T是單調算子，若它滿足：

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

稱T是極大單調算子，若T單調且對任意的x,y∈H，它滿足：

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

定義2設映射T:H→2H，稱T是α-強單調算子，若存在α>0，使它滿足：

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

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

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

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

特別地，當β=0時，稱T是非擴張的。

(ii)T是穩定非擴張的，若它滿足：

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

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

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

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

定義5稱函數f:H→H為強凸的，若存在α>0使它滿足：

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

定義6 設極大單調算子T:H→2H，常數r>0，則

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

稱為T的預解算子。

命題1[8]設極大單調算子T:H→2H，r>0，則JrT是單值非擴張映射。

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

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

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

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

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

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

(6)

命題6[8]設T:H→H是非擴張的，α∈[0,1]，則Id+αT是極大單調算子。

2　主要結果

為了證明方便我們先給出下面兩個假設:

假設1：ω是一個連續可微函數的σ-強凸函數，其中σ∈R++，ω是Lω-Lipschitz 連續的。

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

(7)

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

3　算法的應用

變分不等式約束的雙層優化問題

(8)

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

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

(9)

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

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

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

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

由此可見，經典的變分不等式可以寫成兩個算子和的包含問題。特別地，如果令

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

(10)

4　結　論

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

參考文獻：

[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]董玉達.Splitting methods for monotone inclusions[D].南京：南京大學,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.