最適化セミナーのご案内

B.2 単体法・有効制約法

 単体法は線形最適化問題

\[\begin{array}{@{}lll@{}} \mbox{最小化} & c^t x & x \in R^n \\ \mbox{条\hskip1zw 件} & b_U \ge Ax \ge b_L, & b_U \ge x \ge {b_L}\end{array}\]

に対して,有効制約法は二次計画問題

\[\begin{array}{@{}lll@{}} \mbox{最小化} & \displaystyle \frac{1}{2} x^t Qx + c^t x & x \in R^n \\  \mbox{条\hskip1zw 件} & b_U \ge Ax \ge b_L, & b_U \ge x \ge b_L \end{array}\]

に対して,それぞれ有効な方法です.一度可能基底解が得られれば,問題に対して小さな変更を行った際の解を比較的高速に求めることができるなど,内点法にはない特徴を備えています.


 

 

上に戻る