二次計画問題 (Quadratic Programming, QP)

二次計画問題 (Quadratic Programming, QP)

凸最適化問題の具体例として、二次計画問題 (Quadratic Programming, QP) を挙げます。
この問題は、凸二次関数を最小化するもので、以下の形式を持ちます：

$$
\text{minimize} \quad \frac{1}{2}x^T Q x + c^T x
$$
$$
\text{subject to} \quad Ax \leq b
$$

ここで、$( Q ) $は対称かつ正定値行列、$( c ) $はベクトル、$( A ) $は行列、$( b ) $はベクトルです。

具体例：
$$ Q = \begin{bmatrix} 2 & 0 \ 0 & 2 \end{bmatrix}, \quad c = \begin{bmatrix} -4 \ -6 \end{bmatrix}, \quad A = \begin{bmatrix} 1 & 1 \ -1 & 2 \ 2 & 1 \end{bmatrix}, \quad b = \begin{bmatrix} 3 \ 2 \ 4 \end{bmatrix} $$

この例では、二次関数$ (\frac{1}{2}x^T Q x + c^T x) $を最小化し、線形制約$ (Ax \leq b) $を満たす$ (x) $を見つけます。

以下は、Pythonでこの問題を解くコードです。

cvxpyライブラリを使用して問題を解きます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import cvxpy as cp
import numpy as np

# 定義されたパラメータ
Q = np.array([[2, 0], [0, 2]])
c = np.array([-4, -6])
A = np.array([[1, 1], [-1, 2], [2, 1]])
b = np.array([3, 2, 4])

# 変数の定義
x = cp.Variable(2)

# 目的関数の定義
objective = cp.Minimize(0.5 * cp.quad_form(x, Q) + c.T @ x)

# 制約の定義
constraints = [A @ x <= b]

# 問題の定義
prob = cp.Problem(objective, constraints)

# 問題を解く
result = prob.solve()

# 結果の表示
print(f"Optimal value: {result}")
print(f"Optimal solution: x = {x.value}")

このコードでは、次の手順を踏みます：

  1. cvxpyライブラリをインポートします。
  2. パラメータ$ (Q)$、$(c)$、$(A)$、および$ (b) $を定義します。
  3. 最適化変数$ (x) $を定義します。
  4. 目的関数を定義します。
  5. 制約を定義します。
  6. 問題を定義し、解きます。
  7. 最適解と最適値を表示します。

実行すると、最適な解$ (x) $とそのときの最小値を得ることができます。

[実行結果]

Optimal value: -10.399999999999999
Optimal solution: x = [1.2 1.6]

ソースコード解説

コードの各部分を詳しく説明します。

1. 必要なライブラリのインポート

1
2
import cvxpy as cp
import numpy as np

最初に、最適化ライブラリであるCVXPYと数値計算ライブラリであるNumPyをインポートしています。
CVXPYは凸最適化問題を簡潔に定義し解くためのライブラリです。

2. パラメータの定義

1
2
3
4
5
# 定義されたパラメータ
Q = np.array([[2, 0], [0, 2]])
c = np.array([-4, -6])
A = np.array([[1, 1], [-1, 2], [2, 1]])
b = np.array([3, 2, 4])

ここでは、最適化問題に必要なパラメータを定義しています。

  • Q: 二次形式の係数行列（正定値行列）
  • c: 線形項の係数ベクトル
  • A: 制約条件の係数行列
  • b: 制約条件の右辺ベクトル

3. 変数の定義

1
2
# 変数の定義
x = cp.Variable(2)

次に、最適化変数 x を定義しています。
この変数は2次元のベクトルです。

4. 目的関数の定義

1
2
# 目的関数の定義
objective = cp.Minimize(0.5 * cp.quad_form(x, Q) + c.T @ x)

目的関数を定義しています。
この問題の目的は、以下の形式の関数を最小化することです：

$$
\frac{1}{2} x^T Q x + c^T x
$$

cp.quad_form(x, Q) は$ (x^T Q x) $を計算し、c.T @ x は$ (c^T x) $を計算します。
これらを足し合わせて目的関数を作成し、cp.Minimize を使って最小化します。

5. 制約の定義

1
2
# 制約の定義
constraints = [A @ x <= b]

制約条件を定義しています。
ここでは、以下の形式の線形不等式制約を設定しています：

$$
A x \leq b
$$

6. 問題の定義

1
2
# 問題の定義
prob = cp.Problem(objective, constraints)

最適化問題全体を定義しています。
cp.Problem 関数は、目的関数と制約条件を受け取り、最適化問題を作成します。

7. 問題を解く

1
2
# 問題を解く
result = prob.solve()

定義した最適化問題を解きます。
prob.solve() メソッドは、問題を解いて最適値を返します。

8. 結果の表示

1
2
3
# 結果の表示
print(f"Optimal value: {result}")
print(f"Optimal solution: x = {x.value}")

最適化の結果を表示します。

  • result は最適値（目的関数の最小値）です。
  • x.value は最適解（変数 x の値）です。

全体の流れ

  1. ライブラリをインポートし、パラメータを定義。
  2. 最適化変数を定義。
  3. 目的関数を定義。
  4. 制約条件を定義。
  5. 目的関数と制約条件を組み合わせて最適化問題を定義。
  6. 問題を解く。
  7. 結果を表示する。

このコードは、二次計画問題を解くための一般的な方法を示しており、CVXPYライブラリを使うことで問題の定義と解決を簡潔に行えることを示しています。

結果解説

Optimal value: -10.399999999999999

最適値（目的関数の最小値）は$ (-10.4) $です。
これは、与えられた二次計画問題において、制約条件 $(Ax \leq b) $を満たす$ (x) $に対して目的関数が最小となる値です。

Optimal solution: x = [1.2, 1.6]

最適解$ (x = [1.2, 1.6]) $です。
これは、目的関数$ (\frac{1}{2}x^T Q x + c^T x) $が最小値をとる$ (x) $の値です。
この$ (x) $に対して、制約条件$ (Ax \leq b) $がすべて満たされます。

計算の詳細

目的関数の計算

与えられた$ (x = [1.2, 1.6]) $に対して目的関数を計算します。

$$
\frac{1}{2}x^T Q x + c^T x
$$

まず、二次項を計算します：
$$
x^T Q x = \begin{bmatrix} 1.2 & 1.6 \end{bmatrix} \begin{bmatrix} 2 & 0 \ 0 & 2 \end{bmatrix} \begin{bmatrix} 1.2 \ 1.6 \end{bmatrix} = 1.2 \times 2 \times 1.2 + 1.6 \times 2 \times 1.6 = 2.88 + 5.12 = 8.0
$$

次に、線形項を計算します：
$$
c^T x = \begin{bmatrix} -4 & -6 \end{bmatrix} \begin{bmatrix} 1.2 \ 1.6 \end{bmatrix} = -4 \times 1.2 + -6 \times 1.6 = -4.8 - 9.6 = -14.4
$$

したがって、目的関数の値は：
$$
\frac{1}{2} \times 8.0 + (-14.4) = 4.0 - 14.4 = -10.4
$$

これは、表示された最適値と一致します。

制約条件の確認

次に、与えられた最適解 $(x = [1.2, 1.6]) $が制約を満たすことを確認します：

$$
Ax = \begin{bmatrix} 1 & 1 \ -1 & 2 \ 2 & 1 \end{bmatrix} \begin{bmatrix} 1.2 \ 1.6 \end{bmatrix} = \begin{bmatrix} 1 \times 1.2 + 1 \times 1.6 \ -1 \times 1.2 + 2 \times 1.6 \ 2 \times 1.2 + 1 \times 1.6 \end{bmatrix} = \begin{bmatrix} 2.8 \ 2.0 \ 4.0 \end{bmatrix}
$$

これに対して、制約条件 $(b = [3, 2, 4]) $と比較します：
$$
\begin{bmatrix} 2.8 \ 2.0 \ 4.0 \end{bmatrix} \leq \begin{bmatrix} 3 \ 2 \ 4 \end{bmatrix}
$$

すべての不等式が満たされていることが確認できます。

結論

この問題に対する最適解は$ (x = [1.2, 1.6]) $であり、最適値は$ (-10.4) $です。
与えられた制約条件を満たしつつ、目的関数の値を最小化する解が求められました。