一類非凸Bregman梯度法的線性收斂研究

摘要：梯度下降算法是一類求解無約束優(yōu)化問題的重要方法，其研究中光滑性的假設(shè)具有重要作用。Bregman梯度下降算法是對梯度下降算法的一種推廣，本質(zhì)上可以看作將經(jīng)典的光滑性削弱成相對光滑性時自然產(chǎn)生的。文章研究了Bregman梯度下降算法求解相對強(qiáng)quasar-凸和相對光滑問題的線性收斂性，證明了當(dāng)目標(biāo)函數(shù)為相對強(qiáng)quasar-凸且相對光滑時，Bregman梯度下降算法產(chǎn)生的函數(shù)值序列具有線性收斂速度，同時，給出了迭代序列的收斂性。

關(guān)鍵詞：相對光滑；強(qiáng)quasar-凸；相對強(qiáng)quasar-凸；Bregman梯度下降算法；線性收斂率

中圖分類號：O224文獻(xiàn)標(biāo)志碼：A文章編號：1673-5072（2025）01-0030-06

Linear Convergence of a Class of Non-convex Bregman Gradient Algorithm

Abstract：Gradient descent algorithm is an important method for solving unconstrained optimization problems，and the assumption of smoothness plays a crucial role in its research.Bregman gradient descent algorithm is" an extension of the gradient descent algorithm，and it can be essentially seen as a natural outgrowth when the classical smoothness is reduced to relative smoothness.This paper studies the linear convergence of Bregman gradient descent algorithm for solving relatively strongly quasar-convex and relatively smooth problems.It is proved that when the objective function is relatively strongly quasar-convex and relatively smooth，the sequence of function value produced by Bregman gradient descent algorithm has a linear convergence rate.Meanwhile，the convergence of iterative sequence is also given.

Keywords：relatively smooth;strongly quasar-convex;relatively strongly quasar-convex;Bregman gradient descent algorithm;linear convergence rate

本文考慮如下無約束優(yōu)化問題

minx∈Rnf（x），（1）

式中，f ：Rn→R是一個可微函數(shù)。假設(shè)問題（1）的解集非空，并記為X*；其最優(yōu)函數(shù)值用f*表示。求解問題（1）的方法有很多，當(dāng)目標(biāo)函數(shù)f為凸且L-光滑時，可利用經(jīng)典梯度下降算法［1］進(jìn)行求解，其迭代格式為

實(shí)際上，梯度下降算法（2）也可以看成去依次最小化f的二次逼近函數(shù)，即

式中，‖·‖2是歐式范數(shù)。算法（2）產(chǎn)生的迭代序列{xk}收斂到X*中一點(diǎn)，函數(shù)值序列{f（xk）}次線性收斂到f*［1］。當(dāng)目標(biāo)函數(shù)f為強(qiáng)凸且光滑時，可以得到算法（2）產(chǎn)生的函數(shù)值序列和迭代序列均具有線性收斂率［2］。因此，產(chǎn)生了如下疑問：如果將目標(biāo)函數(shù)的凸性和光滑性至少削弱一個，能否得出與凸光滑函數(shù)類似的次線性收斂結(jié)論？如果將目標(biāo)函數(shù)的強(qiáng)凸性和光滑性至少削弱一個，能否得出與強(qiáng)凸光滑函數(shù)類似的線性收斂結(jié)論？

首先，若將目標(biāo)函數(shù)的凸性和光滑性至少削弱一個，能得出與凸光滑函數(shù)類似的次線性收斂結(jié)論。一方面，若將函數(shù)的凸性削弱為quasar-凸［3］，Guminov等［4］在2017年證明了在目標(biāo)函數(shù)為quasar-凸且光滑時，梯度下降算法產(chǎn)生的函數(shù)值序列具有次線性收斂率。另一方面，若將函數(shù)的光滑性削弱為相對光滑性，類似光滑性導(dǎo)出梯度下降算法（3），相對光滑性的出現(xiàn)自然導(dǎo)出了Bregman梯度下降算法［5］（Nolips算法［6］或原始梯度算法［7］）：

式中，Dh（·，·）是由Legendre函數(shù)h（·）定義的Bregman距離函數(shù)。當(dāng)目標(biāo)函數(shù)為凸且相對光滑時，Bauschke等［6］得出算法（4）的收斂性和次線性收斂率；Lu等［7］得出算法（4）的次線性收斂率。實(shí)際上，若將目標(biāo)函數(shù)的凸性和光滑性同時削弱，即當(dāng)目標(biāo)函數(shù)為quasar-凸且相對光滑時，算法（4）產(chǎn)生的函數(shù)值序列具有次線性收斂率。此外，若quasar-凸性參數(shù)γ1，還能得出迭代序列的收斂性。

另外，若將目標(biāo)函數(shù)的強(qiáng)凸性和光滑性分別進(jìn)行削弱時，也能得出與強(qiáng)凸光滑函數(shù)類似的線性收斂結(jié)論。一方面，若將強(qiáng)凸性削弱為強(qiáng)quasar-凸性，Bu和Mesbahi［8］得出當(dāng)目標(biāo)函數(shù)為強(qiáng)quasar-凸且光滑時，算法（2）產(chǎn)生的迭代序列和函數(shù)值序列均具有線性收斂率。另一方面，若將光滑性削弱為相對光滑性，Lu等［7］得出當(dāng)目標(biāo)函數(shù)為相對強(qiáng)凸且相對光滑時，算法（4）產(chǎn)生的函數(shù)值序列的線性收斂率。

綜上所述，目前并沒有關(guān)于將目標(biāo)函數(shù)的強(qiáng)凸性和光滑性同時進(jìn)行削弱時的線性收斂性方面的結(jié)果。因此，本文將探究當(dāng)目標(biāo)函數(shù)為相對強(qiáng)quasar-凸且相對光滑時，Bregman梯度下降算法的線性收斂性。

1預(yù)備知識

定義1［1］令Lgt;0，稱可微函數(shù)f∶Rn→R是L-光滑的，如果對任意的x，y∈Rn，有

‖f（x）－f（y）‖2L·‖x－y‖2。

L-光滑條件可以得到下降引理：對于任意的x，y∈Rn，滿足

盡管光滑性是優(yōu)化中的一個重要性質(zhì)，但在許多應(yīng)用中，目標(biāo)函數(shù)并不具有這樣好的性質(zhì)。2016年，Bauschke等［6］提出了Lipschitz-like凸性條件，該條件弱于光滑性但強(qiáng)于非光滑性，而后在2018年又被Lu等［7］獨(dú)立地發(fā)現(xiàn)并將其重新命名為相對光滑條件。

下面將先回顧Legendre函數(shù)的定義。

給定一個Legendre函數(shù)h（·），則與h（·）相關(guān)的用作鄰近測度的Bregman距離函數(shù)Dh（·，·）就被確定了［10］：

文獻(xiàn)［7］給出如下相對光滑函數(shù)的例子。

quasar-凸性是一個重要的凸性推廣條件。接下來，回顧一下quasar-凸性的定義。

定義5［3］假設(shè)x*是可微函數(shù)f ：Rn→R的一個最小值點(diǎn)。稱f（·）關(guān)于點(diǎn)x*是γ-quasar-凸的，如果對于任意的x∈Rn，存在一個實(shí)數(shù)γgt;0使得

下面本文將給出2個quasar-凸函數(shù)的例子，可直接利用定義5進(jìn)行證明。

與強(qiáng)凸函數(shù)類似，當(dāng)μgt;0時，強(qiáng)quasar-凸函數(shù)也具有唯一的最優(yōu)解。本文以引理的形式給出，并進(jìn)行證明。

引理1如果函數(shù)f（·）關(guān)于點(diǎn)x*是（γ，μ）-強(qiáng)quasar-凸的且μgt;0，則它有唯一的最優(yōu)解。

證明假設(shè)x′是函數(shù)f（·）的另一個最小值點(diǎn)。令不等式（6）中的x=x′，則有

該不等式成立當(dāng)且僅當(dāng)x′=x*，則與假設(shè)矛盾。

本質(zhì)上，相對強(qiáng)quasar-凸函數(shù)的定義思想和相對光滑函數(shù)的定義思想一致，都是借助Bregman距離函數(shù)Dh（y，x）將函數(shù)推廣到非歐幾何空間。下面，根據(jù)Zhu和Guo［12］定義相對強(qiáng)凸函數(shù)的思想來類似地定義相對強(qiáng)quasar-凸函數(shù)。

定義7令h∶Rn→R∪{+}為Legendre函數(shù)，并假設(shè)x*是可微函數(shù)f ：Rn→R的一個最小值點(diǎn)。稱f（·）在Rn上相對于h（·）關(guān)于點(diǎn)x*是（γ，μ）-強(qiáng)quasar-凸的，如果對于任意的x∈Rn，存在實(shí)數(shù)γgt;0，μ0使得

類似引理1，即（γ，μ）-強(qiáng)quasar-凸函數(shù)最優(yōu)解唯一性的證明（μgt;0），－μ·Dh（x*，x′）0并不能說明x′=x*，因此，（γ，μ）-相對強(qiáng)quasar-凸函數(shù)不一定具有唯一的最優(yōu)解。

2相對光滑相對強(qiáng)quasar-凸函數(shù)的線性收斂率

本節(jié)考慮問題（1），其中f（·）相對于Legendre函數(shù)h（·）是L-光滑的且相對于h（·）關(guān)于一個最小值點(diǎn)x*是（γ，μ）-強(qiáng)quasar-凸的函數(shù)（Lgt;μgt;0）。首先，分析函數(shù)值序列{f（xk）}和序列{Dh（x*，xk）}的線性收斂性。下面直接給出分析收斂性需要用到的一個關(guān)于Dh（·，·）的性質(zhì)。

φ（x）+Dh（x，z）φ（z+）+Dh（z+，z）+Dh（x，z+）。

定理1假設(shè)f∶Rn→R在Rn上相對于Legendre函數(shù)h（·）是L-光滑的且相對于h（·）關(guān)于一個最小值點(diǎn)x*是（γ，μ）-強(qiáng)quasar-凸的函數(shù)，其中Lgt;μgt;0。令序列{xk}是由Bregman梯度下降算法（4）產(chǎn)生的迭代序列。則序列{f（xk）}線性收斂到f（x*），序列{Dh（x*，xk）}線性收斂到0。

證明由于f（·）相對于h（·）是L-光滑的，則對于任意的k∈Z+有

令上式中的x=x*，可得：

〈f（xk），xk－x*〉L·Dh（x*，xk）－L·Dh（x*，xk+1）+f（xk）－f（xk+1）。（11）

由于f（·）相對于h（·）關(guān)于x*是（γ，μ）-強(qiáng)quasar-凸的，即滿足

取任意θ0，式（12）左右兩邊同時乘以θ，然后將得到的式子與式（10）相加，則

將上式與式（11）結(jié)合得到

整理上式得

因此，由上式遞歸得

3結(jié)語

參考文獻(xiàn)：

［1］BECK A.First-order methods in optimization［M］.Philadelphia：SIAM，2017.

［2］NESTEROV Y.Introductory lectures on convex optimization：a basic course［M］.Boston：Kluwer Academic Publishers，2004.

［3］HARDT M，MA T，RECHT B.Gradient descent learns linear dynamical systems［J］.Journal of Machine Learning Research，2018，19（29）：1-44.

［4］GUMINOV S，GASNIKOV A，KURUZOV I.Accelerated methods for alpha-weakly-quasi-convex problems［J］.Computational Management Science，2023，20（1）：36.

［5］DRAGOMIR R A，TAYLOR A B，D’ASPREMONT A，et al.Optimal complexity and certification of Bregman first-order methods［J］.Mathematical Programming，2022，194：41-83.

［6］BAUSCHKE H H，BOLTE J，TEBOULLE M.A descent lemma beyond Lipschitz gradient continuity：first-order methods revisited and applications［J］.Mathematics of Operations Research，2017，42（2）：330-348.

［7］LU H H，F(xiàn)REUND R M，NESTEROV Y.Relatively smooth convex optimization by first-order methods，and applications［J］.SIAM Journal on Optimization，2018，28（1）：333-354.

［8］BU J J，MESBAHI M.A note on nesterov’s accelerated method in nonconvex optimization：a weak estimate sequence approach［Z/OL］.（2020-06-15）［2023-12-04］.https：//arxiv.org/abs/2006.08548.

［9］ROCKAFELLARR T.Convex analysis［M］.Princeton：Princeton University Press，1970.

［10］BREGMAN L M.The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming［J］.Ussr Computational Mathematics amp; Mathematical Physics，1967，7（3）：200-217.

［11］HINDER O，SIDFORD A，SOHONI N S.Near-optimal methods for minimizing star-convex function and beyond［J］.Conference on Learning Theory，2020：1042-1085.

［12］GUO K，ZHU C R.On the linear convergence of a Bregman proximal point algorithm［J］.Journal of Nonlinear and Variational Analysis，2022，6（2）：5-14.

［13］CHEN G，TEBOULLE M.Convergence analysis of a proximal-like minimization algorithm using Bregman functions［J］.SIAM Journal on Optimization，1993，3（3）：538-543.