Slall.net

• Tarski-Seidenberg and quantifier elimination • Boolean minimization and the S-procedure The basic (closed) semialgebraic set defined by polynomials f1, . . . , fm is x ∈ Rn | fi(x) ≥ 0 for all i = 1, . . . , m • The cone of positive semidefinite matrices • Feasible set of an SDP; polyhedra and spectrahedra • If S1, S2 are basic closed semialgebraic sets, then so is S1 ∩ S2; i.e., Given the basic semialgebraic sets, we may generate other sets by set the-oretic operations; unions, intersections and complements.
A set generated by a finite sequence of these operations on basic semial-gebraic sets is called a semialgebraic set.
is semialgebraic, where ∗ denotes <, ≤, =, =.
• In particular every real variety is semialgebraic.
• We can also generate the semialgebraic sets via Boolean logical oper- ations applied to polynomial equations and inequalities Every semialgebraic set may be represented as either x ∈ Rn | fi(x) > 0, hj(x) = 0 for all i = 1, . . . , m, j = 1, . . . , p • in R, a finite union of points and open intervals Every closed semialgebraic set is a finite union of basic closed semialgebraicsets; i.e., sets of the form x ∈ Rn | fi(x) ≥ 0 for all i = 1, . . . , m • If S1, S2 are semialgebraic, so is S1 ∪ S2 and S1 ∩ S2 • The projection of a semialgebraic set is semialgebraic • The closure and interior of a semialgebraic sets are both semialgebraic Some sets are not semialgebraic; for example • the infinite staircase (x, y) ∈ R2 | y = x Tarski-Seidenberg and Quantifier Elimination Tarski-Seidenberg theorem: if S ⊂ Rn+p is semialgebraic, then so are i.e., quantifiers do not add any expressive power Cylindrical algebraic decomposition (CAD) may be used to compute thesemialgebraic set resulting from quantifier elimination Suppose S is a semialgebraic set; we’d like to solve the feasibility problem More specifically, suppose we have a semialgebraic set represented by poly-nomial inequalities and equations x ∈ Rn | fi(x) ≥ 0, hj(x) = 0 for all i = 1, . . . , m, j = 1, . . . , p • Important, non-trivial result: the feasibility problem is decidable.
• But NP-hard (even for a single polynomial, as we have seen)• We would like to certify infeasibility • The Nullstellensatz: a necessary and sufficient condition for feasibility • Valid inequalities: a sufficient condition for infeasibility of real basic • Linear Programming: necessary and sufficient conditions via duality for real linear equations and inequalities We’d like a method to construct certificates for If we can test feasibility of real equations then we can also test feasibilityof real inequalities and inequations, because • inequalities: there exists x ∈ R such that f(x) ≥ 0 if and only if there exists (x, y) ∈ R2 such that f(x) = y2 • strict inequalities: there exists x such that f(x) > 0 if and only if there exists (x, y) ∈ R2 such that y2f(x) = 1 • inequations: there exists x such that f(x) = 0 if and only if there exists (x, y) ∈ R2 such that yf(x) = 1 The underlying theory for real polynomials called real algebraic geometry The real variety defined by polynomials h1, . . . , hm ∈ R[x1, . . . , xn] is VR{h1, . . . , hm} = x ∈ Rn | hi(x) = 0 for all i = 1, . . . , m We’d like to solve the feasibility problem; is VR{h1, . . . , hm} = ∅? • Every polynomial in ideal{h1, . . . , hm} vanishes on the feasible set.
• But this condition is not necessary over the reals Recall Σ is the cone of polynomials representable as sums of squares.
Suppose h1, . . . , hm ∈ R[x1, . . . , xn].
Equivalently, there is no x ∈ Rn such that if and only if there exists t1, . . . , tm ∈ R[x1, . . . , xn] and s ∈ Σ such that Suppose h(x) = x2 + 1. Then clearly VR{h} = ∅ We saw earlier that the complex Nullstellensatz cannot be used to proveemptyness of VR{h} and so the real Nullstellensatz implies VR{h} = ∅.
The polynomial equation −1 = s + th gives a certificate of infeasibility.
We now turn to feasibility for basic semialgebraic sets, with primal problem • every polynomial in cone{f1, . . . , fm} is nonnegative on S • every polynomial in ideal{h1, . . . , hp} is zero on S −1 ∈ cone{f1, . . . , fm} + ideal{h1, . . . , hm} (x, y) ∈ R2 | f(x, y) ≥ 0, h(x, y) = 0 By the P-satz, the primal is infeasible if and only if there exist polynomialss1, s2 ∈ Σ and t ∈ R[x, y] such that Explicit Formulation of the Positivstellensatz Do there exist ti ∈ R[x1, . . . , xn] and si, rij, . . . ∈ Σ such that Do there exist ti ∈ R[x1, . . . , xn] and si, rij, . . . ∈ Σ such that • This is a convex feasibility problem in ti, si, rij, . . .
• To solve it, we need to choose a subset of the cone to search; i.e., the maximum degree of the above polynomial; then the problem is asemidefinite program • This gives a hierarchy of syntactically verifiable certificates • The validity of a certificate may be easily checked; e.g., linear algebra, • Unless NP=co-NP, the certificates cannot always be polynomially sized.
The primal problem; does there exist x ∈ Rn such that Let fi(x) = aTi x + bi, hi(x) = cTi x + di. Then this system is infeasible if −1 ∈ cone{f1, . . . , fm} + ideal{h1, . . . , hp} Searching over linear combinations, the primal is infeasible if there existλ ≥ 0 and µ such that Equating coefficients, this is equivalent to λT A + µT C = 0 λT b + µT d = −1 λ ≥ 0 • Interesting connections with logic, proof systems, etc.
• Failure to prove infeasibility (may) provide points in the set.
• Tons of applications: optimization, copositivity, dynamical systems, quantum mechanics.
Many known methods can be interpreted as fragments of P-satz refutations.
• LP duality: linear inequalities, constant multipliers.
• S-procedure: quadratic inequalities, constant multipliers• Standard SDP relaxations for QP.
• The linear representations approach for functions f strictly positive on • Losslessness: when can we restrict a priori the class of certificates?• Some cases are known; e.g., additional conditions such as linearity, per- fect graphs, compactness, finite dimensionality, etc, can ensure specifica priori properties.
which holds if and only if there exists a diagonal Λ such that Q γ = trace Λ − ε.
The corresponding optimization problem is The primal problem; does there exist x ∈ Rn such that We have a P-satz refutation if there exists λ1, λ2 ≥ 0, µ ∈ R and S −1 = xT Sx + λ1xT F1x + λ2xT F2x + µ(1 − xT x) which holds if and only if there exist λ1, λ2 ≥ 0 such that Subject to an additional mild constraint qualification, this condition is alsonecessary for infeasibility.
What algebraic properties of the polynomial system yield efficient compu-tation? • Sparseness: few nonzero coefficients.
• Newton polytopes techniques• Complexity does not depend on the degree • Symmetries: invariance under a transformation group • Frequent in practice. Enabling factor in applications.
• Can reflect underlying physical symmetries, or modelling choices.
• SOS on invariant rings• Representation theory and invariant-theoretic techniques.
• Ideal structure: Equality constraints.
• SOS on quotient rings• Compute in the coordinate ring. Quotient bases (Groebner) • Structured singular value µ and related problems: provides better up- • µ is a measure of robustness: how big can a structured perturbation • A standard semidefinite relaxation: the µ upper bound.
• Morton and Doyle’s counterexample with four scalar blocks.
• Exact value: approx. 0.8723• Standard µ upper bound: 1• New bound: 0.895 • The set of copositive matrices is a convex closed cone, but.
• Checking copositivity is coNP-complete • Very important in QP. Characterization of local solutions.
• The P-satz gives a family of computable SDP conditions, via: Ono’s inequality: For an acute triangle, (4K)6 ≥ 27 · (a2 + b2 − c2)2 · (b2 + c2 − a2)2 · (c2 + a2 − b2)2 where K and a, b, c are the area and lengths of the edges.
s(x, y, z) = (x4 + x2y2 − 2y4 − 2x2z2 + y2z2 + z4)2 + 15 · (x − z)2(x + z)2(z2 + x2 − y2)2.
(4K)6 − 27 · t21 · t22 · t23 = s(a, b, c) · t1 · t2 + s(c, a, b) · t1 · t3 + s(b, c, a) · t2 · t3

Source: http://slall.net/data/engr210b_0405/positivstellensatz_2004_11_09_01.pdf