Semidefinite programming: Difference between revisions

Revision as of 00:17, 30 August 2021

Revision as of 09:07, 2 September 2021

Line 3:

Semidefinite programming is a relatively new field of optimization which is of growing interest for several reasons. Many practical problems in [[operations research]] and [[combinatorial optimization]] can be modeled or approximated as semidefinite programming problems. In automatic control theory, SDPs are used in the context of [[linear matrix inequality|linear matrix inequalities]]. SDPs are in fact a special case of [[conic optimization|cone programming]] and can be efficiently solved by [[interior point methods]].

All [[linear programming|linear programs]], suchand as(convex) linear[[quadratic programming and |quadratic programming,programs]] can be expressed as SDPs, and via hierarchies of SDPs the solutions of polynomial optimization problems can be approximated. Semidefinite programming has been used in the [[optimization]] of complex systems. In recent years, some quantum query complexity problems have been formulated in terms of semidefinite programs.

== Motivation and definition ==