高校圖書館中的一類優(yōu)化問題及其求解算法*

張善美， 王志尚

(①曲阜師范大學(xué)圖書館;②曲阜師范大學(xué)管理學(xué)院,276826,山東省日照市)

0 引 言

在高校圖書館中，一些問題與稀疏性有著直接的關(guān)系. 例如，對于大數(shù)據(jù)時代產(chǎn)生的海量的電子資源， 迫切需要高效的方式來對海量數(shù)據(jù)進(jìn)行存儲、發(fā)送以及加密處理. 傳統(tǒng)的存儲方法已經(jīng)滿足不了新時代圖書館的信息知識爆發(fā)式的增長，我們需要尋求和探索如何使用較小的成本，在有限的空間中存儲更多的資源. 在文獻(xiàn)[1]中，作者基于智能化圖書館背景提出了一種壓縮存儲方法，首次嘗試將壓縮傳感技術(shù)(通過利用信號、信息的稀疏性，大大提高信號采集能力、信息處理能力，緩解海量數(shù)據(jù)的采樣、存儲、傳輸和分析負(fù)擔(dān))應(yīng)用于圖書館的數(shù)字資源管理中. 這對圖書館館藏中電子資源的存儲，尤其是非文本資源(諸如PDF 版本、JPG 版本、PNG 版本)的存儲有著重要的意義，甚至對于高維度的影像以及視頻的存儲都起到重要的促進(jìn)作用. 另外，高校圖書館作為信息資源的集散地，在不斷滿足科研學(xué)者的信息需求的同時，也存在著信息量龐大和用戶特定需求難以匹配的矛盾. 這時就需要圖書推薦系統(tǒng)發(fā)揮出其作用，使得圖書館資源得到充分利用. 雖然圖書館的個性化推薦系統(tǒng)在圖書館已經(jīng)得到應(yīng)用且為用戶帶來了一定的便利，也在一定程度上提升了圖書館的服務(wù)質(zhì)量，但是由于沒有較高的用戶評價主動性，使得數(shù)據(jù)出現(xiàn)稀疏性問題[2]. 面對數(shù)據(jù)的稀疏性問題,我們?nèi)绾蝸硖幚?才能得到最優(yōu)的方案呢？本文研究與稀疏有關(guān)的一類最優(yōu)化問題——稀疏優(yōu)化.

考慮如下稀疏優(yōu)化問題

這類問題是由國際著名優(yōu)化專家Amir Beck等在文獻(xiàn)[3]中提出，此問題的特例之一就是著名的壓縮傳感問題. 由于其中涉及到的稀疏集合Cs={x∈Rn|‖x‖0≤s}是非凸的,這增加了求解此問題的難度. 文獻(xiàn)[3]提出了經(jīng)典的迭代硬閾值(IHT)算法. 該算法是傳統(tǒng)梯度投影算法的一種推廣,方向取負(fù)梯度方向,步長取1/L(L>Lf,Lf為目標(biāo)函數(shù)梯度的Lipschitz常數(shù)). 該算法由于其良好的恢復(fù)性能,得到了大家的廣泛關(guān)注. 但由于該算法取固定步長,且步長較小,會導(dǎo)致算法在迭代過程中下降速度很慢. 為改進(jìn)IHT算法下降速度慢的不足,Pan等人提出了帶有Armijo步長的IHT算法[4],該算法將IHT算法中的固定步長改進(jìn)為Armijo步長規(guī)則來確定,算法所得迭代點的目標(biāo)函數(shù)都能單調(diào)下降. 但是，正如在文獻(xiàn)[5]中作者指出的那樣，迭代序列有可能會陷入一個非常狹窄和曲折的“山谷”附近，從而產(chǎn)生非常短或曲折的步長，在這種情況下大部分的經(jīng)典單調(diào)線性搜索技術(shù)可能會失效. 由此可見單調(diào)線性搜索并不能很好的解決所有的問題. 我們通常使用“非單調(diào)線性搜索”來解決這一難題. 非單調(diào)線性搜索，顧名思義就是，不是一味地減小函數(shù)的值.當(dāng)遇到上述情況時，非單調(diào)線性搜索偶爾會増加目標(biāo)函數(shù)的值. 函數(shù)值的増加可以使迭代序列走出這些“短或曲折的步長”的困擾. 因此，非單調(diào)線搜索不僅可以提高算法的收斂速度，還能増加找到全局最優(yōu)解的可能性.

在本文中,利用IHT算法的基本思想,迭代方向取目標(biāo)函數(shù)的負(fù)梯度方向,而步長采用了一種非單調(diào)線性搜索技術(shù)來確定. 這樣做使得步長的選取有了更大的靈活性.

1 定義及預(yù)備知識

定義1.1[6]設(shè)Ω為非空閉凸集,對任意向量x∈Rn,稱PΩ(x)=argmin{‖x-y‖:x∈Ω}為x到Ω上的投影.

定義1.2[3]稱由Rn往稀疏集Cs上的投影為支撐映射，記為PCs(x).

由投影定義,PCs(x)應(yīng)包含x中s個絕對值最大的分量和其余n-s個0. 對向量x∈Rn和i∈{1,2,…,n},我們用Mi(x) 代表向量x中按絕對值由大到小排列的分量,即

M1(x)≥M2(x)≥…Ms(x)≥…≥Mn(x)，

PCs(x)={y∈Rn|yi=xi,i∈Is(x);yi=0,i?Is(x)}.

因為Cs是非凸的,所以投影PCs(x)并不一定是唯一的. 當(dāng)Ms(x)=0 或者M(jìn)s(x)>Ms+1(x) 時,PCs(x) 是唯一的. 否則

如果存在兩個及以上xi使得|xi|=Ms(x), 那么可以隨意的選取或者根據(jù)已經(jīng)定好的規(guī)則選取,其他取零.

引理1.1[7](下降引理) 若函數(shù)f是一個連續(xù)可微函數(shù),且其梯度是Lipschitz 連續(xù)的,Lipschitz 常數(shù)為L,則對任意l′≥L，有

f(x)≤hl′(x,y) ?x,y∈Rn,

定義1.3[3]設(shè)x*是一個可行點. 若存在α>0,使得x*∈PCs(x*-α?f(x*)). 則稱x*是一個α-穩(wěn)定點.

引理1.2[3]對α>0,x*是一個α-穩(wěn)定點當(dāng)且僅當(dāng)‖x*‖0≤s,且

Amir Beck等在文獻(xiàn)[3]中提出了IHT算法來求解稀疏優(yōu)化問題,該算法采用固定步長,利用梯度投影來進(jìn)行計算,其算法如下.

算法1.1(IHT算法)

輸入：常數(shù)L>Lf.

初始步：取x0∈Cs.

注1.1上述算法中的Lf為目標(biāo)函數(shù)梯度的Lipschitz常數(shù).

引理1.3[3]設(shè){xk}k≥0是由IHT算法生成的序列. 則

(ⅱ) {f(xk)}是一個不增序列;

(ⅲ) ‖xk-xk+1‖→0.

定理1.1[3]設(shè){xk}k≥0是由IHT算法生成的序列. 則{xk} 的任意聚點都是α-穩(wěn)定點.

IHT算法雖能保證算法在每一步都下降,但由于其取固定步長，不能保證每次迭代都有滿意的下降量. Pan等人在IHT算法的基礎(chǔ)上提出了帶Armijo步長的IHT算法[4],該算法用Armijo步長代替固定步長,使目標(biāo)函數(shù)在每一步有較大的下降量,其算法如下.

算法1.2

步驟1 計算xk+1∈PCs(xk-αk?f(xk)),其中αk=α0γqk,qk是使得下式成立的最小非負(fù)整數(shù)

其中xk(α)=PCs(xk-α?f(xk)).

步驟1.2 若‖xk+1-xk‖≤，停止；否則令k=k+1，返回步驟1.

定理1.2[4]設(shè){xk}是由算法1.2生成的序列. 則有下述結(jié)論成立:

(ⅱ) {xk}的任意聚點都是α-穩(wěn)定點.

2 算法及收斂性

下面采用非單調(diào)的Armijo線搜索來獲得步長,以此來設(shè)計算法,得到算法2.1.

算法2.1

步驟0 選取x0=0,01,0<σ<1,ε>0，指標(biāo)M>0，置k=0.

(2) 若

(3)

滿足，則xk+1=u，轉(zhuǎn)步驟2.

注2.1[k-M]+=max{k-M,0}.

(3) 置Lk=τLk，返回步驟1.

步驟2 若‖xk+1-xk‖≤，停止；否則令k=k+1，返回步驟1.

其中L是目標(biāo)函數(shù)梯度的Lipschitz常數(shù). 由投影算子的性質(zhì)，

引理2.2設(shè){xk}是由算法2.1生成的序列. 則有

(ⅱ) {f(xk)}收斂.

(4)

所以函數(shù){f(xl(k))}是單調(diào)不增的.

又因為函數(shù)f(x)有界，不妨設(shè)

(5)

(6)

(7)

下面證明以下式子成立:

(8)

式(6)和式(7)證明了：當(dāng)j=1時,上述兩式成立. 由數(shù)學(xué)歸納法,只需證明對j(j≥1) 成立時,對j+1 也成立即可.

定理2.1設(shè){xk}是由算法2.1生成的序列. 則{xk}的任何聚點都是α-穩(wěn)定點.

因為{αk}有下界,且下界大于零,兩邊取極限,則有

綜上

這樣,由引理1.2知,得到的聚點是α-穩(wěn)定點.