All published worksheets from http://sagenb.org
Image: ubuntu2004
CVXOPTを使って最適解問題を解く
ここでは、sage上でCVXOPTを使って最適解問題を解く方法に説明します。
線形最適解問題
最初にCVXOPTのTUTORIALからSolving a linear program をsageで解いてみます。
以下の問題がこれから解く、線形最適解問題です。
ここで、minimize f(w)というのは、目的関数を示し、subject to g(w) 0は、不等式制約$g(w)を示します。
従ってこの最適化問題は、不等式制約のもとで目的関数が最も小さくなる値を求めることです。
目的関数と制約条件の可視化
CVXOPTを使って解く前に、sageの可視化ツールを使って目的関数と制約条件を表示してみましょう。
黄色の領域が制約条件で囲まれた部分です。 の直線で、cの値の最も小さいものが、 赤の直線です。
CVXOPTに必要なインポート
まずは、CVXOPTに必要なパッケージをインポートします。
solvers.lpを使って解く
SVXOPTの本では線形最適解問題の一般問題は、次のような形式で与えられます。 不等式制約 と 等式制約 の混在形式。 これをSVXOPTでは、 を導入して、 に分割し、 目的関数のd(定数)を除いた以下の形式で解いています。
solvers.lp()を使って線形最適解問題を解いてみます。lpの使い方をみると、 以下のような引数をとり、不等号制約条件問題では、c, G, hを与えればよいこと が分かります。
solvers.lp(c, G, h, A, b, solver, primalstart, dualstart) minimize c'*x subject to G*x + s = h A*x = b s >= 0
従って、例題をsolvers.lpに与える引数の形式に整理すると、
$$ \begin{array}{lll} c^T & = & \left( \begin{array}{cl} 2 & 1 \end{array} \right) \\ G & = & \left( \begin{array}{rrrr} -1 & 1 \\ -1 & -1 \\ 0 & -1 \\ 1 & -2 \end{array} \right) \\ h & = & \left( \begin{array}{r} 1 \\ -2 \\ 0 \\ 4 \end{array} \right) \end{array} $$線形最適化例題を解く
準備が整ったので、solvers.lpを使って例題を解いてみます。
無事、解として(0.5, 1.5)が求まりました。
2次最適化問題
線形の例題がうまく動いたので、今度は2次最適化問題に進みます。
2次計画問題の例題
CVXOPTの本に紹介されている2次計画問題の例題、次のようなものです。
2次凸目的関数と制約条件の可視化
線形の時と同様に2次凸目的関数と制約条件を可視化してみます。
コンター図に沿って描画したの点線(青)が最も 小さな値を取るのは、(0.25, 0.75)付近であることが見て取れます。
solvers.cpを使って解く
qpのマニュアルには、2次計画問題の標準系として、次の形式で目的関数を表しています。
例題にこの式を当てはめると、Gの不等式制約は、変数xが正の値をとるAに等式制約条件を 記述しまと、P, q, G, h, A, bは次のようになります。 $$ \begin{array}{lll} Q & = & 2 \left( \begin{array}{cc} 2 & 1/2 \\ 1/2 & 1 \end{array} \right) \\ p^T & = & \left( \begin{array}{rr} 1 & 1 \end{array} \right) \\ G & = & \left( \begin{array}{rr} -1 & 0 \\ 0 & -1 \end{array} \right) \\ h & = & \left( \begin{array}{r} 0 \\ 0 \end{array} \right) \\ A & = & \left( \begin{array}{rr} 1 & 1 \end{array} \right) \\ b & = & \left( \begin{array}{r} 0 \end{array} \right) \end{array} $$
計算結果は、可視化で期待したとおり、(0.25, 0.75)が最適解となっています。