picos.expressions.exp_quadratic

Implements QuadraticExpression.

Outline

Classes

QuadraticExpression

A scalar quadratic expression of the form x^TQx + a^Tx + b.

Classes

QuadraticExpression

class picos.expressions.exp_quadratic.QuadraticExpression(string, quadraticPart={}, affinePart=<1×1 Real Constant: 0>, scalarFactors=None, copyDecomposition=None)[source]

Bases: picos.expressions.expression.Expression

A scalar quadratic expression of the form x^TQx + a^Tx + b.

__init__(string, quadraticPart={}, affinePart=<1×1 Real Constant: 0>, scalarFactors=None, copyDecomposition=None)[source]

Initialize a scalar quadratic expression.

This constructor is meant for internal use. As a user, you will most likely want to build expressions starting from variables or a Constant.

Parameters
  • string (str) – A symbolic string description.

  • quadraticPart – A dict mapping PICOS variable pairs to CVXOPT matrices. Each entry (x, y) \mapsto A_{xy} represents a quadratic form \operatorname{vec_x}(x)^T A_{xy} \operatorname{vec_y}(y) where \operatorname{vec_x} and \operatorname{vec_y} refer to the isometric real vectorizations that are used by PICOS internally to store the variables x and y, respectively. The quadratic part Q of the expression is then given as Q = \sum_{x, y} A_{xy}.

  • affinePart (AffineExpression) – The affine part a^Tx + b of the expression.

  • scalarFactors – A pair (u, v) with both u and v scalar real affine expressions representing a known x^TQx + a^Tx + b = uv factorization of the expression.

  • copyDecomposition (QuadraticExpression) – Another quadratic expression with equal quadratic part whose quadratic part decomposition shall be copied.

property A

An affine-augmented quadratic coefficient matrix, condensed.

For a quadratic expression x^TQx + a^Tx + b, this is A = \begin{bmatrix}Q&\frac{a}{2}\\\frac{a^T}{2}&b\end{bmatrix} but with zero rows and columns removed.

The vector y is a condensed version of x that refers to this matrix, so that q.y.T*q.A*q.y equals the expression q.

Raises

ValueError – When the expression is zero.

property L

The L of an LL^T Cholesky decomposition of Q.

Returns

A CVXOPT lower triangular sparse matrix.

Raises
  • ValueError – When the quadratic part is zero.

  • ArithmeticError – When the expression is not convex, that is when the matrix Q is not numerically positive semidefinite.

property M

The M of an MM^T Cholesky decomposition of A.

Returns

A CVXOPT lower triangular sparse matrix.

Raises
  • ValueError – When the expression is zero.

  • ArithmeticError – When the expression can not be written as a squared norm, that is when the extended matrix A is not numerically positive semidefinite.

property Q

The coefficient matrix Q of the expression, condensed.

This equals the Q of the quadratic expression x^TQx + a^Tx + b but with zero rows and columns removed.

The vector x is a condensed version of x that refers to this matrix, so that q.x.T*q.Q*q.x equals the quadratic part x^TQx of the expression q.

Raises

ValueError – When the quadratic part is zero.

property aff

Affine part a^Tx + b of the quadratic expression.

property cst

Constant part b of the quadratic expression.

property fullroot

Affine expression whose squared norm equals the expression.

For a convex quadratic expression q, this is equal to the vector q.M.T*q.y with zero rows removed.

Construction

For a quadratic expression x^TQx + a^Tx + b with A = \begin{bmatrix}Q&\frac{a}{2}\\\frac{a^T}{2}&b\end{bmatrix} positive semidefinite, let A = MM^T be a Cholesky decomposition. Let further y = \begin{bmatrix}x^T & 1\end{bmatrix}^T. Then,

x^TQx + a^Tx + b
&= y^TAy \\
&= y^TMM^Ty \\
&= (M^Ty)^TM^Ty \\
&= \langle M^Ty, M^Ty \rangle \\
&= \lVert M^Ty \rVert^2.

Note that removing zero rows from M^Ty does not affect the norm.

Raises
  • ValueError – When the expression is zero.

  • ArithmeticError – When the expression is not convex, that is when the quadratic part is not numerically positive semidefinite.

property is0

Whether the quadratic expression is zero.

property is_squared_norm

Whether the expression can be written as a squared norm.

If this is True, then the there is a coefficient vector c such that

\lVert c^T \begin{bmatrix} x \\ 1 \end{bmatrix} \rVert^2
= x^TQx + a^Tx + b.

If the expression is also nonzero, then fullroot is c^T \begin{bmatrix} x^T & 1 \end{bmatrix}^T with zero entries removed.

property lin

Linear part a^Tx of the quadratic expression.

property num_quad_terms

The number of terms in the simplified quadratic form.

property quad

Quadratic part x^TQx of the quadratic expression.

property quadratic_forms

The quadratic forms as sparse matrices.

property quadroot

Affine expression whose squared norm equals x^TQx.

For a convex quadratic expression q, this is equal to the vector q.L.T*q.x with zero rows removed.

Construction

Let x^TQx be the quadratic part of the expression with Q positive semidefinite and Q = LL^T a Cholesky decomposition. Then,

x^TQx
&= x^TLL^Tx \\
&= (L^Tx)^TL^Tx \\
&= \langle L^Tx, L^Tx \rangle \\
&= \lVert L^Tx \rVert^2.

Note that removing zero rows from L^Tx does not affect the norm.

Raises
  • ValueError – When the quadratic part is zero.

  • ArithmeticError – When the expression is not convex, that is when the quadratic part is not numerically positive semidefinite.

property rank

The length of the vector quadroot.

Up to numerical considerations, this is the rank of the (convex) quadratic coefficient matrix Q of the expression.

Raises

ArithmeticError – When the expression is not convex, that is when the quadratic part is not numerically positive semidefinite.

property scalar_factors

Decomposition into scalar real affine expressions.

If the expression is known to be equal to ab for scalar real affine expressions a and b, returns the pair (a, b). Otherwise, returns the empty tuple ().

Note that if a = b, then also a is b in the returned tuple.

property x

The stacked variable vector x of the expression, condensed.

This equals the x of the quadratic expression x^TQx + a^Tx + b but entries corresponding to zero rows and columns in Q are removed, so that q.x.T*q.Q*q.x equals the x^TQx part of the expression q.

Raises

ValueError – When the quadratic part is zero.

property y

See A.

Raises

ValueError – When the expression is zero.

Data

picos.expressions.exp_quadratic.PSD_PERTURBATIONS

Maximum number of singular quadratic form perturbations.

PICOS uses NumPy either or CHOLMOD to compute a Cholesky decomposition of a positive semidefinite quadratic form Q. Both libraries require Q to be nonsingular, which is not a requirement on PICOS’ end. If either library rejects Q, then PICOS provides a sequence of PSD_PERTURBATIONS perturbed quadratic forms Q + \epsilon I for increasing \epsilon until the perturbed matrix is found positive definite or until the largest \epsilon was tested unsuccessfully.

If this is zero, PICOS will only decompose quadratic forms that are nonsingular. If this is one, then only the largest epsilon is tested.