摘要：為求解黎曼流形上的大規(guī)?？煞蛛x問題， Kasai等人在（Advances of the neural information processing systems， 31， 2018）中提出了使用非精確梯度和非精確Hessian的黎曼信賴域算法， 并給出了該算法的迭代復(fù)雜度（只有證明思路， 沒有具體證明）。我們指出在該文獻(xiàn)的假設(shè)條件下， 按照其思路不能證明出相應(yīng)的結(jié)果。本文提出了不同的參數(shù)假設(shè)， 并證明了算法具有類似的迭代復(fù)雜度。

關(guān)鍵詞：黎曼流形；非精確信賴域算法；迭代復(fù)雜度；拉回映射

中圖分類號： O224文獻(xiàn)標(biāo)志碼：A文獻(xiàn)標(biāo)識碼

Inexact trust-region algorithms on Riemannian manifolds

LI "Zhiyun，WANG "Xiangmei*

（School of Mathematics， Guizhou University，Guiyang， Guizhou 550025， China）

Abstract： "To solve the large-scale separable problem on Riemannian manifolds， Kasai et al proposed the Riemannian trust-region algorithm with inexact gradients and inexact Hessians in［Advances of the neural information processing systems， 31， 2018］， as well as the estimate of the iteration complexity of this algorithm （only the outline of the proof is given， without providing specific proof）. We note that， under the conditions made in the paper， we can not get the desired result. In the present paper， we propose different assumptions on the parameters and establish a similar iteration complexity of the algorithm.

Key words： Riemannian manifolds;inexact trust-region algorithm;iteration complexity;retraction

1引言

石河子大學(xué)學(xué)報（自然科學(xué)版）第42卷

第3期李祉赟，等：黎曼流形上的非精確信賴域算法

考慮黎曼流形上的大規(guī)模無約束可分離優(yōu)化問題：

minx∈Mf（x）=1n∑ni=1fi（x），（1）

其中M是m維黎曼流形， n1（n很大）， 函數(shù)fi：M→R連續(xù)可微（i= 1， 2， …， n）。這類問題經(jīng)常在機(jī)器學(xué)習(xí)和計算科學(xué)中出現(xiàn)（參見文獻(xiàn)［1-5］ ）。當(dāng)M=Rm時， 即在m維歐氏空間Rm求解問題（1）， 可以用經(jīng)典的梯度下降法來進(jìn)行求解。然而這種方法的缺點(diǎn)就是每次都要計算所有分量函數(shù)的梯度， 當(dāng)m和n很大時梯度的計算量很大。為減少每次迭代的計算量， Robbins等［6］提出了隨機(jī)梯度下降算法（SGD）， 每次迭代只需要計算一個隨機(jī)選取的分量函數(shù)所對應(yīng)的梯度。SGD可以極大減少每次迭代中的計算量， 但它的收斂速度較慢?；赟GD的思想， 學(xué)者們分別提出了隨機(jī)平均梯度算法（SAG）［7］ 和隨機(jī)方差減小的梯度下降法（SVRG）［8］ 。SAG為每一個樣本函數(shù)都保存一個舊的梯度， 在每次迭代中隨機(jī)選擇一個樣本來計算新的梯度替換掉它的舊梯度并以此產(chǎn)生新的迭代方向。相較于SAG， SVRG在達(dá)到線性收斂的同時并不需要為每個樣本都保存一個梯度， 降低了算法的存貯量。以上這些算法都具有良好的全局收斂性， 但局部收斂速度較慢。當(dāng)函數(shù)fi二階連續(xù)可微時， 很多學(xué)者利用函數(shù)的二階信息來構(gòu)造收斂效率更好的優(yōu)化算法。牛頓法就是經(jīng)典的二階算法之一， 該算法每次迭代都需要計算函數(shù)的梯度和Hessian矩陣的逆， 當(dāng)m和n很大時， 目標(biāo)函數(shù)Hessian矩陣的計算量很大。近年來， Roosta等針對大規(guī)模問題提出了非精確信賴域算法及非精確自適應(yīng)三次正則化算法的變體［9-10］， 即通過使用非精確Hessian來減少每次迭代計算成本， 同時保持算法良好的收斂性。他們證明了這些非精確算法具有與原算法相同的迭代復(fù)雜度。

與傳統(tǒng)歐氏空間上的優(yōu)化算法相比， 黎曼流形優(yōu)化的優(yōu)勢在于可以將一些歐氏空間的約束問題轉(zhuǎn)化為黎曼流形上的無約束問題［11-14］。因此， 許多學(xué)者將歐氏空間上的經(jīng)典優(yōu)化算法推廣到黎曼流形上， 例如梯度法、牛頓法、擬牛頓法、信賴域算法等， 參見文獻(xiàn)［11-21］ 及其參考文獻(xiàn)。此外， 為求解黎曼流形上的大規(guī)模問題（1）， 學(xué)者們先后提出了黎曼隨機(jī)梯度下降算法［22］ 、黎曼隨機(jī)方差減小梯度下降算法［23］ 和黎曼非精確信賴域算法［24］ （fi二階連續(xù)可微）。特別地， 黎曼非精確信賴域算法通過使用目標(biāo)函數(shù)的非精確梯度和非精確Hessian提高了算法的收斂效率， 并在相關(guān)參數(shù)的假設(shè)條件下估計了算法的迭代復(fù)雜度（只有證明思路， 沒有具體證明）。我們指出， 在該假設(shè)條件下， 按照文獻(xiàn)中的思路不能證明出相應(yīng)結(jié)果。本文提出了不同的參數(shù)假設(shè)， 并證明了算法具有類似的迭代復(fù)雜度。

本文的結(jié)構(gòu)如下：第二節(jié)介紹了黎曼流形上的一些基本概念和性質(zhì)，第三節(jié)是主要研究內(nèi)容， 我們提出了不同于文獻(xiàn)［24］ 的參數(shù)假設(shè)條件， 并證明了黎曼非精確信賴域算法的迭代復(fù)雜度，在第四節(jié)中總結(jié)全文。

2預(yù)備知識

本節(jié)介紹下文用到的符號和黎曼流形上的基本概念和性質(zhì)， 可參考文獻(xiàn)［11， 25-34］ 。

設(shè)（M，g）是一個完備的m維黎曼流形， g是M上的黎曼度量。設(shè)x∈M， 用TxM表示點(diǎn)x處的切空間， TM：=Ux∈MTxM表示黎曼流形M上的切叢。切空間TxM上任意兩個切向量的內(nèi)積表示為〈·，·〉x， 向量的模長可表示為·x，本文為了符號簡潔省略下標(biāo)x。設(shè)y∈M， 用γ：［0，1］→M表示連接點(diǎn)x與y之間的一條分段光滑曲線， 則曲線γ的長度表示為l（γ）：=∫10γ′（t）dt，x與y之間的黎曼距離表示為d（x，y）：=infΓl（γ）， 其中Γ代表連接點(diǎn)x與y之間的所有分段光滑曲線的集合， infΓl（γ）表示取集合Γ線長的下確界。

用表示M上的Levi-Civita聯(lián)絡(luò)。設(shè)V為M上的一個向量場， 如果γ′V=0， 則稱該向量場沿曲線γ平行。特別地， 對于光滑曲線γ， 如果γ沿其切向量場γ′自平行（即γ′γ′=0）， 則稱γ是一條測地線。設(shè)x，y∈M， 如果連接這兩點(diǎn)的測地線的長度等于它們之間的黎曼距離， 則稱其為連接x與y的最短測地線。文獻(xiàn)［25］ 中Hopf-Rinow定理表明當(dāng)（M，d）是完備距離空間時， 對于任意兩點(diǎn)x，y∈M， 至少存在一條連接它們的最短測地線。

設(shè)f：M→R是定義在M上的二次連續(xù)可微函數(shù)。對任意的x∈M及任意的切向量ξ，η∈TxM，f在x處的黎曼梯度和黎曼Hessian分別表示為gradf（x）和Hessf（x）， 定義為

〈gradf（x），ξ〉=ξ（f），

Hessf（x）（ξ，η）=〈ξgradf（x），η〉.

設(shè)M，N分別是m，n維黎曼流形， F：M→N是光滑映射， x∈M。F在點(diǎn)x處的微分DF：TxM→TF（x）N定義如下：

DF［ξ］（f）=ξ（fF），ξ∈TxM，f∈C∞F（x）N，

其中C∞F（x）N是N在F（x）處所有光滑函數(shù)的集合。

在黎曼流形M上我們使用如下拉回映射概念， 具體可參考文獻(xiàn)［11］ 中定義4.1.1。

定義1拉回映射、二階拉回映射） M上光滑映射R：TM→M稱為一個拉回映射， 如果其在點(diǎn)x∈M的限制Rx：TxM→M具有以下性質(zhì)：

（1） Rx（0x）=x，其中0x表示TxM的零向量;

（2） DRx（0x）=IdTxM， 其中DRx（0x）是Rx在0x處的協(xié)變微分， IdTxM是TxM上的恒等映射（注意T0x（TxM）TxM）。

進(jìn)一步， 如果R還滿足下式， 則稱R為二階拉回映射：

D2dt2Rx（tη）|t=0=0，x∈M，η∈TxM，

其中D2dt2γ（t）是曲線γ（t）的二階導(dǎo)數(shù)。

注1（1） 特別地， 指數(shù)映射是黎曼流形M上的一個二階拉回映射。此外， 我們可以在文獻(xiàn)［9］ 找到更多矩陣流形上拉回映射的例子。

（2） 通常情況下， 歐氏Hessian2fRx（0x）和黎曼Hessian Hessf（x）是不同的， 但當(dāng)使用二階拉回映射時它們是相等的（詳見文獻(xiàn)［24］ 中引理3.9）。

設(shè)指標(biāo)集J=｛1，2，…，n｝， 考慮大規(guī)模優(yōu)化問題（1）：

minx∈Mf（x）=1n∑ni=1fi（x），

其中n1（n很大）， 對任意i∈J，fi：M→R是一個二次連續(xù)可微函數(shù)。在算法研究和數(shù)值計算中很多學(xué)者使用以下（εg，εH）-近似最優(yōu)解概念， 具體定義參見文獻(xiàn)［10］ 中定義1。下文用λmin（A）表示矩陣A的最小特征值。

定義2（（εg，εH）-近似最優(yōu)解） 設(shè)εg，εH∈（0，1）， 如果滿足

gradf（x*）≤εg， λmin（Hessf（x*））≥-εH，

則稱點(diǎn)x*∈M為問題（1）的1個（εg，εH）-近似最優(yōu)解。

事實上， 我們采用了抽樣技術(shù)來選取非精確梯度和非精確Hessian。在迭代過程中， 設(shè)Sg，SHJ分別表示從總樣本集中采取放回或不放回抽樣所獲得的黎曼梯度和Hessian的樣本集，它們的樣本數(shù)可以分別記為|Sg|和|SH|。對任意x∈M， 定義非精確梯度G（x）和非精確Hessian H（x）如下：

G（x）：=1|Sg|∑i∈Sggradfi（x），

H（x）：=1|SH|∑i∈SHHessfi（x）.（2）

為方便起見， 對于xk∈M， 記Gk：=G（xk），Hk：=H（xk）。以下引理指出了當(dāng)樣本量|Sg|和|SH|充分大時， 可以保證非精確的G（x）和H（x）在大概率意義下近似精確的梯度gradf（x）和Hessian Hessf（x）， 具體可以參見文獻(xiàn)［24］ 中定理4.1。

引理1設(shè)δ，δg，δH∈（0，1），R是一個二階拉回映射。假設(shè)對指標(biāo)集J進(jìn)行放回或者不放回的等可能隨機(jī)抽樣生成Sg和SH， 且G（x）和H（x）如（2）所定義。若抽樣樣本數(shù)|Sg|和|SH|滿足

|Sg|≥32（Kmaxg）2log1δ+14δ2g，

|SH|≥32（KmaxH）2log1δ+14δ2H，

則對任意x∈M和任意η∈TxM有

Pr（G（x）-gradf（x）≤δg）≥1-δ，

Pr（（H（x）-2fRx（0x））［η］≤δHη）≥

1-δ，

其中

Kmaxg（x）：=maxi∈Jsupx∈Mgradfi（x），

KmaxH（x）：=maxi∈Jsupx∈MHessfi（x）.

3黎曼非精確梯度和非精確Hessian自適應(yīng)三次正則化算法

為解決大規(guī)?？煞蛛x無約束優(yōu)化問題（1）， Kasai等在文獻(xiàn)［24］中提出了以下使用非精確梯度和非精確Hessian的黎曼非精確信賴域算法（即算法1）， 并給出了黎曼非精確信賴域算法得到（εg，εH）-近似最優(yōu)解的迭代復(fù)雜度定理。但是文獻(xiàn)中只給出了參數(shù)假設(shè)條件和證明思路， 并未給出關(guān)于該定理的具體證明。我們發(fā)現(xiàn)在定理所給出的參數(shù)假設(shè)條件之下， 并不能證明出該定理所敘述的結(jié)論： 算法至多迭代T∈（max｛ε-2gε-1H，ε-3H｝）次得到（εg，εH）-近似最優(yōu)解。因此， 本文提出不同的參數(shù)假設(shè)條件， 并證明了黎曼非精確信賴域算法的迭代復(fù)雜度。

算法1（黎曼流形上的非精確信賴域算法）：

Step 0： 輸入給定參數(shù)εg，εH，ρTH（0，1），γgt;1。給定x0∈M及Δ0∈（0，∞）， 置k：=0;

Step 1： 計算函數(shù)f在xk處的非精確梯度Gk和非精確Hessian Hk;

Step 2： 如果Gk≤εg且λmin（Hk）≥-εH， 則輸出xk;

Step 3： 近似求解子問題：

ηk≈argminη∈TxkM，ηk≤Δkmk（η）：=f（xk）+〈Gk，η〉+12〈Hk［η］，η 〉s.t. ηk≤Δk;（3）

Step 4： 計算ρk：=f（xk）-fRxk（ηk）mk（0xk）-mk（ηk）;

Step 5： 如果ρk≥ρTH， 則有xk+1=Rxk（ηk）和Δk+1=γΔk， 否則有xk+1=xk和Δk+1=Δkγ;

Step 6： 置k：=k+1轉(zhuǎn)回Step 1。

設(shè)｛xk｝M是由黎曼非精確信賴域法所產(chǎn)生的迭代點(diǎn)列。為了對該算法進(jìn)行迭代復(fù)雜度分析， 在本文中我們需要用到以下假設(shè)1-4。

假設(shè)1存在常數(shù)LHgt;0， 對任意常數(shù)k∈N， 使得fR滿足

fRxk（ηk）-f（xk）+〈gradf（xk），ηk〉+12〈2fRx（0x）［ηk］，ηk〉≤12LHηk3.

假設(shè)2存在常數(shù)KHgt;0， 使得非精確Hessian Hk滿足

Hk：=supη∈TxkM，η≤1〈η，Hk［η］〉≤KH， k∈N.

假設(shè)3存在常數(shù)δg，δH∈（0，1）， 對任意常數(shù)k∈N，使得非精確梯度Gk和非精確HessianHk滿足

Gk-gradf（xk）≤δg，

（Hk-2fRxk（xk））［ηk］≤δHηk.

注 2（1） 如文獻(xiàn)［35］ 中Appendix B所示， 當(dāng)M是緊致的且R為二階拉回映射時， 假設(shè)1成立。

（2） 特別地， 由引理1我們可通過抽樣選取｛Gk｝和｛Hk｝， 并確保假設(shè)3在一定概率下成立。

事實上， 在大規(guī)?？煞蛛x優(yōu)化問題中， 求子問題的精確解是難以實現(xiàn)的。因此， 考慮在算法1的第k次迭代中近似求解子問題（3）。近似求解的思路參見文獻(xiàn)［10， 27， 36］， 子問題（3）的近似解ηk通常需要滿足Cauchy Point條件和Eigen Point條件［36］， 即假設(shè)4。

假設(shè)4對任意k∈N， 使得ηCk，ηEk滿足

mk（0xk）-mk（ηk）≥mk（0xk）-mk（ηCk）≥12GkminGk1+Hk，Δk;（4）

當(dāng)λmin（Hk）lt;-εH時， 存在常數(shù)ν∈（0，1］有

mk（0xk）-mk（ηk）≥mk（0xk）-mk（ηEk）≥12ν·|λmin（Hk）|Δ2k，（5）

其中ηCk （Cauchy Point）和ηEk （Eigen Point）分別是子問題（3）沿著近似負(fù)梯度方向（-Gk）和近似負(fù)曲率方向（Hk絕對值最大的負(fù)特征值所對應(yīng)特征向量的方向）的最優(yōu)解， 且ηEk滿足

〈ηEk，Hk［ηEk］〉≤νλmin（Hk）ηEk2lt;0.

我們注意到滿足不等式（4）和（5）的近似解條件在求解子問題（3）時仍然適用。為了確保子問題（3）的近似解滿足以上假設(shè)條件， 我們使用文獻(xiàn)［7］ 提出的在ηCk和ηEk所張成的二維子空間中求解該子問題， 則有

ηk≈argminη∈Span｛ηCk，ηEk｝，ηk≤Δkf（xk）+〈Gk，η〉+12〈Hk［η］，η〉 s.t. ηk≤Δk.

為了對黎曼非精確信賴域法進(jìn)行迭代復(fù)雜度分析， 首先給出下列引理。

引理 2假設(shè)（A1）和（A3）成立， 則對任意k∈N有

|mk（ηk）-fRxk（ηk）|≤LH2Δ3k+δH2Δ2k+δgΔk，（6）

其中LH是假設(shè)1的Lipschitz常數(shù)， 引理2的證明詳見文獻(xiàn)［24］ 的Section B.1。

結(jié)合假設(shè)1-4， 我們在下個引理中給出了算法1在第k次迭代點(diǎn)xk∈M不滿足終止條件時信賴域半徑增加的充分條件。

引理 3假設(shè)1-4成立， 又設(shè)

δg≤min1-ρTH4εg，νεH12Δk，

δH≤min1-ρTH2νεH，1.

如果在第k次迭代點(diǎn)xk∈M處滿足下列條件之一， 則信賴域半徑增加， 即Δk+1=γΔk（γgt;1）：

（1） Gkgt;εg，Δk≤minεg1+KH，（1-ρTH）εg12LH，（1-ρTH）εg3;

（2） λmin（Hk）lt;-εH，Δk≤（1-ρTH）νεH3LH.

證明根據(jù)算法1中Step4-5， 要證明信賴域半徑增加， 只需證明下式成立：

ρk：=f（xk）-fRxk（ηk）mk（0xk）-mk（ηk）≥ρTH.（7）

首先設(shè)條件（1）成立， 則Δk≤Gk1+KH，又由（4）和假設(shè)2可得

mk（0xk）-mk（ηk）≥12GkminGk1+KH，Δk≥12GkΔk.

結(jié)合上式和（6）可得

1-ρk=fRxk（ηk）-mk（ηk）mk（0xk）-mk（ηk）≤

LHΔ3k+δHΔ2k+2δgΔkGkΔk≤1-ρTH，

其中第二個不等式由條件（1）的第二項， δg≤1-ρTH4εg和δH≤1得到，因此（7）成立。

假設(shè)條件（2）成立，由（5）和（6）得

1-ρk=fRxk（ηk）-mk（ηk）mk（0xk）-mk（ηk）≤

LHΔ3k+δHΔ2k+2δgΔkνεHΔ2k≤1-ρTH，

其中第二個不等式由條件（2）的第二項， δg≤νεH12Δk和δH≤1-ρTH2νεH得到，因此（7）成立。

以下引理給出了算法1迭代終止前信賴域半徑Δk的下界估計。本文中將所有滿足（7）的迭代稱為成功迭代， 否則稱為失敗迭代。我們將算法1迭代終止前的所有成功（失?。┑募嫌洖門succ（Tfail）， 它們的迭代次數(shù)可分別記為|Tsucc|和|Tfail|。

引理 4假設(shè)1-4成立， 且參數(shù)滿足

δg≤min1-ρTH4εg，νεH12Δk，

δH≤min1-ρTH2νεH，1.

則對任意k∈N有

Δk≥κΔmin｛εg，εH｝，（8）

其中

κΔ：=1γmin11+KH，1-ρTH12LH，1-ρTH3，（1-ρTH）ν3LH.

證明反證法， 假設(shè)結(jié)論不成立。又設(shè)第k+1次迭代為第一次不滿足（8）的迭代， 即有

Δk+1lt;κΔmin｛εg，εH｝及

Δk+1=Δkγ.（9）

因此，我們可以得到

Δklt;γκΔmin｛εg，εH｝lt;

minεg1+KH，（1-ρTH）12LHεg，（1-ρTH）εg3，（1-ρTH）νεH3LHlt;minεg1+KH，（1-ρTH）εg12LH，（1-ρTH）εg3，（1-ρTH）νεH3LH，（10）

其中最后一個不等式是因為εg∈（0，1）。又因為在第k次迭代算法并未終止， 因此Gkgt;εg或λmin（Hk）lt;-εH成立。結(jié)合對參數(shù)δg和δH的假設(shè)和（10）， 由引理3可得第k次迭代時信賴域半徑增加， 即Δk+1=γΔk， 與（9）矛盾。故結(jié)論成立。

引理5給出了算法終止前成功迭代總次數(shù)的估計。

引理 5假設(shè)引理4中的條件成立， 則算法1迭代終止前成功迭代總次數(shù)有上界：

|Tsucc|≤f（x0）-fminρTHκ-Δmax｛ε-2gε-1H，ε-3H｝，（11）

其中fmin是函數(shù)最優(yōu)值， κ-Δ：=12min｛κΔ，νκ2Δ｝，κΔ如引理4中定義。

證明假設(shè)算法1在第k次迭代時并未終止， 則Gkgt;εg或λmin（Hk）lt;-εH成立。當(dāng)Gkgt;εg， 由（4）， 假設(shè)2和引理4可得

mk（0xk）-mk（ηk）≥εg2minεg1+KH，Δk≥εg2minεg1+KH，κΔεg，κΔεH≥εg2κΔmin｛εg，εH｝;（12）

當(dāng)λmin（Hk）lt;-εH， 由（5）和引理4可得

mk（0xk）-mk（ηk）≥12ν|λmin（Hk）|Δ2k≥12νεHκ2Δmin｛ε2g，ε2H｝.（13）

因為｛f（xk）｝為單調(diào)遞減序列， 可得

f（x0）-fmin≥∑k∈Tsuccf（xk）-f（xk+1）≥∑k∈TsuccρTH（mk（0xk）-mk（ηk））≥|Tsucc|ρTH2min｛κΔ，νκ2Δ｝min｛ε2gεH，ε3H｝，

其中第二個不等式由（7）得到， 第三個不等式由（12）和（13）得到。顯然， （11）成立。

最后， 給出算法1的迭代復(fù)雜度定理。

定理 1假設(shè)引理5中條件成立， 則算法1有限步終止， 且終止前迭代次數(shù)T的估計如下：

T≤2（f（x0）-fmin）ρTHκ-Δmax｛ε-2gε-1H，ε-3H｝+logγ·Δ0κΔmin｛εg，εH｝，

其中κΔ，κ-Δ分別如引理4和引理5中定義。

證明注意到算法終止前總迭代次數(shù)為T=|Tsucc|+|Tfail|，由算法1的迭代機(jī)制可得

ΔT=Δ0γ|Tsucc|-|Tfail|，γgt;1.

又由引理4和引理5知Δk有正下界， |Tsucc|有上界， 因此|Tfail|也有上界（否則Δk→0， 矛盾）。結(jié)合（8）和（11）可得

T=|Tsucc|+|Tfail|≤2|Tsucc|+logγΔ0ΔT≤2（f（x0）-fmin）ρTHκ-Δmax｛ε-2gε-1H，ε-3H｝+logγΔ0κΔmin｛εg，εH｝∈（max｛ε-2gε-1H，ε-3H｝）.

注3（1） Kasai等人在文獻(xiàn)［24］ 中所提出的黎曼非精確信賴域算法中的參數(shù)假設(shè)為：

δg≤（1-ρTH）4εg， δH≤min（1-ρTH）2νεH，1， Δk≥1γminεg1+KH，（1-ρTH）εg12LH，（1-ρTH）εg3，νεHLH;

（2） 本文中參數(shù)假設(shè)為：

δg≤min（1-ρTH）εg4，νεH12Δk， δH≤min（1-ρTH）2νεH，1， Δk≥1γminεg1+KH，（1-ρTH）εg12LH，（1-ρTH）εg3，（1-ρTH）νεH3LH.

4結(jié)論

為得到文獻(xiàn)［24］ 中關(guān)于黎曼非精確信賴域算法的迭代復(fù)雜度， 本文提出不同的的參數(shù)假設(shè)條件， 并給出詳細(xì)證明。由于該算法的每一次迭代都是采用信賴域的子問題的近似解， 因此下一步我們將重點(diǎn)研究在黎曼流形上近似求解信賴域子問題。特別地， 當(dāng)函數(shù)為非光滑情形時， 我們還可以針對大規(guī)?？煞蛛x無約束優(yōu)化問題考慮黎曼流形上的非光滑非精確梯度算法。

參考文獻(xiàn)（References）

［1］SHALEV-SHWARTZ S， BEN-DAVID S. Understanding machine learning： From theory to algorithms［M］. Cambrige：Cambridge University Press， 2014.

［2］ROOSTA-KHORASANI F， DOEL K， ASCHER U. Data completion and stochastic algorithms for PDE inversion problems with many measurements［J］. Electron Transaction on Numerical Analysis， 2014， 42： 177-196.

［3］ROOSTA-KHORASANI F， DOEL K， ASCHER U. Stochastic algorithms for inverse problems involving PDEs and many measurements［J］. SIAM Journal on Scientific Computing， 2014， 36（5）： 3-22.

［4］MA Y， KSECKA J， SASTRY S. Optimization criteria and geometric-algorithms for motion and structure estimation［J］. International Journal of Computer Vision， 2001， 44： 219-249.

［5］NISHIMORI Y， AKAHO S. Learning algorithms utilizing quasi-geodesic flows on the Stiefel manifold［J］. Neurocomputing， 2005， 67： 106-135.

［6］ROBBINS H， MONRO S. A stochastic approximation methods［J］. The Annals of Mathematical Statistics， 1951， 22（3）： 400-407.

［7］ROUX N， SCHMIDT M， BACH F. A stochastic gradient method with an exponential convergence rate for finite training sets［J］. Advances in Neural Information Processing Systems， 2013， 4： 2663-2671.

［8］JOHNSON R， ZHANG T. Accelerating stochastic gradient descent using predictive variance reduction［J］. News in Physiological Sciences， 2013， 1（3）： 315-323.

［9］YAO Z， XU P， ROOSTA-KHORASANI F， et al. Inexact nonconvex Newton-type methods［J］. INFORMS Journal on Optimization， 2021， 3（2）： 154-182.

［10］XU P， ROOSTA-KHORASANI F， MAHONEY M W. Newton-type methods for nonconvex optimization under inexact Hessian information［J］. Mathematical Programming， 2020， 184（1-2）： 35-70.

［11］ABSIL P A， MAHONY R， SEPULCHRE R. Optimization algorithms on matrix manifolds［M］. New Jersey： Princeton University Press， 2008.

［12］WANG X M， LI C， WANG J H， et al. Linear convergence of subgradient algorithm for convex feasibility on Riemannian manifolds［J］. SIAM Journal on Optimization， 2015， 25（4）： 2334-2358.

［13］FERREIRA O P， LOUZEIRO M S， PRUDENTE L F. Gradient method for optimization on Riemannian manifolds with lower bounded curvature［J］. SIAM Journal on Optimization， 2019， 29（4）： 2517-2541.

［14］BENTO C G， BITAR S D B， CRUZ-NETO J X， et al. Computing Riemannian center of mass on Hadamard manifolds［J］. Journal of Optimization Theory and Applications， 2019， 183（3）： 977-992.

［15］ABSIL P A， BAKER C G， GALLIVAN K A. Trust-region methods on Riemannian manifolds［J］. Foundations of Computational Mathematics， 2007， 7： 303-330.

［16］SATO H， KASAI H， MISHRA B. Riemannian stochastic variance reduced gradient［J］. ArXiv preprint arXiv， 2017： 113-137.

［17］HUANG W， GALLIVAN K A， ABSIL P A. A broyden class of quasi-newton methods for riemannian optimization［J］. SIAM Journal on Optimization， 2015， 25（3）： 1660-1685.

［18］GABAY D. Minimizing a differentiable function over a differential manifold［J］. Journal of Optimization Theory and Applications， 1982， 37： 177-219.

［19］RING W， WIRTH B. Optimization methods on Riemannian manifolds and their application to shape space［J］. SIAM Journal on Optimization， 2012， 22（2）： 596-627.

［20］KASAI H， SATO H， MISHRA B. Riemannian stochastic recursive gradient algorithm［C］. Stockholm： In Proceedings of the 35th International Conference on Machine Learning， 2018： 2516-2524.

［21］WANG X M. Subgradient algorithms on Riemannian manifolds of lower bounded curvatures［J］. Optimization， 2018， 67（1）： 179-194.

［22］BONNABEL S. Stochastic gradient descent on Riemannian manifolds［J］. IEEE Transactions on Automatic Control， 2013， 58（9）： 2217-2229.

［23］ZHANG H Y， REDDI S J， SRA S. Riemannian SVRG： Fast stochastic optimization on Riemannian manifolds［J］. Advances in Neural Information Processing Systems， 2016： 29.

［24］KASAI H， MISHRA B. Inexact trust-region algorithms on Riemannian manifolds［J］. Advances in Neural Information Processing Systems， 2018： 31.

［25］DO-CARMO M P. Riemannian geometry［M］. Boston： Birkhuser， 1992.

［26］UDRISTE C. Convex functions and optimization methods on Riemannian manifolds［M］. Berlin： Springer， 2013.

［27］CONN A R， GOULD N I M， TOINT P L. Trust-region methods［M］. Philadelphia： Society for Industrial and Applied Mathematics， 2000.

［28］陳維桓， 李興校. 黎曼幾何引論［M］. 北京： 北京大學(xué)出版社， 2014.

［29］陳維桓. 微分流形初步［M］. 北京： 高等教育出版社， 2019.

［30］潘漢. 黎曼流形優(yōu)化及其應(yīng)用［M］. 北京： 科學(xué)出版社， 2020.

［31］蕭樹鐵， 陳維桓. 大學(xué)數(shù)學(xué)：流形上的微積分［M］. 北京： 高等教育出版社， 2003.

［32］忻元龍. 黎曼幾何講義［M］. 上海： 復(fù)旦大學(xué)出版社， 2010.

［33］JOST J. Riemannian geometry and geometric analysis［M］. Berlin： Springer， 2008.

［34］O’NEILL B. Semi-Riemannian geometry with applications to relativity［M］. New York： Academic Press， 1983.

［35］BOUMAL N， ABSIL P A， CARTIS C. Global rates of convergence for nonconvex optimization on manifolds［J］. IMA Journal of Numerical Analysis， 2019， 39（1）： 1-33.

［36］CARTIS C， GOULD N I M， TOINT P L. Adaptive cubic regularization methods for unconstrained optimization. Part II： motivation， convergence and numerical results［J］. Mathematical Programming， 2011， 127（2）： 245-295.

（責(zé)任編輯：編輯郭蕓婕）

收稿日期：2024-01-11

基金項目：國家自然科學(xué)基金項目（12161017）; 貴州省科技計劃項目（黔科合基礎(chǔ)-ZK［2022］一般110）

作者簡介：李祉赟（1999—）， 女， 碩士研究生， 專業(yè)方向為優(yōu)化理論研究。

*通信作者：王湘美（1972—）， 女， 教授， 從事優(yōu)化理論方向的研究， e-mail： xmwang2@gzu.edu.cn。

DOI：10.13880/j.cnki.65-1174/n.2024.23.022

文章編號：1007-7383（2024）03-0390-07