Sx xf s.t. )( min

制約つき最適化問題
min f ( x)
s.t. x S
2014/6/27
1
制約条件は
g i ( x) 0, (i 1,
h j ( x) 0, ( j 1,
, m) 不等式制約
,l)
等式制約
および，それらの組合せで表現される．
最適性条件を考えよう
2014/6/27
2
不等式制約問題
min f ( x)
s.t. g i ( x) 0, (i 1,
, m)
有効(active)な制約条件
I ( x)
2014/6/27
i g i ( x) 0
1,
,m
3
幾何学的な条件
f ( x* ) T d
*
x : 局所最適解
g i ( x* )T d
なる d
【証明】
0,
0 i I ( x* )
0は存在しない
そのようなdが存在したとする．
i I x*
g i ( x*
十分小さい
i I x*
一方，f ( x *
d)
g i ( x* )
0 に対し g i ( x *
o
だから，
d) 0
g i ( x * ) 0 なので，十分小さいに対し g i ( x *
d)
f ( x* )
を十分小さくとると f ( x *
2014/6/27
g i ( x* ) T d
f ( x* ) T d
d)
o
d) 0
なので，
f ( x * ) となる．
4
g 2 ( x) 0
最適解の場合
f の等高線
大
f ( x* )
*
g1 ( x )
小
x*
g 2 ( x* )
g1 ( x ) 0
2014/6/27
5
最適でない場合
g 2 ( x) 0
f の等高線
大
d
*
小
g1 ( x )
x*
g 2 ( x* )
*
f (x )
g1 ( x ) 0
2014/6/27
6
Gordanの定理
a1 ,
,ap
R nとする．(1), ( 2)のうちいずれか一方が成立
(1) aiT x 0, (i 1,
, p)なる x R nが存在
p
( 2)
y i ai
0, yi
0, y
0 なる y
R pが存在
i 1
(2)
(1)
a1
a1
a2
x
a2
a4
2014/6/27
a3
a4
a3
7
定理（Fritz John）
0
x* : 局所最適解
f ( x* )
i
g i ( x* ) 0,
i 1
g i ( x * ) 0, i g i ( x* ) 0,
【証明】
f ( x* )T d
m
0, g i ( x* ) T d
i
0,
0 , 1,
,
m
0
I x* となるd は存在しない．
0 i
Gordanの定理より
0
f ( x* )
i
i I x
0,
0
i
0 i
g i ( x* ) 0,
*
I x* ,
0
,
i I x*
0
となるが存在する．
i
I x*
2014/6/27
g i ( x* ) 0 なので，
i
0 とおけばよい．
8
Karush-Kuhn-Tucker（KKT）条件
Fritz Johnの条件において 0 0 ならば，
とおくことにより，以下が得られる
i
i
0
Karush-Kuhn-Tucker条件（一次の必要条件）
m
*
f (x )
i
*
g i ( x ) 0,
i 1
g i ( x * ) 0, i g i ( x * ) 0,
2014/6/27
i
i
0, i 1,
: ラグランジュ乗数
,m
9
制約想定
Fritz Johnにおいて 0 0 となるための条件
例） g i ( x* ), i I x* が一次独立
g i が全て凸で g i ( x ) 0 i となる x が存在
など
制約想定が成り立たないとき
→局所解でもKKT条件が成り立たない
f , gi
がすべて凸とする
x* , がKKT条件を満たす
2014/6/27
x* : 大域的最適解
10
等式・不等式制約の場合
min
f ( x)
s.t. g i ( x) 0, (i 1,
, m)
h j ( x) 0, ( j 1,
,l)
h j ( x) 0
h j ( x) 0
h j ( x) 0
とすれば，不等式制約の場合に帰着できる
→制約想定を満たさない
2014/6/27
11
Karush-Kuhn-Tucker（KKT）条件
*
m
f (x )
*
gi ( x )
i
i 1
h j ( x * ) 0, j 1,
2014/6/27
j
*
h j ( x ) 0,
j 1
g i ( x * ) 0, i g i ( x * ) 0,
i,
l
j
i
0, i 1,
,m
,l
: ラグランジュ乗数
12
LPで考える
AT w
c
p
主問題（P）のKKT条件
T
min c x
（Ｐ）
s.t. Ax b, x 0
c
AT w
Ax b, w 0, wT Ax b
2014/6/27
AT w, x 0, x T c
0
x 0, p 0, x T p 0
Ax b, w 0, wT Ax b
c
p 0,
AT w
0
0
13
相補性定理(Complementarity)
（Ｐ）
min c T x
s.t.
Ax b, x 0
（Ｄ）
max b T w
T
s.t.
A w c, w 0
x, w : 実行可能解が最適解
Ax b, w 0, wT Ax b
c
2014/6/27
AT w, x 0, x T c
AT w
0
0
14
ペナルティ関数・ペナルティ法
制約条件からのはずれを，はずれの程度に
比例したペナルティとして目的関数に加える
制約なし最適化問題とする
2014/6/27
15
不等式制約 g ( x) 0 に対し，
l1 ペナルティ： max 0, g ( x)
l2 ペナルティ： max 0, g ( x)
2
ペナルティ関数の例
f ( x)
max 0, g ( x)
0 : ペナルティパラメータ
2014/6/27
16
l1 ペナルティ： max 0, g ( x) の特徴
0 : 十分大とすると，ペナルティ関数の最適解は
元の制約つき問題の解と一致（exact penalty）
しかし，ペナルティ関数は微分不可能
l2 ペナルティ： max 0, g ( x)
2
の特徴
ペナルティ関数は微分可能
しかし，ペナルティ関数の最適解は元の制約つき問題の
制約条件を満たさない．を大きくすれば限りなく近づく
2014/6/27
17
ペナルティパラメータを大きくすると，元の問
題の解に近づくが，数値的不安定を生ずる
改良版が，ＳＱＰ法などの目的関数として利
用されている
考え方は素晴らしく，統計的データ処理，強
化学習，最適制御などで，用いられている
2014/6/27
18
制約付き問題の（実用的）解法
逐次二次計画法（SQP法）
各反復で，
目的関数を（凸）二次近似
制約条件を一次近似
した問題（凸二次計画）を解く
KKT条件に対し内点法（後述）を応用する方法
近年，その有効性が示された
2014/6/27
19
演習課題
次の例題について
1
2
2
max
x1 1
x2 1
2
2
s.t. 4 x1 x2 3
0
x1
0, x2
0
KKT条件を満たすすべての点とそこでのラグラン
ジュ乗数を求めよ
2. 最適解はどこか
締切：７月３日１６時 Ⅳ系事務室
1.
2014/6/27
20

Download Report