非光滑無約束優(yōu)化次梯度法

□張玉鳳

（廣西大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，廣西 南寧 530004）

非光滑無約束優(yōu)化次梯度法

□張玉鳳

（廣西大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，廣西 南寧 530004）

次梯度法是求解非光滑優(yōu)化問題的一類經(jīng)典算法, 也是解決大規(guī)模問題的有效方法. 它在經(jīng)濟學(xué)、力學(xué)、工程和最優(yōu)控制等許多實際問題中有著廣泛應(yīng)用. 本文概述了經(jīng)典次梯度法的來源、算法基本框架及進一步的改進方法, 為次梯度方法的進一步研究提供參考.

非光滑優(yōu)化；次梯度法；橢球法；變尺度

1 引言

本文考慮求解如下形式的非光滑無約束優(yōu)化問題

其中 f:Rn→R為凸函數(shù)，但不一定可微，即函數(shù)在某些點沒有通常意義下的導(dǎo)數(shù)(梯度). 因此，需要對梯度的概念進行推廣，引入 f 在 x處的次微分：

集合?f(x)中的元素稱為 f 在 x處的次梯度. 在算法設(shè)計時，通常假設(shè)對任意給定的x，能計算出函數(shù)值 f(x)及任意一個次梯度g∈?f(x). 類似于光滑情形，有如下最優(yōu)性條件(見文[1])：x*是問題(1)的最優(yōu)解，當(dāng)且僅當(dāng)0∈?f(x*).然而，直接用次梯度法取代光滑優(yōu)化算法中的梯度求解問題(1)，也是行不通的，原因大致歸結(jié)為以下三點：(a)終止條件不再適用. 對于光滑無約束優(yōu)化問題，梯度存在且連續(xù)，并且在極小點處梯度為零. 由此可知當(dāng)?shù)c充分靠近最優(yōu)解時，梯度的范數(shù)小于一個充分小量，而對于非光滑優(yōu)化問題，則沒有類似的結(jié)果.(b)負次梯度方向不再是下降方向. 對于光滑優(yōu)化問題，負梯度方向總是下降方向. 而對于非光滑優(yōu)化問題，并非所有的負次梯度方向都是下降方向. 實際計算表明，由于非光滑優(yōu)化問題中函數(shù)的數(shù)學(xué)性態(tài)較差，許多不使用導(dǎo)數(shù)的直接搜索方法也難以對其求解；(c)對于非光滑優(yōu)化問題，存在“鋸齒”現(xiàn)象. 在這種情況下，如用精確搜索的最速下降法求解非光滑優(yōu)化問題時，可能會收斂到非最優(yōu)解. 因此，對于求解非光滑優(yōu)化問題必須建立新的理論及方法.

眾所周知，次梯度法[1]是求解非光滑優(yōu)化問題(1)最經(jīng)典的方法，其基本思想是用次梯度代替梯度推廣光滑優(yōu)化的方法. 次梯度法結(jié)構(gòu)簡單，計算量小，雖然在求解非光滑優(yōu)化問題方面仍存在缺點，但它是求解非光滑優(yōu)化問題的基礎(chǔ)，也是解決大規(guī)模非光滑優(yōu)化問題的有效算法. 次梯度法簡單的算法結(jié)構(gòu)，引起眾多學(xué)者的關(guān)注[2～6]，并被廣泛應(yīng)用于求解各類實際問題[7-10]. 盡管如此，但如何構(gòu)造一個目標(biāo)函數(shù)的下降方向以及保證算法的快速收斂性仍是研究次梯度算法所面臨的難題. 本文將重點介紹非光滑優(yōu)化問題經(jīng)典次梯度算法的基本框架及改進方法.

2 經(jīng)典次梯度法

在光滑優(yōu)化問題中，通過計算迭代點處的梯度、投影梯度、共軛梯度等容易獲得目標(biāo)函數(shù)的下降方向. 但在非光滑優(yōu)化中，由于目標(biāo)函數(shù)不可微導(dǎo)致在某些點處沒有通常意義下的梯度，故許多基于梯度理論的算法失效. 為此，N.Z.Shor[11]首次提出使用次梯度代替梯度的次梯度法，進而將光滑優(yōu)化中基于梯度的方法推廣到求解非光滑優(yōu)化問題. 下面給出求解問題(1)的次梯度法的基本框架，見文[12].

算法1（經(jīng)典次梯度法）

步驟0 選取初始點x0及滿足一定條件的步長序列{tk}，令k=0；

步驟1 計算gk∈?f(xk)，若gk=0，則停止；否則轉(zhuǎn)步驟2；

步驟2 令xk+1=xk-tkgk，k=k+1，返回步驟1.

由算法1可知，一方面，經(jīng)典次梯度法結(jié)構(gòu)簡單，在每一個迭代點處只需計算目標(biāo)函數(shù)的一個次梯度即可. 另一方面，次梯度法不需要線搜索，步長事先給定，無需求解不等式，降低了計算量. 在以下三種情況下，算法產(chǎn)生的迭代點列均可收斂到最優(yōu)解x*，見文[13].

其中情形2假設(shè)函數(shù)的最優(yōu)值 f*已知. 不同的步長策略對算法的收斂性有不同的影響，當(dāng)步長序列選取得當(dāng)時，可避免鋸齒現(xiàn)象，獲得好的收斂性.另外，通過改變算法的搜索方向也可提高算法的收斂速率. 下面介紹兩種從不同角度出發(fā)改進搜索方向的次梯度法.

3 橢球次梯度法

經(jīng)典次梯度方法的搜索方向直接利用負次梯度.在光滑優(yōu)化算法中，最速下降法中相鄰兩方向的梯度正交，在正交方向外搜索最優(yōu)解x*效果非常差.在非光滑優(yōu)化問題中為了加快收斂，充分利用前面迭代點的次梯度信息，讓相鄰兩個搜索方向盡量正交.通過引入線性算子Hk減小gk+1中與gk共線的分量，得到在迭代點xk處的搜索方向

算法2（橢球次梯度法）

步驟0 選取初始點x0，初始矩陣H0=α0I，初始參數(shù)α0，β0，t0＞0 ，令k=0；

步驟1 計算gk∈?f(xk)，若gk=0則停止；否則轉(zhuǎn)步驟2；

步驟2 計算搜索方向dk=-Hkgk/[(gk)THkgk]1/2；

步驟3 令 xk+1=xk-tkdk，用合適的方式更新參數(shù)αk，βk，tk，按下式更新Hk

令 k:=k+1，轉(zhuǎn)步驟1.

按下列方式選取參數(shù)，會獲得較好的收斂結(jié)果.

其中，n為空間維數(shù).

定理1[12]設(shè)x*為最優(yōu)解，且滿足|x0-x*|2≤α0，則存在M＞0，q＜1，使得由算法2產(chǎn)生的迭代點列{xk}滿足

定理1說明{f(xk)} 的一個子序列R-線性收斂到f(x*).

4 變尺度次梯度法

變尺度次梯度法的主要思想與光滑優(yōu)化的變尺度方法類似，即為得到更好的收斂性，變換原坐標(biāo)空間，特別是當(dāng)次梯度方向與指向最優(yōu)解的方向幾乎垂直時，次梯度法的收斂速度很慢.即使改變搜索步長也不會有所改善，在這種情況下，可以通過變換原空間坐標(biāo)以修正次梯度方向.下面介紹一個變尺度次梯度算法，其迭代點列的更新公式為

其中，tk＞0為搜索步長，Bk∈Rn×n是可逆矩陣，其代表坐標(biāo)空間的一個線性變換.在線性變換后次梯度有一個重要的性質(zhì)：線性變換將原空間中 f 的次梯度映射成變換后空間中某個函數(shù)的次梯度.

具體地，令y=B-1x，x∈Rn，使得 y-空間為變換后的空間.設(shè)g為函數(shù) f 在點處的一個次梯度.在y-空間中，考慮如下函數(shù)F

由于 f 是凸函數(shù)，故F亦為凸函數(shù).此外，對向量BTg及任意的y∈Rn，有

因此，BTg為F在處的次梯度.利用次梯度的這個性質(zhì)，以及適當(dāng)?shù)木€性變換，可以確保迭代點xk與最優(yōu)解集之間的距離是有界的.文[11][14]提供了變換矩陣Bk的一種更新公式

其中，初始矩陣B0∈Rn×n非奇異，特別的可取B0=I.線性變換

上述(4)-(7)完成了坐標(biāo)空間的轉(zhuǎn)化，詳見[15].

5 小結(jié)

本文介紹了求解非光滑優(yōu)化問題經(jīng)典次梯度法的起源、算法基本框架及進一步的改進方法.次梯度法的主要優(yōu)點是算法結(jié)構(gòu)簡單，可求解大規(guī)模優(yōu)化問題.但由于它不能使用梯度，因此在將解決光滑優(yōu)化問題的梯度算法推廣過來時會丟失很多好的性質(zhì)，使得收斂速度較慢.次梯度法的收斂速度依賴于搜索方向的構(gòu)造及步長序列的選取.因此，如何借鑒光滑優(yōu)化方法思想，構(gòu)造收斂速度快的搜索方向，確定搜索步長序列是次梯度法研究的難點和熱點. ■

[1]Shor N Z, Kiwiel K C, Ruszcay?ski A. Minimization methods for nondifferentiable functions [J]. Springer Series in Computational Mathematics, 1985, 3.

[2]韓繼業(yè)，姚恩瑜.對既約次梯度法的改進[J].應(yīng)用數(shù)學(xué)學(xué)報，1984，7(1): 101-108.

[3]譚亞，莊建南.非光滑約束問題的既約次梯度法[J].高等學(xué)校計算數(shù)學(xué)學(xué)報，2000，22(4)：325-330.

[4]Kiwiel K C. An aggregate subgradient method for nonsmooth convex minimization[J]. Mathematical Programming, 1983, 27(3): 320-341.

[5]Kim S, Koh S. On Poljak's improved subgradient method [J]. Journal of Optimization Theory and Applications, 1988, 57(2): 355-360.

[6]Kiwiel K C. Methods of descent for nondifferentiable optimization[M]. Springer Lecture Notes in Mathematics, 1985.

[7]鄧艾東，包永強，趙力.基于能量衰減模型的轉(zhuǎn)子碰摩聲發(fā)射源次梯度投影定位方法[J].機械工程學(xué)報, 2010，46(9)：66-72.

[8]梁瑞宇，鄒采榮,王青云等.基于自適應(yīng)次梯度投影算法的壓縮感知信號重構(gòu)[J].信號處理，2010，26(12)：1883-1889.

[9]曹緒龍，同登科，王瑞和.考慮二次梯度項影響的非線性不穩(wěn)定滲流問題的精確解[J].應(yīng)用數(shù)學(xué)和力學(xué)，2004，25(1)：93-99.

[10]Cavalcante R L G, Yamada I. Multiaccess interference suppression in orthogonal spacetime block coded MIMO systems by adaptive projected subgradient method[J]. Signal Processing, IEEE Transactions on, 2008, 56(3): 1028-1042.

[11]Shor N Z. Minimization methods for nondifferentiable functions[J]. Springer series in computati-on al mathematics, 1985, 3.

[12]Nemhauser G L, Kan A H, Todd M J. Handbooks in operations research and management scienceoptimization[M], 1989.

[13]Kim S, Ahn H. Convergence of a generalized subgradient method for nondifferentiable convex optimization[J]. Mathematical Programming, 1991, 50(1-3): 75-80.

[14]Shor N Z. Nondifferentiable optimization and polynomial problems[J]. Nonconvex Optimization and Its Applications, 1998, 24.

[15]Nedic A. Subgradient methods for convex minimization, Ph.D thesis, MIT, 2002.

【責(zé)任編輯 謝文?！?/p>

Subgradient Methods for Nonsmooth Unconstrained Optimization

ZHANG Yu-Feng
(School of Mathematics and Information Science, Guangxi University, Nanning, Guangxi, 530004)

Subgradient methods are classical methods for solving nonsmooth optimization problems, especially for large-scale problems. They are widely used in many practical applications, such as economics, mechanics, engineering and optimal control. In this paper, we describe the source of classical subgradient methods, the basic framework and further improvements, which provide the basis for further study.

nonsmooth optimization; subgradient; ellipsoid methods; variable metric

O224

A

1004-4671（2015）02-0027-04

2015-03-31

廣西自然科學(xué)基金創(chuàng)新研究團隊（2014GXNSFFA118001）。

張玉鳳（1987～），女，河北河間人，廣西大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院研究生。主要研究方向：最優(yōu)化理論與算法。