定義
- 不等式拘束条件g
- 等式拘束条件h
- 許容解 x
- 許容領域 S
- 最適解、大域的最適解、局所最適解、孤立局所最適解 x*
最適解の存在と一意性
- 最適解が必ず存在するとは限らないし、存在しても一つとは限らない
- 最適解の存在を保証したり、最適解を確実に見つけることは困難
定理
ワイエルシュトラスの定理
- 許容領域Sが有界閉集合で評価関数fがSで連続ならば、最適解が存在する
凸計画問題の性質
- 許容領域Sが凸集合で評価関数fが凸関数ならば、局所最適解は最適解である
凸集合と凸関数の定義
凸集合S:x,y∈S、α∈[0,1]のとき、(1-α)x+αy∈Sとなる
凸関数f:x,y∈S、α∈[0,1]のとき、f((1-α)x+αy)∈(1-α)f+αfとなる
拘束条件なしの最適性条件
停留条件、2次の必要条件、2次の十分条件
拘束条件ありの最適性条件
等式拘束条件hの場合
- ラグランジュ定数λを含むL(x,λ)=f+λhを定義し、これの停留条件を考える
不等式拘束条件gの場合
- 等式拘束条件の場合の最適性条件にλ≥0と相補性条件が加わる
等式拘束条件hと不等式拘束条件gをまとめた定式化(KKT条件)
拘束条件つき最適化問題の数値解法
変換法
逐次2次計画法(SQP)
精密な直線探索
- 囲い込み(bracketing)
- 黄金分割法(Golden section method)
粗い直線探索