1 Definition and Basic Properties

1.1 Linear Matrix Inequalities (LMIs)

A *spectrahedron* is defined as the set of all vectors \(x\in\mathbb{R}^n\) such that a matrix-valued function of \(x\) is positive semidefinite. In standard form, this matrix-valued function is an affine expression \[ A(x)=A_0+\sum_{i=1}^n x_i A_i, \] where each \(A_i\) is a fixed real symmetric matrix of size \(m\times m\). The corresponding spectrahedron is \[ \mathcal{S}=\{x\in\mathbb{R}^n:\ A(x)\succeq 0\}. \] The condition \(A(x)\succeq 0\) is a *linear matrix inequality* (LMI) because the dependence on \(x\) is linear while the inequality is imposed via positive semidefiniteness.

1.2 Positive Semidefinite Matrices and Affine Maps

The basic operation behind spectrahedra is mapping decision variables through an affine map into the cone of positive semidefinite matrices.

1.2.1 Eigenvalue Characterizations

A symmetric matrix \(M\) is positive semidefinite exactly when all its eigenvalues are nonnegative. Equivalently, \(M\succeq 0\) holds if and only if \[ v^\top M v \ge 0 \quad \text{for all } v. \] For spectrahedra, this means feasibility can be tested by evaluating an affine matrix pencil \(A(x)\) and checking that its smallest eigenvalue is at least zero.

1.2.2 Feasibility and Closedness

Because the map \(x\mapsto A(x)\) is continuous and the cone of positive semidefinite matrices is closed, every spectrahedron defined by a fixed LMI is a closed subset of \(\mathbb{R}^n\). The feasible set may be bounded or unbounded depending on whether directions in variable space preserve semidefiniteness.

1.3 Convexity of Spectrahedra

Spectrahedra are convex. If \(x\) and \(y\) satisfy \(A(x)\succeq 0\) and \(A(y)\succeq 0\), then for any \(\lambda\in[0,1]\), \[ A(\lambda x+(1-\lambda)y)=\lambda A(x)+(1-\lambda)A(y)\succeq 0, \] since the positive semidefinite cone is convex and closed under nonnegative linear combinations. This convexity is one of the reasons spectrahedra play a central role in optimization.

1.4 Examples in Low Dimension

In low dimensions, spectrahedra often coincide with familiar convex sets:

  • If \(m=1\), the LMI reduces to a single linear inequality: \(a_0+\sum_i x_i a_i\ge 0\), so \(\mathcal{S}\) is a half-space.
  • In two variables with \(m=2\), the feasibility condition

\[ A(x)=\begin{pmatrix} \alpha(x) & \beta(x)\\ \beta(x) & \gamma(x) \end{pmatrix}\succeq 0 \] can be expressed via \(\alpha(x)\ge 0\), \(\gamma(x)\ge 0\), and \(\det A(x)\ge 0\), yielding regions bounded by quadratic curves in the plane.

  • With diagonal \(A_i\), the LMI decomposes into independent scalar inequalities, producing intersections of half-spaces in different directions.

2 Semidefinite Programming Connection

2.1 Standard Form of Semidefinite Programs

A semidefinite program (SDP) is an optimization problem of the form \[ \min_{x\in\mathbb{R}^n}\ c^\top x \quad \text{subject to } A(x)\succeq 0, \] where \(A(x)=A_0+\sum_i x_i A_i\) and \(c\in\mathbb{R}^n\). More general SDPs also include additional affine equality constraints, but the core geometric object governing feasibility is always a spectrahedron.

2.2 Feasible Sets as Spectrahedra

Given an SDP with LMI constraints, its feasible region is precisely the set of decision variables that render the corresponding matrix constraint positive semidefinite, hence it is a spectrahedron (or an intersection of spectrahedra when multiple LMIs are present).

2.2.1 Objective Functions and Reformulations

While the objective \(c^\top x\) can vary widely (linear in standard SDP form), it does not change the feasible set. Often, SDPs are reformulated by augmenting variables or changing parametrizations so that constraints remain expressible as a single LMI or a small collection of LMIs.

2.2.2 Duality Overview

SDP duality pairs a primal optimization problem with a dual problem whose constraints also involve positive semidefiniteness. At a high level, duality provides a way to certify optimality using matrix-valued multipliers; these multipliers inhabit the dual cone structure of the positive semidefinite cone.

2.3 Interior-Point Viewpoint

Most practical SDP solvers rely on interior-point methods. These methods use the fact that the positive definite matrices (strictly feasible points) form the interior of the positive semidefinite cone, and iterates are constructed to remain within that interior while approaching the boundary where optimal solutions typically occur.

2.4 Certificates of Infeasibility and Optimality

A key theoretical feature of SDP is the existence of certificates:

  • If the spectrahedron is empty, dual feasibility can yield a witness that proves infeasibility.
  • For an optimization problem, under suitable regularity conditions, a dual feasible point coupled with matching objective values provides a certificate of optimality.

These certificates are expressed using semidefinite constraints on the dual variables.

3 Algebraic and Geometric Perspectives

3.1 Boundary Structure via Determinants

The boundary of a spectrahedron is linked to where the associated LMI loses positive definiteness. For a feasible matrix \(A(x)\), the condition \(A(x)\succeq 0\) fails to be strictly feasible when \(A(x)\) becomes singular, i.e., when \(\det A(x)=0\). Since \(A(x)\) is affine in \(x\), the determinant is a polynomial in the variables, so boundary components are governed by polynomial equations and inequalities.

3.2 Rank Conditions and Strata

Geometric strata of a spectrahedron correspond to rank patterns of feasible matrices \(A(x)\).

3.2.1 Low-Rank Points on the Boundary

Lower rank typically indicates a more degenerate boundary position. For example, points where \(A(x)\) has many zero eigenvalues often lie in intersections of multiple boundary components, and such points are frequently relevant in describing extreme behavior.

3.2.2 Multiplicity of Eigenvalues

Eigenvalue multiplicities influence local geometry. When eigenvalues cross or become multiple, the boundary may exhibit features such as curvature changes or non-smoothness. Thus, spectral data translate into geometric regularity properties.

3.3 Projection and Image of Spectrahedra

A projection of a spectrahedron—eliminating some variables—need not be a spectrahedron itself. However, it is always a *semialgebraic* convex set, and in many cases it has a *spectrahedral shadow* representation via higher-dimensional LMIs. This viewpoint is central in understanding how convex sets arise from spectrahedra by variable elimination.

3.4 Relationships to Other Convex Sets

Spectrahedra occupy a prominent position among convex sets because:

  • They are defined directly by convex matrix inequalities.
  • Many convex feasibility regions in optimization can be modeled or approximated by LMIs.
  • They generalize polyhedra (linear inequalities) by replacing scalar nonnegativity with matrix positivity.

At the same time, not every convex set is representable as a spectrahedron in fixed dimension and fixed LMI size, motivating extensions and alternative characterizations.

4 Spectrahedral Cones and Extensions

4.1 Spectrahedral Cones

A spectrahedron can be *conic* when the LMI has no constant term, or after homogenization. Conic spectrahedra correspond to feasibility sets of the form \[ \{x:\ A(x)\succeq 0\} \] where the affine dependence is actually linear in \(x\). These sets align with the structure of homogeneous SDPs and conic duality.

4.2 Homogenization and Conic Formulations

If a spectrahedron is described by an affine LMI \(A_0+\sum_i x_i A_i\succeq 0\), homogenization introduces an extra variable \(t\) to rewrite it as a conic constraint: \[ A_0 t+\sum_i x_i A_i \succeq 0, \] together with an appropriate relation fixing the scale (often \(t=1\) in the original parametrization). This transforms affine feasibility into conic feasibility in a higher-dimensional space.

4.3 Spectrahedra vs. Spectral Sets

The term *spectral* is sometimes used in broader contexts for sets described through spectral constraints (e.g., constraints on eigenvalues of affine matrix functions). In contrast, *spectrahedron* refers specifically to feasibility with respect to positive semidefiniteness of an affine symmetric matrix. The distinction matters because not all spectral constraints correspond to a single LMI.

4.4 Product Constructions and Operations

4.4.1 Sums and Intersections at the LMI Level

Operations on spectrahedra correspond to matrix operations on the defining LMIs:

  • Intersections of spectrahedra can be expressed by block-diagonal concatenation of LMIs, since positive semidefiniteness is preserved under taking direct sums.
  • Minkowski sums are more subtle; they may require lifting to higher-dimensional representations or using conic combinations, and the resulting set may be expressible as a spectrahedral shadow rather than a spectrahedron with the same direct LMI size.

5 Transformations and Equivalence

5.1 Affine Changes of Variables

If \(y=Bx+d\) is an affine change of variables, then composing the LMI with this map yields \[ A(B^{-1}(y-d)) \succeq 0 \] (on the appropriate domain). Thus, spectrahedra related by affine reparametrization are essentially the same convex set up to coordinate transformations.

5.2 Linear Matrix Equivalence

Two LMIs can define the same spectrahedron even when their matrix pencils look different. Equivalence may arise from congruence transformations that preserve positive semidefiniteness (when appropriately applied), from reorganization of basis matrices \(A_i\), or from redundant constraints that do not change feasibility.

5.3 Spectrahedral Representations

5.3.1 Minimal vs. Non-minimal Descriptions

A spectrahedron may admit multiple LMI descriptions, with different matrix sizes \(m\) and different numbers of defining variables. A representation with smaller matrix size can be considered more economical, while larger representations may make algebraic structure easier to express. Determining minimal representations is generally nontrivial, and different applications may prefer different trade-offs between size, sparsity, and interpretability.

5.4 Closure Under Certain Operations

Spectrahedral descriptions are stable under several operations:

  • Direct-sum and affine-reparametrization constructions preserve the spectrahedron form.
  • Under homogenization, affine constraints convert to conic ones.
  • Under appropriate lifting, projections yield related classes such as spectrahedral shadows.

Some operations, however—like arbitrary projections back to the original variable space—may leave the spectrahedron class, requiring more general frameworks.

6 Computational Aspects

6.1 Checking Membership in a Spectrahedron

To test whether a given \(x\) belongs to \(\mathcal{S}\), one computes \(A(x)\) and checks whether its minimum eigenvalue is nonnegative (within tolerance). In practice, this is done using numerical eigensolvers or semidefinite feasibility checks.

6.2 Numerical Stability Considerations

Numerical issues arise from:

  • Ill-conditioned eigenvalue gaps near the boundary.
  • Round-off error when matrices have nearly zero eigenvalues.
  • Accumulation of errors in assembling \(A(x)\).

Robust implementations use scaling, tolerances, and stable linear algebra routines to mitigate these effects.

6.3 Size of LMIs and Complexity Growth

The computational burden of SDPs is influenced by:

  • The matrix size \(m\) of the LMI blocks.
  • The number of variables \(n\).
  • Sparsity and structure in the matrices \(A_i\).

As \(m\) increases, the cost of factorizations and eigenvalue computations can grow quickly, making model design and decomposition important.

6.4 Practical Modeling Patterns

Common modeling strategies include:

  • Block-diagonal LMIs to enforce multiple independent constraints.
  • Lifting and homogenization to translate nonconic constraints into conic form compatible with solvers.
  • Using symmetry to reduce redundant variables and improve numerical behavior.

These patterns aim to preserve the LMI structure while keeping problem size manageable.

7 Theoretical Results and Common Theorems

7.1 Characterizations Using Semidefinite Constraints

Spectrahedra can be characterized as feasible sets of semidefinite constraints defined by affine symmetric matrix pencils. Many equivalence and representation results rely on translating geometric conditions into algebraic matrix properties, such as kernel structure at boundary points.

7.2 Extreme Points and Exposed Faces

In convex geometry, faces of a convex set can often be described as points where supporting hyperplanes touch the set. For spectrahedra, exposed faces correspond closely to ranges and nullspaces associated with matrices \(A(x)\) at boundary points. Extreme points may occur at locations where the defining matrix has low rank and strong degeneracy properties, reflecting how the spectrahedron’s boundary is controlled by eigenvalue collapse.

7.3 Helton–Vinnikov Style Phenomena

For certain low-dimensional settings (notably involving two variables), results of the Helton–Vinnikov flavor assert that specific convex semialgebraic sets in the plane can be represented by determinant conditions of appropriately sized matrix pencils. Such phenomena highlight unexpected links between plane algebraic curves and spectrahedral geometry, illustrating that, in special regimes, spectrahedral representation can be effectively characterized.

7.4 Relaxations in Convex Optimization

Convex relaxations often replace a nonconvex feasible region by a larger spectrahedral set that is convex and computationally tractable. The relaxation is chosen so that:

  • it contains feasible solutions of the original problem (or approximates them), and
  • it provides bounds on the optimal value.

The quality of these relaxations depends on how tight the spectrahedral model is, which is influenced by algebraic and geometric properties of the underlying constraints.

8 Applications and Motivation

8.1 Control and Systems Theory

In control, spectrahedra arise from constraints ensuring stability or performance, such as matrix inequalities guaranteeing Lyapunov conditions. Many synthesis and analysis tasks translate into feasibility or optimization problems over semidefinite-constrained sets, with spectrahedra serving as the natural geometric substrate.

8.2 Robust Optimization

Robust formulations frequently require inequalities to hold for families of uncertainty. When uncertainty enters linearly, these conditions can often be reformulated as LMIs via worst-case bounds and transformation rules, producing spectrahedral feasible regions for decision variables.

8.3 Convex Geometry and Factorization Viewpoints

Spectrahedra provide concrete examples in convex geometry where algebraic data (determinants, ranks, eigenvalues) can be used to study faces, boundaries, and representability. Factorization perspectives also play a role: positive semidefinite constraints correspond to Gram-type factorizations, connecting geometry to linear algebraic decompositions.

8.4 Optimization Over Structured Constraints

Many real-world optimization problems impose structured constraints best expressed in matrix form—such as correlation constraints, covariance modeling, and matrix-valued regularization. Using spectrahedral modeling enables these requirements to be handled within a convex optimization framework, leveraging both theory (duality and certificates) and computational tools (interior-point methods).