Objective Function with a Coefficient Matrix¶

One way to represent the objective function is by using a multidimensional polynomial coefficient array. This is a convenient formulation when a real-valued two-dimensional array $Q$ and a real-valued vector $p$ have already been calculated so that the objective function is represented as $x^\top Q x + p^\top x + c$. Also, when the number of terms in the objective function is approximately the square of the number of variables, this can be advantageous in terms of formulation speed compared to constructing the objective function using the Poly.

Coefficient matrix class¶

A second-order variable polynomial can be represented by a matrix as follows.

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

Here, $x$ is a vector of variables, $Q$ is a coefficient matrix, $p$ is a vector of coefficients, and $c$ is a constant.

For example, the following binary variable quadratic polynomial

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

can be expressed in terms of the matrix and vector as follows:

\[\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}\]

The matrix() method of VariableGenerator specifies the length of the variable vector and creates a quadratic variable polynomial represented by an instance of the Matrix class.

You can create an instance of the Matrix class with a binary variable vector of length 2 as follows.

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

For example, we give the coefficients corresponding to the polynomial $2 q_0 q_1 + q_0 - q_1 + 1$.

We give a quadratic coefficient matrix in a NumPy array (numpy.ndarray) with the attributes quadratic. You can set the coefficient matrix values by element access as follows.

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

Alternatively, you can assign a NumPy array if the arrays have the same form.

import numpy

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

Note

Q$ does not have to be a symmetric matrix. In the example above, it is sufficient if $Q_{0, 1} + Q_{1, 0} = 2$.

Similarly, you can obtain the first-order coefficient vectors with the linear attribute and constants with the constant attribute.

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

Let’s ensure that the coefficients are set correctly.

>>> 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

Note

The diagonal terms in $Q$ represent the coefficients of the squared terms, but be careful with binary and Ising variables since squaring a variable equals that variable or 1, respectively.

Binary variable polynomials
- First-order coefficients are determined from the diagonal of $Q$ and $p$.
Ising variable polynomials
- The constant is determined from the diagonal term of $Q$ and $c$.

To obtain the variable array that Matrix has, refer to the variable_array attribute. Since constraints are given in polynomial classes (Poly), you need to obtain the variable array to add constraints on a matrix-based objective function.

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

You can convert from the matrix form to a polynomial class (Poly) with the to_poly() method.

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

Tip

In the example above, the variable array was a one-dimensional vector, but a matrix form can be created for a multidimensional variable array as well.

>>> 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

In general, with $n$ as the dimension of the variable array, $Q$ is a coefficient array of dimension $2n$ (a matrix for $n = 1$), $p$ is an array of coefficients of dimension $n$ (a vector for $n = 1$), and $c$ is a constant.

The matrix form of a multidimensional array can be useful in fast formulations with multidimensional variables, such as the formulation of Quadratic Assignment Problem.