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

劉勇進，李若男

(沈陽航空航天大學 理學院，110136)

基礎(chǔ)科學與工程

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

劉勇進，李若男

(沈陽航空航天大學 理學院，110136)

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

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

(1)

其中0≠ui∈-,+。上述定義的多面集與加權(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)是對角矩陣，且其對角線元素wi>0，i=1,2,…,n，‖·‖1表示的是l1范數(shù)，‖·‖表示的是l范數(shù)，也即，對任意的由此看出加權(quán)l(xiāng)1、l范數(shù)上圖錐就是這類多面集的特殊形式。

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

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

設H是有限維實Hilbert空間，令C是H上的閉凸集，則C的對偶錐定義為

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

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

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

s.t.y∈C。

(2)

(3)

(4)

(5)

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

定義

且對于i=1,2,…,n有

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

其中

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

(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].北京:科學出版社,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] 王英楠,修乃華.幾類非對稱矩陣錐分析 [D].北京:北京交通大學,2011.

[7] 劉梅嬌,單鋒,姜永.范數(shù)錐投影算子的計算[J].數(shù)學進展,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].沈陽航空航天大學學報,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

國家自然科學基金面上項目(項目編號：11371255);遼寧省“百千萬人才工程”項目(項目編號：遼百千萬立項[2015]51號)

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

2095-1248(2017)05-0081-05

0221.2

A

10.3969/j.issn.2095-1248.2017.05.012

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