凸関数の方向微分可能性について(最適化の数理とその応用)

凸関数の方向微分可能性について

富山大学経済学部経営学科

白石俊輔

Abstract:凸関数の方向微分可能性は、通常その微分商(dk 甑 1quotient) $tarrow[f(x+\phi-flx)yt$

の単調性によって説明される。 ここでは、凸関数を max 型関数として捉えることによって、 今一度

その方向微分可能性について考察することを試みる。

1.

準備

:

$f:\mathbb{R}^{n_{arrow(-\infty,+\infty]}}$

_{は下半連続な真凸関数で、}

int

(dom_$f$) $\neq\emptyset$ とする。 微

分不可能計画問題では、 関数が微分不可能な点 $X$

においても方向微分:

$f’(xfl)= \lim_{t}\downarrow 01\lambda x+u)-J\langle x)]/t$_,

が任意の方向

$d$

に関して存在する事を前提とする事が多い。 凸関数は

int

(dom$f$)

上でこの性質を持つ。

ここでは、

凸関数を

$\max$型関数として捉えることによって,

今一度方向微分可能性について考察することを試みる。

そこで次のような

$R^{n_{x}}R$

の集合を用意する。

$L(f)$ $:=\{(\alpha,\beta)\in \mathbb{R}^{n_{x}}\mathbb{R}|<\alpha,z>+\beta\leq J(z), \forall z\in \mathbb{R}^{n}\}$

.

この時次の定理が成立する。

Theorem

1.

(Rockafellar[25]

Theorem

12.1)

$f(x)= \sup\{<\alpha,x>+\beta|(\alpha,\beta)\in L(f)\}$

.

(1)

即ち、

凸関数は一次関数の max 型関数として表わされる。

2.

方向微分可能性:

$\max$

型関数の微分可能性定理として、 最も広く知られている

のは次の定理であろう。

Theorem

2.

(Danskin [81

Chap.III Theorem

1) 連続関数 $\varphi:\mathbb{R}^{n_{x}}Tarrow \mathbb{R}$ に対し新たに

関数 $\Phi;\mathbb{R}^{n_{arrow(-\infty,+\infty]}}$ _{と解集合写像} $M:\mathbb{R}^{n}arrow T$ _{を次式で定める}

:

$\Phi(x)=\sup\{\varphi(x,t)|_{t}\in T\}$,

今もし

$\mathbb{R}^{m}\supset T$ _{がコンパク トで、} $\nabla_{X}\varphi(x,t)$ が存在し、

しかも両変数に関して連続

であれば、$\Phi$

は任意の方向に方向微分可能であり次の式が成立する

:

$\Phi’(x4)=\max\{<\nabla_{X}\varphi(x,t),d>|_{t}\in M(x)\}$

.

この公式を

(1)

に直裁適用しようとすると一箇所困難が生じる。 それは, 定理 2 の$T$ にあたる $L(P$

がコンパクトではない事にある。

併し、 定理

2

において$T$

自身のコン

パクト性は実は本質的ではなく、

$M$

に適当な有界性があればよい。

Theorem

2’.

(Auslender[3]

Chap.IV

Theorem

1.7) 定理

2

において $T$

は必ずしもコン

パクトではないとする。

その代わり、

集合値関数

$M$_が$X$の近傍で (i) 空ではなく、 (ii)

一様有界であるとする。

この時次式が成立する

:

$\Phi’(x;d)=\sup\{<\nabla_{X}\varphi(x,t),d>|_{t}\in M(x)\}$

.

こちらの定理を

(1)

に適用する事によって、

凸関数の方向微分可能性を帰結する。

(1)で $M(x)$ にあたる集合は

:

$M_{J}(x);=\{(\alpha,\beta)\in L(D|<a,x>+\beta=f(x)\}$,

となる。 この $M_{J}(x)$ について(i) は $(x,J(x))$ と $\varphi if$

との分離定理によって示され

る。 (u)

を示すために

$\epsilon>0$

を用いて聯

\Leftarrow )

を膨らました

(

有界

)

集合を定義する

:

$M_{f)}^{\epsilon_{(x):=\{(a,\beta)\in L(f1<a,x>+\beta\geq f(x)-\in\}}}$

.

Lemma.

$x\in int$(dom$f$) に対し $x$ の近傍 $U$ があって、 適当な $\epsilon>0$ をとれば

:

$M_{f^{\epsilon}}(x) \supset\bigcup_{y\in U^{M}\oint \mathcal{Y})}$ (2)

が成立する。 従$’\supset$て

$M \oint x$) は (i)

を満たす。

以上の結果を併せる事によって凸関数の方向微分可能性を得る。

Remark:

$M_{J}(x)$ と $M_{f^{\epsilon}}(x)$

の第一成分への射影を考えると、

各々劣微分畝

x)

およ

び $\epsilon$- 劣微分 $\partial J(x)$

になることが容易に確かめられる。

ここで:

$\partial_{6}f(x)=\{a\in \mathbb{R}^{n}|<a,z-x>\leq J(z)-j(x)+\epsilon, \forall z\epsilon \mathbb{R}^{n}\}$

.

従って (2)

の表わす関係式は

:

$\partial_{6}f(x)\supset\bigcup_{y\epsilon U}\partial fiy)$

となるが、

これは微分不可能凸最小化アルゴリズムのひとつである、

バンドル法

の基礎となる関係式である。

(LemaI$\propto$化 m1[20],Zowe[29])

3.

二階の方向微分:

ここでは、二階の$D\ddot{m}$

の方向微分について考察する

:

$r(x \beta)=\lim_{t}\downarrow 0^{[f(x+d\cdot\beta)-f’(x;d)yr}$ (3)

前述註により、

$f’(xfl)= \max\{<\alpha d>|\alpha\in\partial\lambda x)\}$ となることが分かる。 それゆえ、 二階の $D^{\cdot}$

の方向微分を調べる際も、

_$\max$型関数 X\rightarrow f\sim 幼

の微分可能性を考察する事になる。

但し今回は制約集合がパラメトリッ

クな形であることに注意する。

この関数の連続性から調べよう。

勿論この関数は

連続ではないのだが、

畝x)

の単調性によって次のような連続性は成り立つ。

Proposition.

$1\dot{r}_{t}\downarrow_{0}f’(x+dd)=f’(x\beta)$

.

残念ながら、 凸関数は一般には二階方向微分可能でないことは次の例からも分か

る。 $f(x)=|_{X}|^{r}$_,

_$1<r<2$

.

二階の \supset 蚕方向微分可能性が欠落するのはパラメトリックな問題:

maximize

$<\alpha,d>$

$xt$

.

$f(x)$ _十戸(\alpha )- $<\alpha x>\leq 0$

.

(4)

カ ‘.

凸計画問題ではあるけれども、

Slater

条件のような正則性条件が成立しないこ

とに起因している。

研は

$f$ の共役関数)

この難点を解決するためには、

$\partial_{6}f(x)$ に対

応するいま一つの$\max$型関数$Xarrow f_{\epsilon’}(x$紛 $= \max\{<\alpha,d>|\alpha\in\partial_{6}f(x)\}$ を用いればよ

$\ovalbox{\tt\small REJECT}$

.

$<\alpha,d>$

$s.t$

.

J(X)

_{十戸 (\alpha )--} $<\alpha x>\leq\epsilon$

.

Theorem

3.(Lemar\’echal&Nurminsk\"u [21],

Auslender

[4]) 関数$Xarrow f_{\epsilon’}(x$

幼は常に次

の形で方向微分が可能である。

$f_{\epsilon’’}(x\beta)=1\dot{m}_{t}\downarrow 0^{[f_{\epsilon’}(x+d;d)-f_{\epsilon’}(x;d)]/t}$

この $f_{\epsilon}(x$

切が我々が本来知りたかった

(3)

と緊密な連絡があることも分かってい

6

$0$ (Shiraishi [281)

References

[1] A.D. Alexandrov (1939),“Theexistencealmost$ever\gamma$wheoe of second differential ofa

convex

fUnction

and

some

associatedpropertiesof

convex

surfaces,”(in Russian)UcenyeZapiskiLeningr.Gos.Univ.Ser.

Math. 37,3-35.

[2] V.I. Amol’d (1992),Catastrophe theory. Third,revised andexpanded edition.(Springer,BerlinHeidelberg

NewYork)

[3] A. Auslender(1976),optimization.M\’ethdesnum\’enque (Masson, Paris)

[4] –(1982),“On thedifferentialpropertiesof the support function of the$\epsilon-subdiff\sigma ential$ofa

convex

fnction,“MathematicalProgramming24,_257-268.

[5] H.Busemann(1958),Convex

_sulfaces.

$\sigma nt\propto science$,NewYork)

[6] R.Cominettiand R.Correa (1990),“A$geneIu izd$second-orderderivativeinnonsmoothoptimization,“

SIAM J. Control andoptimization28,$789-8\infty$

.

[7] J.P.Crouzeix(1977),“Arelationship between the second derivative ofa

convex

function and ofits

conjugate,MathematicalProgramming 13,_364-365

[8] J.M.Danskin (1967),$\Pi oe$theory

of

${\rm Max}-{\rm Min}_{\sim}$(Springer,Berlin Heidelberg NewYolk)

[9] V.F. Dem’yanovandA.B.Pevnyi (1974),“Expansion with respecttoaparameter of theextremum

values ofgameproblems,” U.S.S.R.Computational Math. andmath.phys. 14,33-45.

[10] N.Furukawa (1983), $Opt\dot{u}$nalityconditionsinnondifferentiable$pro\ovalbox{\tt\small REJECT} g$and their applicationsto

bestapproximations,“ AppliOd Math.

&optimization

9,337-371.

[11] R.E. Greene and K. Shiohama (1981),”Convexfunctionsoncomplete noncompact manuifolds:

Topologicalstructure,“Invent.math. 63, 129-157.

[12] –and–(1981),“Convexfimctionsoncomplete noncompact manuifolds: Differentiable

soeucture,” Am.scient.

\’Ec.

Norm. Sup.

4e

s\’ene 14,357-367.

[13] J.-B.$H\ddot{m}aH$-Urruty (1986),“Anewset-valued second order derivative forconvexfllnctions,” in:J.-B. $H\ddot{m}ffl$-Urrutyed.,Mathematics foroptimization.(Elsevier), 157-182.

[14]

_–and

A.Seeger (1989),“Thesecond-ordersubdifferential and the Dupin indicatrices of a

non-differentiable

convex

function,”Proc. LondonMath.Soc.58,351-365.

[15] W.W.Hogan (1973),*Pointto setmaps in\ddagger nathematical_{programming,“ SIAM Review} 15,591-603.

[17] H.Kawasaki (1988),“The

upper

and lower secondorder directional derivativesofa sup-typefunction,” MathematicalProgranming41,327-339.

[18] –(1992),“Second-order necessaryandsufficientoptimalityconditionsforminimizing asup-type

function,“Applied Math.

&optimization

26, 195-220.

[19] N.Kinugawa (1992),“Anoteofsecond-order$diff\varpi ntiabihty$andboundednoesofgeneralizedHe\infty a*

(in Japanese)MasterThesis,WasedaUniversity.

[20] C.$\ m’\infty M$ _(1989), ”Nondifferentiable optimization,” in:G.LNemhauseretaled.,Handbooks in

OR&MS, $Vol1$(Elsevier),_529-572.

[21]

_–and

E.Nurminskii(1980),“Sur ladiff\’eIentiabilit\’edelafonction d’appuidu$sous- diff6r\infty tial$

approche,“ Comptes Rendusdel’Acade’miedessciences290,S\’erie$A,$$855-858$

.

[22] _{F. Mignot} (1976), “Contr\^oledansles$i’n\alpha_{i^{u}}a\ddagger ions$vanationnelles elliptiques,” J. Functional Analysis

22,_130-185

[23] M.Moussaoui and A. Seeger (1992),”Sensitivityanalysi$s$ofoptimalvaluefimctions of

convex

parumetric

programs

withpossiblyempty solutionsets,“Repnint.University ofAvignon.

[$24J$ R.R. Phelps (1989), Convexfunctions,monotone operatorsanddifferentiability. (Springer)

[25] R.T.Rockafellar (1970),Convex Analysis. (PrincetonUniversityPress, Rinceton)

[26] A.Seeger (1988),“Second order$di\varpi tional$derivativein parametric optimmization problems,“Math.

O.R. 13, 124-139.

[27] –(1992),”Secondderivatives ofa

convex

functionandofitsLegendre-Fencheltiansformate,“

SIAM J.optimization2,405424.

[28] S.Shraishi (1992)“OnconnectionsbetweenapproximaZesecond-order$d\dot{u}\infty tional$derivative and

second-orderDiniderivative for

convex

functions,”to

appear

inMathematicalProgranmiing.

[29] J.Zowe(1985), “Nondiffeientiable optimization,$*in$:K.Schittkowskied.,Computational