劉勇進(jìn)，李若男

(沈陽(yáng)航空航天大學(xué) 理學(xué)院，110136)

基礎(chǔ)科學(xué)與工程

一類(lèi)多面集投影算子方向?qū)?shù)的研究

劉勇進(jìn)，李若男

(沈陽(yáng)航空航天大學(xué) 理學(xué)院，110136)

首先刻畫(huà)了一類(lèi)多面集的對(duì)偶錐和極錐，進(jìn)而給出了這類(lèi)多面集上投影算子方向?qū)?shù)的具體計(jì)算方法，研究結(jié)果不僅為該類(lèi)多面集投影算子廣義次微分的刻畫(huà)提供了技術(shù)支持，也為相關(guān)優(yōu)化問(wèn)題的靈敏度分析和算法收斂性分析奠定了理論基礎(chǔ)。

投影算子；多面集；方向?qū)?shù)；對(duì)偶錐；極錐

(1)

其中0≠u(mài)i∈-,+。上述定義的多面集與加權(quán)l(xiāng)1、l范數(shù)上圖錐有著密切的聯(lián)系，其中加權(quán)l(xiāng)1范數(shù)上圖錐記為定義為

加權(quán)l(xiāng)范數(shù)上圖錐記為定義為

其中W=diag(w1,w2,…,wn)是對(duì)角矩陣，且其對(duì)角線元素wi>0，i=1,2,…,n，‖·‖1表示的是l1范數(shù)，‖·‖表示的是l范數(shù)，也即，對(duì)任意的由此看出加權(quán)l(xiāng)1、l范數(shù)上圖錐就是這類(lèi)多面集的特殊形式。

2011年，修乃華[6]等對(duì)加權(quán)l(xiāng)范數(shù)上圖錐投影算子進(jìn)行了研究，并給出其具體表達(dá)式。劉梅嬌等[7]于2013年利用閉凸錐上投影算子應(yīng)滿(mǎn)足的條件，分情況討論給出了l1范數(shù)上圖錐的計(jì)算公式。劉勇進(jìn)等[8]在2013年的文章里提出了計(jì)算在半封閉空間和盒子變量上的向量投影的快速算法，最終可以用來(lái)計(jì)算Ky-Fank范數(shù)上圖錐的投影算子。2014年，丁超等[9]在他們的文章中給出了l1、l范數(shù)上圖錐投影算子的計(jì)算方法，并且討論了其方向?qū)?shù)的具體表達(dá)形式。2015年，劉勇進(jìn)等[10]詳細(xì)研究了加權(quán)l(xiāng)1/l上圖錐投影算子的微分性質(zhì)，主要包括投影算子的方向?qū)?shù)、B次微分和Clarke廣義Jacobian矩陣等。2016年，劉勇進(jìn)等[11]又給出了一類(lèi)特殊閉凸錐，即非負(fù)卦限上投影的l1范數(shù)上圖錐，較為豐富的理論結(jié)果，著重研究了它的變分和微分性質(zhì)，詳細(xì)地描述了其對(duì)偶錐、切錐、法錐和臨界錐的表達(dá)形式，并刻畫(huà)了它的方向?qū)?shù)、B次微分和Clarke廣義Jacobian矩陣等。

記號(hào)說(shuō)明：如果I是一個(gè)集合，則|I|表示集合I的基數(shù)。若C是閉凸集，則intC表示C的內(nèi)部，bdC表示C的邊界。為方便起見(jiàn)，在有限維實(shí)Hilbert空間上，內(nèi)積均記為〈·,·〉，它誘導(dǎo)的范數(shù)記為‖·‖。

設(shè)H是有限維實(shí)Hilbert空間，令C是H上的閉凸集，則C的對(duì)偶錐定義為

C*:=y∈H:〈x,y〉≥0,?x∈C，

且有C的極錐C°:=-C*。

記ΠC(·)為閉凸錐C上的投影算子，即對(duì)任意給定的x∈H，ΠC(x)是如下凸優(yōu)化問(wèn)題的唯一最優(yōu)解：

s.t.y∈C。

(2)

(3)

(4)

(5)

引理1 假設(shè)給定(x,t)∈Rn×R和u∈Rn。令π是{1,2,…,I2}的一個(gè)排序使得

定義

且對(duì)于i=1,2,…,n有

推論1假設(shè)給定(x,t)∈Rn×R和u∈Rn，我們有以下結(jié)論：

其中

根據(jù)推論1，對(duì)給定的(x,t)∈Rn×R和u∈Rn，定義指標(biāo)集α,β和γ為

(6)

由此可得

則由(6)可得

則有

由此推得

由(6)可以推知

3 結(jié)論

[1] BONNANS J F,SHAPIRO A.Perturbation analysis of optimization problems [M].Springer,New York,2000.

[2] 張立衛(wèi),吳佳,張藝.變分分析與優(yōu)化 [M].北京:科學(xué)出版社,2013.

[3] BONNANS J F,RAMIREZ C H.Perturbation analysis of second-order cone programming problems[J].Mathematical Programming,2005,104(2):205-227.

[4] WANG Y,ZHANG L W.Properties of equation reformulation of the Karush-Kuhn-Tucker condition for nonlinear second order cone optimization problems[J].Mathematical Methods of Operations Research 2009,70(2):195-218.

[5] SUN D F.The strong second order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications[J].Mathematics of Operations Research,2006,31(4):761-766.

[6] 王英楠,修乃華.幾類(lèi)非對(duì)稱(chēng)矩陣錐分析 [D].北京:北京交通大學(xué),2011.

[7] 劉梅嬌,單鋒,姜永.范數(shù)錐投影算子的計(jì)算[J].數(shù)學(xué)進(jìn)展,2013,42(4):563-568.

[8] LIU Y J,WANG S Y,SUN J H.Finding the projection onto the projection onto the intersection of a closed half-space and a variable box[J].Operations Research Letters,2013,41(3):259-264.

[9] DING C,SUN D F,TOH K C.An introduction to a class of matrix cone programming[J].Mathematical Programming,2014,144(1-2):141-179.

[10]LIU Y J,HAN N,WANG S Y,etal.Differential properties of the metric projectors over the epigraph of the weighted and norm[J].Pacific Journal of Optimization,2015,11(4):737-749.

[11]LIU Y J,WANG L.Properties associated with the epigraph of the l1 norm function of projection onto the nonnegative orthant[J].Mathematical Methods of Operations Research,2016,84(1):205-211.

[12]韓寧,劉勇進(jìn),劉梅嬌.一類(lèi)閉凸錐上投影算子的計(jì)算[J].沈陽(yáng)航空航天大學(xué)學(xué)報(bào),2013,30(5):88-91.

[13]CLARKE,F H.Optimization and nonsmooth analysis [M].New York:John Wiley & Sons,1983.

[14]HARAUX P T.How to differentiate the projection on a convex set in Hilbert space[J].Journal of the Mathematical Society of Japan,1977,29:615-631.

[15]PANG J S.Newton′s method for B-differentiable equation[J].Mathematics of Operations Research,1990,15(1-3):149-160.

Researchonthedirectionalderivativeoftheprojectoroveraclassofpolyhedralsets

LIU Yong-jin，LI Ruo-nan

(College of Science,Shenyang Aerospace University,Shenyang 110136,China)

This paper characterizes the specific structure of the dual cone and the polar cone of a class of polyhedral sets and then presents the explicit formula of the directional derivative of the projector over this kind of polyhedral sets.The results achieved in this paper provide technical support for the characterizations of the generalized differential of the polyhedral sets,as well as lay theoretical foundations for the sensitivity analysis and the convergence analysis of methods for the related optimization problems.

projector;polyhedral sets;directional derivative;dual cone;polar cone

2017-09-08

國(guó)家自然科學(xué)基金面上項(xiàng)目(項(xiàng)目編號(hào)：11371255);遼寧省“百千萬(wàn)人才工程”項(xiàng)目(項(xiàng)目編號(hào)：遼百千萬(wàn)立項(xiàng)[2015]51號(hào))

劉勇進(jìn)(1977-)，男，江西贛州人，教授，主要研究方向：優(yōu)化理論與方法、矩陣優(yōu)化、數(shù)值計(jì)算，E-mail：yjliu@sau.edu.cn。

2095-1248(2017)05-0081-05

0221.2

A

10.3969/j.issn.2095-1248.2017.05.012

(責(zé)任編輯：劉劃 英文審校：靖可)