二次計画法（Quadratic Programming, QP）

二次計画法（Quadratic Programming, QP）

CVXPYを使用して二次計画法（Quadratic Programming, QP）の問題を解く方法を説明します。

二次計画法の一般的な形式は以下のようになります。

目的関数：
$$
\text{minimize} \quad \frac{1}{2} x^T P x + q^T x
$$

制約：
$$
Gx \leq h
$$
$$
Ax = b
$$

ここで、$(x)$は決定変数のベクトル、$(P)$は正定値対称行列、$(q)$はベクトル、$(G)$、$(h)$、$(A)$、および$(b)$はそれぞれ行列またはベクトルです。

プログラム例

以下は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
28
29
import cvxpy as cp
import numpy as np

# 定義する二次計画法の問題
P = np.array([[2, 0], [0, 2]])    # 目的関数の2次項の係数
q = np.array([-2, -5])            # 目的関数の1次項の係数
G = np.array([[1, 2], [1, -4], [-1, 0], [0, -1]]) # 不等式制約の係数
h = np.array([3, 3, 0, 0])        # 不等式制約の右辺
A = np.array([[1, 1]])            # 等式制約の係数
b = np.array([1])                 # 等式制約の右辺

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

# 目的関数を定義
objective = cp.Minimize((1/2) * cp.quad_form(x, P) + q @ x)

# 制約を定義
constraints = [G @ x <= h, A @ x == b]

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

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

# 結果を出力
print(f"最適値: {result}")
print(f"最適解: {x.value}")

説明

  1. 行列およびベクトルの定義:

    • P、q、G、h、A、b それぞれ問題の行列およびベクトルを定義します。

  2. 変数の定義:

    • x = cp.Variable(2) で、最適化変数 $( x ) $を定義します。
      ここでは2次元の変数を考えています。

  3. 目的関数の設定:

    • objective = cp.Minimize((1/2) * cp.quad_form(x, P) + q @ x) で、目的関数を定義しています。

  4. 制約の設定:

    • constraints = [G @ x <= h, A @ x == b] で不等式制約と等式制約を定義しています。

  5. 問題の解決:

    • prob = cp.Problem(objective, constraints) で問題を作成し、result = prob.solve() で解を求めます。

  6. 結果の出力:

    • 最適値と最適解を出力します。

このようにして、CVXPYを使用して二次計画法の問題をシンプルに解くことができます。

CVXPYは非常に強力であり、もっと複雑な制約や目的関数にも対応することができます。

[実行結果]

最適値: -4.0
最適解: [1.78280298e-24 1.00000000e+00]

結果解説

CVXPYを使用した二次計画法の解の結果について説明します。

解の結果

  • 最適値 (Objective Value): $-4.0$
  • 最適解 (Optimal Solution): $[1.78280298e-24, 1.00000000e+00]$

1. 最適値 (Objective Value)

最適値: -4.0 という結果は、設定した二次計画法の目的関数を最小化したときの最小値が$ -4.0 $になることを示しています。
つまり、与えられた制約の範囲内で目的関数の評価が最も低くなる点（最適解）での値が$ -4.0 $です。

2. 最適解 (Optimal Solution)

最適解: [1.78280298e-24, 1.00000000e+00] という結果は、$( x ) $の最適値が$ [1.78280298e-24, 1.00000000e+00] $であることを示しています。
これが、与えられた目的関数を最小にする$ ( x ) $の値です。

結果の詳細

  • 最適解$ ( x )$:
    • $( x_1 ) = 1.78280298e-24$
    • $( x_2 ) = 1.00000000e+00$

ここで、$( x_1 ) $が非常に小さい値（ほぼゼロ）になっていますが、これは最適解の計算過程での丸め誤差や数値計算の性質からくるものです。

実質的には$ ( x_1 \approx 0 ) $と解釈しても問題ありません。

制約の確認

この結果が制約を満たしていることを確認してみましょう。

【不等式制約】
$[ Gx \leq h ]$

ここで$ ( G ) $と$ ( h ) $は次のように定義されます。
$[ G = \begin{pmatrix} 1 & 2 \ 1 & -4 \ -1 & 0 \ 0 & -1 \end{pmatrix}, \quad h = \begin{pmatrix} 3 \ 3 \ 0 \ 0 \end{pmatrix} ]$

最適解$ ( x ) $が $[0, 1] $付近であることを考慮します。

  • 第1の制約: $( 1 \cdot 0 + 2 \cdot 1 \leq 3 ) $ は$ ( 2 \leq 3 ) $で成立。
  • 第2の制約: $( 1 \cdot 0 - 4 \cdot 1 \leq 3 ) $は$ ( -4 \leq 3 ) $で成立。
  • 第3の制約: $( -1 \cdot 0 \leq 0 ) $は$ ( 0 \leq 0 ) $で成立。
  • 第4の制約: $( 0 - 1 \cdot 1 \leq 0 ) $は$ ( -1 \leq 0 ) $で成立。

これらの不等式制約はすべて満たされています。

【等式制約】
$[ Ax = b ]$

ここで $( A ) $と$ ( b ) $は次のように定義されます。
$[ A = \begin{pmatrix} 1 & 1 \end{pmatrix}, \quad b = 1 ]$

  • 制約: $( 1 \cdot 0 + 1 \cdot 1 = 1 )$

こちらの等式制約も満たされています。

まとめ

今回求めた最適解と最適値は、与えられた二次計画法の目的関数および制約条件に対して正しく計算されています。

最適解$ [1.78280298e-24, 1.00000000e+00] $が正しい最適解であり、これにより目的関数の最小値 $ -4.0 $が得られました。

  • 最適値 (目的関数の最小値) は$ -4.0$。
  • 最適解は$ ( x_1 \approx 0 )$、$( x_2 = 1 )$。