Semidefinite programming relaxations for semialgebraic problems

By Pablo A. Parrilo. 2003

1,712 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Certified Defenses against Adversarial Examples (2018, methodology): “Such methods typically use sum-of-squares verification (Papachristodoulou & Prajna, 2002; 2005; Parrilo, 2003) and are restricted to relatively low-dimensional dynamical systems, but could plausibly scale to larger settings.”
Detecting global optimality and extracting solutions in GloptiPoly (2003, methodology): “Note that there exist a dual approach to build hierarchy of LMI relaxations, based on real algebraic geometry and sum-of-squares (SOS) decompositions of positive polynomials, see [16] for the theory and [18] for a Matlab/SeDuMi implementation.”
50 Years of Integer Programming 1958-2008 - From the Early Years to the State-of-the-Art (2010, background): “692 18.3.2 Max-Cut and graph bisection . . . . . . . . . . . . . . . . . . . . . . . . 693 18.3.3 Stable sets, cliques and the Lovász theta function . . . . . .”
Symmetry groups, semidefinite programs, and sums of squares (2002, background): “Besides its obvious theoretical interest, this is also a relevant question in many areas of applied mathematics, such as continuous and combinatorial optimization, as well as real polynomial system solving via the connections with the Positivstellensatz [20, 21 ,33].”
Vacuum stability conditions from copositivity criteria (2012, background): “Now, however, the elements on the minor diagonal of the matrix (20) are not independent any more [36]: they depend on two parameters c1 and c2 with the condition that c1 + c2 = 1.”
Lyapunov Based Analysis and Controller Synthesis for Polynomial Systems using Sum-of-Squares Optimization (2003, background): “Recent advances in convex optimization, [21], when paired with the important Positivstellensatz from real algebraic geometry, [3], allow us to use convex optimization to search for polynomials that meet certain conditions.”
LMI Techniques for Optimization Over Polynomials in Control: A Survey (2010, methodology): “For fixed degree of , the condition above can be rewritten as an LMI feasibility test by exploiting the technique in Section III-A, see also the works [6], [24].”
SOS approximations of nonnegative polynomials via simple high degree perturbations (2005, background): “But s.o.s. polynomials are also of primary importance for practical computation, especially in view of their numerous potential applications, notably in polynomial optimization; see e.g. [9, 14 , 17, 19].”
Nonnegative Polynomials and Sums of Squares (2010, background): “Algorithms to obtain such representations, when they are known, have many applications in polynomial optimization [9], [10], [11].”
Feedback control of quantum state reduction (2004, background): “be reduced to the following question: Is the set empty? Such problems are notoriously difficult to solve and their solution is known to be NP-hard in general [51].”
Approximation of the joint spectral radius using sum of squares (2007, methodology): “A useful scheme, introduced in [Par00, Par03] and relatively well-known by now, relaxes the nonnegativity constraints to a much more tractable sum of squares (SOS) condition, where p ( x ) is required to have a decomposition as p ( x ) = i p i ( x ) 2 .”