第8回の授業資料

計画数理
第８回：縁付きHessian行列
林俊介
KKT条件（前回の復習）
不等式制約と等式制約の両方を含む問題を考える．
(P)
(P) の制約関数は一次独立制約想定を満たすとする．
Karush-Kuhn-Tucker (KKT)条件
不等式制約へのラグランジュ乗数（必ず0以上）
等式制約へのラグランジュ乗数
（負にもなりえる．）
一次独立制約想定（前回の復習）
(P)
局所最適解において効いているすべての制約関数の勾配ベクトル
が一次独立であるとき，一次独立制約想定 (LICQ) を満たすという．
数式で書くと，以下を満たすことを要請している．
局所最適解，
は一次独立である．
とする．このとき，
KKT条件の図的解釈
(P)
（前回の復習）
KKT条件
(効いている)
(効いていない)
(効いている)
4
二次の最適性条件
（前回の復習）
• 一次独立制約想定(LICQ)が成り立つとする．
• KKT点において弱い意味で効いている制約が無いものとする．
（i.e., 効いてる制約に対するラグランジュ乗数は正）
最適性の二次の必要条件
: (P) のラグランジュ関数
ただし，
: 効いてる制約の添字集合
※ この条件は，
が
上で正定値であること意味する．
例題：１次，２次の必要条件の検証
この制約だけが最適解で効いている．
6
例題：１次，２次の必要条件の検証
KKT条件
であるので，においてラグランジュ乗数を
とすることにより，KKT条件が成立することが分かる．
7
例題：１次，２次の必要条件の検証
２次の必要条件
: 効いてる制約の
添字集合
8
例題：１次，２次の必要条件の検証
２次の必要条件
: 効いてる制約の
添字集合
ただし，
そのものは半正定値ではないことに注意！
縁付きHessian行列
（縁付きヘッセ行列，境界付きヘッセ行列）
Note: 不等式制約をもつ問題
でも，最適解で効いてる制約
が同定できれば，局所的には
等式制約と同じ．
縁付きHessian行列を使えば，等式制約のみをもつ最適化問題に対して，
最適性の二次の必要条件・十分条件がよりチェックしやすくなる．
まずは簡単のため，変数が２次元で，等式制約が１つのみの場合を考える．
このとき，
ラグランジュ関数：
縁付きヘッセ行列：
縁付きHessian行列
（縁付きヘッセ行列，境界付きヘッセ行列）
定理
（証明）
停留点：
を満たす点
（KKT点と同じ）
: Hの行列式
（※）
11
縁付きHessian行列（縁付きヘッセ行列）
（証明つづき）
のときは，
として同様に議論
12
縁付きHessian行列（縁付きヘッセ行列）
（証明つづき）
（証明おわり）
13
一般的な結論（極小値必要条件）
以下のような等式制約つき最適化問題を考える
このとき，停留点
における極小値必要条件は，
ただし，
14
一般的な結論
（等式制約２つ，変数の次元４）
このとき，停留点
における極小値必要条件は，
15
一般的な結論（極小値十分条件）
等式制約つき最適化問題
このとき，停留点
における極小値十分条件は，
極小値必要条件の不等号が
すべて狭義に成立
16
一般的な結論（極大値条件）
等式制約つき最適化問題
このとき，停留点
における極大値必要条件は，
十分条件は，
（等式制約２つ，変数の次元４）
停留点
における極大値必要条件は，
17
例題
18
19
20
21

Download Report