内点法のバックアップ(No.1) - PukiWiki

[ トップ ] [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ] [ リンク元 ]

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
内点法へ行く。
- 1 (2007-11-21 (水) 11:15:24)
- 2 (2007-11-21 (水) 11:46:39)
- 3 (2007-11-28 (水) 11:45:23)
- 4 (2007-12-06 (木) 18:16:25)

数理計画法

内点法
- 主問題
  minimize. $c^{T}x$
  s.t. $Ax=b\ \wedge\ x \geq 0$
- 双対問題
  maximize. $b^{T}y$
  s.t. $s=c-A^{T}y\ \wedge\ s\geq 0$
- Aの各行ベクトルが一次独立で、主問題・双対問題にそれぞれ
  どの成分も0にならない許容解が存在することは仮定しておく。
  このような許容解は内点許容解と呼ばれる。
- 多項式時間主双対内点法