• 検索結果がありません。

最適化数学入門

N/A
N/A
Protected

Academic year: 2021

シェア "最適化数学入門"

Copied!
6
0
0

読み込み中.... (全文を見る)

全文

(1)

c オペレーションズ・リサーチ

最適化数学入門

Karush–Kuhn–Tucker 条件の眺望―

奥野 貴之

受験数学で定番でもある関数の最小化問題もしくは最大化問題は,実は応用数学の基礎分野である最適化数 学への入口とも言える.そして,最適化数学は高度情報化社会で意思決定をするためのツールとして欠かせな いものとなっている.本稿では,お馴染みの変数が一つの関数の最小化問題から始めて最適化数学への簡単な 入門を行う.とくにKarush–Kuhn–Tucker条件と呼ばれる,最適解が満たすべき数学的性質の解説を行う.

読者の知識としては,高校の数学IIと数学Bにおける微分法とベクトルの知識があることを想定している.

キーワード:最適化,最適化問題,Karush–Kuhn–Tucker条件

1. はじめに

今日複雑な世の中がうまく動いている背景には,さ まざまな数学の問題が精錬されたテクニックによって 絶え間なく解かれているという現実があります.その 中の問題の一つに,高校生の皆さんが授業において既 に中を覗き込んでいるものがあります.それが本稿で 紹介する 最適化問題 であり,それらを取り扱う数 学の分野を 最適化数学 と言います.コンピュータ の能力の飛躍的向上と相まって現代社会で重要な意思 決定の道具となっている分野です.本稿では, 最適化 問題 を紹介するとともに,Karush–Kuhn–Tucker 件という最適化問題において最も重要な数学的性質の 一つを学んでいきたいと思います.

2. 最適化問題

最適化問題とは,制約となるいくつかの条件がある 状況下で,ある目的にとって最適な選択肢を見つけ出す 問題のことを言います.皆さんの身の回りにあったり,

新聞・テレビなどで取り上げられる課題の多くが最適 化問題として表現することが可能です.たとえば,出 発地から目的地へ最短時間で到達する経路を見つける 問題,数千種類ある株の中から見込まれる収益が最大 となる株の組み合わせ(ポートフォリオと言います)

を見つける問題,または限られた材料から製品を複数 種類生産する際に,収益が最大となるように各製品の 生産個数を決定する問題などが最適化問題として表す ことができます.

おくの たかゆき

東京理科大学工学部第一部経営工学科

162–8601 東京都新宿区神楽坂1–3

また,皆さんにとって最適化問題は初めてのもので はありません.実際,y=x2+ 2x(−1 x3) 最小値,最大値を求める問題は高校で習う問題ですが,

これも最適化問題です.最適化数学はこうした問題の 延長線上にあるのです.

さて,こうした最適化問題は取りうる選択肢の集ま りをS,目的の達成度を測る関数をfとして下のよう に数式で表現することができます.この形の問題を 数 理計画問題 とも呼び,集合S 実行可能集合 ,関 f 目的関数 と呼びます.

最小化 f(x) 制約条件x∈S

さて,これは実行可能集合Sに属する点( 実行可能 解 と言います)の中で目的関数f(x)が最小となる 最適解 xを求めよと読みます1.先ほど述べた経路 検索の問題を上の形として表すならば,Sは出発地か ら目的地までの経路の集まり,f(x)は経路xに対する 距離とおけばよいことになります.

ちなみに,実行可能集合Sは不等式や等式を用いて S = {x = (x1, x2, . . . , xn) | g(x) 0, h(x) = 0}

と 表 さ れ る こ と が 多 く2,そ の 場 合 は 集 合 の 定 義 式 で あ る 不 等 式 や 等 式 だ け を 用 い て 最小化 f(x) 制約条件 h(x) = 0, g(x) 0 と書きます.本稿ではこの形を用います.

1 f(x)を最大化したい場合は−f(x)を最小化することを 考えてください.

2 x= (x1, x2, . . . , xn)とはn個の実数の組で表される座 xを意味します.n= 2の場合はただの(x, y)座標にお ける点です.

2015 9 35

(2)

3. 具体例

具体的な問題を最適化問題として定式化してみま しょう.

3.1 生産個数を決定する

ある工場で木材から鉛筆,机,椅子を生産する状況 を考えましょう.各製品の1単位当たりの収益と重さ は下の表に従うとします. このとき木材1,000 kg

収益 重さ 鉛筆(1ダース) a 0.05 kg

机(1台) b 50 kg

椅子(1脚) c 4 kg

ら得られる収益を最大にするには鉛筆,机,椅子を何 単位ずつ生産すべきでしょうか.鉛筆をx1ダース,机 x2台,椅子をx3脚生産するとしましょう.さて,

x1x2x3が満たすべき条件としては

(1) 0.05x1+ 50x2+ 4x31,000(総重量の制約)

(2)x1x2x30以上の整数

で表現することができます.また目的としては,総収 ax1+bx2+cx3の最大化,つまり−ax1−bx2−cx3 の最小化です.そうすると解くべき最適化問題は次の ように表現することができます.

最小化 −ax1−bx2−cx3

制約条件 (x1, x2, x3)∈S;

S(1), (2)を満たす (x1, x2, x3)の集合

3.2 体積最大の直方体を求める

つぎに縦,横,高さの和が一定値L をとる直方 体の中で体積が最大のものを求める問題を考えまし ょう.直方体の 3 辺の長さを x1x2x3 とします.

このとき制約条件として,まず長さの和が一定より x1+x2+x3 = Lが導かれます.加えて,長さは0 以上ですからx1, x2, x30です.最後に目的は体積 x1x2x3の最大化,すなわち−x1x2x3の最小化です.

そうすると解くべき最適化問題は 最小化 −x1x2x3

制約条件 x1+x2+x3=L x1, x2, x30

となります.この問題の最適解は(x1, x2, x3) = (L/3,

L/3, L/3)です.皆さん,理由を考えてみてください.

4. 最適解が満たすべき性質

前節の二つの具体例のように,制約条件と目的をど れほど達成できたかの目安を数学的に表現できたなら ば,多くの意思決定問題が最適化問題として表すこと ができます.このとき,得られた最適化問題の最適解 が存在する3ならば,それをどのように見つけるのか は自然に生まれる疑問です.最適解を見つけるために は,候補となる点を実行可能集合の中から効率よく選 び出す必要があります.そのためには最適解が満たす べき性質を利用するという手が考えられます.もちろ ん,最適解かどうかは,実行可能集合S上の他の点と 目的関数の値を一つずつ比較すれば判定できます.と ころが,3.2節の直方体の例のようにSの点の数が無 限に考えられる場合はそんなことは不可能ですし,点 の数が有限な場合でもその数が莫大な場合は現実的に 難しいでしょう.したがって,闇雲に関数値を比較する 方法とは異なるアプローチが必要です.それらは,考 察対象となる最適化問題における目的関数や実行可能 集合の特徴によって異なりますので,ここですべてを 網羅することはできません.

そこで本稿では,最適化問題の中でも,制約条件と していくつかの1次不等式をもち,目的関数としてす べての点で微分可能な関数をもつ問題:

(P1)

最小化 f(x) 制約条件

n j=1

aijxj bi (i= 1,2, . . . , m) に限定します4.(aij, bi (i = 1,2, . . . , m, j = 1, 2, . . . , n)は定数とします.)このタイプの問題は応用 範囲が広く,とくにf(x)1次関数であるとき,この 問題は線形計画問題と呼ばれ,非常に実用性が高いこ とで知られています.以降では,1変数関数に関する 最小化問題を皮切りに,この問題の最適解が満たすべ き必要条件であるKarush–Kuhn–Tucker条件(KKT 条件)を解説していきます.

3「最小化x 制約条件x0」のように必ずしも最適解が

存在するとは限りません.

4 1次等式n

j=1cjxj=dが存在するときは,その式は 2本の不等式n

j=1cjxjdn

j=1cjxjdとおき直 せばよいことは明らかでしょう.

36

(3)

1 f(x)のグラフと接線の様子

5. 微分可能な1変数関数の最小化問題 この節では,次のような微分可能な1変数関数(変 数が一つの関数)の最小化問題を考えてみましょう.

最小化 f(x) 制約条件axb

ここでababであるような定数とします.また,

xを実行可能解とし,実行可能性を保持するようなx からの変化量の集合,すなわちax+dxbとな dxの集合をT(x)で表すとします.またf(x) f(x)の微分係数とします.

5.1 最適解であることの必要条件

xが最適解であることの必要条件を考えてみましょ う.x が最適解ならば,dx T(x)方向に進むと f(x)は増えなければいけません.一方,xにおける 接線y=f(x)(x−x)+f(x)yの値はf(x)dx だけ変化します.ところが,x付近では,接線のy 値の増減はf(x)の増減を表しているのですから(図1 参照)変化量f(x)dx0以上である必要がありま す.したがって,最適解であることの必要条件として 以下が成り立ちます.

f(x)dx0 (dx∈T(x)) (1) xの位置によって上の式を詳しく見てみましょう.

(i)x=bの場合は,dx∈T(x)としてdx0 ものしかとれません.よって(1)からf(x)0です.

(ii)a < x < bの場合は,dxとして正負両方にと ることができます.すると(1)からf(x) = 0です.

(iii)x=aの場合は,(i)と同様にしてf(x)0 が得られます.

以上から,最適解の候補として,区間中と区間の端 (i)(ii)(iii)が成り立っているような点を調べた らよいことがわかります.こうしたことは,教科書の

内容を別の表現で書いただけのように見えますが,実 (1)(P1)のような複雑な最適化問題に対しても 考えることができるのです.詳しくは6節と7節で説 明します.

5.2 性質(1)の十分性について

1x=aを見ればわかるように,(1)x 最適解であることの十分条件ではありません.しかし,

目的関数fが下に凸な放物線である2次関数であれば,

(1)は最適解であることの十分条件となることが知ら れています.より一般的に,目的関数fが凸性5を満た せば(1)は十分条件となります.(証明は演習問題とし ます.)したがって,このような場合ならば(1)を満た す点は最適解であることが保証できます.

6. 2変数2次関数の最適化問題

前節までは,1変数関数の最適化問題で最適解が満た すべき性質を考えました.この節では変数を一つ増や して2変数の2次関数というものを考えます.x1x2 を変数,abcdefを定数とします.このとき下 のような形をした関数を2変数2次関数と言います.

1

2ax21+bx1x2+1

2cx22+dx1+ex2+f では,具体的につぎのような2変数2次関数に関する 最適化問題(P2)を考えてみましょう.

(P2)

最小化 x21+x22−x1x25x15x2

制約条件 2x1+ 3x212, x10, x20

この問題の最適解はどこにあるでしょうか.1変数の場 合と違い,一筋縄でいきそうにありませんね.イメー ジができるように0≤x1, x2 10における目的関数 のグラフを図2に,x1x2座標における目的関数の等 高線と実行可能集合を図3に示しておきます.ここで 目的関数の等高線とは,地図における等高線と同じ概 念で,関数値をその点における高さと見なして,同じ 関数値をもつ点を結んだものです.図2と図3を見比 べればわかるように,図3において楕円となっている のが−2010010203040の関数値にそれぞれ 相当する等高線です.全平面上で目的関数を最小化す

5 f(tx+ (1t)y)tf(x) + (1t)f(y) (0t1) すべてのx,yで成り立つという性質,直感的に言うとグ ラフ上の2点を結んだ線分よりもグラフが凹んでいる性質 のことを言います.

2015 9 37

(4)

2 f(x1, x2) =x21+x22−x1x25x15x2(0x1, x2 10)のグラフ

3 目的関数の等高線と実行可能集合(0x1, x210)

る点は真ん中の楕円の中心部にあり,中心部に近づく につれて目的関数値が低くなっていくのがわかります.

そうすると図3から最適解は実行可能集合である直角 三角形の斜辺の真ん中あたりにありそうです.

6.1 最適解であることの必要条件

最適解の位置や目的関数の増減のイメージはわきま したか? では,x = (x1, x2)を最適解として,x が満たすべき性質を導いてみましょう.そのために前 節で考えたT(x)と似たものを考えます.実行可能解 x= (x1, x2)に対して,(x1+dx1, x2+dx2)が実行可 能解となるような2次元ベクトルdx = [dx1, dx2] 集合を考えます6.この集合をT(x)と新たに表すこと にします.加えて,この節ではT(x)から決まるつぎ のベクトルの集合N(x)を定義します.

6 同じ成分x1, x2をもつベクトルと座標の違いを明らかに するために,ベクトルは[ ]で囲んで[x1, x2]と表し,座 標は( )で囲んで(x1, x2)と表すことにします.

4 N(x)の形状

1 xに対するN(x)

xの位置 N(x)

三角形内部 {[0,0]}

頂点O {s[0,1] +t[1,0]|s, t0} 頂点A {s[2,3] +t[1,0]|s, t0} 頂点B {s[2,3] +t[0,1]|s, t0} OA\ {O, A} N1={s[1,0]|s0} BO\ {B, O} N2={s[0,1]|s0} AB\ {A, B} N3={s[2,3]|s0}

N(x) ={e|すべてのd∈T(x)について d·e0が成り立つ.} ここで定義式中の · は内積記号です.したがって,

N(x)とはT(x)に属するどのようなベクトルdとも,

なす角が90度以上となるベクトルeの集合を意味して います.図4では,それぞれの実行可能解xの位置にお けるN(x)の形を示しています.たとえば,実行可能集 合である三角形の3頂点をA(0,4)B(6,0)O(0,0) としましょう.すると A(0,4) において T(0,4) = {s AO+t AB|0s, t1}ですから,N(0,4)(図4 ではN(A)です)は{s[2,3] +t[−1,0]|s, t0}とな ります.ここで[2,3][−1,0]は,直線2x1+3x2= 12 x1= 0に対する法線ベクトルの中でも実行可能集 合の外側を向いたベクトルです.その他の実行可能解 xに対するN(x)を表1にまとめておきます.

さて,最適解であるための必要条件として,前節の (1)の拡張でもある下の補題が成り立ちます.

補題6.1. x= (x1, x2)を問題(P2)の最適解とする.

このとき

−[2x1−x25,2x2−x15]∈N(x) (2) が成り立つ.

38

(5)

証明. f(x1, x2) =x21+x22−x1x25x15x2とお き,dx = [dx1, dx2]∈T(x)を一つとる.このとき,

容易に確かめられるようにすべての自然数n1に対 してdx/n = [dx1/n, dx2/n]∈T(x)が成り立つ.x が最適解なので

0f(x)−f

x+ dx1

n ,dx2

n

=1

n((2x1−x25)dx1+ (2x2−x15)dx2)

1 n2

(dx1)2+ (dx2)2−dx1dx2

=1

n[2x1−x25,2x2−x15]·dx

1

n2((dx1)2+ (dx2)2−dx1dx2)

である.ここで右辺の最後の式の第2項を左辺に移項 して両辺にnを掛けると

[2x1−x25,2x2−x15]·dx

1

n

(dx1)2+ (dx2)2−dx1dx2

= 1 n

dx11

2dx2 2

+3 4(dx2)2

を得る.すると,dx T(x)は任意に選んだので,

左辺(とおく)が0以下であることを証明すれ ば題意は示される.(dx1−dx2/2)2 + 3(dx2)2/4 = 0となるベクトルdx に関してはα 0 が成り立 つので,(dx1 −dx2/2)2 + 3(dx2)2/4 > 0となる dx のみを考える.さて,今からα 0を背理法で 示す.α > 0と仮定すると上の式から 0 < α ((dx1−dx2/2)2+ 3(dx2)2/4)/nが任意の自然数n ついて成り立つ.ところが,nを十分大きくとると (dx21+dx22−dx1dx2)/n < αとなり,矛盾が生じる.

よってα0である.以上から題意が示された.

では,補題6.1の意味を考えてみましょう.まずベ クトル−[2x1−x25,2x2−x15]は唐突に出て きたように見えますが,証明からわかるように2点間 の目的関数値の差に由来する自然なものです.次節で も書きますが,このベクトルは目的関数の勾配ベクト ルの逆向きのベクトルに相当するものであり,5節で −f(x)に対応しています.その方向と内積が正で あるような向きに進むと関数値が下がる性質がありま す.逆に,内積が負であるような方向に進めば関数値 は上がってしまいます.図5はいくつかの点における ベクトル−[2x1−x25,2x2−x15]を等高線図に

5 各点におけるベクトル[2x1x25,2x2x15]

プロットしたものです.ある点から矢印の方向に進め ば,その点の楕円の内部に入っていく様子から,目的関 数値が下がる方向だということが観察できます.した がって,このようなベクトルがN(x)に含まれている ということは,xから実行可能集合のどの点に進んで も関数値が増大することを意味します.このことから (2)xが最適解ならば自然に成り立つ性質であるこ とがわかります.

6.2 条件(2)を満たすxを求める

では,(2)を満たすxを実際に求めてみましょう.そ の前に,つぎのように関数と集合を定義しておきます.

g= [2x1−x25,2x2−x15], g1(x) =−x1, g2(x) =−x2, g3(x) = 2x1+ 3x212

v1= [−1,0], v2= [0,−1], v3= [2,3]

I(x) ={i|gi(x) = 0, i∈ {1,2,3}}

ここでviは直線gi(x) = 0の法線ベクトルの中で実行 可能集合の外側に向いたベクトルであることに注意して ください.さて,xの位置によって(2)をもう少し詳し く見ることができます.たとえばxがもし頂点Aにい るならばI(x) ={1,3}であり,g1(x) =g3(x) = 0, g2(x) <0です.また,表 1から(2)の式は,ある λ1, λ30が存在して−g=λ1v1+ 0v2+λ3v3と表 せることを意味します.他のx の位置についても同 様です.これらはまとめて下のようにスッキリと書く ことができます.

xが最適解ならば,あるλ1λ2λ3が存在して g+

3 i=1

λivi= 0,

gi(x) = 0, λi0 (i∈I(x)), gi(x)<0, λi= 0 (i /∈I(x))

2015 9 39

(6)

が成り立つ.

上 の 式 を 問 題 (P2) に 対 す る Karush–Kuhn–

Tucker条件 あるいは KKT条件 と言い,λiを制 gi(x)0に関する Lagrange乗数 と言います.

KKT条件は最適解を見つけ出すうえでとても有効な 条件として知られており,最適化問題を解くための手 法の多くがこの条件に基づいて開発されています.こ れを利用して,xを求めてみましょう.ずるいようで すが,図3からI(x) ={3}のようです.これを利用 して上のKKT条件を書き直すと[2x1−x25,2x2 x15] +λ3[2,3] = 0,2x1+ 3x212 = 0, λ1=λ2= 0, λ30, x10, x20となります.これらを解くと,

x1 = 99/38, x2 = 43/19, λ1 = λ2 = 0, λ3 = 39/38 が得られます.

6.3 KKT条件の十分性について

最適解であることの必要条件としてKKT条件を導 きましたが,1変数の場合と同様,目的関数が凸性を 満たすならばKKT条件を満たす点は最適解であるこ とが知られています.問題(P2)の目的関数に関して も凸性が成り立っており,上で求めた解は問題(P2) 最適解ということが保証できます.

7. 多変数関数に関する最適化問題

この節では,4節における最適化問題(P1)に対する KKT条件を述べます.そのために

∇f(x) = ∂f(x)

∂x1 ,∂f(x)

∂x2 , . . . ,∂f(x)

∂xn

, I(x) = i

n j=1

aijxj =bi, i∈ {1,2, . . . , m}

, ai= [ai1, ai2, . . . , ain] (i= 1,2, . . . , m)

とおきます.ここで第1行目のベクトルは関数f(x) 勾配ベクトルと呼ばれます.∂f(x)/∂xixiに関す る偏微分と言い,f(x)xiのみを変数とする関数と みなしたときの微分係数を表します.n= 1のときは

∇f(x) =f(x)となります.またn= 2として前節の 目的関数f(x) =x21+x22−x1x25x15x2を考える ∇f(x) = [2x1−x25,2x2−x15]となります.

さて,最適化問題(P1)に対するKKT条件として

以下が成り立ちます.

定理7.1. x= (x1, x2, . . . , xn)を問題(P1)の最適 解とする.このとき,

∇f(x) + m i=1

λiai= 0, n

j=1

aijxj−bi= 0, λi0 (i∈I(x)), n

j=1

aijxj−bi<0, λi= 0 (i /∈I(x))

となるλ1, λ2, . . . , λmが存在する.逆に,目的関数が 凸性を満たすならば,上が成り立てばx(P1)の最 適解である.

8. おわりに

本稿では最適化数学入門として,最適化問題におい て最適解が満たすべきKKT条件を紹介しました.本 稿では,問題(P1)を中心に考えましたが,より複雑 な形をした最適化問題まで拡げてKKT条件を考える ことができます.こうしたKKT条件を含む最適化理 論の入門書として[1]を,本格的な専門書として[2] あげておきます.

また6節の問題では,手作業でKKT条件が成り立

つ解とLagrange乗数を求めました.しかし,変数や

制約条件の個数が増大するにつれて手作業で最適化問 題を解くのは難しくなっていきます.現代社会で解か れている最適化問題の中にはそれらが数万単位のもの も少なくありません.そうした問題をコンピュータで 効率的に解くための強力な数値解法も多く開発されて います.数値解法に関する専門書として[3]をあげて おきます.

最後になりましたが,本稿をきっかけに一人でも最 適化数学に興味をもっていただけたら幸いです.

参考文献

[1] 福島雅夫,『数理計画入門』,朝倉書店,1996.

[2] 福島雅夫,『非線形最適化の基礎』,朝倉書店,2005.

[3] 矢部博,『工学基礎 最適化とその応用』,数理工学社,

2006.

40

図 1 f (x) のグラフと接線の様子 5. 微分可能な 1 変数関数の最小化問題 この節では,次のような微分可能な 1 変数関数(変 数が一つの関数)の最小化問題を考えてみましょう. 最小化 f (x) 制約条件 a  x  b ここで a , b は a  b であるような定数とします.また, x ∗ を実行可能解とし,実行可能性を保持するような x ∗ からの変化量の集合,すなわち a  x ∗ + dx  b とな る dx の集合を T (x ∗ ) で表すとします.また f  (x) を f(
図 2 f(x 1 , x 2 ) = x 2 1 +x 2 2 −x 1 x 2 − 5x 1 − 5x 2 (0  x 1 , x 2  10) のグラフ 図 3 目的関数の等高線と実行可能集合 (0  x 1 , x 2  10) る点は真ん中の楕円の中心部にあり,中心部に近づく につれて目的関数値が低くなっていくのがわかります. そうすると図 3 から最適解は実行可能集合である直角 三角形の斜辺の真ん中あたりにありそうです. 6.1 最適解であることの必要条件 最適解の位置や目的関数の増減のイメージ

参照

関連したドキュメント

スマートグリッドにつきましては国内外でさまざまな議論がなされてお りますが,

その太陽黒点の数が 2008 年〜 2009 年にかけて観察されな

学側からより、たくさんの情報 提供してほしいなあと感じて います。講議 まま に関して、うるさ すぎる学生、講議 まま

都調査において、稲わら等のバイオ燃焼については、検出された元素数が少なか

下山にはいり、ABさんの名案でロープでつ ながれた子供たちには笑ってしまいました。つ

化学物質は,環境条件が異なることにより,さまざまな性質が現れること

入所者状況は、これまで重度化・病弱化等の課題から、入院後に退所及び死亡に 繋がる件数も多くなってきていた。入院者数は 23