Objective Function with a Coefficient MatrixΒΆ

One way to represent the objective function is by using a multidimensional polynomial coefficient array. This formulation is convenient in one case. It applies when a real-valued two-dimensional array \(Q\) and a real-valued vector \(p\) are already calculated. Then 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 approach can be advantageous. It is faster to formulate than the objective function built with 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. It 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 check that the coefficients are set as expected.

>>> 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. Be careful with binary and Ising variables. For them, 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, let \(n\) be the dimension of the variable array. Then \(Q\) is a coefficient array of dimension \(2n\) (a matrix for \(n = 1\)). Also, \(p\) is an array of coefficients of dimension \(n\) (a vector for \(n = 1\)). Finally, \(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.