凸計画問題
最適化問題において、制約を満たす解を実行可能解、制約を満たす領域を実行可能領域と呼ぶ。 目的関数が凸関数で、実行可能領域が凸集合であるような問題を凸計画問題と呼ぶ。
凸集合・凸関数
集合 が凸集合であるとは、 を満たすことと同値である。 また、関数 が下に凸であるとは、 を満たすことと同値である。
凸関数の具体例
- 線形関数
- アフィン関数
- 正定値行列 について、
- ノルム
- について、
微分可能な凸関数の最適化
解析的に解く
勾配ベクトルが0ベクトルとなるを解析的に求める。
近似的に解く
最急降下法やそれに類する手法により近似解を求める。
凸計画問題の種類
-
が微分可能
- 制約なし
- の微分をにする点が解析的に求まる
- その点が最適解
- 求まらない
- 最急降下法などで近似的に解く
- の微分をにする点が解析的に求まる
- 等式制約
- ラグランジュの未定乗数法
- 不等式制約
- ラグランジュの未定乗数法
- SVM導出などで出てくる
- 制約なし
-
が微分不可能
- 制約なし
- 等式制約
- 不等式制約