Sup-型関数の2次の方向微分について(非線形解析学と凸解析学の研究)

Second-order directional

derivatives of

$\sup$

-type

functions

$\mathrm{S}\mathrm{u}\mathrm{p}$

-

型関数の

2

次の方向微分について

Hidefumi Kawasaki($\mathrm{G}\mathrm{r}\mathrm{a}\mathrm{d}\mathrm{u}\mathrm{a}\mathrm{t}\mathrm{e}$ School ofMathematics, Kyushu Univ.)

川崎英文 (九州大学大学院数理学研究科)

Abstract

In this paper, we deal with the following $\mathrm{s}\mathrm{u}_{\mathrm{I}}\succ$-type function:

$S(x):= \sup_{t\in\tau}G(X(t),t)x\in X$, (1)

where $T$ is a compact metric space, $X$ is a subspace of the set of all

$n$-dimensional vector-valued continuous functions $C(T)^{n}$ equipped with

the uniform norm. We denote by $G_{x}$ and $G_{xx}$ the gradient (row) vector

and the Hesse matrix of $f$ w.r.t. $x$, respectively, and assume themto be

continuous on $R^{n}\cross T$. This $\mathrm{s}\mathrm{u}_{\mathrm{I}}\succ \mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}$ function is induced from a phase

constraint

$G(x(t), t)\leq$ $\forall_{t\in T}$

which appears in variationalproblems and optimal control problems [15].

Onthe other hand, another$\sup-$-type function has been deeply studied:

$S_{0}(x):= \sup_{t\in\tau}G(X,t)x\in R^{n}$, (2)

$\mathrm{C}\mathrm{l}\mathrm{a}\mathrm{r}\mathrm{k}\mathrm{e}[1]$, Correaand$\mathrm{S}\mathrm{e}\mathrm{e}\mathrm{g}\mathrm{e}\mathrm{r}[2]$, Danskin [3], Dem’yanov and$\mathrm{M}\mathrm{a}\mathrm{l}\mathrm{o}\mathrm{z}\mathrm{e}\mathrm{m}\mathrm{o}\mathrm{v}[4]$

Demyanovand$\mathrm{Z}\mathrm{a}\mathrm{b}\mathrm{r}\mathrm{o}\mathrm{d}\mathrm{i}\mathrm{n}[5]$,Hettich and$\mathrm{J}\mathrm{o}\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{n}[6]$, Ioffe[7], $\mathrm{K}\mathrm{a}\mathrm{w}\mathrm{a}\mathrm{s}\mathrm{a}\mathrm{k}\mathrm{i}[8][9]$

$[10][11][13],$ $\mathrm{S}\mathrm{h}\mathrm{i}\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{S}\mathrm{h}\mathrm{i}[17],$ $\mathrm{S}\mathrm{e}\mathrm{e}\mathrm{g}\ominus \mathrm{r}[16],$ $\mathrm{W}\mathrm{e}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{g}[18]$. We encounter this $\mathrm{s}\mathrm{u}_{\mathrm{I}}\succ$-type function in Tchebycheff approximation. When

$T$ dependson $x$,

the minimization problem of

_S0

$(x)$ becomes a parametric optimization

problem. To tell the truth, $S_{0}(X)$ is a special case of$S(x)$. Indeed, ifwe

take as $X\{x\in C(T)^{n}|x(t)\equiv \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{t}\mathrm{v}\mathrm{e}\mathrm{C}\mathrm{t}\mathrm{o}\mathrm{r}\in R^{n}\}$, then $S(x)$ reduces

論文の概要 次の $\mathrm{S}\mathrm{u}\mathrm{p}$ 型関数の1次と2次の方向微分について考察する。 $S(x):= \sup_{t\in\tau}G(X(t),t)x\in X$, (3) ただし $T$ はコンパクト距離空間, $X$ _は $n$次元ベクトル値連続関数全体 $C(T)^{n}$ の部分空間とする。 この Sup-型関数は変分問題や最適制御問題の相条件 $G(x(t), t)\leq$ $\forall_{t}\in T$ を考察するとき出会う。本論文では、 この相条件から包絡線がが生成さ れるかどうかを調べるために、$\sup$ 型関数 S(のの 2 次の方向微分を表す 公式を与える。 方、 従来よく研究されてきた $\mathrm{S}\mathrm{u}\mathrm{p}$ 型関数は次の関数である。 $S_{0}(X):= \sup_{t\in\tau}c(x, t)x\in R^{n}$, (4) この関数はチ\iotaビシ ir_{フ近似問題と密接に関係する。 さらに、集合}$T$ が $x$ に依存してよいとすれば、$S_{0}$(のの最小化問題はパラメトリック最適化 問題になる。S(のが

S0

$(x)$ と本質的に異なる点は、後者は $x$ と $t$ が独 立に動けるのに対し、前者は $x$ が $t$ に依存することである。 しかしなが ら、$S_{0}(X)$ は S(ののスペシャルケースと見なすこともできる。 つまり、 $X$ として $n$ 次元ベクトル値定数関数全体$\{x(t)\equiv a|a\in R^{n}\}$ をとれば よい。従って、$S(x)$ は S0(_{のの多くの性質を受け継ぐことになる。 結論} を先に述べると、相条件からも包絡線が生成される。

In the following, we denote by $T(x)$ the set of all extreme points

$G(x(\cdot), \cdot)$, that is,

$T(x):=\{t\in T ; G(x(t), t)=S(x)\}$, $x\in C(T)^{n}$.

THEOREM 1 The

_function

$S(x)$ is continuous.

THEoREM 2 The

_function

$S(x)$ is directionally

differentiable

in any

di-rection$y\in X$, a掘伽碗rectional deriva 伽 e is given 吻

Applying Theorem 2 to the$\sup$-type function induced from the one.

sidedphase constraint:

$s(t)\leq x(t)\forall_{t}$, (6)

where $s(t)$ is a given continuous function, we get the following result:

COROLLARY 1 Let $s\in C(T)$

.

Take $G(x, t):=s(t)-x$

for

any $x\in \mathrm{R}$

and $t\in T$. Then

$S’(x;y)=- \min yt\in\tau(x)(t)$.

Taking constant functions as$x(t)$ and$y(t)$ inTheorem 2, weget

Dan-skin’s formula.

COROLLARY 2 $(Danskinl\mathit{3}])$ The

function

$S_{0}(x)$ is directionally

differ-entiable in any direction $y\in R^{n}$ and its directional derivative is given

$by$

$S_{0}’(x;y)= \max\{G_{x}(X,t)y;t\in T(x)\}$

.

(7)

Next, we consider a second-order directional derivative of$S(x)$.

DEFINITION 1 The upper second-order directional derivative

_of

$S(x)$ at

$x$ in the direction$y$ is

defined

by

$\overline{s}’’(x;y)=\lim_{arrow\epsilon+}\sup_{0}\frac{S(x+\epsilon y)-^{s}(_{X)(\cdot)}-\epsilon s’x,y}{\epsilon^{2}}$ (8)

DEFINITION 2 ([9]) For any

_functions

$u,$ $v\in C(T)$ satisfying

$\{$

$u(t)\geq 0\forall_{t\in T}$,

$v(t)\geq 0$

if

$u(t)=0$, (9)

we

_define

a

_function

$E:Tarrow[-\infty, +\infty]$ by

$E(t):=\{$

$\sup\{\lim\sup\frac{v(t_{n})^{2}}{4u(t_{n})};\{t_{n}\}$

satisfies

(11)$\}$ ,

if

$t\in T_{0}$,

$0$

if

$u(t)=v(t)=0$ and $t\not\in T_{0}$,

$-\infty$ otherwise,

(10)

THEOREM 3 Let$x$ and$y$ be arbitrary

functions

in$C(T)^{n}$. Then itholds

that

$\overline{S}’’(x;y)=\max\{\frac{y(t)^{T}c_{xx}(X(t),t)y(t)}{2}+E(t)$ ; $t\in T(x;y)\}$ , (12)

where $T(x;y):=\{t\in T(x) ; S’(x;y)=G_{x}(x(t), t)y(t)\}$ _and $E(t)$ is

defined

via

_Definition

2 by taking

$u(t)=S(x)-c(X(t), t)$, $v(t)=S’(x;y)-G_{x}(X(t), t)y(t)$. ₍₁₃₎

Taking constant functions as $x(t)$ and $y(t)$ in Theorem 3, we get the

following formula due to [9].

COROLLARY 3 Let$x$ and$y$ be arbitrarypoints in$R^{n}$. Then itholds that

$\overline{S}^{\prime/}(x;y)=\max\{\frac{y^{T}G_{xx}(X,t)y}{2}+E(t)$ ; _{$t\in\tau(x;y)\}$} , (14)

where $E(t)$ is

defined

via

Definition

2 by taking

$u(t)=S(X)-c(x, t)$, $v(t)=S’(x;y)-Gx(X, t)y$ . (15)

We proved in [9] and [10] that an envelope is formed from $G(x, t)$

when $E(t)>0$ at some point $t$. Similarly, an envelope is formed from

$G(x(t), t)$ _when $E(t)>0$ at some $t$.

Example We can find an envelope even in the simplest onesided phase

constraint:

$x(t)\geq 0\forall_{t}$,

that is, $G(x, t)=-X$. Let $x(t):=t^{2},$ $T:=[-1,1]$ and $y(t):=-2t$. Then

$\phi(\epsilon)$ _$:=$ $S(X+\epsilon y)$

$=$ $\max\{-x(t)-\epsilon y(t)|t|\leq 1\}$ $=$ _{$\max_{1}\{2|t|\leq t\epsilon-t^{2}\}$} $=$ $\{$ $\epsilon^{2}$ $|\epsilon|\leq 1$ $|2\epsilon|-1$ $|\epsilon|\geq 1$

For each $t\in[-1,1]$, the function $2t\epsilon-t^{2}$ is affine w.r.t. $\epsilon$. However,

It isclear fromthedefinitionof theuppersecond-orderdirectional

deriva-tive that

$\overline{S}^{\prime/}(X;y)=\lim\sup\frac{\phi(\epsilon)-\phi(\mathrm{o})-\epsilon\phi’(0)}{\epsilon^{2}}=\inarrow+01$.

On the other hand, the functions $u(t)$ and $v(t)$ defined by (13) become

$u(t)=s(X)-G(x(t), t)=0-(-X(t))=t2$,

$v(t)=S’(x;y)-Gx(_{X(}t),$

$t)y(t)=-y(0)-(-y(t))—2t$

,

respectively. Hence

$E(t)=\{$ 1, $t=0$,

$-\infty$, $t\neq 0$.

Since $G(x, t)$ is affine w.r.t. $x$, its second partial derivative vanishes. So

the right hand side of (12) equals 1.

参考文献

[1] $\mathrm{F}.\mathrm{H}$. Clarke, ”Generalized gradients and applications”, Trans. Amer.

Math. Society., vol. 205, pp. 247-262, (1975).

[2] R. Correa and A. Seeger, ”Directional derivative of a minimax

func-tion” NonlinearAnalysis, Theory and Appl., vol. 9,pp. 13-22, (1985).

[3] $\mathrm{J}.\mathrm{M}$. Danskin, The Theory

of

Max-Min and its Applications to

[4] $\mathrm{V}.\mathrm{F}$. Dem’yanovand$\mathrm{V}.\mathrm{N}$. Malozemov, Introduction to Minimax. John

Wiley and Sons, New York, (1974).

[5] $\mathrm{V}.\mathrm{F}$. Demyanov and $\mathrm{I}.\mathrm{S}$. Zabrodin, ”Directional differentiability of a

continual maximum function of quasidifferentiable functions”, Math.

Program. Study, vol. 29, pp. 108-117, (1986).

[6] $\mathrm{R}.\mathrm{P}$. Hettich and H.Th. Jongen,

Semi-infinite

programming:

condi-tions

_of

optimality and applications in J. Stoer (ed.) Opti$\mathrm{m}iz$ation

Techniques 2. Springer, (1972).

[7] A. Ioffe, On $\mathit{8}ome$ recent developments in the theory

of

second order

optimality conditions in S. Dolezki (ed.) Optimization, Lecture Notes

in Math., Vol. 1405, pp. 55-68, Springer, New York, (1989).

[8] H. Kawasaki, ”An envelope-like effect of infinitely many inequality

constraints on second-order necessary conditions for minimization

problems” Math. Program., vol. 41, pp. 73-96, (1988).

[9] H. Kawasaki, ”The upper and lower second order directional

deriva-tives of a $\sup-$-type function” Math. Program., vol. 41, pp. 327-339,

(1988).

[10] H. Kawasaki, ”Secondordernecessaryoptimality conditions for

min-imizing a $\sup-$-type function” Math. Program., vol. 49, pp. 213-229,

(1991).

[11] H. Kawasaki, ”_{Second-ordernecessary}

and sufficient optimality

con-ditions for minimizing a$\mathrm{s}\mathrm{u}\iota\succ \mathrm{t}\mathrm{y}\mathrm{p}\mathrm{e}$ function” Appl. Math. and Optim.,

vol. 26, pp. 195-220, (1992).

[12] H. Kawasaki, ”A second-order property ofspline functions with one

free knot”, J. Approx. Theory, 78, 293-297, (1994).

[13] H. Kawasaki, ”A first-order envelope-like effect ofnonsmooth

func-tions with an application to best approximation by polygonal curves

with free knots”, in Proceedings of APORS’94 ($\mathrm{e}\mathrm{d}\mathrm{s}$. M. Fushimi and

[14] H. Kawasaki and S. Koga, ”Legendre conditions for a variational

problems with one-sided phase constraints”, to appear in J. of Oper.

Res. Soc. of Japan.

[15] S. Koga and H. Kawasaki, ”Legendre conditions for variational

prob-lemswithinequality phaseconstraints”, in Proceedings of APORS’94,

pp.484-489, (1995).

[16] Seeger A., ”Second order directional derivatives in parametric

opti-mization problems” Math. Oper. Res. vol. 13, pp. 124-139, (1988).

[17] S. Shiraishi, ”Directional differentiability of $\max$-functions and its

applications to

convex

functions”, in Proceedings of APORS’94,

pp.477-483, (1995).

[18] W. Wetterling, ”Definitheits bedingungen f\"ur relative Extrema bei

Optimierungs- und

Approximationsaufgaben”

Numer. Math., vo115,