semidefinite

Semidefinite refers to a property of matrices and to a class of optimization problems known as semidefinite programming. In linear algebra, a real symmetric matrix A is called positive semidefinite (PSD) if x^T A x ≥ 0 for all real vectors x. For complex matrices, the analogous condition uses Hermitian A. If x^T A x > 0 for all nonzero x, A is positive definite (PD). Semidefinite matrices have nonnegative eigenvalues; equivalently, A is PSD if and only if there exists a matrix B with A = B^T B (Cholesky-like factorization, possibly with B rectangular).

Semidefinite programming (SDP) is a convex optimization framework in which one minimizes a linear objective subject to linear matrix inequality constraints requiring a symmetric matrix to be PSD. A standard form uses a decision vector x and a matrix-valued affine function F(x) = F0 + sum xi Fi, with the constraint F(x) ≽ 0 (PSD). SDPs generalize linear programming and share strong duality under suitable regularity conditions. They can be solved efficiently using interior-point methods.

Applications span control theory, structural optimization, quantum information, combinatorial optimization via semidefinite relaxations, and machine learning. Variants include low-rank semidefinite programming and sparse SDP. Related concepts include sum-of-squares decompositions, which lead to SDP formulations for polynomial optimization.