第 4 章制約付き最適化問題

第 4 章 制約付き最適化問題

4.1 ^{制約付き最適化問題}

この章では，関数を最小化する際に変数に制約の付いた問題を扱う．

例 18. 例 8 の問題を再掲する．

最大化 f (x, y) := xy

制約 x + y = 4, x ≥ 0, y ≥ 0 となる．ここで x + y = 4 より，

xy = x(4 − x) = − x ² +4x = − (x − 2) ² +4 となる．

0 x

y

A B

C

点が A :(1, 3) → B :(2, 2) → C :(3, 1) と動くとき，関数 f (x, y) = xy の値は，

(x, y) A B C

f (x, y) 3 $ 4 % 3

と変化する．よって x + y = 4 を満たす点で B に近いものの中では， B において f (x, y) の関数値が一番大きくなる .

このような点を制約無しの最適化問題と同様に局所最大解と呼ぶ . さらに , B はす べての点に対しても最大解にもなっている . このような点を大域最大解と呼ぶ . し たがって題意を満たす一辺が 2 の正方形のとき面積が最大になる .

制約付き最小化問題の定義

以下で言葉をきちん定義しよう．今までと同様に最小化問題で主に説明するが最 大化問題も同様である . また変数を一般に n 個として扱う .

制約付き最小化問題 とは以下のような問題を指す：集合 C を数ベクトル空間 R ⁿ の部分集合とする .

最小化 f (x)

制約 x ∈ C (4.1)

最小化問題 (4.1) において , 上記のような集合 C を 実行可能領域 , C の点を 実行 可能解 と呼ぶ . ここで , 「 x ∈ C 」とは「 x が C に含まれる」ことを意味する . 例 えば，例 8 の制約

x + y = 4, x ≥ 0, y ≥ 0

のように式を用いて表される．このときに用いられる式を 制約式 と呼ぶ ． 定義 . x ¯ ∈ C が x ¯ に充分近い C 上のすべての x に対して

f (x) ≥ f(¯ x)

のとき f (¯ x) を (4.1) の局所最小値 , ¯ x を局所最小解と呼ぶ . 定義 . x ¯ ∈ C が C 上のすべての x に対して

f (x) ≥ f(¯ x)

のとき f (¯ x) を (4.1) の大域最小値 , ¯ x を大域最小解と呼ぶ .

4.2 ^{等式制約が一つの場合}

4.2.1 ^{曲線上の増減表}

制約付き最適化問題を調べるには，実行可能領域上での目的関数の値の変化を， 1 変数関数の増減表に似たものを用いて調べることから始める ．

1 次関数を円周上で最適化

1

2 3

0 x

y

1 1

−1

−1

⇐ ⇒

図 4.1: 円と x + y の 等高線

始めに，円周上で 1 次関数を最小化または最大 化する問題を考える ;

最小化，又は最大化 f (x, y) := x + y 制約 x ² + y ² = 1.

図 4.1 を見てみよう．直線 ! 2 は f (x, y) = x + y =

− 1 を満たす直線である . よって， ! 2 は f の等高 線になっている．直線 ! 1 ， ! 3 もある値に対する f の等高線であり，等高線上での f (x, y) の値は ! 3 ，

! 2 ， ! 1 の順で大きくなる . 以下で， f の等高線と

局所最適解の関係を見てみよう．

円と ! 2 の位置関係

さて , f の等高線 ! 2 と円との交点の近くを詳しく見てみる .

2 A

B C

⇐ ⇒

図 4.2: ! 2 と円の交点の周り で拡大

3

A

B C

A B

C

⇐ ⇒

図 4.3: ! 3 と円の接点の周り で拡大

拡大図 4.2 のように点 A ， B ， C を定める . すると，点が A → B → C と動くと き関数 f の値は，

! 2 と円の交点の近く

(x, y) A B C

f (x, y) 大 % 小 % もっと小

と変化するのが読み取れるだろう . よって , ! 2 と円の交点は局所最適解にはならない．

円と ! 3 の位置関係

一方，別の等高線 ! 3 と円の接点付近では（図 4.3 を見よ），

! 3 と円の接点の近く (x, y) A ^! B ^! C ^!

f (x, y) 大 % 小 $ 大

と変化する．いま， ! 3 と円の接点は ( − 1/ √

2, − 1/ √

2) であり，表よりその点に近い 円周上の点の中では， ( − 1/ √

2, − 1/ √

2) が f (x, y) の値を一番小さくする . したがっ て , ( − 1/ √

2, − 1/ √

2) が局所最小解である．同様に，図 4.1 で等高線 ! 1 と円の接点 は局所最大解になっていることがわかるだろうか．

一般の関数を円周上で最適化

次に，一般の関数を円周上で最適化する問題を考えよう．一次関数でなくても，目

的関数の等高線と実行可能領域の位置関係は，局所最適解と密接なつながりを持つ．

A B

⇐ ⇒ C

⇐⇒ ^D

E

図 4.4: 目的関数の等高線と実行可能領域 1 目的関数の等高線と実行領域の関係（その 1 ）

例えば，目的関数の等高線が図 4.4 のようになっていると仮定する．すると A ， B ， C ， D ， E のどの点が局所最小解または局所最大解だろうか？ 点を A → B → C と 動かすと，図から増減表は

(x, y) A B C

f (x, y) 大 % 中 % 小

となる．したがって，点 B は局所最小解ではない．一方，点を C → D → E と動か すと，図から増減表は

(x, y) C D E

f (x, y) 中 % 小 $ 中

となるので，点 D は局所最小解になる．

目的関数の等高線と実行領域の関係（その 2 ）

それでは，目的関数の等高線が図 4.5 のようになった場合はどうだろうか？

A B

C

⇐⇒

図 4.5: 実行可能領域と目的関数の等高線 2

この場合は，点を A → B → C と動かすと，図から増減表は

(x, y) A B C

f (x, y) 小 % 大 % 小

となるので，点 B は局所最大解になる．

4.2.2 ^{ラグランジュ乗数法}

一般の関数を一般の曲線上で最適化

上記のように，ある点が局所最適解ならば，そこで等高線と実行可能領域は接して いることがわかる．これと，勾配ベクトルと等高線との関係より以下の定理を得る．

定理 9 ( ラグランジュ乗数法 ). 最適化問題

最小化，又は最大化 f (x) 制約 g(x) = 0

を考え， x ¯ を局所最適解とする . ∇ g(¯ x) ) = 0 ならば , ある数 λ が存在して ,

! ∇ f (¯ x) = λ ∇ g(¯ x) g(¯ x) = 0

が成り立つ .

勾配ベクトルと等高線

まず，この定理を理解する為に，以下の重要な幾何的関係を説明する：

「関数の勾配ベクトルと等高線とは直交する」

ただし，上記の「直交する」とは，ある点において「勾配ベクトル」とそこでの「等 高線の接線」が直交していることをいう（図 4.6 右を参照） ．

(a, b)

f (x, y) = f(a, b)

z = f(x, y)

(a, b)

O

O x

y z

x y

(a, b, f(a, b))

∇ f (a, b)

図 4.6: 接平面，等高線と接線の関係

これについて解説しよう．まず，関数 f のグラフ z = f (x, y) と (a, b) における 接平面

z = f (a, b) + f x (a, b)(x − a) + f y (a, b)(y − b) (4.2) を考える（図 4.6 右）．点 (x, y, z) = (a, b, f (a, b)) を通り xy 平面に平行な平面

z = f (a, b) (4.3)

で， f のグラフと接平面を切ると断面は図 4.6 のようになる．

このとき，接平面の断面は等高線の (x, y) = (a, b) における接線になっている ． この接線は平面 (4.2) と (4.3) の交線なので，

f x (a, b)(x − a) + f y (a, b)(y − b) = 0 (4.4) で与えられる．ここで，式 (4.4) はベクトルと内積 を用いて，

"

f x (a, b) f y (a, b)

#

·

"

x − a y − b

#

= 0

とも書ける . よって，勾配ベクトル ∇ f (a, b) は等高線の (x, y) = (a, b) における接線 と直交していることが分かる ．したがって，勾配ベクトルは等高線と直交している．

(a, b)

O x

y z

∇ f(a, b)

z

図 4.7: 接平面と勾配ベクト ルの向き

さらに，接平面の式 (4.2) に

"

x y

#

=

"

a b

#

+ ∇ f (a, b) =

"

a + f x (a, b) b + f y (a, b)

#

を代入すると

z = f (a, b) + f x (a, b) ² + f y (a, b) ² > f(a, b) となるので， ∇ f (a, b) は接平面の z 座標が増 加する方向を向いている．よって，

勾配ベクトルは

関数値が増える方向を向いている

ことも覚えておこう（図 4.6 の勾配ベクトルの向きも参照）．

定理 9 の解説

以上の準備のもとに定理 9 を解説する．まず， x ¯ を局所最適解とする．上の考察

より， ∇ f (¯ x) は点 x ¯ で f の等高線と直交している．また，定理直前の考察から， f

の等高線は実行可能領域と x ¯ で接している．ここで，実行可能領域は値 0 に対する

g の等高線であることに注意する．これよりさらに，実行可能領域は ∇ g(¯ x) と点 x ¯ で直交していることがわかる．まとめると

∇ f (¯ x) ⊥ { f の等高線 } 「接する」 { 実行可能領域 } ⊥ ∇ g(¯ x) が成り立つ．

ところで， 「 f の等高線と実行可能領域が x ¯ で接している」とは， x ¯ において， 「 f の 等高線と実行可能領域の接線が一致している」ことを表す．したがって， ∇ f(¯ x) と

∇ g(¯ x) は同一の直線と直交しているので，平行であり ∇ f (¯ x) = λ ∇ g(¯ x) と書ける．

実行可能領域に関する停留点

定理の式を用いて以下を定義する．

定義 . ある実数 λ に対して，

! ∇ f (¯ x) = λ ∇ g(¯ x) g(¯ x) = 0

を満たすような点 x ¯ を 実行可能領域に関する停留点 と呼ぶ．ただし，省略しても 誤解がない場合は，単に停留点と呼ぶ．

A B

C

⇐⇒

図 4.8: 局所最適解にならな い停留点

通常の停留点と同じように , 実行可能領域 に関する停留点であっても最適解にならない ものは存在する（図 4.8 参照）．

最適解の存在定理

証明はしないが最適解の存在定理を一つ挙 げておく .

定理 10. 目的関数が連続で , 実行可能領域が 有界閉集合ならば , 最適化問題は大域最小解 と大域最大解を持つ .

制約付き最適化問題で特に等式制約を持つ 問題は，実行可能領域が有界閉集合になる場 合が多い．最適解の存在があらかじめ分かっ

ていると議論が楽になり， 1 階微分の情報（ラグランジュ乗数法）のみで，最適解

を探せることも多い．

4.3 等式制約付き最小化問題の解き方

この節では具体的に例題を解いてみよう．以下，全ての例題で実行可能領域が有 界閉集合になっている．したがって，あらかじめ大域最適解が存在するとわかって いる．

例 19.

最小化 f (x, y) := x − y

制約 g(x, y) := 2x ² + 3y ² − 1 = 0 この例では説明のために冗長な解答を書く．

ラグランジュ乗数法（定理 9 ）より，局所最適解は，

! ∇ f (x, y) = λ ∇ g(x, y), g(x, y) = 0

を (x, y) ， λ について解いたときの， (x, y) に含まれている．いま，目的関数と制約

式の勾配ベクトルは , それぞれ

∇ f (x, y) =

"

1

− 1

#

, ∇ g(x, y) =

"

4x 6y

#

となるので，上式は

 

 

 



1 = λ4x

− 1 = λ6y

2x ² + 3y ² − 1 = 0

となる．これを満たす (x, y) ， λ を見つければ， (x, y) が停留点になる（ λ は存在 すれば良く , 必ずしも求める必要はない）．

第 1 式より 4x ) = 0 となるので , λ = 1/(4x) として第 2 式に代入すると , y = − 2x/3 を得る . これを第 3 式に代入すると , x = ± (

3/10 が求まる . このとき y = ∓ ( 2/15 となる . よって，停留点は (x, y) = ( ± (

3/10, ∓ (

2/15) である．

したがって , (x, y) = ( ± (

3/10, ∓ (

2/15) での目的関数 f の値を比べると，大域最

小解が ( − (

3/10, (

2/15) ，大域最小値が f ( − (

3/10, (

2/15) = − (

3/10 − ( 2/15 である．

図 4.9: 停留点と大域最適解 の関係

解説 . さて，上記の方法で本当に大域最小値

が求まっているだろうか？この節のはじめに

書いたように例 19 の実行可能領域は有界閉

集合であり，必ず大域最適解が存在する．さ

らに図 4.9 のように，すべての大域最適解は

停留点に含まれる（これに関して下記「特異 点」を参照）．言い換えると，停留点の内ど れかが大域最適解なのである．したがって，

停留点の値を比較し最小の値をとるものが大域最適解である．

特異点

∇ g(a) = 0

^{が成り立つ点}

a

^を

g

^{の特異点と呼ぶ．図}

4.9

の包含関係が成り立つため

には，定理にあるように大域最適解が制約式の特異点にならないという仮定が必要であ る．例

19

^では

∇ g(x, y) = ) 4x

6x

*

で，これが零ベクトルになるのは

(x, y) = (0, 0)

のときのみである．しかし，実行可能 領域には

(0, 0)

は入っていないので，制約式

g

は実行可能領域に特異点を持たない．し たがって，どの大域最適解（実行可能領域に入っているので）も制約式の特異点になら ない．したがって，図

4.9

の包含関係が成り立つ．

実際は，自然な実行可能領域に特異点は少ないので（ないことも多い），始めは気に せずに図

4.9

が成り立つと思って勉強を進めた方が良い．

例 20.

最小化又は最大化 f (x, y, z) := x − y + z ²

制約 g(x, y, z ) := x ² + y ² + 2z ² − 1 = 0 ラグランジュの乗数法より，局所最適解は

! ∇ f (x, y, z) = λ ∇ g(x, y, z) g(x, y, z) = 0

を (x, y, z ) ， λ について解いたときの (x, y, z) に含まれている．いま，

∇ f (x, y, z ) =



  1

− 1 2z



  , ∇ g(x, y, z) =



  2x 2y 4z



 

より，上式は

( ∗ )

 

 

 



 

 

 

1 = 2λx

− 1 = 2λy 2z = 4λz

x ² + y ² + 2z ² − 1 = 0 となる． ( ∗ ) の第 1 式より λ ) = 0 なので，

x = 1

2λ , y = − 1

2λ (4.5)

となり，

x = − y (4.6)

を得る．また， ( ∗ ) の第 3 式より

z(1 − 2λ) = 0 (4.7)

となる．ここで場合分けをする．

z = 0 のとき， ( ∗ ) の第 4 式と式 (4.6) より 2x ² − 1 = 0 を得るので， (x, y, z ) = ( ± 1/ √

2, ∓ 1/ √

2, 0) となる．

z ) = 0 のとき，式 (4.7) より λ = 1/2 となるので，式 (4.5) より x = 1 ， y = − 1 を得るが， ( ∗ ) の第 4 式よりこれは解にならない．

したがって，停留点は ( ± 1/ √

2, ∓ 1/ √

2, 0) となり，そこでの値を比較すると，大 域最小解は ( − 1/ √

2, 1/ √

2, 0) ，大域最小値は f ( − 1/ √ 2, 1/ √

2, 0) = − √

2 となる．

例 21 (2 次形式の最小値 ). この例では， 2 次形式の持つ性質を示す．

A = 1 _{a b}

b c

2 を対称行列として以下の最小化問題を考える．

最小化 f (x, y) := 1

x y 2 A

"

x y

#

= ax ² + 2bxy + cy ² 制約 g(x, y) = x ² + y ² − 1

すると，最小値は A の最小固有値 , 最小解はその固有ベクトルになる．

ラグランジュ乗数法より，最適解は実行可能領域に関する停留点になる．よって，

! ∇ f (x, y) = λ ∇ g(x, y), g(x, y) = 0

を (x, y) ， λ について解けばよい．いま

∇ f (x, y) =

"

2ax + 2by 2bx + 2cy

#

, ∇ g(x, y) =

"

2x 2y

#

より，第一式は "

2ax + 2by 2bx + 2cy

#

= λ

"

2x 2y

#

なので，停留点の式は 

 



 



"

a b b c

# "

x y

#

= λ

"

x y

# , x ² + y ² − 1 = 0

と書ける．これを解けば良いのだが，直接解くのは意外に大変である．そこで少し

見方を変えると，この式は λ が A の固有値で， (x, y) がその固有ベクトルあり，か

つ大きさが 1 であるということを表している．よって，停留点は A の固有ベクト ルと一致する．

ここで， λ ， (x, y) をそれぞれ A の固有値と固有ベクトルとすると，

f (x, y) = 1

x y 2 A

"

x y

#

= 1

x y 2 3 λ

"

x y

#4

= λ(x ² + y ² ) = λ

となる．よって，停留点での f の値は固有値と一致する．したがって，最小化問題 の最小値は A の固有値の中で小さい方であり，最小解は A の最小固有値に対する 固有ベクトルである． ．

4.4 ^{等式制約が複数の場合}

制約式が複数ある場合を解説する．

定理 11. 最小化問題

最小化 f (x)

制約 g 1 (x) = 0, g 2 (x) = 0, . . . , g m (x) = 0

を考え， x ¯ を局所最小解とする . ∇ g 1 (¯ x), . . . , ∇ g m (¯ x) が一次独立ならば , ある数 λ 1 , . . . , λ m が存在して ,

∇ f (¯ x) = λ 1 ∇ g 1 (¯ x) + · · · + λ m ∇ g m (¯ x) g 1 (¯ x) = 0, g 2 (¯ x) = 0, . . . , g m (¯ x) = 0 が成り立つ .

∇g2(a, b, c) g1(x, y, z) = 0

g2(x, y, z) = 0 (a, b, c) ∇g1(a, b, c)

図 4.10: 実行可能領域（空

間内の円）

解説 . この定理はきちんと示そうとすると難 しい．そこで具体例を用いて解説するので，

図を見て成り立ちそうだという直感を得てほ しい．

制約式が複数の場合は 3 変数の問題を考え た方が良い． α ， β ， γ ， δ を定数とする．

最小化 f (x, y, z) = αx + βy + γz + δ 制約

! g 1 (x, y, z) = x ² + y ² + z ² − 1 = 0 g 2 (x, y, z) = x + y + z − 1 = 0 実行可能領域は球面と平面との共通部分にな

るので，図 4.10 のように空間内の円である．この実行可能領域が制約式が複数の場

合の典型例になる．

(a, b, c)

図 4.11: 実行可能領域と接

する平面 制約式が一つの時と同じように， x ¯ =

(a, b, c) が局所最適解の時は，目的関数の等

高面 と実行可能領域が接する．ただし，空間 内の円と接する平面は図 4.11 のように回転 しても，やはり接している．よって，実行可 能領域に接する平面の法線ベクトルは，回転 させた平面のものも含めて，

λ 1 ∇ g 1 (a, b, c) + λ 2 ∇ g 2 (a, b, c)

と書ける．いま，目的関数の (a, b, c) を通る 等高面の法線ベクトルは ∇ f(a, b, c) である ので，

∇ f (a, b, c) = λ 1 ∇ g 1 (a, b, c) + λ 2 g 2 (a, b, c) が成り立つ．

練習問題 4. 1. 実行可能領域に関する停留点とその点での目的関数の値を求め , 最 小解を探せ .

(1).

最小化 f (x, y) := 2x − 3y

制約 g(x, y) := 2x ² + y ² − 1 = 0 (2).

最小化 f (x, y) := x ³ + y ³

制約 g(x, y) := x ² + y ² − 1 = 0

2. x, y が原点を中心とする半径 1 の円周上の点であるとき , 2x ² − 6xy + 2y ² の最小 値と最大値を求めよ .

4.5 ^定理 9 ^の証明

2 変数の最小化問題の場合を証明する． x ¯ = (a, b) を局所最小解とする．いま，関 数 u(t) = (x(t), y(t)) で， t = 0 の近くで微分可能で，

u(0) = ¯ x, g(u(t)) = 0

を満たすものが存在するとしよう．すると定理の主張は簡単に示せる．実際， x ¯ は 局所最小解で， u(t) は制約を満たしているので， f (u(t)) ≥ f (¯ x) = f (u(0)) が成り 立つ．よって，制約なしの最適化問題

最小化 f (u(t)), t ∈ R

は t = 0 で局所最小値を取る．したがって， （ 1 変数関数に対する） 1 次の最適性条 件より，合成関数 f ◦ u の t = 0 における微分は

d

dt f (u(t)) 5 5 5 5

t=0

= ∇ f (¯ x) · u ^! (0) = 0

を満たす．また， t = 0 の近くで g(u(t)) = 0 なので， g ◦ u の微分も d

dt g(u(t)) 5 5 5 5

t=0

= ∇ g(¯ x) · u ^! (0) = 0

を満たす . したがって， ∇ f (¯ x) と ∇ g(¯ x) は 2 次元ベクトルで一つのベクトル u ^! (0) に直交しているので，ある定数 λ が存在して， ∇ f (¯ x) = λ ∇ g(¯ x) が成り立つ．よっ て証明された．

さて , 上記のような u(t) の存在を示そう．これには陰関数定理を用いる． ∇ g(¯ x) ) = 0 より，特に g y (¯ x) ) = 0 とする．すると，陰関数定理より関数 ϕ で， x = a の近くで 微分可能で，

! g(x, ϕ(x)) = 0 （ x は a に近い任意の数）

ϕ(a) = b

を満たすものが存在する．よって， t = 0 の近くで，

u(t) =

"

a + t ϕ(a + t)

#

と定義すると上記を満たす関数 u を得る．