Optimization Models
Home
Software
Links
Index
Contact
1. Introduction
1.1. Overview
1.2. Optimization Models
2. Linear Algebra
2.1. Vectors
2.2. Matrices
2.3. Linear Equations
2.4.  Least-Squares
2.5. Eigenvalues
2.6  Singular Values
3. Convex Models
3.1. Convexity
3.2. LP and QP
3.3. SOCP
3.4. Robust LP
3.5. GP
3.6. SDP
3.7. Non-Convex Models
4. Duality
4.1. Weak Duality
4.2. Strong Duality
4.3.  Applications
5. Case Studies
5.1. Senate Voting
5.2. Antenna Arrays
5.3. Localization
5.4. Circuit Design

Semidefinite cone

Positive semidefinite matrices

A symmetric matrix \(P = P^T \in \mathbf{R}^{n \times n}\) is said to be positive semi-definite if the associated quadratic form is non-negative, that is:

\[ \forall \: x \in \mathbf{R}^n  :  x^TPx \ge 0. \]

An alternate condition is that every eigenvalue of \(P\) is non-negative. We use the acronym PSD to refer to the term ‘‘positive semidefinite’’, and the notation \(P \succeq 0\) to express that \(P\) is PSD.

A matrix is said to be positive definite if the above condition is satisfied strictly for non-zero \(x\):

\[ \forall \: x \in \mathbf{R}^n, \;\; x \ne 0  :  x^TPx > 0. \]

An alternate condition is that every eigenvalue of \(P\) is positive. We use the acronym PD to refer to the term ‘‘positive definite’’, and the notation \(P \succ 0\) to express that \(P\) is PD.

Semidefinite cone

The set of PSD matrices in \(\mathbf{R}^{n \times n}\) is denoted \(\mathbf{S}_+\). That of PD matrices, \(\mathbf{S}_{++}\).

The set \(\mathbf{S}_+\) is a convex cone, called the semidefinite cone. The fact that it is convex derives from its expression as the intersection of half-spaces in the subspace \(\mathbf{S}^n\) of symmetric matrices. Indeed, we have

\[ \mathbf{S}_+ = \bigcap_{x \in \mathbf{R}^n} \left\{ P \in \mathbf{S}^n  :  x^TPx \ge 0 \right\} . \]

Rank-one PSD matrices

PSD matrices with rank one can be expressed as \(P = vv^T\) for some \(v \in \mathbf{R}^n\). The associated quadratic form is a squared linear form:

\[ x^TPx = x^T(vv^T)x = (x^Tv) (v^Tx) = (v^Tx)^2. \]

Link with covariance matrices

Covariance matrices are PSD matrices, since they can be expressed as an expected value of a squared linear form: if \(X\) is a random variable, the covariance matrix of \(X\) is defined as

\[ \mathbf{E} (X - \mathbf{E}(X))(X - \mathbf{E}(X))^T, \]

where \(\mathbf{E}\) denotes the expectation operator. Conversely, any PSD matrix can be interpreted as a covariance matrix, for some distribution. Hence, the PSD cone is exactly the set of covariance matrices.