係数行列による目的関数の作成¶

目的関数を表現する方法の 1 つとして、多項式の係数からなる多次元配列を用いる方法が用意されています。この方法は、目的関数が \(x^\top Q x + p^\top x + c\) と表されるような実数値の 2 次元配列 \(Q\) と実数ベクトル \(p\) がすでに計算されている場合に便利な定式化方法です。また、目的関数の項の数が変数の数の 2 乗程度の場合に、定式化速度において Poly クラスを用いて目的関数を構築する場合と比較して有利となる場合があります。

係数行列クラス¶

2 次の変数多項式は次のように行列で表現することができます。

\[x^\top Qx + p^\top x + c\]

ここで、\(x\) は変数のベクトル、\(Q\) は係数行列、\(p\) は係数のベクトル、\(c\) は定数です。

例えば、次の二次形式のバイナリ変数多項式は

\[2 q_0 q_1 + q_0 - q_1 + 1\]

次のように行列とベクトルで表現できます:

\[\begin{split}Q = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} , \quad p^\top = \begin{pmatrix} 1 & -1 \end{pmatrix} , \quad c = 1\end{split}\]

\[x^\top = \begin{pmatrix} q_0 & q_1 \end{pmatrix}\]

VariableGenerator の matrix() メソッドは、変数ベクトルの長さを指定して Matrix クラスのインスタンスで表現された二次の変数多項式を作成します。

次のようにして長さ 2 のバイナリ変数ベクトルを持つ Matrix クラスのインスタンスを作成できます。

from amplify import VariableGenerator

gen = VariableGenerator()
m = gen.matrix("Binary", 2)

>>> print(m)
(x^T) Q x + (p^T) x + c
where:
  x = [q_0, q_1],
  Q = [[ 0.,  0.],
       [ 0.,  0.]],
  p = [ 0.,  0.],
  c = 0

例として、多項式 \(2 q_0 q_1 + q_0 - q_1 + 1\) に対応する係数を与えます。

二次の係数行列は quadratic アトリビュートで NumPy 配列 (numpy.ndarray) として与えられます。次のように要素アクセスによって係数行列の値を設定できます。

q = m.quadratic
q[0, 1] = 1
q[1, 0] = 1

または、配列の形が同じであれば、NumPy 配列を代入することもできます。

import numpy

m.quadratic = numpy.array([[0, 1], [1, 0]])

注釈

\(Q\) は必ずしも対称行列である必要はありません。上記の例では \(Q_{0, 1} + Q_{1, 0} = 2\) を満たしていれば十分です。

同様に、一次の係数ベクトルは linear、定数は constant アトリビュートで取得できます。

p = m.linear
p[0] = 1
p[1] = -1
m.constant = 1

正しく係数が設定できたか確認します。

>>> print(m)
(x^T) Q x + (p^T) x + c
where:
  x = [q_0, q_1],
  Q = [[ 0.,  1.],
       [ 1.,  0.]],
  p = [ 1., -1.],
  c = 1

注釈

\(Q\) の対角項は二乗の項の係数を表しますが、バイナリ変数およびイジング変数において、変数を二乗したものはその変数および 1 とそれぞれ一致するため、注意が必要です。

バイナリ変数多項式
- 一次の係数は \(Q\) の対角項と \(p\) から決定されます
イジング変数多項式
- 定数は \(Q\) の対角項と \(c\) から決定されます

Matrix の持つ変数配列を取得するには、variable_array アトリビュートを参照します。制約条件は多項式クラス (Poly) で与えるため、行列形式の目的関数に制約条件を与えたい場合には変数配列を取得する必要があります。

>>> x = m.variable_array
>>> print(x)
[q_0, q_1]

行列形式から多項式クラス (Poly) への変換は to_poly() メソッドで行えます。

>>> print(m.to_poly())
2 q_0 q_1 + q_0 - q_1 + 1

Tip

上記の例では変数配列が一次元ベクトルでしたが、多次元の変数配列に対しても同様に行列形式を作成できます。

>>> gen = VariableGenerator()
>>> m = gen.matrix("Binary", shape=(2, 2))
>>> print(m)
(x^T) Q x + (p^T) x + c
where:
  x = [[q_{0,0}, q_{0,1}],
       [q_{1,0}, q_{1,1}]],
  Q = [[[[ 0.,  0.],
         [ 0.,  0.]],
        [[ 0.,  0.],
         [ 0.,  0.]]],
       [[[ 0.,  0.],
         [ 0.,  0.]],
        [[ 0.,  0.],
         [ 0.,  0.]]]],
  p = [[ 0.,  0.],
       [ 0.,  0.]],
  c = 0

変数配列の次元を \(n\) として一般に、\(Q\) は次元数 \(2n\) の係数配列 (\(n = 1\) の場合は行列)、\(p\) は係数の \(n\) 次元配列 (\(n = 1\)の場合はベクトル)、\(c\) は定数を表します。多次元配列の行列形式は二次割当問題の定式化など、多次元の変数を用いた高速な定式化において有用なことがあります。