凸計画問題

最適化問題において、制約を満たす解を実行可能解、制約を満たす領域を実行可能領域と呼ぶ。 目的関数が凸関数で、実行可能領域が凸集合であるような問題を凸計画問題と呼ぶ。

凸集合・凸関数

集合 が凸集合であるとは、 を満たすことと同値である。 また、関数 が下に凸であるとは、 を満たすことと同値である。

凸関数の具体例

  • 線形関数
  • アフィン関数
  • 正定値行列 について、
  • ノルム
  • について、

微分可能な凸関数の最適化

解析的に解く

勾配ベクトルが0ベクトルとなるを解析的に求める。

近似的に解く

最急降下法やそれに類する手法により近似解を求める。

凸計画問題の種類

  • が微分可能

    • 制約なし
      • の微分をにする点が解析的に求まる
        • その点が最適解
      • 求まらない
        • 最急降下法などで近似的に解く
    • 等式制約
      • ラグランジュの未定乗数法
    • 不等式制約
      • ラグランジュの未定乗数法
      • SVM導出などで出てくる
  • が微分不可能

    • 制約なし
    • 等式制約
    • 不等式制約