修士論文

修士論文

最適化問題の近似解について

三 重 大 学 大 学 院 教 育 学 研 究 科 教 科 教 育 専 攻

209MOll

宝 来 美 緒

2012

2

10

目次

序 論

1 

第

1

5 1‑1

[ s ‑ y ]

5 1‑2 

6 

2章 問 題 の 解 法 8 

2‑1 

8  2‑2 

2‑3 

φm(Y)

1 3

第

3

1 9  

3‑1

1 9

第 4章 計 算 例 22 

4‑1

1

4‑2 

2

2 2   2 4  

5

27 

5‑1

27

5‑2 

2 7  

序論

修士の学生として三重大学で数学を学ばせていただいている中で、

2010

8henP e i ‑ P i n g

G l o b a l o p t i m i z a t i o n  f o r  t h e  sum o f  g e n e r a l i z e d  p o l y n o m i a l  

a c t i o n a lf u n c t i o n s  ( 2 0 0 6 )  [ 8 ‑ Y }

いての話を聞く機会を得た。

その際、私は数学の応用について大きな刺激を受けた。それまで私が学んだ数学は、主 に存在と一意性を証明していくというものであったからである。問題を具体的に解くとど ういう値になるか、という方法まで含んだ数学を学んだのはその時が生まれて初めてであ った。もともと理論的背景よりも、具体的例の解法に興味のある私は、彼女らの論文に今 までにない興味を覚え、何とか理解しようと努力した。

何度も彼女の元を訪ね、個人的に分からないところを教えてもらったが、私には非常に 難解であった。彼女が帰国した後もその作業は続いた。そうして勉強する中で、分かつてき たことは、彼女らの行ったことは、目的関数・制約条件ともに多変数の一般化有理式の線 形和とする大域的最適化問題の理論と具体的方法、アルゴリズムである、ということであ った。

そこでまず考えたのが、目的関数・制約条件の中にあらわれる線形和をもっと拡張でき ないか、ということで、あった。現実社会の中で、私が学部で学んだ経済学においては、線 形な関数が出るということはほとんどなく、関数というのは一回微分が正、つまり単調増 加、二回微分が負、つまり凸性という

INADA

ほとんどだからである

( c f . [ C ‑ N . l ] ， [ C‑N.2 ] ， [ C . N . 3 ] )

また、工学等を調べても、そのようなタイプの問題が多い。例えば工学の問題だが

問題:下図のような

2

2W

(最適化パラメーター

: X 1 ， X2 ，  X 3 '   s) 

[パイプ断面]

直径

Xl

2 π p J x 4 f x d 2 S 2 + x 4 i x 4 2 x 4 ;  

p :

2W 

制糊約条耕イ件牛(仇

b

ν 1 1 l

' b b

2 2

トラスの高さ制限

x

3

b 1

‑b 2

O

ル2

重みによるトラスの変形を防ぐ条件

w

. f S πxi ‑ b 3 x

X3

高さ

X3 

[  : パ 一 一 ^W(S2  条 ⁺  件 XD2 ‑b4XIX3(xf  +  xD

X l  ~ 0 ，  X2 

0 ，  X3 

0 

のような問題はそのタイプである。この場合の単調増加かっ凸な関数とは

J

また

( X Z ) Z   .  ' ‑̲  { X 1

( X Z ) Z + X 3¥ ' "  

i n   _./~1

_tx~r

咋{ー?でー)

^ 2   ^ 1 、 ^ 1

2 " 

主 主

_{ /  _{3 X 1 ‑ ( X Z ) 2 + X 3}

_{¥ 2}  

S u b j e c t  

e X 2

e  X 1  

、 "1'

" 2 / 

らも、同様の問題である。この場合の関数とは

J

l o gや exp

そこで、彼女らの論文の目的関数・制約条件の中の線形和を

INADA

そのことがより彼女らの論文を理解することにつながるのではなし、かと思った。

拡張後の非線形問題形式は以下のものとなる。

h j ， _{hk f}

exp

︑

1/

ω 一 ∞

b由a〆

'e

aE︑

LH 

4A 

P‑ F 

V山

一 一

︑_{. E} ノ

x 

rE

m  n 

ω 

s u b j e c t  t o   g k

= 1 ， … ， P ， j=1 ，

，

， k=1 ， … ， M )  

ここで

. a   . . . b   . . b  

aj(X)4310EHEditi

bj(X):=Z2102HLxfi 勺 kj(X):=Z2102JL

i t t

dMX):=zEipiltH

Jiti 帆

( X )

^{( X )} >  0 ，  d k j ( x ) >  0 

以下の条件を付ける。

{ h j ( Y j ) } '  

00=  1 … め { h j ( Y j ) } ' ^く o

1 ，  . . .  

{ h k j ( Y k f ) } '  

0 

^{= 1 ， . . . ，} Kk)  { h k f ( Y k j ) } ' ^く o

= 1 ，  . . . ， 九 )

{ h j  

e x p ( z j ) } "  

0

h j

e X P ( z j ) } " ^く O

{ hk j  

e x p ( z k f ) } "  

0

hk j

exp(zkD

O

これらの問題の大域的最適解を

Shen

1. 

a j ( x )

b j  ( x )

C k f ( X )

d k f ( X )

2 .

3 .

結果、

Shen

Shen

e x p

本論文では、目的関数、制約条件

l

h j

h

Shen

具体的計算のためのアルゴリズムは

Shen

その概略を以下に記す。

①目的関数を定義域内で上で記したように、下で抑える線形な関数で線形化する。

②線形化した関数の最小値を求める。

③②で求めた最小値の

^E

④ 目 的 関 数 が ③ の

^E

2

⑤ ④ の 最 小 値 の ε近傍をとる。目的関数が、

E

E

ε

ただ残念なことに現在の私には、実際にこのアルゴリズムに従いプログラムを組み、コン ピューターに実行させるだけの力がない。そのため、手計算で計算機を用いて実行できる 範囲で、この方法でどのように解が近似されていくかの例をつけた。実際のプログラムを 組んだ、多変数のあらわれる工学や経済学でのこの修士論文の適用できる具体的例での計 算は修士後の課題としたい。

最後に、歴史的に目的関数、^r 制約関数がともに非凸な関数による非線形最適化問題に対 する解法については、現在、いくつかの解法が提案されている。比較的汎用なものとして

「遺伝的アルゴ^Pリズムjがある。しかし、この方法は、条件によっては局所的最適解しか 求められない、ということが指摘されている。今のところ提案されている解法は、関数の 形、条件等によって解けたり、解けなかったりする、というのが現状であることを付け加

えておく。

本修士論文を作成するに当たり、専門性に欠け、また出来の悪い私を親身にご指導下さ った数学教室の教官方、事務の方には、言葉で言い尽くせないほどのお世話をおかけした。

例の構成につきご指摘を下さった露峰教授、アルゴリズムの理解につき、私のとんちん かんな質問にも丁寧なご指導を下さった谷口教授には感謝しでもしきれないものである。

また、数学全般にわたり、厳しくご指導下さった蟹江教授、数学教育につき、暖かくご 指導下さった中西、田中両教授に深く感謝したい

最後に、このような私をいつも支え続けてくれた家族と友人に心より感謝する。

第1章目的関数・制約条件の中にあらわれる線形和の 関数和への拡張

1‑1  論 文

[ S ‑ y ]

Shen

IR1.

^N

X:={Xε Jm.

N 

0

2

N}

本修士論文では、指数が負も含む実数の多項式の和を簡単のために一般化有理式と呼ぶ。

aj(x)

， 

，

ai(X):=Z2102HLX72i，bj(X):=Z21休日立14i

gk(X):=231Fit日立141(j=1p

，

，

こ こ で

γ

b

0 )  

R

0 )

>  0

>  0 

さらに

X

ω(X):=Lf=l Cjお い 数 定 数 j= 1， ...， 

p )  

$  0

Xg:={XεX I gk(X)壬

o

M)} 

そのとき、問題は以下のものである。

問題(p) X

g

ω ( X )

とする。

ここで大域的とは、局所的に最小値になるというのではなく、 X

g

O

2

[ S . y ]

E

あたえれば、すべてのタイプの問題にアルゴ、リズムを適応できるところである。

拡張後の問題

1‑2 

上の問題の非線形大域的最適化問題の目的関数・制約関数は一般化有利関数の線形和で あるが、それらを一般化有利関数とある条件を満たす合成したものの線形和に拡張する。

そこで、以下で考える問題は次である。

X

^N

x={Xε IRl.NIO<Xi壬

Xi

X ;

2

N}

aj (x)， bj(x)， Ckj(X)， dkj(x)も同様に一般化有理関数とする。

. . . . . a   ̲ . a  

ai(x):=Z21F品目立1X7iti，bj(x):22LoanLditi，cki(X):2221FEjtH立1xpiti，

Auba 

x  y‑

噌A

N‑ P  HH

+  

‑  

d

︐

n p  

' z '

噌A

d k z  

nabt 

v ム

一 一

︑ ︐

Jx 

rz

M町 E︑

J U

  ( j  

γ，寸， T~j' T~εN ^， sjt， ß~， ß~jt， ß~jt ^{:実数定数(#O)，yEi，yR}パEiti，ytiti:実数定数の指数

( = t = 0 )  

今、 aj(x)，bj (X)， Ckj(X)， dkj(x)は閉領域

X

とする。

最小値、最大値が存在する。その最小値、最大値を aj'可， bj， bj， Ckj， Ckj' dkj， dkf  これらは条件より正となる。

となる。

を与えその上で aj壬aj(X) S; aj' bjぎbj(X) 

s ;  

， 

s ;  

三高，

s ;  

( i i ) ^， e a

hj (Y，  hJ) kj(Ykj): lRl.→lRl. 

( j

P 

P 

M)

> 

( j  

…

^{く o}

⁺ 

^，

{hkj(YkJ)}' > ⁰ 

a 

a 

であり、かっ

( h g E

^{l o g Z )}

{hj ⁰ exp(有)}"> 0または{hj⁰ exp(有)}"< 0  {hkj ⁰ exp(zkj)}" 

> 

とする。

目的関数を

州):宅

条件関数を

(dkj(X

^r 

g k ( X )   : =  

， ; ¥  

k f  

= 

，  ， . "  

= 

，  . . "  

そこで

g k ( X )

0

X

X h

g k ( X )

X

h  : =   { X l g k ( X )

= 

， … ，

問題(PO) i  XεXh において し

minω(X)

再び言うと、

S h e n

l S ' Y ]

J

( P ω

このように拡張することで

S h e n

X1

e l ￥ 守 千 子

2

3

h

X1

1‑

x

Xz  X1  .  ¥  X1  +4X2  /  ¥  X1  ‑X2  / 

S h e n

2

以下ではε近似解の解法を記述する。 ε近似解とは値を εで近似する解である。最適値 をとる独立変数を

ε

2‑1 

ここでは後に行う関数の線形化への前段階として、問題(PO)の同等な問題(Pl)への変換に ついて記す。

前段階としてIR

^N

^N

1R2P+2L~=1 恥上の問題(Pl)へ変換する。

次元が拡張されることに注意する。

ここで、

(PO)はIR

^N

^N

1R2P+2L~=1 向上の問題となる。

仰 )(ヱヰ1hj(32)) の aj(X)， bj (x)の代わりに変数Ij，mjと置き換える。それをψ(n，DDlI)と 書く。

V 山 : =

酬 の:=Z21hi(ミ)^{(j  = 1， .，.，} 

^T 

1R2P+2L~=1 的内の区間 H をaj(x)，^{bj(x)， Ckj(X)， dkj(x)}の最小値・最大値を用いて次で定義する。

H:={(n， DDlI，  $ ，tt)ε 1R2P+2L~=1 的 laj 三 lig 可，bj^三mj

豆 町

Ckj S;旬壬Ckj，dkj壬t_同壬dkj

( j

以下ではこれがn，DDlI，$， ttの定義域となる。次に

XxH

ZH := {(x， n， DDlI，  $  tt)εXxHI ， gk(S， tt) S; 0 (k=l，…，M)  I

j

  ‑aj(x)壬O，bj(x)一mj壬

o ( j

S同ーCkj(X)S; O，dkj(x)ーtkjS 0 (j=l，…，Kk ' k = 1， ...，  M)  aj(x)ーlj三0，mj ‑bj(x)壬

o ( j

Ckj(X)ーSkjS; 0， tkj ‑dkj(x)壬

o

そこで、 ZH上の次の問題(Pl)を考える。

るめ求を

︑ ︐

︐ て m ︑ uvft お ψ

n

h m  

﹁l

Il _﹂

唱・&

pi  

題

同司S: 日

1

そのとき

( P O )

1 )

定理

1 X上の問題( P ω

XxH

P l )

(証明) (P

O )

l j   : =  a j (

mj: =  bj (

k f  : =  C k j (

t I q   ^{: =}  dk f(

︑ ︑ ︐ ︐ ︐ ノ

J町 一

q

i

︑ ︑

h H

4A 

P‑ F 

V ︐  

一 一

︑ ︑

E﹄︐/

依 一 ' w

b‑ a 

/ z e a

‑

hH 

4i 

p‑ F 

で ん

Lf_同!¥ 

_{hk k} i _f   (割判明

Pkf ・ )

(Pl)の最適解を (X#， n#， mm#， s#，~#)とすると、制約条件より

j=l

b j ( x # )  

mf  O

^μaj(x#)

^O

^{b j ( x # ) : $mf}

f = l

k=

0

^{S k f #: $   C k f ( X # ) ' O}

^{f ( X # ): $  t k f #}  

j=K+l

0<  a j ( 山 . l r ^O く れ ^{b j ( x # )}

j=K k 

k= 

0 く C k j ( X # ): $  S k f #

O く t k f #: $  d k f ( X # )  

く 1 _{S k} 4 _{i #  ‑}

c k i ( 克 )

{ h j ( Y j ) } '  

0 

= 

… め { h j ( Y j ) } ' く OU = 

{ h k f ( Y k D } '   >  ⁰ 

=  1

){ h k j ( Y k j ) } ' く o

=  1

( b j ( x # ) ¥  ̲ ̲ .  

{m

( b j ( x # ) ¥̲ ̲ .  

{mf¥ 

j

h j

^{h j} ザ)ゆえ ^l

ZL1hj(Z37)41hjm ( d k i ( X # )

^{( t k i # ¥}

j  = 

( k  = 

f

^{: $  hk f}  

比 zhM25;)gZ21h

^O

( P O )

ヰ^lhj(鴇)三ヰ^lhj(招)

立1州 = 立lhj(鴇)壬ヰ^lhj_(鴇)~界lhj(手)

① 出w

''

'a

E

︑

hu 

︑

p‑ F 

︿ 一

︑

lf

白川

LH 

唱A

P‑ P 

V ム

ゆえに

( P O )

Ij  := aj(xつ，m;:= bj(x*)  Ski := Cki(ピ)， tki  := dki(Xっ

とすると

lj  ‑aj(xワgo，bj(x*)^』 m;goG=I，…，K) sh‑ckj(

ピ)

O

0 

~ 0

1

k=l

M

gk(X*) = 

Lf~l

ゆえに(X*，H*， mm*， s*， tt*)は(Pl)の条件をみたす。

(X#， n#， mm#， s#，が)は(Pl)の最適解で、あるので

L f = l

①，②より

︑ ︐ ︐ ︐ /

J町 一

qf

'E

E

︑

︑

hH 

4i 

p' F 

T 

一 一

︑ ︑

EE

m J︐a

J I ‑ 一 ザ

‑

LH 

噌A

P

v l H   ・ 戸

ゆえに

( P O )

l )

(証明終)

独立変数の指数関数での置き換え

2‑2 

次に一般化有理式の各項を線形な関数にするために、変数を指数関数で書き直す。

(Pl)の目的関数、制約条件の変数、 x内，ntj， ski' tkiO = 1，…，Pf = 1，…，  P k = 1，…，M)は正で あることより、

^Xj

Yi := In Xj ， YN+j := ln lj  ， YN+P+j := ln mj ， 

YN+2P+r~二1Pn+i:zlnskj ， YN+2P+ZEL1 的+r~二ÌPn+í

0 

IRN+2P+2r~=1 許可 1nxi:$Yi:$ln 王i ，

ln aj壬YN+j:$ln

有 ，

YN+2P+r~二IPdiglnEE ，

ln 恒三 YN+2叫L 恥+r~二ip刊 :$lndkf

IRN X H上の一般化有理式の各項はIRNX IRZP+

z

t t )

ー

bj(x)、S対一 Ckf(X)C阿(X)一旬、 dki(X)一旬、 tki‑d阿(X)は、以下のように関数と exp(y)の合 成関数の和で表すことができる。

Lf=l哨

Z21hd)=221 いxp 仇+2叫lPk+r~二ÌPn+í^{‑ YN+ZP+出 Pn+i)}

l j

  ‑aj(x) = e的 N+j)‑22101叫 (Lf!，品川

(aj(x)

ー

L~!1

片付)ーmi=Z21PRexp(ZE1YRω 

T~ 一一

(町一 bj(x)= exp(YN+P+j) ‑Lム伊良exp(L立1Y~iYi)

Skj ‑Ckj(X) = 叫(YN+Z叫 E二lM)‑22102

円

(Ckj(X)‑hj=Z21FLte叫Lfと1Y品川

dki(X)

ー

一叫(恥叫巴

/、 T~，一

(tkf ‑dki(X) = exp (YN+2P+r~1 叫r~二ip刊)-Lよ ß~Jtexp(Lf!，1 Y~iYi) ⁾ 

ここで、 hj (Yj)

， 

ψmt(x): IR

→

， 

+ 

+ 

< P m t ' ( x )   >  0

< P らt ( x )

0 

{ψmt 

e x p ( y ) } "  

{ψmt 

e x p ( y ) } " く

ψ(n， mm)，

g k ( $

t t )

  ‑a j I j ( x )

a j

‑mj

m j  ‑bj  ( x )

S

C k i ( X )

C k i ( X )  ‑S k i 、 d

( X )

t k f、 t k j‑d

( X )

zhhto

(zrMZL 許 k λ m t i Y i )( λ m t i :

< P m t  

e x p ( y )

f m t ( y )

φm 匂 ):=274fmt(zrMZL9kλmtiYi)

φ 。 ( y )

φm(y)(m = 1

2

M)

g k ( $

t t )

φm(y)(m =  M  +  1

M +P)

I j‑a j  ( x )

a j ( x )‑

φm(y)(m = M  +  P+  1

M +  2 P )

bj ( x ) ー mj

m j‑b j ( x )

φm(y)(m=M+2P+1

M+2P+ZLPK)

S k j‑c k f ( x )

C k i ( X )‑S k j

φm(y)(m=M+2P+L

lPk+1

M+2P+2ZE19k)

d k j ( x ) ー t k f

t k f  ‑dk f(

( P

φ 。 ( y )

条件関数は

φm(y)(m = 1

M+2P+2ztL1PK) 

そこで

n~:= { y  

nOIφm(y)  _~ 0  (m = 1

2

M  +  2P +  2  _{L~=l 許吟}}

とすると

( P l )

( P 2 )

るめ

ぺ 求 レ を お け

?﹂

ιl

tw

pu

自

U時φε・

m y m  

﹁i ll lL

ウh

σ 

31J 

日付什

次に

( P 2 )

φm(y)

S h e n

e x p

e x p

証明のあらすじはほぼ

S h e n

2‑3  各

の線形化について

問題(

P 2 )

M+2P+2ztL19k)

= 0

M+2P+22LP

2 )

)

z

fmorMZLPKMiYi)

j= 1，…， N j = 1，…，

P 

⁼ 

Y i  := 1 n x i   ， Y i   : =  l n

Y N + j  := l n  a j   ，苅苫:= l n a j  

YN+2P+L~二iPn+j:=lnfE'YN+2P+法二~ P

l  : =  l n  C k i  

^{:= l n  dk i}  

YN+2P+L巴1 肱+L~二1Pn+j:=lndkj とする。

。 ^{q c} 

^O 

^{q ロ {yεIR N+2 P +2}

^{= l  P k  I Y I}

^{Y i}

( i   = 1ι..N+2P+22tL19k)} 

n q  ̲ 

N+2P+2L

= 1  P k   Et :=Zi=1KZ1λmtiYi 

。

^q.̲ 

P k

ニ

EL‑‑Zi=1minpmtifAmtif}

言守 Ç'f N+2P+2L~ 手

k̲ ̲  ̲ ̲ ̲   r ' ¥  

出

:=Zi=1Mmax{λmtiY7

mtiyn

(m = 0

1

2

M +  2P +  2L~=1Pk ， t  = 1

Tm 

( f m t ' ( y )  

⁰

m t ' ( y )

0 )かっ ( f m t " ( y )  

0またはf m t " ( y )

0 

ら t (

よ っ て [ 盟 ， 司 に お し 叫

t (

一次関数F出 (y~~)， Hg~(y~~) が存在する。

F~~ ~

_mt 

H . . mq  . . . i  

Y 

トlb争乱削m

E

'u u'

一‑一

T i t i l ‑

‑

6

・02・

: i

l i

‑ ‑

t v

a

f

mt  i 

Y 

:・

::

官

Y

(膏)‑^f

^mt 

FS(市):= 否ーな? (叫‑盟)+ 

f m t (

とする。

らt(Y~~)は国，否~で連続、(盟，否)で微分可能であるので

ω:)=fm電ずとなるc~i

^{E  (岱翠)が存在する。}

( f m t " ( y )  

0

f m t " ( y ) <  0 

川 市 ) は [ 盟 問 で 単 調 増 加 ま た は 単 調 減 少 で あ る の で

とする。

逆関数、 fmf1(Y 出)が存在する。よって、

~nq ^{̲  c  ' ‑ 1  ( f m t (}

^{) ‑ f m t}

' ‑ m t

t ¥ 

同

^{) ‑ f m t}

出

^(Y2?):=

^Y

^{( Y 2 ?}

^c

^{+  f m t ( c}

( f m t " ( y )  

^{0 )}  

( f m t " ( y ) く 0 )

(出 (Y~n (Y~~):=

^{ 

lF出 (Y~~)

とすると

fmt(Y~~)三 L22(YS:)

V ' 1

^q 

φ m( ' 1 )  =  r i : ' l   ^{f m t   ( ' 1 )  ; ; : : :}  

そこで次の線形化された大域的最適化問題を考える。

L~q(y)

^{: =}