数学やプログラミングの備忘録

数理最適化, Python, C++をメインに紹介するブログ。

MENU
トップ > 数理最適化 > python + CVXOPT: 制約無し凸二次計画問題を解く

python + CVXOPT: 制約無し凸二次計画問題を解く

数理最適化 数理最適化-二次計画法

今日は、python の CVXOPT と呼ばれるライブラリを使って制約無し凸二次計画問題を解いてみます。

CVXOPT の基本的な使い方も紹介します。

CVXOPT は、多分 CONVEX と OPTIMIZATION の造語でしょうね。 調べた感じだと、線形計画問題や制約付き凸二次計画問題なども解けるようです。

目次

例題

\begin{array}{ll} \min_{x} & 2x^2 + y^2 + x y + x + y\\ \text{s.t.} & x \in \mathbb{R}^n \end{array}

変数として x, y の二つを持つ最適化問題です。

このくらいの小さい問題なら手計算で解くことができます。

手計算で解く方法は以下の記事で紹介しています。

www.letsopt.com

ちなみに、最適解はこちら。

x = -1/7,\ y = -3/7

CVXOPTのインストール

  • conda でインストール
conda install -c conda-forge cvxopt
  • pip でインストール
pip install cvxopt

CVXOPTの使い方

この記事では、制約無し凸二次計画問題を解く場合のCVXOPTの使い方を紹介します。

CVXOPTは、目的関数を以下の形式で与える必要があります。

\begin{array}{ll} \min_{x} & \frac{1}{2} x^T Q x + p^T x\\ \text{s.t.} & x \in \mathbb{R}^n \end{array}

つまり、行列 Q と ベクトル p を作り、CVXOPTに与えます。

ここの 例の場合の Q, p を作ってみます。

Q=2 \left( \begin{array}{cc} 2 & 0.5\\ 0.5 & 1 \end{array} \right) ,\ p = \left(\begin{array}{c} 1\\ 1 \end{array}\right)

次に実際にpythonプログラムで解いてみましょう！

CVXOPTで例題を解くコード

from cvxopt import matrix, solvers

# min f(x) = 1/2 x^T Q x + p^T x

# 行列 Q とベクトル p を生成
Q = 2 * matrix( [ [2, 0.5], [0.5, 1] ] )
p = matrix( [1.0, 1.0] )

# 最適化スタート
sol = solvers.qp( Q, p )

# 結果を出力
print('ステータス = {}'.format(sol['status']))
print('最適値 = {}'.format(sol['primal objective']))
print('最適解:')
print(sol['x'])

実行結果

ステータス = optimal
最適値 = -0.2857142857142857
最適解:
[-1.43e-01]
[-4.29e-01]

ステータスが optimal と出れば、最適解を無事見つけたことになります。

今後、他のライブラリも紹介していこうと思います。

おわり