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

張善美， 王志尚

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

0 引 言

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

考慮如下稀疏優化問題

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

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

1 定義及預備知識

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

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

由投影定義,PCs(x)應包含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)并不一定是唯一的. 當Ms(x)=0 或者Ms(x)>Ms+1(x) 時,PCs(x) 是唯一的. 否則

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

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

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

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

引理1.2[3]對α>0,x*是一個α-穩定點當且僅當‖x*‖0≤s,且

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

算法1.1(IHT算法)

輸入：常數L>Lf.

初始步：取x0∈Cs.

注1.1上述算法中的Lf為目標函數梯度的Lipschitz常數.

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

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

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

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

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

算法1.2

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

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

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

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

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

2 算法及收斂性

下面采用非單調的Armijo線搜索來獲得步長,以此來設計算法,得到算法2.1.

算法2.1

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

(2) 若

(3)

滿足，則xk+1=u，轉步驟2.

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

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

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

其中L是目標函數梯度的Lipschitz常數. 由投影算子的性質，

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

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

(4)

所以函數{f(xl(k))}是單調不增的.

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

(5)

(6)

(7)

下面證明以下式子成立:

(8)

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

定理2.1設{xk}是由算法2.1生成的序列. 則{xk}的任何聚點都是α-穩定點.

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

綜上

這樣,由引理1.2知,得到的聚點是α-穩定點.