はじめての最適化 読書メモ

数学 人工知能技術 デジタルトランスフォーメーション 機械学習技術 本ブログのナビ

はじめての最適化 読書メモ

はじめての最適化より

「本書は具体的に理解できるよう、図形的説明を多用しながら分かりやすく詳説する。問題と解法の直感的理解を促し、具体的な問題を解けるようになることを目標とする。本文を簡潔に述べるように努めて、追加説明や他に言及したいことなどを側注とした。各章末には練習問題を配し巻末に全ての問題の解答を付けている。はじめて最適化問題を学ぶ初学者には、数学的復習から入っていくので、大変理解しやすく学べる好書である。」

第1章　数学的準備

1.1 多変数関数

f(x,y)=x2 + y2のようにxとyの二つの変数により値が決まるような関数を2変数関数
変数が複数ある関数を”多変数関数”とよぶ
f(x,y)=x2+y2のグラフ
等高線
同じ値を持つものをも一つの直線
f(x,y)=-x3-3xy2+y3+3xのグラフと等高線

1.2 微分

1.2.1 微分と積分

1.2.1.1 微分

平均変化率
変数関数f(x)に対してfの変化量/xの変化量=(f(a+h)-f(a))/hをx=aからa+hと変化するときのfの”平均変化率”とよぶ
例
f(x)=x2の時
x=1の近くにおける平均変化率
(f(1+h)-f(1))/h=((1+h)2-1)/h
(2h + h2)/h = 2 + h (h≠0)
値
h→0での”極限”
極限の定理
xがaと異なる値を取りながらαに近づく時、f(x)がある一定値αに近づくことを、x→aの時f(x)の”極限”という
x→αの時、f(x)が一定値に近づかない時、f(x)は”発散”するという
瞬間変化率と微分
Fのx=αにおける”瞬間変化率”または”微分係数”と呼ぶ
任意の点xに対する微分係数f'(x)をfの”微分”と呼ぶ
基本公式
接線
関数f(x)の瞬間変化率は点x=aにおける接戦の傾きを表す
接戦の方程式
片側極限と片側微分
Fの平均変化率においてx=aからa+hと変化する時、h>0ならば　xは増加し、h<0ならばxは現象する
右側微分
h>0を満たしながら、h→0とする時
極限limh→0+
右側極限
左側微分
H<0を満たしながら、h→0とする時
極限limh→0-
左側極限
両方合わせて、それぞれ”片側微分”、”片側極限”とよぶ
命題

1.2.1.2 偏微分

概要
2変数関数に対して微分を考える
(x, y)が[a b]→[a+h b]と変化した時
f(x, y)の平均変化率
(f(a+h, b) – f(a, b)) / h
xのx偏微分
片方の変数のみ変化する
偏微分の図形的な意味
(x, y) =(a, b)におけるf(x, y)のx偏微分
x偏微分のイメージ
曲線z=f(x,b)のx=aにおける傾き
(x, y) =(a, b)におけるf(x, y)のy偏微分
y偏微分のイメージ
曲線z=f(a,y)のy=bにおける傾き

1.2.1.3 合成関数の微分

(x,y)をx軸、y軸に並行に変化させた時
1変数関数の微分法で求める
(X,y)が斜めに変化した時はどうするのか?
例
f(x, y) = x2 + y2
[a b] → [a b] + t[2 3] z(t) = f(a + 2t, b + 3t)
t=0からtと変化したときの平均変化率
2fx(a, b) + 3fy(a, b)
命題
2変数関数f(x,y)と1変数関数x(t),y(t)に対して
z(t) = f(x(t), y(t))とおくと
dz(t)/dt = fx(x(t),y(t))x'(t) + fy(x(t),y(t))y'(t)

1.2.2 接平面

概要
1変数関数では微分を用いて接戦の式を表せる
2変数関数では偏微分を用いると、接平面の式を表すことができる
2変数1時間数のグラフ
z=ax+by
平面の式の一般化
平面の式の一般化
αx + βy + γz + δ = 0
[α β γ]は左の平面に垂直なベクトル
法線ベクトル
ベクトル[α β γ]に垂直で、(a, b, c)を通る平面
α(x-a) +β(y-b) + γ(z-c) = 0
接平面の式
h(x, y) = f(a, b) + fx(a, b)(x-a) + fb(a, b)(y-b)
f(a, b), fx(a, b), fy(a,b)は定数なのでh(x, y)は2変数の1次関数
点(a, b, f(alb))を含む平面
h(x, y)は曲面z=f(x, y)に(a, b, f(a, b))で接する平面
接平面

1.2.3 テイラーの定理

1.2.3.1 高階微分

f(x)の微分f'(x)をもう一度微分したものをf”(x)と書き、fの2回微分と呼ぶ
F”(x)をさらに微分したものをf”'(x)と書き、fの3回微分と呼ぶ
fの2回微分
2変数関数f(x,y)に対して、x偏微分fx(x,y)をもう一度x偏微分したものをfxx(x,y)などと書く
2変数関数f(x,y)に対して、x偏微分fx(x,y)をy偏微分したものをfxy(x,y)などと書く

1.2.3.2 テイラーの定理(1変数)

テイラーの定理(1次と2次のみ)
点aとxを決めると、あるaとxの間の数cが存在して
f(x)=f(a) + f'(a)(x-a) + R2(x) , R2(x)=f”(c)/2 *(x-a)2
別のcに対して、f(x) = f(a) + f'(a)(x-a) + f”(a)/2 (x-a)2 + R3(x)
R3(x) = f”'(c)/3! (X-a)3
ランダウ記号
R2(x), R3(x)は剰余項
n次の場合のテイラーの定理
f(x) = f(a) + f'(a)(x-a) + ・・・ +f(n)(a)/N!(x-a)n + o((x-a)n)
o:ランダウ記号

1.2.3.3 テイラーの定理(多変数)

テイラーの定理(1次と2次)
f(x,y) =f(alb) +fx(alb)(x-a) + fy(a,b)(y-b) +o(∥x-a, y-b∥)
∥x-a, y-b∥=√(x-a)2 + (y-b)2
また、上式も成り立つ
曲面z=f(x,y)と接平面
接2次曲面
N変数関数fに対する式

1.3 積分

1.3.1 積分と基本公式

不定積分
関数f(x)に対して、F'(x)=f(x)となるF(x)をf(x)の原始関数と呼ぶ
f(x)の原始関数F(x)と定数Cを用いて ∫f(x)dx = F(x) +C と書ける関数∫f(x)dxをf(x)の”不定積分”、Cを”積分定数”と呼ぶ
基本公式
定理1.8 部分積分
関数f(x), g(x)に対して、以下が成り立つ
∫f(x)g'(x)dx = f(x)g(x) – ∫f'(x)g(x)dx
定理1.10 置換積分
関数f(x),g(x)に対して、x=g(x)とおくと、以下が成り立つ
∫f(x)dx = ∫f(g(t))g'(t)dt
定積分
関数f(x)の原始関数F(x)と区間[a, b]に対して、以下の式をx=aからbまでの”定積分”と呼ぶ
f(x)が[a,b]で0以上の時、y=f(x)とx軸および直線x=a,x=bに囲まれた図名の面積は定積分に一致する

1.4 ベクトルと行列

1.4.1 行列と行列式

1.4.1.1 行列の演算

行列の演算
ベクトルと行列
ベクトルの内積と大きさ
転置行列
逆行列
単位行列
AX=XA=Eを満たす行列XをAの逆行列

1.4.1.2 行列式

行列式
3×3の行列式
余因子
定義1.13 行列式
行列式の変形
行列の積、転置と行列式

1.4.2 連立1次方程式と階数

1.4.2.1 ガウスの消去法

例
x=tとおくと解は
ガウスの消去法の行列表現

1.4.2.2 階段行列と階数

一般に行列Aとベクトルx,bを用いて、連立方程式は、”Ax=b”と表せる
ガウスの消去法の操作は、 拡大係数行列[A b]では以下に対応する
ある行の定数倍をたの行に足す
行を入れ替える
行に0以外の数をかける
行基本変形をすることで上記のように変形でき、解を求めることができる
色のついていない部分はゼロ
変形後の行列を”階段行列”と呼ぶ
一般に、任意の行列Aは、行基本変形により、階段行列に変形することができる
得られた階段行列の「零ベクトルでない行ベクトルの個数」を”Aの階数”とよび”rankA”と書く
例
rankA = 2

1.4.2.3 次元定理

一次独立と一次従属
ベクトルbがベクトルa1,…,anと実数α1,…,αnを用いて、 b=α1a1+…+αnanと書けるとき
bはa1,..,anの”一次結合”で書けるという
一次独立・従属の定義
二つのベクトルa,bが”一次独立”であるとは
aがbの定数倍でなく、bもaの定数倍でない
三つのベクトルa,b,cが”一次独立”であるということは
どのベクトルも他の二つのベクトルの一次結合で書けない
どちらの場合も一次独立でないとき
“一次従属”である
ベクトルの特殊な位置関係
一次独立はベクトルの一般的な関係
定義
N個のベクトルa1,…,anが”一次独立”であるとは
どのベクトルも他のn-1個のベクトルの一次結合で書けないことを言う
一次独立でない時、一次従属であると言う
基本解と次元定理
命題
行列A、ベクトルbに対して、 連立一次方程式Ax=bが解を持つ時、 ベクトルpが存在して以下のどちらかが成り立つ
解はx=pのみである
一時独立なベクトルq1,…qlが存在して、以下が成り立つ
xはAx=bの解 ⇔ x=p + t1q1 +… +tlql (t1,…tlは実数)
pを特殊解
q1,…qlを基本解
階数と基本回に関する定理
行列A、ベクトルbに対して、 n変数連立一次方程式 Ax=b を考える
rank [A b] =rank A ならば以下が成り立つ
Ax=bは解を持ち、基本解の個数 = n – rank A
rank [A b] ≠ rank Aならば Ax=b は解を持たない
例
rank [A b] =3、　rank[A] =2
rank{A b] ≠ rank A
解を持たない
斉次連立一次方程式
右辺が0である連立一次方程式を”斉次連立一次方程式”と呼ぶ
Ax=0
rank A = r
(n-r)個の一次独立なベクトルv1,…,vn-rが Ax=0 を満たせば、それらは基本解である

1.4.3 逆行列、行列式と階数

逆行列と行列式の関係
定理1.22
行列Aが逆行列を持つ(Aが正則行列) ⇔ |A| ≠ 0
行基本変形の性質
定理1.23
以下の3つは同値である
n x n行列Aが逆行列を持つ(Aが正則行列)
|A| ≠ 0
rank A = 0
定理1.24
n x n行列Aの列ベクトルa1,…,anとする
|A| ≠ 0 ⇔ a1,..,anは一次独立
が成り立つ
行ベクトルにも同様のことが成り立つ
定理1.26
行列Aに対してrankA=rならば
行列式が0でない部分行列の大きさはrxr以下である
さらに、ちょうどrxrの大きさを持つ部分行列で、行列式が0でないものが存在する

1.5 固有値と固有ベクトル

1.5.1 固有値と固有ベクトル

概要
例
固有値と固有ベクトルの定義
任意の正方行列Aに対して、上記のようなベクトルが必ず存在することがわかっている
定義1.28
正方行列Aに対して、スカラーλとベクトルuが存在して
Au = λu , u≠0
λをAの固有値
uを固有値λの固有ベクトル
固有ベクトルを見つける方法
失敗列
成功例
固有値の求め方
固有ベクトルの求め方

1.5.1.1 3×3行列の固有値と固有ベクトル

1.5.2 行列の対角化

1.5.2.1 行列の対角化

例
対角成分以外が0である行列を”対角行列”と呼ぶ
ある正則行列Pと対角行列Dを用いて P-1AP=D とできる時
Aは対角化可能
対角化不可能な行列も存在する

1.5.2.2 対称行列の直行対角化

定義1.33
対称行列
tA=A
直交行列
tQQ=E
定理1.34
nxn対称行列は以下の性質を持つ
全ての固有値が実数
N個の固有ベクトルを持つ
異なる固有値に対する固有ベクトルは直交している
行列式と固有値
定理1.36
nxnの対称行列Aにおいて、固有値をλ1,λ2,…, λnとする
|A|=λ1λ2…λnが成り立つ

1.6 陰関数定理

関数が一つの場合
関数が複数の場合

第2章 凸関数

狙い
最適化の世界では「凸であるか」か「凸でないか」が問題の分かれ目になる
凸関数とは

2.1 凸関数の性質

2.1.1 凸関数の定義

“関数は十分滑らかである”とする
十分な回数微分可能で偏微分が連続である
例
2次関数f(x)=x2+bx+c
最小値を容易に求めることでできる
定義2.1
fをn変数関数とする
0<λ<1を満たす全てのλと、全てのu,v∈ℝnについて
f((1-λ)u + λv) ≤ (1-λ)f(u) + λf(v) が成り立つ時、fを”凸関数”と呼ぶ
-fが凸関数の時、fを”凹関数”と呼ぶ
“狭義凹関数も同様である
1変数凸関数と2変数凸関数
解説
狭義凸関数
0<λ<1に対して
(1-λ)u + λvは点u,vの内分点
(1-λ)f(u) + λf(v)は、値f(u),f(v)の内分点
図
点(u,f(u))と(v,f(v))を結んだ線分がfのグラフよりも上部にある
Fが凸関数
狭義凸関数でない凸関数の例
ABはグラフより上
CDはグラフ上
点(u,f(u))と点(v,f(v))を結んだ線分が、fのグラフ上、またはグラフより上部にある

2.1.2 凸関数と接平面

概要
1変数凸関数に接戦を引くと、接戦はグラフの下部に位置しグラフと交わることはない
接平面でも同様
2変数関数fが凸ならば、 全ての(a,b),(x,y) ∈ ℝ2に対して
f(x, y) ≥ f(a, b) +fx(a, b)(x-a) + fy(a, b)(y-b) が成り立つ
n変数関数においても同様のものが成り立つ
勾配ベクトル
定義2.2
2変数勾配ベクトル
N変数勾配ベクトル
例
凸関数と接平面に関数不等式
命題2.4
n変数関数fに関して、以下が成り立つ
Fが凸関数 ⇔ f(v) ≥ f(u) + ∇f(u)・(v-u)

2.2 凸関数の判定

2.2.1 凸性と微分

1変数関数、f(x)=x2は凸関数だが、f(x)=√(1+x2)は凸関数か?
定理2.5
1変数関数hに対して、以下が成り立つ
hが凸関数 ⇔ 全てのt∈ℝに対してh”(t) ≥ 0
2変数関数、g(x,y)=x2 – 2xy +2y2は凸関数か?
微分を用いて関数の凸性を調べることができる
ヘッセ行列
多変数の場合、1変数関数の1階微分に勾配ベクトルが対応し、2階微分にはヘッセ行列が対応する
定義2.6
2変数関数fと(x,y)に対して上記をヘッセ行列と呼ぶ
関数が十分滑らかならばfxy=fyxが成り立つ
例
f(x,y)=x3 + 2xy + 3y2の時
勾配ベクトルとヘッセ行列は
一般のn変数関数fとu={x1,…,xn)に対するヘッセ関数は
ヘッセ行列による条件
ヘッセ行列を用いると以下のような凸性の判定方法がある
定理2.7
N変数関数fに対して以下が成り立つ
(1) fが凸関数 ⇔ 各点a ∈ ℝnで、tu∇2f(a)u ≥ 0 が成り立つ
(2) fが狭義凸関数 ⇔ 各点a ∈ℝnで、tu∇2f(a)u > 0が成り立つ
例
f(x,y) = x2 – 2xy +2y2とすると
勾配ベクトルとヘッセ行列は
u=t(u1,u2)とする
tu∇2f(x,y)u=2u12 -4u1u2 *4u22
全てのベクトルuに対して正
よって凸関数である

2.2.2 行列の正値性

概要
2次形式
行列のアプローチ
定義2.9
行列Aとベクトルu=(u1,u2,…,un)に対して
U1,u2,…,unを変数にもつ多項式 p(u) = tuAu を”2次形式”と呼ぶ
例
行列Aに対してu=(x,y)とする
上記は2次形式である
行列Bとして上記のようにすると
上記も2次形式である
正値性の定義
定義2.11
行列Aを対称行列とする
tA=Aを満たす行列
例
全てのu∈ℝnに対して、2次形式がtuAu≥0を満たす時
Aを”半正定値”という
逆の符号が成り立つ時
Aを”半負定値”という
u≠0を満たす全てのu∈ℝnに対して、tuAu>0を満たす時
Aを”正定値”という
逆の符号が成り立つ時
Aを”負定値”という
U∈ℝnによってtUAuの符号が正にも負にもなるとき、Aを”不定”という
例
例1
2次形式(tuAu)=2×2+y2
2×2+y2>0なのでAは正定値
例2
2次形式=x2+2xy-y2
u=(1,0)では正となるが、u=(0,1)では負となり、Bは不定となる
凸関数の判定定理の再提(正値性を用いて)
定理2.13
関数fに関して以下が成り立つ
fが凸関数 ⇔ 各点a∈ℝnにおいて、ヘッセ行列∇2f(a)が半正定値である
fが狭義凸関数 ⇔ 各点a∈ℝnにおいて、ヘッセ行列∇2f(a)が正定値である

2.2.2.1 正値性の調べ方

概要
関数のヘッセ行列が各点で半正定値であれば、その関数は凸になる
行列が半正定値であるかどうかをどう調べるか?
線形代数を用いた一般的な方法
固有値を用いた判定法
Aを対称行列とすると、以下の主張が成り立つ
(1) Aが半正定値 ⇔ Aの固有値が全て0以上
(2) Aが正定値 ⇔ Aの固有値がすべて正
(3) Aが不定 ⇔ Aが性と負の固有値を持つ
例
f(x,y) = 3×2 -2xy +3y2とする
勾配ベクトルとヘッセ行列は
ヘッセ行列は定数行列であり、固有値は4.8
よってヘッセ行列は正定値で、fは狭義凸関数である
行列式を用いた判定法
正値性を調べたい行列が2×2行列であれば、以下のように行列式を用いて判定可能
定理2.16
(1) |A|>0かつa>0 ⇔ Aは正定値
(2) |A|>0かつa<0 ⇔ Aは負定値
(3) |A|<0 ⇔ Aは不定
例
f(x,y)=3×2 -2xy +3y2において
ヘッセ行列の正値性を行列式を元いて調べる
|∇2f(x,y)| =32 >0かつfxx(x,y)=6>0
よってヘッセ行列は正定値である

第3章 最適化問題

狙い
多変数関数の最小値、最大値を求める手法

3.1 最適化問題とは?

概要
最適化問題とは関数を最小化、または最大化する問題
例3.1
縦横の辺の長さの和が4となる長方形の中で、面積が最大になるのどのような長方形か?
最大化
f(x,y)=xy
制約
x+y=4,x≥0, y≥0
(制約付き)最適化問題
例3.2
平面に4点(1,3),(2,5),(3,5),(4,7)が与えられたとき、 これらの点の最も近くを通る直線は?
直線はy=ax+b
点(1,3)との直線との誤差は3-(1・a+b)
誤差の二乗の和の最小にする直線を求める
最小二乗法
最小化
f(a,b)={3-(a+b)}2 + {5-(2a+b)}2 + {5-(3a+b) + {7-(4a+b)}2
制約
なし
制約なし最適化

3.1.1 制約なし最適化問題

最小化する関数f(x):目的関数
最適解の定義
制約なし最小化問題に対する最適解の定義
定義3.3
ẋが全てのx∈ℝnに対してf(x)≥f(ẋ)の時、 f(ẋ)を大域最小値、ẋを大域最小解と呼ぶ
一般的に大域最小解を見つけることは難しいので、 局所解を見つける手法を使う
定義3.4
Ẋに十分近い全てのx∈ℝnに対して f(x) ≥f(ẋ)の時、 f(ẋ)を局所最小値、ẋを局所最小解と呼ぶ
例3.5
最小化 f(x)=x2+2x+3
f(x)=x2+2x+3=(x+1)2+2
f(x)≥f(-1)=2 (全てのx)
x=2は術の実数xに対して、最小の値を与える
大域最小解
例3.6
最小化 f(x)=x3-x
大域最小解は存在しない
局所最小解
極値問題
微分積分で扱う極値問題も最適化問題
定義3.7
x≠ẋを満たし、 ẋに十分近い全てのxに対してf(x)>f(ẋ)が成り立つ時、 fはẋで極小値を取ると言う
x≠ẋを満たし、 Ẋに十分近い全てのxに対してf(x)<f(ẋ)が成り立つ時、 fはẋで極大値を取ると言う
極大値と極小値をまとめて”極値”と呼ぶ
最適値と極値の関係
例3.8 極小値にならない最小値
最小化 f(x,y)=x2 + 2xy +y2
f(x,y)=(x+y)2より全ての(x,y)に対してf(x,y)≥0となる
f(0,0)=0より
0はfの大域最小値、(0,0)はfの大域最小解となる
(x,y)=(t,-t)と言う点の上では全てfは0になる
f(0,0)と同じ値をとる点があるので、fは(0,0)で極小値を取らない
最小解が一意ではない

3.2 最適条件

概要
最適解の性質と関数のグラフとの関係
最大化問題は目的関数に(-1)をかけると最小化問題になる

3.2.1 1次の最適性条件

1変数関数の場合は増減表より最適解が求まる
1変数関数の定理3.9
1変数関数f(x)に対して、点aが局所最適解ならばf'(a)=0となる

3.2.1.1 多数関数

多変数関数では増減表が書けない
以下のような1変数関数と同様の性質が成り立つ
定理3.10 1次の最適性条件
点ẋが局所最適解ならば∇f(ẋ)=0が成り立つ
定理3.11 点pが、∇f(p)=0を満たす時、pをfの”停留店”と呼ぶ
局所最適解が存在すれば、それは常に停留点になる
よって、停留点を全て見つければ最適解は必ずその中にある

3.2.1.2 停留点の幾何学的イメージ

例
最小化 f(x,y)=x3 – 3xy +y3の局所最小解を(x,y)=(alb)とする
目的関数の勾配ベクトルは
局所最小解である(x,y,z)=(a,b,f(a,b))はグラフのどこにあるのか?
点(alb,f(alb)はグラフが下に窪んだ部分の一番底に位置している
窪みの一番底に接する平面を描くと、水平な平面になる
点(alb)におけるfの接平面
z=f(a,b) + fx(a,b)(x-a) + fy(a,b)(y-b)
平面は水平なので、任意の(x,y)に対して接平面の式のz座標は一定値f(a,b)
よってfx(a,b)=fy(a,b)=0
∇f(a,b)=0

3.2.2 停留点と局所最適化

局所最適解ならば停留点となるが、停留点であっても、局所最適解とは限らない
例
最小化 f(x,y)=x2-y2
∇f(0,0)=0となるが局所最小解ではない
f(0,0)は最も小さい値になっていない
3.2.3 2次の最適性条件
停留点の中からどのように局所最適解を見つけるのか?
グラフからの推測
最小化 f(x,y)=x3 -3xy +y3
各点の勾配ベクトル
Fの留意点を計算すると(0,0)と(1,1)
グラフを見ると(0,0)はグラフがねじれた点、(1,1)は下に窪んだ点にある
(1,1)が局所最小解
ヘッセ行列を用いた判定法
目的関数fの式から各留意点が局所最小解かどうかを知るためには?
停留点ẋを局所最小解とすると、点ẋにおいて、少なくともグラフは下に窪んでいる
Ẋで下に窪んでいる ⇔ 点ẋの近くで関数fは「局所的に凸関数である」
定理3.13 2次の最適性条件
(1) (必要性) ẋが局所最小解である ⇒ ∇f(ẋ)=0かつ∇2f(ẋ)が半正定値
(2) (十分性) ∇f(ẋ)=0かつ∇2f(ẋ)が正定値 ⇒ ẋは局所最小解である。さらにそこで極小値をとる
(3) (否定) ∇2f(ẋ)が不定値の時、ẋは局所最適解ではない
2次の最適性条件の幾何学的イメージ
グラフとヘッセ行列の正定値性との関係
最適性と2次の条件の関係
2次の最適性条件でわからない最適解
(ロ)を満たさなくても最小解になることがある
例
最小化 f(x,y)=x4+y4
勾配ベクトルとヘッセ行列
停留点は(0,0)
(0,0)でのヘッセ行列は零行列
(ロ)を満たさない
任意の(x,y)でf(x,y)≥0なので(0,0)は大域最小解
(x,y)≠(0,0)の時、f(x,y)>0なので、(0,0)は極小解

3.3 局所最適解の求め方

例1
最小化 f(x,y)=x2+xy+y2-9x-9y+27の局所最適値
停留点を求める
勾配ベクトル
連立方程式の解
(x,y)=(3,3)
この点に対して、2次の最適性条件を調べる
ヘッセ行列を計算する
(x,y)=(3,3)の時
この行列の正値性を調べる
解法1
行列∇2f(3,3)の固有値を求めると1,3となるので、 定理より∇2f(3,3)は正定値である
解法2
fxx(3,3)>0かつ|∇2f(3,3)|>0なので、定理より行列∇2f(3,3)は正定値である
よって(3,3)は局所最小解であり、局所最小値はf(3,3)=0である
例2
f(x,y)=x3-3xy+y3の局所最適値を求める
勾配ベクトルとヘッセ行列を求める
停留点を求める
停留点は(x,y)=(0,0),(1,1)となる
ヘッセ行列の定値性を調べる
(0,0)ではヘッセ行列の行列式は、|∇2f(0,0)|<0を満たす
ヘッセ行列は不定値
局所最適解ではない
(1,1)ではfxx(1,1)=6>0かつ|∇2f(1,1)|=27>0
ヘッセ行列は正定値
局所最小解
局所最初値は-1
符号の表
概要
例3
f(x,y)=x3 + y3 -6x -6yの局所最適値は?
勾配ベクトルとヘッセ行列は
連立方程式
停留点(x,y)=(±√2, ±√2)
符号と最適性の関係
(x,y)=(√2,√2)の時、局所最小値-8√2
(x,y)=(-√2,-√2)の時、局所最大値8√2をとる
局所最適解は全て求まっているか?
最後の例では停留点が4つ求まり、局所最適解は存在すれば全てこの4つの中にある
局所最適値と極値
極値は局所最適値の中でも特別なもの

3.4 凸性と最適解

2次の最適性条件を調べても、ある点ẋが局所最適解であることしかわからない
大域最適解を見つけるためにはどうすれば良いか?
関数が凸であれば大域最適解を簡単に見つけられる
定理3.18
N変数関数fを凸関数とすると、fの留意点は大域最小解になる

3.5 定理3.13の証明

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

概要
制約のついた最適化問題にはラグランジュ乗数法という解法がある
一般的な場合に用いるKKT条件もある

4.1 制約付き最適化問題

例
最大化 f(x,y) := xy
制約 x+y=4, x≥0, y≥0
xy=x(4-x)=-x2+4x=-(x-2)2+4
A:(1,3)→B:(2,2)→C:(3,1)
制約付き最小化問題の定義
制約付き最小化問題
最小化 f(x)
制約 x∈C
集合Cを数ベクトル空間ℝnの部分集合
集合Cを”実行可能領域”
Cの点を”実行可能解”
「x∈C」とは「xがCに含まれる」ことを意味する
定義4.2
Ẋ∈Cがẋに十分近いC上の全てのxに対してf(x)≥f(ẋ)の時、 ẋをを局所最小解、f(ẋ)を局所最小値と呼ぶ
定義4.3 ẋ∈CがC上の全てのxに対してf(x)≤f(ẋ)の時、 ẋを大域最小解、f(ẋ)を大域最小値と呼ぶ
概念図

4.2 等式制約が１つの場合

概要
2変数関数f(x,y)を円周上で最小化する問題

4.2.1 曲線状の減衰表

目的関数の等高線を用いて、実行可能領域上での目的関数の変化を調べる
1次関数を円周上で最適化
円周上で一次関数を最小化または最大化
最小化または最大化 f(x,y):=x+y
制約 x2+y2=1
直線ℓ2はf(x,y)=x+y=-1を満たす直線
fの等高線
ℓ1,ℓ3もある値に対するfの等高線
円と𝓁2の関係
図で点がA→B→Cと動く時、関数fの値は
等高線𝓁2と円の交点は局所最適解にはならない
円と𝓁3の関係
等高線𝓁3と円の接点付近
(-1/√2, -1/√2)で(x,y)の値は一番小さくなる
(-1/√2, -1/√2)が局所最小解
等高線𝓁1は局所最大解
一般の関数を円周上で最適化
1次関数ではない、一般の関数の最適化
目的関数の等高線と実行可能領域の関係(その1)
等高線と実行可能領域が交わる
局所最適解ではない
等高線と実行可能領域が接する
局所最適解になる
目的関数の等高線と実行可能領域の関係(その2)
等高線と実行可能領域が交わる
局所最適解ではない
等高線と実行可能領域が接する
局所最適解

4.2.2 ラグランジェ乗数法

一般の関数を一般の曲線上で最適化
局所最適解で目的関数の等高線と実行可能領域は接する
定理4.4 ラグランジュ乗数法
最小化または最大化 f(x)
制約 g(x)=0
Ẋを局所最適解とする
∇g(ẋ)≠0ならば、ある数λが存在して
∇f(ẋ) = λ∇g(ẋ), g(ẋ)=0が成り立つ
勾配ベクトルと等高線
勾配ベクトルと等高線とは直行する
「直交する」とは
勾配ベクトルとそこでの等高線の接戦が直行していること
関数fのグラフz=f(x,y)と(a,b)における接平面 z=f(a,b)+fx(alb)(x-a)+fy(a,b)(y-b)を考える
点(a,b,f(a,b))を通りxy平面に並行な平面z=f(a,b)でfのグラフと接平面を切った時の断面
等高線の接戦の式
fx(a,b)(x-a) + fy(a,b)(y-b) = 0
勾配ベクトル∇f(a,b)と等高線の(x,y)=(a,b)における接戦が直交している
勾配ベクトルは関数値が増える方向を向いている
制約付き停留点
最適解の存在定理

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

例
前提条件
最小化 f(x,y):=x-y
制約 g(x,y):=2×2+3y2-1=0
ラグランジュ乗数法より、局所最適解は上式を(x,y),λについて解いた時の(x,y)に含まれている
目的関数と制約条件の勾配ベクトル
式は
上式を満たす(x,y),λを見つければ、(x,y)が停留点になる
停留点(x,y)=(±√(3/10), ∓√(2/15))
fに停留点を代入
大域最小解(-√(3/10),√(2/15))
大域最小値(-√(3/10-√(2/15))
例
前提条件
最小化 f(x,y):=x-y+z2
制約 g(x,y,z):=x2+y2+2z2-1
目的関数と制約式の勾配ベクトル
式は
z=0の時
(x,y,z)=(±1/√2, ∓1/√2, 0)
z≠0の時
解にはならない
例
前提条件
目的関数と制約条件の勾配ベクトル
式は
停留点はAの固有ベクトルと一致する

4.3 等式制約が複数の場合

4.3.1 制約が２つの場合

定理4.10 最小化問題
最小化 f(x)
制約 g1(x)=0, g2(x)=0
Ẋを局所最小解とする
∇g1(ẋ), ∇g2(ẋ)が一時独立ならば、 ある数λ1,λ2が存在して、以下が成り立つ
∇f(ẋ)= λ1∇g1(ẋ) + λ2∇g2(ẋ)
g1(‘ẋ)=0, g2(ẋ)=0
実行可能領域図
最小化
f(x,y,z) =αx + βy + γz +δ
制約
g1(x,y,z)=x2+y2+z2-1=0
g2(x,y,z)=x+y+z-1=0
実現可能領域は、球面と平面との共通部分
空間のえん
等高面
3変数関数が同じ値をとる点(x,y,z)の集合 f(x,y,z)=(定数)
等高面
勾配ベクトルと等高面は直交する
局所最適解で目的関数の等高面は、実行可能領域と接する
実行可能領域と接する平面
目的関数の等高面と実行可能領域が「接する」とは どのような位置関係にあるのか?
実行可能領域に接する平面の法線ベクトルはλ1∇g1(a,b,c) + λ2∇g2(a,b,c)
(A,b,c)は局所最小解
⇒ 局所最小解で目的関数の等高面と実行可能領域は接する
⇒ 目的関数の勾配ベクトルは∇f(a,b,c)=λ1∇g1(a,b,c) + λ2∇g2(a,b,c)

4.3.2 制約数が一般の場合

制約数が任意の個数の場合は以下のようになる
定理4.11 最小化問題
最小化 f(x)
制約 g1(x)=0,g2(x)=0,…,gm(x)=0
Ẋを局所解とする
g1(ẋ),…gm(ẋ)が一時独立ならば、ある数λ1,..,λmが存在して
∇f(ẋ) = λ1∇g1(ẋ) +…+ λmgm(ẋ)
g1(ẋ) = 0, g2(ẋ) = 0, …,gm(ẋ) = 0

4.4 2次の最適性条件

概要
制約付き最適化問題で2階微分を用いて、最適解の十分条件を考える
点ẋが、最小化 f(x)、制約 g(x)=0の局所最適解らなる条件について
目的関数の等高線と実行可能領域が接している場合
Bは局所最小解になる
目的関数の等高線が接していても、接点でねじれている場合
Bは局所最小解にならない
局所最適解にならない停留点の例
まず簡単な最適化条件の定理
定理4.12 最適化問題
最小化 f(x)
制約 g1(x)=0,g2(x)=0,…,gm(x)=0
ある実数λ1,…,λmに対して、 ẋが上記の式を満たす時、 ẋは局所最小解である

4.4.1 2次の最適性必要条件

定理4.13 最小化問題
最小化 f(x)
制約 g1(x)=0,g2(x)=0,…,gm(x)=0
局所最小解をẋとする
∇g1(ẋ),…∇gm(ẋ)が一時独立ならば、 ある数λ1,..,λmに対して、以上が成り立つ
定義4.14
点ẋを集合C上の点とする
あるε>0に対して、(-ε, ε)上のベクトル関数u(t)=(u1(t),…un(t))で u(0)=ẋ、u(t)∈Cを満たすものが存在する時
ベクトルu'(0):=[u1′(0)….un'(0)]をCのẋにおける”接ベクトル”と呼ぶ
解説例
Cがx2+y2+z2=1を満たす集合

4.5 不等式制約問題

概要
等式と不等式を持つ場合の制約について
例4.17 投影問題
平面4x+y+2z=2
単位球の内部x2+y2+z2≤1
上記の共通部分で、点(2, 3, 4)までの距離が一番近い点を求める
定式化
最小化
f(x,y,z):=(x-2)2+(y-3)2+(z-4)2
制約
g1(x,y,z):=x2+y2+z2-1≤0
g2(x,y,z):=4x+y+z-2=0

4.5.1 不等式が１つの場合

制約式が円周と内部を表す不等式一つのみの場合
最小化
f(x,y)
制約
g(x,y):=x2+y2-1≤0
(a,b)を上記の条件での局所最小解とすると、 次の二つの場合が考えられる
(a,b)が円の内部にある(g(a,b)< 0)の場合
∇f(a,b)=0が成り立つ(通常の留意点)
(a,b)が円周上にある(g(a,b)=0)の場合
ある実数λが存在して
-∇f(a,b)=λ∇g(a,b) かつλ>0
勾配ベクトルの向きと不等式領域
定理4.18 最小化問題
最小化
f(x)
制約
g(x)≤0
Ẋが局所最小解であり、 ∇g(ẋ)≠0ならば、 ある数λが存在し、 以下が成り立つ
-∇f(ẋ) = λ∇g(ẋ)
λg(ẋ) = 0, λ≥0
g(ẋ) ≤ 0
例
最小化
f(x,y) = x2 + 6xy + y2
制約
g(x,y)= x2 + y2 -1 ≤ 0
定理4.18より
をx,y,λについて解く
x2+y2-1<0の場合
上式を満たすものは
λ=0
(x,y)=(0,0)
x2+y2-1=0の場合
上式を満たす点を探す
固有値問題を解いて答えを得る
λ>0を満たすものは
(x,y) = (0,0), (±1/√2, ∓1/√2)
それぞれにおける目的関数fの値を調べる
最小値はf(±1/√2, ∓1/√2)=-2
点(±1/√2,∓1/√2)で -∇f(x,y)が直交外側を向いている

4.5.2 不等式が複数ある場合

定理4.20 最小化問題
最小化
f(x)
制約
g1(x)≤0, g2(x)≤0
に対して、ẋが局所最小解であり、 {∇g1(ẋ), ∇g2(ẋ)}が一次独立であるとする
ある数λ1,λ2が存在して
-∇f(ẋ) = λ1∇g1(ẋ) + λ2∇g2(ẋ)
λigi(ẋ) = 0, λi ≥ 0
gi(ẋ) < 0 (i=1,2)

4.5.3 制約に不等式と等式がある場合(KKT条件)

定理4.21 最小化問題
最小化
f(x)
制約
g1(x)≤0, g2(x)≤0
h(x)=0
に対して、ẋが局所最小解であり、 {∇g1(ẋ), ∇g2(ẋ), ∇h(ẋ)}が一次独立であるとする
ある数λ1,λ2,μが存在して
-∇f(ẋ) = λ1∇g1(ẋ) + λ2∇g2(ẋ) + μ∇h(ẋ)
λigi(ẋ) = 0, λi ≥ 0, gi(ẋ) ≤ 0
μ:任意, h(ẋ)=0
例
最大化
f(x,y,z)=αx + βy + γz +δ
制約
g1(x,y,z)=x2+y2+z2-1≤0
g2(x,y,z)=-x-1/2≤0
h(x,y,z)=x+y+z-1=0
実行可能領域例

4.5.4 例題

例
最小化
f(x,y,z):=(x-2)2 + (y-3)2 +(z-4)2
制約
x2 + y2 + z2 ≤ 1
4x + y+ 2z = 2
KKT条件

4.6 凸計画

目的関数も制約式も全て凸関数である問題を”凸計画”と呼ぶ
定理4.24
最小化
f(x)
制約
gi(x) ≤ 0 i=1,…,m
f,gは凸関数であるとする
ẊがKKT条件を満たせばẋは大域最小解である

第5章 線形計画問題

狙い
線形計画法とは、目的関数と制約式が全て1次しきであるような最適化問題
変数と制約式の数がともに数千個あるような場合でも、コンピューターを持ちして高速に解を求められる

5.1 線形計画問題とは

線形計画法とは、目的関数と制約式が全て1次しきであるような最適化問題
例
ある工場で製品1、製品2を生産する
製品1は原料Aを1kg、原料Bを3kg使用し、8万円で売れる
製品2は原料Aを1kg、原料Bを1kg使用し、6万円で売れる
原料Aが4kg、原料Bが6kgある時、製品1と製品2をいくつづつ作れば利益が最大になるか?
まとめの表
最適化問題で定式化
製品1の個数をx1、製品2の個数をx2
最小化
-8×1-6×2 (利益)
最大化問題点だが、目的関数を(-1)倍すれば、最小化問題になる
制約
x1 + x2 ≤ 4 (原材料Aの在庫)
3×1 + x2 ≤ 6 (原材料Bの在庫)
x1, x2 ≥ 0

5.2 単体法

概要
最適化問題の定式化
最小化
-x1 -2×2 -3×3
制約
x1 +x3 ≤ 2
2×1 + x2 + 2×3 ≤ 5
3×1 + x2 +2×3 ≤ 6
X1, x2, x3 ≥ 0
実行可能領域と等高面

5.2.1 単体法の概要

実行可能領域の頂点が道の場合のアプローチ
単体法
単体法の主要な操作

1 スラック変数を導入する

x4, x5, x6を導入
同値な問題に変形
最小化
– x1 – 2×2 – 3×3
制約
x1 + x3 + x4 = 2
2×1 + x2 + 2×3 + x5 = 5
3×1 + x2 +2×3 + x6 = 6
X1, x2, x3 ,x4, x5, x6≥ 0
実行可能解
制約式の変形
x4=0,×5=0より
二つの平面x1+x3=2, 2×1+x2+2×3=5上の点

2 辞書を作る

スラック変数x4,x5,x6を左辺に残し、残りを右辺へ移項し、目的関数をzとおく
辞書1
最小化
z = – x1 – 2×2 – 3×3
制約
x4 = 2 – x1 – x3
x5 = 5 – 2×1 – x2 – 2×3
x6 = 6 – 3×1 -x2 -2×3
X1, x2, x3, x4, x5, x6 ≥ 0
左辺に現れる変数x4,x5,x6を”基底変数”
基底変数は目的関数の変数に含まれていない
右辺に現れる変数x1,x2,x3を”非基底変数”

3 実行可能規定解を求める

辞書の非基底変数x1,x2,x3を全て0として得られる実行可能領解
実行可能基底解
目的関数z=0
実行可能解の多面体の頂点

4 解の更新

解の更新ルール
非基底変数の中から、 目的関数において係数が負であるものを一つ選び、 その値をt、その他の非基底変数の値を0とおく
全ての基底変数が負にならない範囲で、 上記で選んだ非基底変数の値tを最大まで増やす
更新ルール1
係数が負である非基底変数をtとし、その他を0とする
更新ルール2
X4,x5,x6が負にならない最大のtはt=2
新しい実行可能解
代入すると
新しい実行可能解で目的関数は減少
解の更新ルールの図形的意味

5 辞書の更新

元の実行可能解と新しい実行可能解の比較
非基底変数x3を規定変数に、 基底変数x4を非基底変数に入れ替えた 新しい辞書を作成
x3 = 2 – x1 -x4
上式を全ての式に代入
辞書2
最小化
z = -6 + 2×1 -2×2 +3×4
制約
x3 = 2 – x1 – x4
x5 = 1 – x2 + 2×4
x6 = 2 – x1 – x2 +2×4
x1,x2,x3,x4,x5,x6≥0
辞書2は新しい実行可能解を実行可能規定解に持つ辞書である

6 4,5の反復

反復一回目
辞書2の非基変数x1,x2,x4
目的関数の係数が負であるのはx2のみ
x2=t
その他の非基底変数x1,x4=0
変数x2=tを増加させる
x2が基底変数、x5が非基底変数になるように辞書を更新
新しい辞書3
反復二回目
新しい実行可能解
新しい辞書4
目的関数の変数の係数が全て0以上になっているので解の更新を終了

7 単体法の終了

全ての変数が0以上という制約があるので、 辞書4の最適値はx1=x3=x5=0の時-10
辞書4の最適解
最適値-10
元の問題の最適解
最適値-10
考察
頂点の位置が分かっていれば、簡易に計算が可能
ピボット
単体法の簡便な計算方法
辞書1の書き換え
左辺にx4がある式のx3を”ピボット”とよび丸で囲む
制約第2式の右辺からx3を消す
他の式にも適用し新しい辞書を作る

5.2.2 例題

最小化
– x1 – 2×2
制約
x1 + x2 ≤ 3
– 2×1 + x2 ≤ 2
x1,x2≥0
スラック変数を導入して辞書を作る
辞書1
最小化
z = – x1 – 2×2
制約
x3 = 3 – x1 – x2
x4 = 2 + 2×1 1 x2
x1,x2,x3,x4≥0
D1
ピボット
新しい辞書
新しい辞書
目的関数の係数が全て0以上であるので解の更新は終了
D3の最小解は(1/3, 8/3, 0, 0)
元の問題の最小解(1/3,8/3)、 最小値は-17/3

5.2.3 例外処理

(1) 問題が非有界
線形計画問題が最適解を持たない場合
実行可能領域が空集合
目的関数をいくらでも小さくできることができる場合
例
最小化
-x1
制約
X1 – x2 ≤ 1
-x1 + x2 ≤ 1
X1,x2≥0
スラック変数を導入して辞書を作る
目的関数の変数で係数が負のものはx2
制約式ではx2の係数は正、または0なので、x2の値はいくらでも大きくできる
目的関数をいくらでも小さくできるので、最適解は存在しない
実行可能領域が非有界でも問題が非有界とは限らない
(2) 辞書の退化
非有界な問題とは逆に非規定変数の値を全く増やせない場合もある
例
最小化
-x1
制約
x1 – x2 ≤ 0
x1 + x2 ≤ 2
x1, x2 ≥ 0
単体法を適用するために、辞書を作成
目的関数の変数で係数が負のものはx1のみ
x1を0から少しでも大きくすると、 x3が負になるので、 x1は少しも増加させることができない
x3とx1を入れ替えて辞書を作成
D1では増加できる非規定変数x2が存在する
全ての係数が0以上になるので終了
最適値は-1、最適解は(1,1)となる
(3) 辞書の巡回
退化した辞書を更新しても、 退化しない辞書を得ることができず、 辞書を更新しても退化した状態が無限に続く場合
巡回
巡回を避けるためには、 解と辞書を更新する際に、 “ブランドのピボット選択法”を用いる
解の更新ルールで非基底変数をえらぶときに、添字が最小のものを選ぶ
選んだ非基底変数を増やすことで0になる規定変数が複数ある場合、 それらの中で添字が最小のものを選ぶ
ブランドのピボット選択法を使うとアルゴリズムが非常に遅くなる
(4) 初期点が実行不可能
単体法では、辞書の非規定変数全てに0を代入し、実行可能基底解を得るが
上記が実現可能でない場合がある
例
最小化
-x1
制約
x1 – x2 ≤ -1
x1 + x2 ≤ 2
x1, x2 ≥ 0
辞書
非規定変数x1,x2に0 0 0を代入すると (x1, x2, x3, x4)=(0, 0, -1, 2)
実行可能解を得られない
この場合は、はじめに実行可能解(辞書)を探す必要がある
元の問題の目的関数を無視
制約式に新しい変数x5を入れる
最小化
z = x5
制約
x5 = 1 + x1 -x2 + x3
x4 = 2 + 2×1 -x2
x1,x2,x3,x4,x5 ≥ 0
目的関数は x5 = x3 – (-1 – x1 + x2)
D1の制約第一式の両辺の差
5.3 線形計画問題の一般化
概要
行列とベクトルを用いて表現が可能

5.3.1 線形計画問題の変形

(1) 最大化問題の場合
(2) 制約が等式の場合
(3) 変数に変数がない場合

5.4 双対問題

5.4.1 双対問題

線形計画問題には、双対問題と呼ばれる裏に隠されたもう一つの問題がある
例: 栄養問題
栄養素には1日の最低摂取量が決められている
食品1, 2には主に2種類の栄養素が含まれている
それぞれ、各栄養素の最低摂取量と食品の価格が決まっている
問題
消費者の視点
必要な栄養を摂りながら食費を最小にするには、 どのような割合で二つの食品を購入すれば良いか?
定式化(P0)
最小化
3×1 + x2
食費最小化
制約
4×1 + 3×2 ≥ 7
栄養Aの摂取量
5×1 + 2×2 ≥ 8
栄養Bの摂取量
x1, x2 ≥ 0
ビタミン剤を作る製薬会社の視点
通常の食品より安く栄養を取れるように ビタミン剤の価格を抑えながら、売り上げを最大にするには、 ビタミン剤の価格をどのように設定すれば良いか?
定式化(D0)
ビタミン剤Aとビタミン剤Bをそれぞれ栄養素Aと栄養素Bのビタミン剤とする
ビタミン剤の単位辺りの価格をy1,y2とする
最大化
7y1 + 8y2
売り上げ
制約
4y1 + 5y2 ≤ 3
価格を商品1以下に
3y1 + 2y2 ≤ 1
価格を商品2以下に
問題P0と問題D0の関係
P0の目的関数
3×1 + x2
≥ (4y1 + 5y2)x1 + (3y1 + 2y2)x2
= (4×1 + 3×2)y1 + (5×1 + 2×2)y2
≥ 7y1 + 8y2
D0の目的関数
「消費者の食品購入費(3×1 + x2)」≥「製薬会社のビタミン剤の売り上げ(7y1 + 8y2)」
消費者一人当たりの「製薬会社のビタミン材の売り上げの最大値」は 「消費者の食品購入費の最小値」を超えられない
双対問題の定義
食費最小化問題(P0)は、 ベクトルと行列を使うと
具体的な数値を記号で置き換えると
定義5.3
問題(P)に対して、 係数を入れ替えた以下の問題(D)を双対問題と呼ぶ
双対問題(D)に対して、元の問題(P)は主問題と呼ばれる

5.4.2 双対定理

双対問題は、 栄養問題だけではなく 一般の線形計画問題において、 重要な役割を持つ
例
「生産コスト最小化」と「工場の買収価格」
定理5.4 双対定理
(P)
最小化
tcx
制約
Ax ≥ b
x ≥ 0
(D)
最大化
tby
制約
tAy ≤ c
y ≥ 0
主問題(P)と双対問題(D)に実行可能解が 少なくとも一つつづ存在するならば
(P)と(D)にそれぞれ最適解x*, y*が存在し
tcx*(Pの最小値) = tby*(Dの最大値)が成り立つ
栄養問題における双対定理の解釈
この定理を栄養問題に適用すると
「製薬会社のご多眠剤の売り上げの最大値」=「消費者の食品購入費の最小値」
様々な主問題と双対問題
例

5.4.3 潜在価格

例
工場で製品1、製品2を作っている
各製品の価格と必要な原材料A、 Bの量は上記のようになっている
Q1:在庫を考慮しながら、各製品をいくつずつ作れば利益が最大になるか
製品1の個数をx1、製品2の個数をx2とする
定式化(P)
最大化
8×1 + 6×2
制約
x1 + x2 ≤ 4
3×1 + x2 ≤ 6
x1, x2 ≥ 0
(P)に単体法を適用すると解は(x1, x2) = (1, 3), 最適値26
Q2:原材料Aか原材料Bのどちらかの在庫を1kgだけ増やせるとしたら、 どちらを増やした方が最大利益が増えるか?
定式化(P1)
最大化
8×1 + 6×2
制約
x1 + x2 ≤ 4 (+ 1)
在庫を1kgだけ増やす
3×1 + x2 ≤ 6 (+ 1)
在庫を1kgだけ増やす
x1, x2 ≥ 0
双対問題の解の役割
(P)を主問題として、 双対問題(D)を作る
最小化
4y1 + 6y2
制約
y1 + 3y2 ≥ 8
y1 + y2 ≥ 6
X1,x2 ≥ 0
(D)を単体法で計算すると (y1,y2) = (5,1)
双対問題(D)は以下の性質を持つ
(P)の一つ目の制約式の右辺を1増やすと、最適値は5(y1の値)増える
(P)の二つ目の制約式の右辺を1増やすと、最適値は1(y2の値)増える
原材料Aの在庫を1増やしたほうが最大利益の増加が大きい
潜在価格
双対問題の解y1は原材料Aの隠された価値を表す
Y1は原材料Aの”潜在価格”と呼ばれる

5.5 ファルカスの補題

5.5.1 ファルカスの補題

ファルカスの補題 (Farkas’s lemma)
連立線形不等式に関する基本定理
これを用いて双対定理を証明することができる
補題5.7 ファルカスの補題
(F1)の幾何学的な意味
定義5.8
(F2)の幾何学的意味
ファルカスの補題の幾何学的意味

5.5.2 双対定理の証明

定理5.4

5.5.3 フーリエ・モツキンの消去法

ファルカスの補題の証明方法
フーリエ・モッキンの消去法 (Fourier-Motzkin elimination)
連立線形不等式の変数消去を行うアルゴリズム
凸多面体に対する射影定理
不等式の増加数

5.5.4 ファルカスの補題の証明

ファルカスの補題の変形
ファルカスの補題の証明

第6章 変分問題

概要
通常の最適化問題では「点の集合」から関数を最小にするような点を求める
変分問題とは「関数の集合」から汎関数と呼ばれる別の関数の値を最小にする関数を求める
例
2点を結ぶ線分の中で長さが最小のものはどんな線分か?
2点を結ぶ線分の集合が関数の集合
線分の長さが汎関数の値

6.1 変分問題

概要
関数y(x)が表す曲線のx=0からx=1までの長さ
「関数のグラフの長さ」は「関数を変数に持つ関数」になる
汎関数
関数を変数に持つ関数
変分問題
汎関数を最小化または最大化する問題
変分問題の例
例 最速降下線
二つの地点をつなぐ滑り台で最も降りるのが早いものの形は?
xy平面でy軸を下向きにとる
質点が(a,o)から(b,B)までy軸方向に重力と滑り台からの反発力を受けて移動する
最も早く(b,B)に到達する滑り台の形は?
滑り台の形を関数y(x)のグラフで表す
重力による加速をgとおくと、 質量mの質点がy(x)まで下がった時の速さvは エネルギー保存則よりo=mv2/2 – mgy(x)
v=√(2gy(x))
微小区間における曲線の長さは√(1+y'(x)2)∆x
速さで割ることで時間は
この汎関数を最小にする関数のグラフが最速な滑り台の形を表す
例 懸垂線
両端が同じ高さの柱に結ばれたロープがどのような形で垂れ下がるのか?
両端の高さをh、ロープの長さをℓ、単位長さあたりの質量をm
x座標を水平方向、y座標を垂直方向
ロープの形をy(x)という関数のグラフで表し、両端の座標をa,bとする
ロープは一エネルギーを最小にするような形をとる
位置エネルギー
を長さの条件のもとで最小化
例 人員計画問題
ある仕事の量を扱うのに必要な人員数を維持しながら、 人件費をなるべく少なくできる人員計画を立てたい
時期xにおける仕事量をs(x)、人員数をy(x)とする
人件費を上式のように定義
給与は人員数に比例するのでy(x)の一次式
雇用と解雇に必要な費用は高額になるので、人員の増加率y'(x)の2次式と仮定
最適な人員計画

6.1.1 汎関数

概要
単純な変分問題
汎関数Fに具体的な関数を代入して、値を計算する
y1(x)=xのとき
y2(x)=x2のとき
F(y2)>F(y1)
F(y)の値を一番一作するにはどのような関数y(x)か?を考えるのが変分問題
発見的に最小解を見つける
積分に関する性質の利用
汎関数Fの値は全てのy(x)に関して0以上
Fの値を0にするようなy(x)が最小
ȳ(x)=1(定数関数)とする
F(ȳ(x))=0
最小
ȳ(x)=1は目代の最小解となる
関数の微分に依存する汎関数
問題
積分の中にy'(x)があること、 積分区間が[1,2]であること、 制約がついていることに注意
全てのFに対して0以上
Fの値を0とするような制約を満たす関数f(x)を探す
Fの値を0にするには
y'(x)=1であれば良い
制約:y(1)=2, y(2)=3
ȳ(x)=x+1であれば全てを満たす
最小解
変分問題の一般解
一般形
最小化
F(y)
目的関数
制約
y∈C
関数y(x)が関数の集合Cに入っている
定義6.4
関数ȳ(x)∈Cが全ての関数y(x)∈Cに対してF(y)≥F(ȳ)を満たす時
ȳ(x)を問題の”大域最小解”と呼ぶ
定義6.5
関数ȳ(x)∈Cがȳ(x)に十分「近い」全てのy(x)∈Cに対してF(y)≥F(ȳ)を満たす時
ȳ(x)を問題の”局所最小解”と呼ぶ
関数の近さ
関数ȳ(x)に「近い」関数とは
ȳ(x)とグラフが近い関数のことを示す
例
関数v(x)と十分小さいεに対して
Ȳ + εv(x)を考える
ȳ(x)のグラフが少し変化したものになさっているのでȳ(x)に「近い」関数である
ノルム
関数の近さを数学的に定義する方法の一つ
ノルム
関数の近さをを測るのに、どのノルムを使うかによって問題の性質が異なる
制約を満たし「近い」関数
制約 y(0)=0, y(1)=1がある場合
被積分関数
3変数関数f(x,y,z)に対しての汎関数
f(x,y,z)のy変数にy(x), z変数にy'(x)を代入
fを”被積分関数”と呼ぶ
例
目的関数
の被積分関数はf(x,y,z)=(y-1)2
目的関数
の被積分関数はf(x,y,z) = y +1/2z2
汎関数の省略記号
f(x,y(x),y'(x))=f[y(x)]と書く
関数の括弧に”[ ]”を用いる
F(y)は

6.1.2 方向微分

推測で見つけるのではなく、汎関数の微分を用いて、最適解を見つける
“関数を少し変化させた時に汎関数が変化する割合(瞬間変化率)”で定義
汎関数値の変化量
関数y(x)を「少し変化させる」とは
関数v(x)と小さい数εに対して
y(x) + εv(x) とすること
汎関数がどのように変化するのか?
汎関数の変化量
F(y + εv) – F(y)
汎関数の変数に対して
F(y) ⟷ y(x)
F(y + εv) ⟷ y(x) +εv(x)
具体的な関数に対する汎関数の変化量
例
y(x)=x2
v(x)=x3
y(x) + εv(x) = x2 + εx3
F(y+εv)-F(y) = ∫(x2 + εx3)2dx – ∫(x2)2dx = ∫(x4 + 2εx5 + ε2×6 -x4)dx =1/3ε + 1/7ε2
関数y(x)がx2→x2+εx3と変化した時の汎関数の変化量
汎関数の擬似的な変化率
計算を簡単にするために、 両辺をεで割ることで変化量のみを考慮した 擬似的な平均変化率を使用する
v方向の平均変化率は、汎関数Fのv方向の変化量/εの変化量
(F(y+εv)-F(y))/ε=1/3 + 1/7ε
v方向の平均変化率
ε→0の極限
定義6.7
方向微分のイメージ
例
方向微分
変化量の計算
v方向の平均変化率
ε→0とした時
方向微分の公式
命題6.8
関数y(x),v(x)に関して
Φ(ε)=F(y+εv) (一変数関数)
(F(y+εv) – F(y)) / ε = (Φ(ε) – Φ(0)) / ε
方向微分は
補題
汎関数Fの被積分関数f(x,y)がz変数を持たない場合
方向微分の例
例1
汎関数
f(x,y,z)=y2
fy=2y, fz=0
方向微分
例2
汎関数
f(x,y,z)=y+1/2z2
fy=1, fz=z
方向微分

6.1.3 凸関数

汎関数についての凸性を考える
定義6.10
Fを汎関数とする
任意の関数y(x),v(x)に対して
F(y+v)≥F(y) + DF(y)(v)が成り立つ時
Fを”凸汎関数”と呼ぶ
凸汎関数のイメージ図
例
上記の汎関数は凸汎関数である
汎関数が凸になる条件
一般的な凸性の判定方法
定義6.12
3変数関数f(x,y,z)に対して、xを定数とみなす
(y,z)の関数を g(y,z) = f(x,y,z)とおく
全てのxに対してg(y,z)が凸関数である時
f(x,y,z)は第2、第3変数に対して凸であるという
命題6.13
3変数関数f(x,y,z)に対して
定理6.14
汎関数
任意のx∈ [a, b]に対して
被積分関数f(x,y,z9が第2、第3変数に対して凸ならば
汎関数Fも凸である
凸汎関数の例
例1
汎関数
被積分関数f(x,y,z)=x + y2 + z2は凸関数なので、Fは凸関数である
例2
汎関数
被積分関数f(x,y,z)=-x2 + y2 + z2は(x,y,z)に関しては凸ではない
第2,第3変数に関しては凸である
したがって凸汎関数である

6.2 変分問題の最適性条件 (オイラー・ラグランジュ方程式)

概要
変分問題の基本式
関数yに対して、y(a)=A, y(b)=Bという制約がつく問題
固定端問題
例 最速降下問題
式
議論が優しい順に説明
汎関数の大域最適解の十分条件
汎関数の局所最適解の必要条件
方向微分の第2公式
準備として方向微分の公式を表す
補題6.17 方向微分の第2公式
汎関数に対して
方向微分は上式で表せる

6.2.1 凸汎関数に対する最適性十分条件

目的関数が凸汎関数の時、大域最適解の十分条件を求める
定理6.18
停留関数
定義6.19

6.2.2 解法例
6.2.3 一般の汎関数に対する最適性必要条件
6.2.4 解法例

第7章 制約付き変分問題

7.1 制約付き変分問題

7.1.1 最適性条件の考察
7.1.2 制約付き変分問題の最適性条件
7.1.3 解法例
7.1.4 凸性を用いた最適性十分条件
7.1.5 線形汎関数

7.2 有名な変分問題の解

7.2.1 最速降下法
7.2.2 懸垂線

第8章 計算機利用

8.1 基本操作

8.1.1 グラフを描く
8.1.2 微分積分の計算
8.1.3 行列の計算

8.2 最適化問題を解く

8.2.1 制約なし最適化問題を解く
8.2.2 制約付き最適化問題を解く
8.2.3 線形計画問題を解く

8.3 変分問題を解く

変分問題をコンピュータで解く場合には、 オイラー・ラグランジェ方程式を導出し微分方程式を解く方法と、 近似回を直接求める方法がある

8.3.1 変分問題を解く

8.3.1.1 オイラー・ラグランジェ方程式を解く
8.3.1.2 リッツの方法
変分問題を数ベクトル空間上の最適化問題で近似する方法

8.3.2 制約付き変分問題を解く

8.3.2.1 オイラー・ラグランジェ方程式を解く

第9章 練習問題の解答