spezielle Klasse von Optimierungsproblemen.

Für m, n ∈ ℕ seien B, A₁,…,A_n symmetrische (m, m)-Matrizen. Die Menge \begin{eqnarray}S:=\left\{x\in {{\mathbb{R}}}^{n}|\mathop{\sum ^{n}}\limits_{i=1}{x}_{i}\cdot {A}_{i}-B\,\text{ist negativ semidefinit}\right\}\end{eqnarray} wird ein Spektahedron genannt. Das Problem dersemidefiniten Optimierung (SDP) besteht in der Minimierung eines linearen Funktionals über S, also, mit \(c\in {{\mathbb{R}}}^{n}\): \begin{eqnarray}(SDP):\text{minimiere}\ {c}^{T}\cdot x,x\in S.\end{eqnarray} Viele interessante Optimierungsprobleme, z. B. multi-quadratische Optimierungsprobleme und Eigenwertaufgaben, können in ein (SDP) umformuliert werden.

[1] Boyd, S.; Vandenberghe, L.: Semidefinite programming. SIAM Review 38, 1996.