余紅蕾

(滁州城市職業(yè)學(xué)院 教育系，安徽 滁州239000)

1 引言

假設(shè)有兩個(gè)很大的正整數(shù)n和m，考慮如下所示的一般帶約束凸優(yōu)化問題：

minimizief(x)

(1)

subject togk(x)≤0,?k∈{1,2,…,m}

(2)

x∈χ

(3)

假設(shè)1：

·優(yōu)化問題(1)-(3)存在唯一(可能不唯一)的最優(yōu)解x*∈χ。

·存在Lf≥0，對(duì)于?x,y∈χ，使‖f(x)-f(y)‖≤Lf‖x-y‖；對(duì)于k∈{1,2,…,m} ，存在Lgk≥0，對(duì)于?x,y∈χ，使‖gk(x)-gk(y)‖≤Lgk‖x-y‖。令Lg=[Lg1,…,Lgm]T。

·存在β≥0，對(duì)于?x,y∈χ，使‖g(x)-g(y)‖≤β‖x-y‖。

·存在C≥0，對(duì)于?x∈χ，使‖g(x)‖≤C。

·存在R≥，對(duì)于?x,y∈χ，使‖x-y‖≤R。

其中，q(λ)是優(yōu)化問題(1)-(3)的拉格朗日對(duì)偶函數(shù)。

2 算法設(shè)計(jì)

2.1 大規(guī)模凸優(yōu)化問題

問題(1)-(3)可以利用內(nèi)點(diǎn)法(或牛頓法)來(lái)解決，這些方法需要在每次迭代的時(shí)候進(jìn)行Hessian矩陣及其逆矩陣的計(jì)算。每次迭代的計(jì)算復(fù)雜度和內(nèi)存空間復(fù)雜度在O(n2)和O(n3)之間。當(dāng)n非常大時(shí)，計(jì)算和空間開銷都是巨大的。例如，假設(shè)n=105，每個(gè)浮點(diǎn)數(shù)使用4字節(jié)儲(chǔ)存，那么就需要用40 GB的內(nèi)存來(lái)保存每次迭代的Hessian矩陣。因此，大規(guī)模的優(yōu)化問題通常采用基于梯度或基于分解的方法進(jìn)行求解。

2.2 Primal-Dual次梯度法

2.3 拉格朗日對(duì)偶方法

利用拉格朗日對(duì)偶方法求解問題(1)-(3)的收斂速度為O(1/t)[3]。如果函數(shù)f(x)和gk(x)具有可分解的結(jié)構(gòu)，拉格朗日對(duì)偶方法可以將x(t)的計(jì)算分解為更小的子問題。但是，如果函數(shù)f(x)和gk(x)不可分解，則每次計(jì)算x(t)時(shí)都需要解一個(gè)有約束的凸優(yōu)化問題，大大增加了計(jì)算的復(fù)雜度[4]。

2.4 一種新的算法

考慮一個(gè)大規(guī)模的凸優(yōu)化問題，其中函數(shù)f(x)或者gk(x)不具有可以分解的結(jié)構(gòu)。筆者通過結(jié)合Primal-Dual次梯度法和拉格朗日對(duì)偶方法的優(yōu)點(diǎn)，提出了一種新的算法，其框架如下所示。

算法1 新的算法初始化:· 步長(zhǎng)γ為正常數(shù)· 選擇x(-1)∈χ· Qk(0)=max{0,-gk(x(-1))}對(duì)于每一個(gè)t:· 定義梯度d(t)=?f(x(t-1))+∑mk=1[Qk(t)+gk(x(t-1))]?gk(x(t-1))· 計(jì)算x(t)=Pχ[x(t-1)-γd(t)],其中,Pχ[g]是投影操作· 計(jì)算Qk(t+1)=max{-gk(x(t)),Qk(t)+gk(x(t))}· 計(jì)算x(t+1)=1t+1∑tτ=0x(τ)

3 基本分析

定義1：假設(shè)χ?n是一個(gè)凸集。若存在L>0，使‖h(y)-h(x)‖≤L‖y-x‖，那么函數(shù)h:→χ?m則具有利普希茨連續(xù)性。

定義2：假設(shè)χ?n，函數(shù)h(x)在χ上連續(xù)并可微。若h(x)在χ上是利普希茨連續(xù)，則函數(shù)h(x)在χ上是光滑的。

引理1[5]：若函數(shù)h在χ上是光滑的，那么有h(y)≤h(x)+

定義3：假設(shè)χ?n是一個(gè)凸集。若存在一個(gè)常數(shù)α>0，使在χ上是凸函數(shù)，則函數(shù)h在χ上是強(qiáng)凸函數(shù)。

引理2：假設(shè)χ?n是一個(gè)凸集。假設(shè)函數(shù)h是強(qiáng)凸函數(shù)，xopt是函數(shù)h在χ上全局最小解。那么，有

引理3：在算法1中，有

1) 在每一步迭代t∈{0,1,…}中，對(duì)于k∈{1,2,…,m}，Qk(t)≥0。

2) 在每一步迭代t∈{0,1,…}中，對(duì)于k∈{1,2,…,m}，Qk(t)+gk(x(t-1))。

3) 當(dāng)t=0，‖Q(0)‖2≤‖g(x(-1))‖2；當(dāng)t∈{1,2,…}，‖Q(t)‖2≥‖g(x(t-1))‖2。

引理5：在每一個(gè)迭代t中，李雅普諾夫漂移的上界是

Δ(t)≤QT(t)g(x(t))+‖g(x(t))‖2

(4)

4 上界以及算法收斂分析

4.1 上界分析

引理7：假設(shè)x*是最優(yōu)解。對(duì)于t≥0，有

證明：假設(shè)t≥0。令φ(x)=f(x)+[Q(t)+g(x(t-1))]T。由引理3的第二部分可知，Q(t)+g(x(t-1))中的每一個(gè)元素都是非負(fù)數(shù)。因此，φ(x)是凸函數(shù)。由于d(t)=φ(x(t-1))，算法1中的投影操作可以轉(zhuǎn)化成以下的優(yōu)化問題：

x(t)=Pχ[x(t-1)-γd(t)]

(5)

(6)

其中，(a)由函數(shù)φ(x)的凸性可得；(b)根據(jù)函數(shù)φ(x)的定義可得；(c)由引理3的第二部分可得。

由于函數(shù)f(x)在χ上是光滑的函數(shù)(假設(shè)1)，根據(jù)引理1，有

(7)

由假設(shè)1可知，每一個(gè)函數(shù)gk(x)在χ上都是光滑的。因此，[Qk(t)+gk(x(t-1))]gk(x)也是光滑的。由引理1，有

對(duì)上述不等式關(guān)于k∈{1,2,…,m}求和，得到

(8)

將公式(7)和(8)相加，得到

(9)

其中，(a)由函數(shù)φ(x)定義可得。

將公式(6)帶入公式(9)，可得

(10)

其中，(a)由‖g(x(t-1))-g(x(t))‖≤β‖x(t)-x(t-1)‖可得。將該不等式與公式(4)相加，能夠得到

此時(shí)，引理7得證。

4.2 收斂速率

定理1說(shuō)明了算法1的誤差以速度O(1/t)減少，即算法1的收斂速率是O(1/t)。

5 結(jié)論

針對(duì)大規(guī)模的凸優(yōu)化問題，提出了一種新的具有更快收斂速度的原對(duì)偶方法，每次迭代僅需要進(jìn)行簡(jiǎn)單的梯度更新，從而降低復(fù)雜度。未來(lái)的工作將探討如何在真實(shí)的應(yīng)用場(chǎng)景實(shí)現(xiàn)筆者提出的算法。