制約つき最適化問題

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