第7回の授業資料

計画数理
第７回：制約つき非線形計画
林俊介
制約付き最適化問題
制約付き最適化問題
テキストに書かれている問題
上記の問題
制約付き最適化問題と無制約最適化問題
制約付き最適化問題
無制約最適化問題
前々回の授業で最適性
の条件を勉強した．
3
無制約最適化問題の最適性条件（前々回の授業）
(P)
最適性の一次の必要条件
local minimum
（局所最小点）
local maximum
（局所最大点）
saddle point
（鞍点）
無制約最適化問題の最適性条件（前々回の授業）
(P)
最適性の一次の必要条件
最適性の二次の必要条件
最適性の二次の十分条件
これらの条件は「制約付き」最適化問題に直接適用できるか？
No!
反例
6
Karush-Kuhn-Tucker (KKT) 条件
7
１次の必要条件
制約付き最適化問題の場合，最適性の１次の必要条件
は，Karush-Kuhn-Tucker (KKT) 条件という名前でも
知られている．
以前はKuhn-Tucker条件と言われていたが，最近
無制約最適化
は Karush を加えて呼ばれるのが一般的．
制約付き最適化
以後，しばらくは簡単のため，不等式制約のみを含む問題を考える．
8
Karush-Kuhn-Tucker (KKT) 条件
(P)
問題 (P) の制約関数が一次独立制約想定を満たしているものと仮定．
効いてる制約の勾配ベクトルが
一次独立（詳しくは後で説明）
Karush-Kuhn-Tucker (KKT) 条件
（ラグランジュ乗数）
テキストでは u で表記
9
KKT条件の意味
Karush-Kuhn-Tucker (KKT) 条件
ラグランジュ関数の x
に対する偏微分が0.
ラグランジュ関数
(相補性条件: complementarity condition）
KKT条件の図的解釈
(P)
11
KKT条件の図的解釈
(P)
KKT条件
(効いている)
(効いていない)
(効いている)
12
KKT条件の図的解釈
微小なボールが領域 S の内部を転がり，
(P)
で止まった状況を想像しよう．
KKT条件は力のつり合い式とも解釈できる．
壁１
壁３
壁の内部
壁2
13
KKT条件の図的解釈
(P)
次のような場合はどう考えられるか?
(すべての制約が効いていない.)
14
KKT条件の図的解釈
(P)
KKT条件
（効いてない）
（効いてない）
（効いてない）
(無制約最適化の場合と一緒）
すべての制約が
で効いていない．
(P) は
の周りでは，本質的に無制
約最適化問題である．
15
KKT条件の図的解釈
(P)
では，次の場合はどうか？
16
KKT条件の図的解釈
(P)
KKT条件
（効いている）
（効いていない）
（効いている）
(Notice: 効いていない制約と弱い意味で効いている制約は，
それらを取り除いたとしても，一般には局所最適解が変わらない．）
17
KKT条件（等式制約も含む場合）
不等式制約と等式制約の両方を含む問題を考える．
(P)
(P) の制約関数は一次独立制約想定（後述）を満たすとする．
Karush-Kuhn-Tucker (KKT)条件
不等式制約へのラグランジュ乗数（必ず0以上）
等式制約へのラグランジュ乗数
（負にもなりえる．）
一次独立制約想定 (LICQ: Linear Inequality Constraint Qualification)
(P)
局所最適解において効いているすべての制約関数の勾配ベクトル
が一次独立であるとき，一次独立制約想定 (LICQ) を満たすという．
数式で書くと，以下を満たすことを要請している．
局所最適解，
は一次独立である．
とする．このとき，
一次独立制約想定を満たしている例
(P)
以下の例の場合，
において効いている制約は
20
一次独立制約想定を満たしていない例
(P)
以下の例の場合，
において効いている制約は
実際，KKT条件は満たさない．すなわち
を満たす
は存在しない．
ただし，こんな例はあまり
出てこない．（普通は一次
独立制約は満たされる．）
KKT条件のベクトル表現
(P)
ベクトル表現
(P)
KKT条件 (ベクトル表現)
転置ヤコビ行列
（ヤコビ行列を転置したもの）
凸最適化問題に対するKKT条件
(P)
(P) は凸最適化問題（凸計画問題）といわれる．
非凸最適化問題
凸最適化問題
23
テキストでの表記との比較
テキストでの表記
最適化問題
KKT条件
本授業スライドでの表記
最適化問題
KKT条件
どちらも同じことを言ってる！
（記号や添字の付け方が違うだけ．）
24
二次の最適性条件
25
無制約最適化問題の場合
(P)
無制約最適化の場合，二次の最適性条件は以下のとおりであった．
最適性の二次の必要条件
最適性の二次の十分条件
制約つき最適化問題の場合，この条件はより複雑になる．
26
二次の最適性条件
(制約つきバージョン)
• 一次独立制約想定(LICQ)が成り立つとする．
• KKT点において弱い意味で効いている制約が無いものとする．
（i.e., 効いてる制約に対するラグランジュ乗数は正）
最適性の二次の必要条件
: (P) のラグランジュ関数
ただし，
: 効いてる制約の添字集合
※ この条件は，
が
上で（局所的に）正定値であること意味する．
(もし
が（空間全体で）半正定値なら，上の条件は満たす．
よって，上の条件は通常の半正定値性よりも緩い条件である．）
27
二次の最適性条件
(制約つきバージョン)
• 一次独立制約想定(LICQ)が成り立つとする．
• KKT点において弱い意味で効いている制約が無いものとする．
（i.e., 効いてる制約に対するラグランジュ乗数は正）
最適性の二次の十分条件
ただし，
: (P) のラグランジュ関数
: 効いてる制約の添字集合
28
条件の適用例
なので，二次の
最適性条件は自動的に成り立つ．
は赤の破線である．ラグランジュ
関数は，赤の破線上で下に凸なので，
二次の最適性条件は成り立つ．
29

Download Report