Skip to content

QuadraticExpression

Bases: QuadraticProgramElement

Representation of a quadratic expression by its coefficients.

Source code in q3as/quadratic/problems/quadratic_expression.py 
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
class QuadraticExpression(QuadraticProgramElement):
    """Representation of a quadratic expression by its coefficients."""

    def __init__(
        self,
        quadratic_program: Any,
        coefficients: Union[
            ndarray,
            spmatrix,
            List[List[float]],
            Dict[Tuple[Union[int, str], Union[int, str]], float],
        ],
    ) -> None:
        """Creates a new quadratic expression.

        The quadratic expression can be defined via an array, a list, a sparse matrix, or a
        dictionary that uses variable names or indices as keys and stores the values internally as a
        dok_matrix. We stores values in a compressed way, i.e., values at symmetric positions are
        summed up in the upper triangle. For example, {(0, 1): 1, (1, 0): 2} -> {(0, 1): 3}.

        Args:
            quadratic_program: The parent QuadraticProgram.
            coefficients: The (sparse) representation of the coefficients.

        """
        super().__init__(quadratic_program)
        self.coefficients = coefficients

    def __getitem__(self, key: Tuple[Union[int, str], Union[int, str]]) -> float:
        """Returns the coefficient where i, j can be a variable names or indices.

        Args:
            key: The tuple of indices or names of the variables corresponding to the coefficient.

        Returns:
            The coefficient corresponding to the addressed variables.
        """
        i, j = key
        if isinstance(i, str):
            i = self.quadratic_program.variables_index[i]
        if isinstance(j, str):
            j = self.quadratic_program.variables_index[j]
        return self.coefficients[min(i, j), max(i, j)]

    def __setitem__(
        self, key: Tuple[Union[int, str], Union[int, str]], value: float
    ) -> None:
        """Sets the coefficient where i, j can be a variable names or indices.

        Args:
            key: The tuple of indices or names of the variables corresponding to the coefficient.
            value: The coefficient corresponding to the addressed variables.
        """
        i, j = key
        if isinstance(i, str):
            i = self.quadratic_program.variables_index[i]
        if isinstance(j, str):
            j = self.quadratic_program.variables_index[j]
        self.coefficients[min(i, j), max(i, j)] = value

    def _coeffs_to_dok_matrix(
        self,
        coefficients: Union[
            ndarray,
            spmatrix,
            List[List[float]],
            Dict[Tuple[Union[int, str], Union[int, str]], float],
        ],
    ) -> dok_matrix:
        """Maps given coefficients to a dok_matrix.

        Args:
            coefficients: The coefficients to be mapped.

        Returns:
            The given coefficients as a dok_matrix

        Raises:
            QiskitOptimizationError: if coefficients are given in unsupported format.
        """
        if isinstance(coefficients, (list, ndarray, spmatrix)):
            coefficients = dok_matrix(coefficients)
        elif isinstance(coefficients, dict):
            n = self.quadratic_program.get_num_vars()
            coeffs = dok_matrix((n, n))
            for (i, j), value in coefficients.items():
                if isinstance(i, str):
                    i = self.quadratic_program.variables_index[i]
                if isinstance(j, str):
                    j = self.quadratic_program.variables_index[j]
                coeffs[i, j] = value
            coefficients = coeffs
        else:
            raise QiskitOptimizationError(
                f"Unsupported format for coefficients: {coefficients}"
            )
        return self._triangle_matrix(coefficients)

    @staticmethod
    def _triangle_matrix(mat: dok_matrix) -> dok_matrix:
        lower = tril(mat, -1, format="dok")
        # `todok` is necessary because subtraction results in other format
        return (mat + lower.transpose() - lower).todok()

    @staticmethod
    def _symmetric_matrix(mat: dok_matrix) -> dok_matrix:
        upper = triu(mat, 1, format="dok") / 2
        # `todok` is necessary because subtraction results in other format
        return (mat + upper.transpose() - upper).todok()

    @property
    def coefficients(self) -> dok_matrix:
        """Returns the coefficients of the quadratic expression.

        Returns:
            The coefficients of the quadratic expression.
        """
        return self._coefficients

    @coefficients.setter
    def coefficients(
        self,
        coefficients: Union[
            ndarray,
            spmatrix,
            List[List[float]],
            Dict[Tuple[Union[int, str], Union[int, str]], float],
        ],
    ) -> None:
        """Sets the coefficients of the quadratic expression.

        Args:
            coefficients: The coefficients of the quadratic expression.
        """
        self._coefficients = self._coeffs_to_dok_matrix(coefficients)

    def to_array(self, symmetric: bool = False) -> ndarray:
        """Returns the coefficients of the quadratic expression as array.

        Args:
            symmetric: Determines whether the output is in a symmetric form or not.

        Returns:
            An array with the coefficients corresponding to the quadratic expression.
        """
        coeffs = (
            self._symmetric_matrix(self._coefficients)
            if symmetric
            else self._coefficients
        )
        return coeffs.toarray()

    def to_dict(
        self, symmetric: bool = False, use_name: bool = False
    ) -> Dict[Union[Tuple[int, int], Tuple[str, str]], float]:
        """Returns the coefficients of the quadratic expression as dictionary, either using tuples
        of variable names or indices as keys.

        Args:
            symmetric: Determines whether the output is in a symmetric form or not.
            use_name: Determines whether to use index or names to refer to variables.

        Returns:
            An dictionary with the coefficients corresponding to the quadratic expression.
        """
        coeffs = (
            self._symmetric_matrix(self._coefficients)
            if symmetric
            else self._coefficients
        )
        if use_name:
            return {
                (
                    self.quadratic_program.variables[i].name,
                    self.quadratic_program.variables[j].name,
                ): v
                for (i, j), v in coeffs.items()
            }
        else:
            return {(int(i), int(j)): v for (i, j), v in coeffs.items()}

    def evaluate(self, x: Union[ndarray, List, Dict[Union[int, str], float]]) -> float:
        """Evaluate the quadratic expression for given variables: x * Q * x.

        Args:
            x: The values of the variables to be evaluated.

        Returns:
            The value of the quadratic expression given the variable values.
        """
        x = self._cast_as_array(x)

        # compute x * Q * x for the quadratic expression
        val = x @ self.coefficients @ x

        # return the result
        return val

    def evaluate_gradient(
        self, x: Union[ndarray, List, Dict[Union[int, str], float]]
    ) -> ndarray:
        """Evaluate the gradient of the quadratic expression for given variables.

        Args:
            x: The values of the variables to be evaluated.

        Returns:
            The value of the gradient quadratic expression given the variable values.
        """
        x = self._cast_as_array(x)

        # compute (Q' + Q) * x for the quadratic expression
        val = (self.coefficients.transpose() + self.coefficients) @ x

        # return the result
        return val

    def _cast_as_array(
        self, x: Union[ndarray, List, Dict[Union[int, str], float]]
    ) -> Union[dok_matrix, np.ndarray]:
        """Converts input to an array if it is a dictionary or list."""
        if isinstance(x, dict):
            x_aux = np.zeros(self.quadratic_program.get_num_vars())
            for i, v in x.items():
                if isinstance(i, str):
                    i = self.quadratic_program.variables_index[i]
                x_aux[i] = v
            x = x_aux
        if isinstance(x, list):
            x = np.array(x)
        return x

    @property
    def bounds(self) -> ExpressionBounds:
        """Returns the lower bound and the upper bound of the quadratic expression

        Returns:
            The lower bound and the upper bound of the quadratic expression

        Raises:
            QiskitOptimizationError: if the quadratic expression contains any unbounded variable
        """
        l_b = u_b = 0.0
        for (ind1, ind2), coeff in self.to_dict().items():
            x = self.quadratic_program.get_variable(ind1)
            if x.lowerbound == -INFINITY or x.upperbound == INFINITY:
                raise QiskitOptimizationError(
                    f"Quadratic expression contains an unbounded variable: {x.name}"
                )
            y = self.quadratic_program.get_variable(ind2)
            if y.lowerbound == -INFINITY or y.upperbound == INFINITY:
                raise QiskitOptimizationError(
                    f"Quadratic expression contains an unbounded variable: {y.name}"
                )
            lst = []
            if ind1 == ind2:
                if x.lowerbound * x.upperbound <= 0.0:
                    # lower bound and upper bound have different signs
                    lst.append(0.0)
                lst.extend([x.lowerbound**2, x.upperbound**2])
            else:
                lst.extend(
                    [
                        x.lowerbound * y.lowerbound,
                        x.lowerbound * y.upperbound,
                        x.upperbound * y.lowerbound,
                        x.upperbound * y.upperbound,
                    ]
                )
            lst2 = [coeff * val for val in lst]
            l_b += min(lst2)
            u_b += max(lst2)
        return ExpressionBounds(lowerbound=l_b, upperbound=u_b)

    def __repr__(self):
        # pylint: disable=cyclic-import
        from ..translators.prettyprint import expr2str, DEFAULT_TRUNCATE

        return f"<{self.__class__.__name__}: {expr2str(quadratic=self, truncate=DEFAULT_TRUNCATE)}>"

    def __str__(self):
        # pylint: disable=cyclic-import
        from ..translators.prettyprint import expr2str

        return f"{expr2str(quadratic=self)}"

bounds: ExpressionBounds property

Returns the lower bound and the upper bound of the quadratic expression

Returns:

Type Description
ExpressionBounds

The lower bound and the upper bound of the quadratic expression

Raises:

Type Description
QiskitOptimizationError

if the quadratic expression contains any unbounded variable

coefficients: dok_matrix property writable

Returns the coefficients of the quadratic expression.

Returns:

Type Description
dok_matrix

The coefficients of the quadratic expression.

__getitem__(key)

Returns the coefficient where i, j can be a variable names or indices.

Parameters:

Name Type Description Default
key Tuple[Union[int, str], Union[int, str]]

The tuple of indices or names of the variables corresponding to the coefficient.

 required

Returns:

Type Description
float

The coefficient corresponding to the addressed variables.
Source code in q3as/quadratic/problems/quadratic_expression.py 
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
def __getitem__(self, key: Tuple[Union[int, str], Union[int, str]]) -> float:
    """Returns the coefficient where i, j can be a variable names or indices.

    Args:
        key: The tuple of indices or names of the variables corresponding to the coefficient.

    Returns:
        The coefficient corresponding to the addressed variables.
    """
    i, j = key
    if isinstance(i, str):
        i = self.quadratic_program.variables_index[i]
    if isinstance(j, str):
        j = self.quadratic_program.variables_index[j]
    return self.coefficients[min(i, j), max(i, j)]

__init__(quadratic_program, coefficients)

Creates a new quadratic expression.

The quadratic expression can be defined via an array, a list, a sparse matrix, or a dictionary that uses variable names or indices as keys and stores the values internally as a dok_matrix. We stores values in a compressed way, i.e., values at symmetric positions are summed up in the upper triangle. For example, {(0, 1): 1, (1, 0): 2} -> {(0, 1): 3}.

Parameters:

Name Type Description Default
quadratic_program Any

The parent QuadraticProgram.

 required
coefficients Union[ndarray, spmatrix, List[List[float]], Dict[Tuple[Union[int, str], Union[int, str]], float]]

The (sparse) representation of the coefficients.

 required
Source code in q3as/quadratic/problems/quadratic_expression.py 
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def __init__(
    self,
    quadratic_program: Any,
    coefficients: Union[
        ndarray,
        spmatrix,
        List[List[float]],
        Dict[Tuple[Union[int, str], Union[int, str]], float],
    ],
) -> None:
    """Creates a new quadratic expression.

    The quadratic expression can be defined via an array, a list, a sparse matrix, or a
    dictionary that uses variable names or indices as keys and stores the values internally as a
    dok_matrix. We stores values in a compressed way, i.e., values at symmetric positions are
    summed up in the upper triangle. For example, {(0, 1): 1, (1, 0): 2} -> {(0, 1): 3}.

    Args:
        quadratic_program: The parent QuadraticProgram.
        coefficients: The (sparse) representation of the coefficients.

    """
    super().__init__(quadratic_program)
    self.coefficients = coefficients

__setitem__(key, value)

Sets the coefficient where i, j can be a variable names or indices.

Parameters:

Name Type Description Default
key Tuple[Union[int, str], Union[int, str]]

The tuple of indices or names of the variables corresponding to the coefficient.

 required
value float

The coefficient corresponding to the addressed variables.

 required
Source code in q3as/quadratic/problems/quadratic_expression.py 
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
def __setitem__(
    self, key: Tuple[Union[int, str], Union[int, str]], value: float
) -> None:
    """Sets the coefficient where i, j can be a variable names or indices.

    Args:
        key: The tuple of indices or names of the variables corresponding to the coefficient.
        value: The coefficient corresponding to the addressed variables.
    """
    i, j = key
    if isinstance(i, str):
        i = self.quadratic_program.variables_index[i]
    if isinstance(j, str):
        j = self.quadratic_program.variables_index[j]
    self.coefficients[min(i, j), max(i, j)] = value

evaluate(x)

Evaluate the quadratic expression for given variables: x * Q * x.

Parameters:

Name Type Description Default
x Union[ndarray, List, Dict[Union[int, str], float]]

The values of the variables to be evaluated.

 required

Returns:

Type Description
float

The value of the quadratic expression given the variable values.
Source code in q3as/quadratic/problems/quadratic_expression.py 
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
def evaluate(self, x: Union[ndarray, List, Dict[Union[int, str], float]]) -> float:
    """Evaluate the quadratic expression for given variables: x * Q * x.

    Args:
        x: The values of the variables to be evaluated.

    Returns:
        The value of the quadratic expression given the variable values.
    """
    x = self._cast_as_array(x)

    # compute x * Q * x for the quadratic expression
    val = x @ self.coefficients @ x

    # return the result
    return val

evaluate_gradient(x)

Evaluate the gradient of the quadratic expression for given variables.

Parameters:

Name Type Description Default
x Union[ndarray, List, Dict[Union[int, str], float]]

The values of the variables to be evaluated.

 required

Returns:

Type Description
ndarray

The value of the gradient quadratic expression given the variable values.
Source code in q3as/quadratic/problems/quadratic_expression.py 
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
def evaluate_gradient(
    self, x: Union[ndarray, List, Dict[Union[int, str], float]]
) -> ndarray:
    """Evaluate the gradient of the quadratic expression for given variables.

    Args:
        x: The values of the variables to be evaluated.

    Returns:
        The value of the gradient quadratic expression given the variable values.
    """
    x = self._cast_as_array(x)

    # compute (Q' + Q) * x for the quadratic expression
    val = (self.coefficients.transpose() + self.coefficients) @ x

    # return the result
    return val

to_array(symmetric=False)

Returns the coefficients of the quadratic expression as array.

Parameters:

Name Type Description Default
symmetric bool

Determines whether the output is in a symmetric form or not.

 False

Returns:

Type Description
ndarray

An array with the coefficients corresponding to the quadratic expression.
Source code in q3as/quadratic/problems/quadratic_expression.py 
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
def to_array(self, symmetric: bool = False) -> ndarray:
    """Returns the coefficients of the quadratic expression as array.

    Args:
        symmetric: Determines whether the output is in a symmetric form or not.

    Returns:
        An array with the coefficients corresponding to the quadratic expression.
    """
    coeffs = (
        self._symmetric_matrix(self._coefficients)
        if symmetric
        else self._coefficients
    )
    return coeffs.toarray()

to_dict(symmetric=False, use_name=False)

Returns the coefficients of the quadratic expression as dictionary, either using tuples of variable names or indices as keys.

Parameters:

Name Type Description Default
symmetric bool

Determines whether the output is in a symmetric form or not.

 False
use_name bool

Determines whether to use index or names to refer to variables.

 False

Returns:

Type Description
Dict[Union[Tuple[int, int], Tuple[str, str]], float]

An dictionary with the coefficients corresponding to the quadratic expression.
Source code in q3as/quadratic/problems/quadratic_expression.py 
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
def to_dict(
    self, symmetric: bool = False, use_name: bool = False
) -> Dict[Union[Tuple[int, int], Tuple[str, str]], float]:
    """Returns the coefficients of the quadratic expression as dictionary, either using tuples
    of variable names or indices as keys.

    Args:
        symmetric: Determines whether the output is in a symmetric form or not.
        use_name: Determines whether to use index or names to refer to variables.

    Returns:
        An dictionary with the coefficients corresponding to the quadratic expression.
    """
    coeffs = (
        self._symmetric_matrix(self._coefficients)
        if symmetric
        else self._coefficients
    )
    if use_name:
        return {
            (
                self.quadratic_program.variables[i].name,
                self.quadratic_program.variables[j].name,
            ): v
            for (i, j), v in coeffs.items()
        }
    else:
        return {(int(i), int(j)): v for (i, j), v in coeffs.items()}