picos.expressions.exp_quadratic¶

Implements QuadraticExpression.

Classes

class picos.expressions.exp_quadratic.QuadraticExpression(string, quadraticPart={}, affinePart=AffineExpression.zero(), scalarFactors=None, copyDecomposition=None)[source]¶

Bases: picos.expressions.expression.Expression

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

__add__(other)[source]¶: Denote addition from the right hand side.

__ge__(other)[source]¶: Return a constraint that the expression is lower-bounded.

__init__(string, quadraticPart={}, affinePart=AffineExpression.zero(), 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.

__le__(other)[source]¶: Return a constraint that the expression is upper-bounded.

__mul__(other)[source]¶: Denote scaling from the right hand side.

__neg__()[source]¶: Denote the negation of the expression.

__radd__(other)[source]¶: Denote addition from the left hand side.

__rmul__(other)[source]¶: Denote scaling from the left hand side.

__rsub__(other)[source]¶: Denote substraction with self on the right hand side.

__sub__(other)[source]¶: Denote substraction from the right hand side.

__truediv__(other)[source]¶: Denote division by a constant scalar.

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[source]¶

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[source]¶

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[source]¶: Affine part $a^Tx + b$ of the quadratic expression.

property cst[source]¶: Constant part $b$ of the quadratic expression.

property fullroot[source]¶

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[source]¶: Linear part $a^Tx$ of the quadratic expression.

property num_quad_terms[source]¶: The number of terms in the simplified quadratic form.

property quad[source]¶: Quadratic part $x^TQx$ of the quadratic expression.

property quadratic_forms¶: The quadratic forms as a map from variable pairs to sparse matrices.

Warning

Do not modify the returned matrices.

Deprecated since version 2.2: This property will be removed in a future release.

property quadroot[source]¶

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$ , this is the pair (a, b). Otherwise, this is None.

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.

Objects

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.

Default value

Fork me on GitLab