2次計画法

Overview

2次計画法とは、次のような2次関数を線形制約の下で最適化（最小化ないしは最大化）する問題のことです。

$ f(x, y) = x^2 + xy + y^2 + 2x + 4y

Theory

ライブラリの関数に入力するには標準形に変換しなければいけません。cvxoptでは、制約条件なしの2次計画問題の標準形は次のような形を仮定します。

$ \frac{1}{2}x^TPx + q^Tx

$ P = \begin{pmatrix}2 & 1\\ 1 & 2\\ \end{pmatrix}, q = \begin{pmatrix}2\\4\\ \end{pmatrix}

$ f(x, y) = \frac{1}{2}\begin{pmatrix}x & y\\ \end{pmatrix}\begin{pmatrix}2 & 1\\1 & 2\\ \end{pmatrix}\begin{pmatrix}x\\y\\ \end{pmatrix} + \begin{pmatrix}2 & 4\\ \end{pmatrix}\begin{pmatrix}x\\y\\ \end{pmatrix}

Coding

$ Minimize: f(x, y) = x^2 + xy + y^2 + 2x + 4y

code: Python

import numpy as np

import cvxopt

sol = cvxopt.solvers.qp(P, q)

--------------------------------------------------------------------------

-4.0

--------------------------------------------------------------------------

$ Minimize: f(x, y) = x^2 + xy + y^2 + 2x + 4y \quad Subject \ to: x + y = 0

code: Python

import numpy as np

import cvxopt

sol = cvxopt.solvers.qp(P, q, A=A, b=b)

--------------------------------------------------------------------------

-1.0000000000000016

--------------------------------------------------------------------------

$ Minimize: f(x, y) = x^2 + xy + y^2 + 2x + 4y \quad Subject \ to: 2x + 3y \leqq 3

code: Python

import numpy as np

import cvxopt

sol = cvxopt.solvers.qp(P, q, G=G, h=h)

--------------------------------------------------------------------------

pcost dcost gap pres dres

0: 1.8858e+00 2.9758e-01 2e+00 5e-18 2e+00

1: -2.1066e+00 -2.1546e+00 5e-02 2e-16 7e-01

2: -3.9999e+00 -4.0665e+00 7e-02 3e-16 2e-16

3: -4.0000e+00 -4.0007e+00 7e-04 1e-15 1e-16

4: -4.0000e+00 -4.0000e+00 7e-06 3e-16 6e-17

5: -4.0000e+00 -4.0000e+00 7e-08 9e-16 2e-16

Optimal solution found.

-4.0

--------------------------------------------------------------------------