非線形計画法

(1)

非線形計画法

条件付き最適化問題は目的関数と制約条件で示すが、この中に一つでも 1 次式でないものが含まれる問題を総称して非線形計画法いう。非線形計画問題は、多くの分野で研究されているが、複雑性により十分汎用的なものは確立されておらず、限定的なものに限り幾つかの提案がなされている。ここでは簡単な解法について紹介する。

１．制約なし極値問題

（１）単純問題の解法

１変数で表される関数z f(x)^の極値は f(x)0を解くことによって求められる。

■例：某都市施設を建設することになった。施設の規模を変えると便益Bも建設費用Cも変化する。与えられた単位規模当たりの便益と費用をもとに、便益を最大にする規模 S を求める。

（２）近似解法

複雑な関数であっても、ある値aの近傍における近似値として下式のテーラー展開によって求めることができる。a0の場合にはマクローリン展開とも呼ばれる。

3

2 ( )

! ) 3

! ( ) 2 )(

( ) ( )

( f x a

a f x

a x a f a f x

f  



 









２変数の場合のテーラー展開による近似値はどうなるだろうか。

) , (x₁ x₂ f

z  として、x₁ aht, x₂ bkt,(a,b,h,k:const.)とすれば

x z x k

h

x k z x x hk z x

h z k k x h z x x h z x k x h z x

z

dt dx x

x k h z x

z dt

dx x

x k h z x

z dt

z k d x h z x

z dt dx x

z dt dz

2

2 1

2 2 2 2 2 1

2 2

1 2 2 2

2 2

2 1

2

2 1

2 2

1 2

2 2

2 1 1

1 2 1

2 2

2 1

2 2 1 1

2 ,



 







 



 



 



 



 















 



 















 



 





 







 



 

 



 







 



 

 

 



 



 



 

となって、微分演算子も単なる変数記号のように扱うことで分かりやすく表現でき、これの高次導関数は以下のように示される。

5 ,

0 6 30

max ,

3 ,

10

30 ²



















S dS S

dZ

C B Z S C S

B

(2)



 





 ⁿ 

r

r r n

n r r n r n n

n

x x k z h dt C

z d

0 1 2

さらにz f(x₁,x₂)を、z  f(x₁ht,x₂ kt)((t))として、tをパラメータとする点

) ,

(x₁ x₂ との位置関係を示せるように再表現しておき(t) f(x₁ ht,x₂ kt)の近似値を求める。u x₁ht, v x₂ ktとすると(t) f(u,v)

v k u h

t v v t u u

t 









 



















であり、これに

v x

u v

u x

v v x

u u x





 









 

 





 



 











 







2

1 1

1

0 1

を代入すると

2

1 k x

h x

t 



 





 





 である。

このことから ⁽ ⁾( ) f(u,v) k y

h x t

m

m 

 







 



 

 となって、同様に簡単に表現される。

ここで(t)^{のマクローリン展開は}



 











 (0)

! ) 2 0 ( ) 0 ( ) (

t2

t

t であり

) , ( )

0 ( ), , ( )

0 ( ), , ( ) 0

( ₁ ₂

2

2 1

2 1 2 1

2

1 f x x

k x h x

x x x f x k

h x

x

f 



 







 



 

  



 







 



 







であるから、代入して

 ) ,

! ( ) 2 , ( )

, ( )

( ₁ ₂

2

2 1

2 2 1 2 1

2

1 f x x

k x h x

x t x x f x k

h t x x f

t 



 







 



 

 



 







 



 







tの値は任意であり、見通し良くするためt 1 とすると

 ) ,

! ( 2 ) 1 , ( )

, ( ) ,

( ₂ ₂

2

2 1

2 1 2 1

2 1 2

1 f x x

k x h x

x x x f x k

h x x f k x h x

f 



 







 



 

 



 







 



 





となる。ここで、hx₁,k x₂としてベクトル表現すると

(3)

   

^



 























 







 



 





































2 1

2 2 2

2 1

2

2 1

2 2

1 2

2 1 2

1

2 1 2

1 2

2 1

1 2!

1

x x x

f x

x f

x x

f x

x x

f x f x

x f x x x x f

t t

と

なって、 , ( ), ( )

2 2 2

2 1

2

2 1

2 2 1 2

2 1 2

1 x x H x

x f x

x f

x x

f x

f f

x f x f x

x 











































 







とおくと xx  x  x x x (x)x

! 2 ) 1

( ) ( )

( f f H

f ^t ^t と簡潔に表される。 )

(x

H は f(x)のヘッセ行列と呼ばれる。f(x)のx^o（上付きのｏはOptimizeの頭文字）の近傍では次のようになる。

















 x x x x x x x

x ( )

! 2 ) 1

( ) ( )

( ô f ô f ô ^t ^tH ô

f ) (x

f が x^o で極値（ここでは局所的最小値としよう）となるための条件は

0 ) ( ,

)

(    

f x 0 x^tH x x である。なおH(x)は、対称行列であるが、これの固有値は実数であり、例えば固有値対角行列をΛ、固有値ベクトルをC とすれば、次のようになってy_i² 0^よりλ_i 0しかないので、よってヘッセ行列H(x)^{は正定値である。}

１）ニュートン・ラプソン法 )

(x

f をx^kにおいてテーラー展開すると

となるが、右辺の近似式を０にするxを求めるべく、

これをxで偏微分して０とおく。つまり、

     

0 x x x x

x x x x

x x x x x x x

x x x

x x

























 

 



 

 



) )(

( ) ( ) )(

(

! 2 2 ) 1 ( 0

) )(

( )

! ( 2 ) 1 ( ) ( )

(

k k

k t

k k

t k k

H f

f

両辺にH^¹(x)をかけて整理するとxx^k H^¹(x)f(x^k) となる。xd^k として

k k

k x d

x ^1   とし、繰り返し計算を行って近似値としての解を求める。

ステップ０：所期点(x⁰)を決める。k 0 ステップ１：f(x^k)0であればストップ。

) )(

( )

!( 2 ) 1 ( ) ( ) ( )

( f ^k f ^k ^t ^k ^k ^tH ^k

f x  x  x xx  xx x xx

) ( 0

), (

, ,

) (

2 y x

y y x x x x

x x x

t i

i i t

t t t

t t

t

C y

λ C

C H

C C H HCC I

C C C

C HC C C HC H

H









































y

x

f(x)

X^(k+1) X^(k)

(4)

ステップ２：d^k x^k H^¹(x)f(x^k)を計算する。

ステップ３：x^k^1 x^k d^k^とする。

ステップ４： f(x^k^¹) f(x^k) 0ならストップ。k k1とし、ステップ１に戻る。

■例：z f(x)x₁⁴ x₂⁴ minをニュートン法で求めよ。但し、出発点x⁽⁰⁾ (1,1)とし、計算値の差が0.015以下になったら計算作業中止せよ。

これは式よりx^O (0,0)でminz0であることは一目瞭然であるが、近似計算により漸次z0であることがわかる。

0124 . 0 ,

0030 . 81 0

* 16 2 4

0154 . 27 0

* 8 2

27 8 27

8 ,

27 4 27

4 ) ( ) (

, 4

* 12 0 9

0 4

* 12

9 ) ( , 9

* 4 12 0

9 0

* 4 12 ) ( , 9 4 9 4 ) ( 3

078 . 9 0

* 4 2

9 4 9 4 ,

9 2 9 2 ) ( ) ( 48 0 9 48 0

9 ) (

9 0 48 9 0 48 12

0 0 ) 12

( , 27 32 27 32 4

) 4 ( 2

395 . 81 0 32

3 2 3 2

3 1 3 1 1 , 1

3 1 3 1 ) ( ) ( ,

12 0 1 12 0

1 ) (

12 0

0 12 12

0 0 ) 12

( 4 , 4 4

) 4 ( 1

2 0

) 3 ( 4 (

4 )

4 (

4 )

3 (

3 ) 2 ( ) 3 ( 1

3

2 2 2 2

1 2 2

3 4 3 4 4 )

2 (

2 ) 1 ( ) 2 ( 1

2 1

3 , 2 3 2 2 2 2 1

3 , 2 3 3 2 2 3 1 )

1 (

1 ) 0 ( ) 1 ( 1

1 1

1 , 1 2 2 2 1 2

1 , 1 3 2 3 1

2 1 ) 0 (

2 1 2

1

2 1 2

1

z z

z k

z

f H

H H

f k

z

f H H

x H x

x f x

k z

f H H

x x x

x H f

x x x

f x f f

k z k

x x x

x

x j x

x i x



 



 



 







 



 



 























 

























































 







 





























 



 



 























 































































 



 





















 



 





























































 

















































 







 



















 



 







 

















































x x x x

x x

x

x x x x

x x

x

x x

x x x x

x x

x

x x

(5)

２）最急降下法

これは探索点における勾配の負の方向を探索方向として用いるほうほうである。つまり作業実施点x^kからの探索方向として次のベクトルを用いる。

t n

k k

k

x f x

f x

f f 



 





















 ( ) ( ) ( )

) (

2 1

x x

d 

これを次のステップを繰り返して行いf(x^*)0になるまで繰り返す。

ステップ０：所期点(x⁰)を決める。k 0 ステップ１：f(x^k)0であればストップ。

ステップ２：d^k f x( ^k)とする

ステップ３： f(x^k αd^k)が最小となる値α^を求める。

これは簡単に求められないことが多く、D(α^k) f(x^k αd^k)としてD(α^k)よりα^を求める方法がある。

ステップ４：x^k^¹  x^k α^d^k^とする。k k1とし、ステップ１に戻る。

２．制約つき極値問題

（１）ラグランジュの未定乗数法

２変数x₁,x₂の間にg(x₁,x₂)0の関係があるとき、z f(x₁,x₂)の極値を考えよう。x₂

はx₁の関数であるから、zはx₁のみの関数である。ここで、g(x₁,x₂)0は陰関数であり、

両辺を微分して

2 1 2

1

1 2 1

2 1

2 2 1 1 1 1

, 0

x x x

x g

g dx dx dx

g dx dx g

dx x

g dx dx x

g dx

dg    



 



 

となって、z f(x₁,x₂)の極値なので

) 0 ( , 0 )

( 2

2 1 2 1 2

2 1 2 1

1 2 1 2 2 1 1 1 1



 







 

 



  _x

x x x x x

x x x

x g

g g f g f g f g dx f

dx dx dx x

f dx dx x

f dx

dz

である。よってzに極値を与えるx₁は ( , ) 0, 0

1 2 1 2

2

1  _x _x  _x _x 

i x x f g f g

g の根でなくてはな

らない。よって、これを求め、

1 1x

fx の符号を調べることによって極大か極小かを判定することができる。

ここで ( )

2 2 1

1 g f g λ

f_x _x  _x _x  ^{なる関係を利用して} 0, 0

2 2

1  _x1  _x  _x 

x λg f λg

f ^となり、

かつg(x₁,x₂)0の式は、(x₁,x₂,λ) f(x₁,x₂)λg(x₁,x₂) λ:const.とおいて、下式を解くのと等価である。

(6)

0 ,

0

2 1

 



 





 







λ x

x

但しλ（ラグランジュ乗数という）の符号は正負どちらでもよい。

一般に変数x₁,x₂,,x_nについてm(n)^個の条件g_i(x₁,x₂,,x_n)0 (i1,2,,m)

のもとで関数z f(x₁,x₂,,x_n)^{の極値を求めるには、}

. : ) ( )

( ) (

1

const λ

g λ

f _i

m

i i

i x

x λ

x,









 とおいて、_λ  g_i(x)0

j であるから

) , , 2 , 1 ( 0 ),

, , 2 , 1 (

0 i m

n λ

x_j j  _i   





 

 



 の連立方程式で求められる。

■例：x₁x₂ 4の条件のもとでz x₁² x₂²を最小にせよ。

この問題の答えは、目的関数が原点からの距離の2乗に等しいから、原点からx₁x₂ 4

に下ろした垂線の交点である。

普通に解くには、条件式を変形したx₂ 4x₁を目的関数に代入したz x₁² (4x₁)²

を微分して求める。つまり

8 ,

2 ,

0 2

4 ₁ ₁ ₂ _min

1









 x x x z

dx dz

ラグランジュの方法を用いれば、

) 4 (

) , ,

( ₁ ₂  ₁²  ₂²  ₁ ₂ 

 x x λ x x λ x x

8

2 ,

4

4 2 2

0 2

min

2 1

2 2

1 1



































 









 





x x

λ

λ x x

x λ x λ

λ x x

この方法ではλ4に選んでおけば値がx₁x₂ 4の直線上ではz x₁² x₂²と同じ値をとることを示している。また、

λ λ x λ

x λ 4

2 2 2

2 2 2 2

1   



 



 

 



 

 



 ^{と変形され、}^{値の最小値は}λ^{値によって変化す} る。つまり、λ^値と_min及びその座標(x₁,x₂)は次のようになっている。

(7)

) 3 , 3 ( ) , ( 6 6

) 5 . 2 , 5 . 2 ( ) , ( 5 . 7 5

) 2 , 2 ( ) , ( 8 4

) 5 . 1 , 5 . 1 ( ) , ( 5 . 7 3

) 1 , 1 ( ) , ( 6 2

) 5 . 0 , 5 . 0 ( ) , ( 5 . 3 1

) 0 , 0 ( ) , ( 0 0

2 1 min

























































x x λ

これにより_minはx₁ x₂の直線上を辿りながら原点からx₁ x₂ 4と交わるところまで次第に増加し、この点を過ぎると次第に減少していることがわかる。また、λがどんな値であっても直線x₁x₂ 4上の値は常に一定である。_minは鞍点となっている。

■例：体積 V の円筒形水槽を特殊な板で作ることになった。水槽は底面・側面のみを囲う構造である。このとき、板の面積を最小にする底面の半径ｒと高さｈの比を求めよ。

1 : 1 2 :

2

, 2 0 2 2

, 0 ,

0 2

2 2

, 2 0 2

, 0 2

) (

2 )

, , (

min 2

0

2

2 2































 

















 





















r r h

h

h λ h

λ h rh λ h r rh λπ h π r r π

r λ r

λ r

λπ r h π

h r π V λ rh π r π λ h r

πrh πr S

h πr V ０

1 1

2 2

3 3

4 4

5

5 6

6

０ 1 1

2 2

3 3

4 4

5

5 6

6

ｚmin＝8

ｚ＝8 ｚ＝10 ｚ＝12

ｚ＝16

Φ ＝16 Φ＝12 Φ＝10 Φ＝9 Φmin＝8

16 12 10

16 12 10 9

λ＝０の時のｚの変化 λ ＝－4の時のΦの変化

(8)

（２）キュンタッカーの条件

制約式は等号で結ばれていれば比較的簡単に求められるが、一つでも不等式が含まれると解は一意に決められないことが多い。非線形計画法は、かなり複雑な理論であるので一般的解法は現在でもはっきりせず、一定の条件を満たす問題を解く場合に限られる。

問題にある関数を図形に表現した場合、下に凸となるものを凸関数、上に凸となるものを凹関数と呼んでいる。

) (x

g_i のすべてが凸関数であり、 f(x)^{も凸関数であるとき}

を凸計画法という。この中に一つでも凹関数なる場合を非凸計画法という。

) (x

g_i のすべてが凹関数であり、 f(x)^{も凹関数であるとき}

を凹計画法という。

目的関数が凸関数の場合、最小値を求めることは容易であるが最大値を求めることは特定の場合を除き一般に困難であり、凹関数の場合、反対に最大値を求めることは容易であるが最小値については困難である。ここでは凸計画法、又は凹計画法に限定して述べる。

双対性は

主問題：













 min cx

z

0 x

b Ax

とすると、双対問題：













 max wb

0 w

c w

y A

である。

これの非対称形は、主問題：













 min 0 cx

x b x

z A

、双対問題：















 max wb

y

0 w 0, w

c wA

である。

又は、主問題：















 min cx

z

0 x 0, x

b Ax

、双対問題













 max wb

y

0 w

c wA

（※）

の組となる。非対称形は通常の双対問題と等価である。なぜならスラック



1



⁰

 _m

t s s

s  とすると、

   

_^^min



 



 





 



 

s 0 x c z s b,

I x

A と表せて、この

min )

(

0

) , , 2 , 1 ( 0 ) (













 x f z

x

m i

x

g_i 

max )

(

0

) , , 2 , 1 ( 0 ) (













 x f z

x

m i

x

g_i 

(9)

非対称性双対問題を書くと、^w



^A ^^I

 

^ ^c ⁰



^, ^y^^wb^^max となる。これは )

0 wI ( 0 w c,

wA    となり通常形に同じとなるからである。

よって

について、(1)は

であり、



11 1



1 1

1

1  a



 











 _n

n

a x a

g x

g   ^、dx_i  y_i^とし、



n



t  y₁  y

y

とすると、a₁y0,a₂y0,,a_ky0となる。また、 _io

i o

x a f  



 







 とすると、(3)はa_oy0

と示して、a_o t₁a₁ t₂a₂ t_ka_kが存在する。（ファーカスの定理より）

なぜなら先の（※）を書き直して、

と

となるからである。ところで、i1,,n^{のうち、①}i1,,l^はy_i 0^、②il1,,n はy_i 0,y0である。②の場合は双対定理がそのまま使えるが①の場合は通常の双対定理、つまり

と

でなくてはならない。よって通常形と非対称形を一緒に扱うため、tAza_o^{として調整}

項zを添えることにする。②の場合は調整項不要のためz_i 0(il1,,n)^である。















 min

0 , 0

y a

y y

0 y

z o

A















 min 0 0 t

t a

t _o

u A













 min 0 y a

y 0 y

z o

A















 min 0 0 t

t a

t _o

u A

















 



 













 





) 3 ( , , 1 0

) 2 ( ,

, 1 0

) 1 ( ,

, 1 0

n i

x dx f

l i

dx

k j

x dx g

i

i i o

i i

i i i













 



 





 



 





 



 





0 0 0

2 2 1 1

1 2

2 1 1 1 1

n n k k

k

n n

i i

i

n n

x dx dx g

x dx g x g

x dx dx g

x dx g x g

x dx dx g

x dx g x g

