Nagoya
Institute of
Technology
Nagoya Institute of Technology
（ソフトマージン）サポートベクトルマシン
ソフトマージン
サポートベクトルマシン
目的関数が未知パラメータの二次関数
制約条件が未知パラメータの一次等式/一次不等式
二次計画問題（Quadratic Programming）
Nagoya Institute of Technology
制約付最適化問題
Nagoya Institute of Technology
等式制約
Nagoya Institute of Technology
等式制約
目的関数の等高線
等式制約条件
Nagoya Institute of Technology
等式制約
目的関数の等高線
最適解
等式制約条件
Nagoya Institute of Technology
等式制約
目的関数の等高線
最適解
等式制約条件
Nagoya Institute of Technology
最適解近傍での線形近似
最適解
近傍の目的関数の線形近似
最適解
近傍の等式制約の線形近似
Nagoya Institute of Technology
最適解近傍での線形近似
Nagoya Institute of Technology
最適解近傍での線形近似
Nagoya Institute of Technology
最適解近傍での線形近似
Nagoya Institute of Technology
等式制約付最適化問題の最適性条件
Nagoya Institute of Technology
等式制約付最適化問題の最適性条件
目的関数の等高線の接線と等式制約の接線が平行であるとは
Nagoya Institute of Technology
等式制約が複数ある場合
Nagoya Institute of Technology
等式制約が複数ある場合
複数の等式制約の交線と目的関数の等高線が平行であるとは
Nagoya Institute of Technology
等式制約付最適化問題の最適性条件
等式制約付最適化問題の最適性条件
Nagoya Institute of Technology
ラグランジュ関数
等式付最適化問題の最適解
ラグランジュ関数の極値
Nagoya Institute of Technology
課題1
Nagoya Institute of Technology
課題1
Nagoya Institute of Technology
不等式制約
不等式制約条件
アクティブ制約
最適解
において等号が成り立っているもの
ノンアクティブ制約
最適解
において不等号が成り立っているもの
Nagoya Institute of Technology
不等式制約
アクティブ制約
等式制約と同様に扱う
ノンアクティブ制約
最適解の性質に影響を与えない
Nagoya Institute of Technology
不等式制約
問題点1. どれがアクティブ制約か前もって知ることができない
問題点2. アクティブ制約の最適性条件は本当に等式制約条
件と同じでよいのか
Nagoya Institute of Technology
不等式制約
目的関数の等高線
最適解
等式制約条件
Nagoya Institute of Technology
不等式制約
目的関数の等高線
最適解
不等式制約条件
Nagoya Institute of Technology
不等式制約
目的関数の等高線
最適解
不等式制約条件
Nagoya Institute of Technology
最適解近傍での線形近似
最適解
近傍の目的関数の線形近似
最適解
近傍の等式制約の線形近似
Nagoya Institute of Technology
最適解近傍での線形近似
Nagoya Institute of Technology
最適解近傍での線形近似
Nagoya Institute of Technology
最適解近傍での線形近似
Nagoya Institute of Technology
法線ベクトル
Nagoya Institute of Technology
不等式制約の最適性条件
図4（b） 最適解
を増やす向き
図4（c） 最適解でない
一致
を減らす向き
Nagoya Institute of Technology
相補性条件
Nagoya Institute of Technology
等式・不等式付最適化問題の最適性条件
Nagoya Institute of Technology
課題2
①
②
③
③
②
①
Nagoya Institute of Technology
課題2
Nagoya Institute of Technology
課題2
Nagoya Institute of Technology
ラグランジュ関数
制約付最適化問題
ラグランジュ関数
Nagoya Institute of Technology
ラグランジュ双対関数
Nagoya Institute of Technology
ラグランジュ双対問題
主問題
双対問題
Nagoya Institute of Technology
主問題と双対問題
主問題（P）：
双対問題（D）：
を制約条件下で最小化する
を制約条件下で最大化する
Nagoya Institute of Technology
二次計画問題の双対問題
二次計画問題
Nagoya Institute of Technology
二次計画問題の双対問題
step1
step2
step3
Nagoya Institute of Technology
二次計画問題の双対問題
二次の項
一次の項
一次の制約条件