A class of convex optimization problems where a linear objective is minimized or maximized subject to affine (linear) constraints and a symmetric matrix variable constrained to be positive semidefinite.

Principle

Replace nonconvex matrix constraints by the convex cone of positive semidefinite matrices; express linear matrix inequalities and linear objective functions to obtain a problem solvable by interior-point or first-order convex methods.

Demonstration

Minimize trace(CX) subject to trace(A_i X) = b_i for i = 1..m and X >= 0 (X positive semidefinite); this formulation captures relaxations of combinatorial problems and design problems in control and signal processing.

Misapplication

Treating semidefinite relaxations as exact solutions without checking rank conditions or integrality can yield overly optimistic conclusions; applying dense SDP solvers to very large-scale sparse problems without exploiting structure leads to impractical computation.

Consequence

When used appropriately, SDP provides tight convex relaxations for many hard problems, enables polynomial-time solvability in the interior-point sense, and yields certificates of optimality or infeasibility via dual solutions.

Reversal

The reversal is to restrict to linear programming by enforcing diagonal matrix variables or dropping PSD constraints, which simplifies computation but loses expressiveness to model correlations and quadratic forms.

Boundary

Applies to problems expressible with linear matrix inequalities and symmetric PSD matrix variables; excludes inherently nonconvex objectives or constraints that cannot be convexified, and cases where integer constraints are mandatory without relaxation.

Semantic Tension

Tension exists between solution accuracy (tightness of SDP relaxation) and computational tractability (size and sparsity exploitation), and between dense interior-point solvers (high accuracy) and first-order methods (scalability but looser termination guarantees).

Synthesis

Semidefinite programming frames problems with matrix variables and PSD constraints as convex programs: linear objectives plus linear matrix inequalities define a tractable convex cone optimization that balances modeling power with algorithmic complexity.