極大值函數Clarke廣義Jacobi計算的新算法

宋林森, 高 巖

(上海理工大學 管理學院,上海 200093)

?

極大值函數Clarke廣義Jacobi計算的新算法

宋林森, 高 巖

(上海理工大學 管理學院,上海 200093)

基于計算Clarke廣義Jacobi在非光滑優化數值方法中的必要性,針對一類非光滑函數——極大值函數進行研究,通過對一不等式系統具備特定形式解所需條件的考慮,給出了計算此類函數Clarke廣義Jacobi中一個元素的新方法.數值試驗表明,與以往算法相比,該算法減小了計算量、簡單易行、容易實現.

非光滑分析; 優化; 廣義Jacobi; 極大值函數

非光滑優化是最優化理論與方法中的一個重要分支,在經濟計劃、工程設計、交通運輸及生產管理等方面都有著廣泛的應用.在非光滑優化問題中,由于目標函數或約束函數不具備連續可微的性質,傳統的基于微分概念的優化理論和方法已經不再適用.20世紀70年代,作為對連續可微函數梯度概念的推廣,Clarke針對局部Lipschitz函數首次提出了廣義梯度的概念[1],并隨之推廣產生了有限維向量值局部Lipschitz函數Clarke廣義Jacobi的定義形式.自此,以Lipschitz函數為主的非光滑分析與優化理論逐步完備并成為了一個獨立的研究方向.

目前,針對非光滑優化問題已形成許多有效的算法[2-7].然而,在非光滑優化問題和非光滑方程組的非光滑數值方法中,Clarke廣義Jacobi的計算仍是必須的子算法,它可用來保證算法是可執行的.例如,在求解非光滑方程的半光滑牛頓法中,需要計算函數在當前點Clarke廣義Jacobi中的一個元素以產生下一步迭代點;在非光滑優化約束方法中需要通過計算來搜集Clarke廣義Jacobi中的元素才能進一步獲取下降方向等.但是,在通常情況下,一般類局部Lipschitz函數的Clarke廣義Jacobi目前還無法算出,對其研究僅限于一些特殊的函數類型,如分片光滑函數[8-11]、投影函數[12]、上圖正可達函數[13]等.

考慮極大值函數

式中:x∈n;Ji為有限指標集;fij:n→為連續可微函數.

文獻[8-10]對此類函數的Clarke廣義Jacobi進行了研究.文獻[8]中提出了通過判斷不等式組是否相容來確定此類函數廣義Jacobi中一個元素的方法,但由于在實際問題中,這種算法往往需要對較多個不等式組進行判斷,計算量過大.文獻[9-10]分別對算法進行了改進并提高了計算效率.本文通過對一不等式系統具備特殊形式解所需條件的考慮,給出了向量極大值函數Clarke廣義Jacobi中一個元素的新算法及其合理性證明.數值試驗表明,與文獻[9-10]中的算法相比,本文算法的計算量更小,甚至在指標集中元素充分有限的情況下,可以通過觀察直接得出其中的一個元素,簡單易行.

1 算法及有關定理

局部Lipschitz函數f(x)=(f1(x),…,fm(x))T,其中,x∈n,fi:n→,在任意點x′處的Clarke廣義Jacobi定義為該函數在該點B微分?Bf(x′)的凸包,可記為?f(x′).其中,?Bf(x′)={limJf(xi)/xi→x′,xi?Ωf},Ωf為n中f(x)所有不可微點組成的集合[14].

現給出計算極大值函數Clarke廣義Jacobi的算法及相關定理.

首先,對于任意給定點x∈n,定義如下指標集:

(1)

顯然,上述指標集具備如下性質:

(2)

(3)

引理1中的不等式系統Lj1…jm(x)為

(4)

引理3 對于任意pi∈+且1≤pi≤n,如果為單點集或pi=n,總有

(5)

1≤l≤qi-1,qi>1

也即

1≤l≤qi-1,qi>1

現給出本文的主要結論(定理1).

這時,由于aqi<0,必存在εi>0,使得aqi<-εi.

現分兩部分證明.

首先證明不等式系統Lj1…jm(x)中第i個不等式存在解yi=(λi1,λi2,…,λin)T,其中,yi滿足下面性質:

a.λik≥0,其中,1≤k≤n;

因為

因為

結合定理1,給出計算函數f(x)在x處Clarke廣義Jacobi中一個元素算法的具體步驟:

2 數值試驗

在相同的Matlab 2010a運行環境下,現通過一個例子將本文算法與文獻[9-10]中提出的算法進行對比.為方便起見,在進行數值試驗時,將文獻[9-10]中的算法分別記為算法1和算法2,本文算法記為算法3.

例 已知

其中,x=(x1,x2,x3,x4)T

以x1=(1,0,-1,0)T為例,給出?f(x1)中一個元素的具體計算方法.

a. 通過計算fij(x)在x1處的函數值確定指標集J1(x1)={1,2,3,4},J2(x1)={1,2,3,4},J3(x1)={1,2,3,4}和J4(x1)={1,2,3,4}.計算梯度

c. 結合定理1,可知

表1給出了計算?f(x1)中1個元素時3種算法所需的基本運算次數.其中,表中“乘法”指的是算法運行中所需要的乘法運算；“比較”指的是算法運行中梯度的模及各元素坐標大小之間的對比.

表2給出了3種算法在5個不同點處計算Clarke廣義Jacobi元素所需的CPU時間,其中,x1=(1,0,-1,0)T,x2=(1,0,-1,1)T,x3=(1,0,0,-1)T,x4=(2,1,-1,0)T,x5=(2,1,0,1)T.

從表1可以看出,算法2和算法3較算法1減少了乘法運算,算法3所需“比較”次數明顯少于算法2.從表2中不同算法的CPU運行時間來看,算法3在5個不同點處的CPU運行時間較算法1和算法2都普遍減少,計算效率普遍提高.

表1 3種算法的基本運算次數

表2 不同算法在不同點處的CPU時間

3 結 論

從不等式系統Lj1…jm(x)一個確定解的形式入手,給出了下指標ji的選取方式,進而得到了極大值函數Clarke廣義Jacobi中的一個元素,與文獻[9-10]中的算法1和算法2一起擴大了極大值函數Clarke廣義Jacobi的已知范圍.但是,通過數值試驗發現,算法3較算法2的優越性僅在x1,x4,x5處相對明顯,因此,算法的高效率仍與給定點有著密不可分的關系,在一些非光滑問題的數值算法中,要選擇適當的計算Clarke廣義Jacobi的方法,才能保證整個算法的有效運行.

[1] CLARKE F H.Generalized gradients and applications[J].Transactions of the American Mathematical Society,1975,205:247-262.

[2] QI L Q,SUN J.A nonsmooth version of Newton’s method[J].Mathematical Programming,1993,58(1/2/3):353-367.

[3] GAO Y.Newton methods for solving nonsmooth equations via a new subdifferential[J].Mathematical Methods of Operations Research,2001,54(2):239-257.

[4] HINTERMüLLER M.A proximal bundle method based on approximate subgradients[J].Computational Optimization and Applications,2001,20(3):245-266.[5] SAGASTIZBAL C.Composite proximal bundle method[J].Mathematical Programming,2013,140(1):189-233.

[6] 王偉偉,高巖.凸可行問題的一種次梯度投影算法[J].上海理工大學學報,2009,31(5):422-426.

[7] 張清葉,高巖,馬良.求解非光滑優化問題的改進大洪水算法[J].上海理工大學學報,2016,38(1):43-47.[8] GAO Y,XIA Z Q.Finding a Clarke subgradient for smooth composition of max-type functions[J].Archives of Control Sciences,1994,3(3/4):181-191.

[9] GAO Y.Calculating an element of B-differential for a vector-valued maximum function[J].Numerical Functional Analysis and Optimization,2001,22(5/6):561-575.

[10] HUANG Z D,MA G C.On the computation of an element of Clarke generalized Jacobian for a vector-valued max function[J].Nonlinear Analysis:Theory,Methods & Applications,2010,72(2):998-1009.

[11] KHAN K A,BARTON P I.Evaluating an element of the Clarke generalized Jacobian of a composite piecewise differentiable function[J].ACM Transactions on Mathematical Software (TOMS),2013,39(4):1-28.

[12] KONG L,TUNCEL L,XIU N.Clarke generalized Jacobian of the projection onto symmetric cones[J].Set-Valued and Variational Analysis,2009,17(2):135-151.

[13] COLOMBO G,MARIGONDA A,WOLENSKI P R.The Clarke generalized gradient for functions whose epigraph has positive reach[J].Mathematics of Operations Research,2013,38(3):451-468.

[14] 高巖.非光滑優化[M].北京:科學出版社,2008.

(編輯:石 瑛)

New Algorithm for Calculating the Clarke Generalized Jacobi for a Maximum Function

SONG Linsen, GAO Yan

(Business School,University of Shanghai for Science and Technology,Shanghai 200093,China)

The calculation of the element of Clarke generalized Jacobi is necessary in nonsmooth optimization algorithms.By introducing a special solution of an inequality system,an algorithm for calculating the Clarke generalized Jacobi for a vector valued maximum function was proposed.Comparing with the existing algorithms,the results of numerical experiment indicate the cost of the computation with the present algorithm is less and the algorithm is easier to be implemented.

nonsmooth analysis; optimization; generalized Jacobi; maximum function

1007-6735(2016)05-0409-05

10.13255/j.cnki.jusst.2016.05.001

2015-09-30

國家自然科學基金資助項目(11171221);高等學校博士學科點專項基金資助項目(20123120110004)

宋林森(1982-),女,博士研究生.研究方向:非光滑優化理論與算法.E-mail:slinsen@163.com

高 巖(1962-),男,教授.研究方向:非光滑優化、混雜系統控制等.E-mail:gaoyan@usst.edu.cn

O 223

A