-
Notifications
You must be signed in to change notification settings - Fork 24
/
index.html
2 lines (2 loc) · 14.2 KB
/
index.html
1
2
<!DOCTYPE html>
<html lang="en"><head><meta charset="UTF-8"/><meta name="viewport" content="width=device-width, initial-scale=1.0"/><title>Sum-of-Squares Programming · SumOfSquares</title><script data-outdated-warner src="../assets/warner.js"></script><link href="https://cdnjs.cloudflare.com/ajax/libs/lato-font/3.0.0/css/lato-font.min.css" rel="stylesheet" type="text/css"/><link href="https://cdnjs.cloudflare.com/ajax/libs/juliamono/0.039/juliamono-regular.css" rel="stylesheet" type="text/css"/><link href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/5.15.3/css/fontawesome.min.css" rel="stylesheet" type="text/css"/><link href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/5.15.3/css/solid.min.css" rel="stylesheet" type="text/css"/><link href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/5.15.3/css/brands.min.css" rel="stylesheet" type="text/css"/><link href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.13.11/katex.min.css" rel="stylesheet" type="text/css"/><script>documenterBaseURL=".."</script><script src="https://cdnjs.cloudflare.com/ajax/libs/require.js/2.3.6/require.min.js" data-main="../assets/documenter.js"></script><script src="../siteinfo.js"></script><script src="../../versions.js"></script><link class="docs-theme-link" rel="stylesheet" type="text/css" href="../assets/themes/documenter-dark.css" data-theme-name="documenter-dark" data-theme-primary-dark/><link class="docs-theme-link" rel="stylesheet" type="text/css" href="../assets/themes/documenter-light.css" data-theme-name="documenter-light" data-theme-primary/><script src="../assets/themeswap.js"></script></head><body><div id="documenter"><nav class="docs-sidebar"><div class="docs-package-name"><span class="docs-autofit"><a href="../">SumOfSquares</a></span></div><form class="docs-search" action="../search/"><input class="docs-search-query" id="documenter-search-query" name="q" type="text" placeholder="Search docs"/></form><ul class="docs-menu"><li><a class="tocitem" href="../">Index</a></li><li class="is-active"><a class="tocitem" href>Sum-of-Squares Programming</a><ul class="internal"><li><a class="tocitem" href="#Quadratic-forms-and-Semidefinite-programming"><span>Quadratic forms and Semidefinite programming</span></a></li><li><a class="tocitem" href="#Polynomial-nonnegativity-and-Semidefinite-programming"><span>Polynomial nonnegativity and Semidefinite programming</span></a></li><li><a class="tocitem" href="#When-is-nonnegativity-equivalent-to-sum-of-squares-?"><span>When is nonnegativity equivalent to sum of squares ?</span></a></li></ul></li><li><a class="tocitem" href="../variables/">Variables</a></li><li><a class="tocitem" href="../constraints/">Constraints</a></li><li><span class="tocitem">Tutorials</span><ul><li><input class="collapse-toggle" id="menuitem-5-1" type="checkbox"/><label class="tocitem" for="menuitem-5-1"><span class="docs-label">Getting started</span><i class="docs-chevron"></i></label><ul class="collapsed"><li><a class="tocitem" href="../generated/Getting started/circle/">Nonnegative over a variety</a></li><li><a class="tocitem" href="../generated/Getting started/getting_started/">Getting started</a></li><li><a class="tocitem" href="../generated/Getting started/motzkin/">Motzkin</a></li><li><a class="tocitem" href="../generated/Getting started/sos_decomposition/">A trivial SOS decomposition example</a></li><li><a class="tocitem" href="../generated/Getting started/sum-of-squares_matrices/">Sum-of-Squares matrices</a></li></ul></li><li><input class="collapse-toggle" id="menuitem-5-2" type="checkbox"/><label class="tocitem" for="menuitem-5-2"><span class="docs-label">Polynomial Optimization</span><i class="docs-chevron"></i></label><ul class="collapsed"><li><a class="tocitem" href="../generated/Polynomial Optimization/bound_on_global_extremum/">Bound on Global Extremum</a></li><li><a class="tocitem" href="../generated/Polynomial Optimization/polynomial_optimization/">Polynomial Optimization</a></li></ul></li><li><input class="collapse-toggle" id="menuitem-5-3" type="checkbox"/><label class="tocitem" for="menuitem-5-3"><span class="docs-label">Systems and Control</span><i class="docs-chevron"></i></label><ul class="collapsed"><li><a class="tocitem" href="../generated/Systems and Control/lyapunov_function_search/">Lyapunov Function Search</a></li><li><a class="tocitem" href="../generated/Systems and Control/stabilization_of_nonlinear_systems/">Stabilization of nonlinear systems</a></li></ul></li><li><input class="collapse-toggle" id="menuitem-5-4" type="checkbox"/><label class="tocitem" for="menuitem-5-4"><span class="docs-label">Other Applications</span><i class="docs-chevron"></i></label><ul class="collapsed"><li><a class="tocitem" href="../generated/Other Applications/bounds_in_probability/">Bounds in Probability</a></li></ul></li><li><input class="collapse-toggle" id="menuitem-5-5" type="checkbox"/><label class="tocitem" for="menuitem-5-5"><span class="docs-label">Noncommutative and Hermitian</span><i class="docs-chevron"></i></label><ul class="collapsed"><li><a class="tocitem" href="../generated/Noncommutative and Hermitian/noncommutative_variables/">Noncommutative variables</a></li><li><a class="tocitem" href="../generated/Noncommutative and Hermitian/sums_of_hermitian_squares/">Sums of Hermitian squares</a></li></ul></li><li><input class="collapse-toggle" id="menuitem-5-6" type="checkbox"/><label class="tocitem" for="menuitem-5-6"><span class="docs-label">Sparsity</span><i class="docs-chevron"></i></label><ul class="collapsed"><li><a class="tocitem" href="../generated/Sparsity/term_sparsity/">Term sparsity</a></li></ul></li><li><input class="collapse-toggle" id="menuitem-5-7" type="checkbox"/><label class="tocitem" for="menuitem-5-7"><span class="docs-label">Symmetry</span><i class="docs-chevron"></i></label><ul class="collapsed"><li><a class="tocitem" href="../generated/Symmetry/cyclic/">Cyclic symmetry for Sums of Hermitian Squares</a></li><li><a class="tocitem" href="../generated/Symmetry/dihedral_symmetry_of_the_robinson_form/">Dihedral symmetry of the Robinson form</a></li><li><a class="tocitem" href="../generated/Symmetry/even_reduction/">Even reduction</a></li><li><a class="tocitem" href="../generated/Symmetry/permutation_symmetry/">Symmetry reduction</a></li></ul></li><li><input class="collapse-toggle" id="menuitem-5-8" type="checkbox"/><label class="tocitem" for="menuitem-5-8"><span class="docs-label">Extension</span><i class="docs-chevron"></i></label><ul class="collapsed"><li><a class="tocitem" href="../generated/Extension/certificate/">Certificate</a></li><li><a class="tocitem" href="../generated/Extension/hypercube/">Hypercube</a></li><li><a class="tocitem" href="../generated/Extension/typed/">Multivariate polynomials implementations</a></li><li><a class="tocitem" href="../generated/Extension/univariate_solver/">Univariate Solver</a></li></ul></li></ul></li></ul><div class="docs-version-selector field has-addons"><div class="control"><span class="docs-label button is-static is-size-7">Version</span></div><div class="docs-selector control is-expanded"><div class="select is-fullwidth is-size-7"><select id="documenter-version-selector"></select></div></div></div></nav><div class="docs-main"><header class="docs-navbar"><nav class="breadcrumb"><ul class="is-hidden-mobile"><li class="is-active"><a href>Sum-of-Squares Programming</a></li></ul><ul class="is-hidden-tablet"><li class="is-active"><a href>Sum-of-Squares Programming</a></li></ul></nav><div class="docs-right"><a class="docs-edit-link" href="https://github.com/jump-dev/SumOfSquares.jl/blob/master/docs/src/sumofsquares.md" title="Edit on GitHub"><span class="docs-icon fab"></span><span class="docs-label is-hidden-touch">Edit on GitHub</span></a><a class="docs-settings-button fas fa-cog" id="documenter-settings-button" href="#" title="Settings"></a><a class="docs-sidebar-button fa fa-bars is-hidden-desktop" id="documenter-sidebar-button" href="#"></a></div></header><article class="content" id="documenter-page"><h1 id="Sum-of-Squares-Programming"><a class="docs-heading-anchor" href="#Sum-of-Squares-Programming">Sum-of-Squares Programming</a><a id="Sum-of-Squares-Programming-1"></a><a class="docs-heading-anchor-permalink" href="#Sum-of-Squares-Programming" title="Permalink"></a></h1><p>This section contains a brief introduction to Sum-of-Squares Programming. For more details, see [BPT12, Las09, Lau09].</p><h2 id="Quadratic-forms-and-Semidefinite-programming"><a class="docs-heading-anchor" href="#Quadratic-forms-and-Semidefinite-programming">Quadratic forms and Semidefinite programming</a><a id="Quadratic-forms-and-Semidefinite-programming-1"></a><a class="docs-heading-anchor-permalink" href="#Quadratic-forms-and-Semidefinite-programming" title="Permalink"></a></h2><p>The positive semidefiniteness of a <span>$n \times n$</span> real symmetric matrix <span>$Q$</span> is equivalent to the nonnegativity of the quadratic form <span>$p(x) = x^\top Q x$</span> for all vector <span>$x \in \mathbb{R}^n$</span>. For instance, the polynomial</p><p class="math-container">\[x_1^2 + 2x_1x_2 + 5x_2^2 + 4x_2x_3 + x_3^2 = x^\top \begin{pmatrix}1 & 1 & 0\\1 & 5 & 2\\ 0 & 2 & 1\end{pmatrix} x\]</p><p>is nonnegative since the matrix of the right-hand side is positive semidefinite. Moreover, a certificate of nonnegativity can be extracted from the Cholesky decomposition of the matrix:</p><p class="math-container">\[(x_1 + x_2)^2 + (2x_2 + x_3)^2 = x^\top \begin{pmatrix}1 & 1 & 0\\0 & 2 & 1\end{pmatrix}^\top \begin{pmatrix}1 & 1 & 0\\0 & 2 & 1\end{pmatrix} x\]</p><h2 id="Polynomial-nonnegativity-and-Semidefinite-programming"><a class="docs-heading-anchor" href="#Polynomial-nonnegativity-and-Semidefinite-programming">Polynomial nonnegativity and Semidefinite programming</a><a id="Polynomial-nonnegativity-and-Semidefinite-programming-1"></a><a class="docs-heading-anchor-permalink" href="#Polynomial-nonnegativity-and-Semidefinite-programming" title="Permalink"></a></h2><p>This can be generalized to a polynomial of arbitrary degree. A polynomial <span>$p(x)$</span> is nonnegative if it can be rewritten as <span>$p(x) = X^\top Q X$</span> where <span>$Q$</span> is a real symmetric positive semidefinite matrix and <span>$X$</span> is a vector of monomials.</p><p>For instance</p><p class="math-container">\[x_1^2 + 2x_1^2x_2 + 5x_1^2x_2^2 + 4x_1x_2^2 + x_2^2 = X^\top \begin{pmatrix}1 & 1 & 0\\1 & 5 & 2\\ 0 & 2 & 1\end{pmatrix} X\]</p><p>where <span>$X = (x_1, x_1x_2, x_2)$</span> Similarly to the previous section, the Cholesky factorization of the matrix can be used to extract a sum of squares certificate of nonnegativity for the polynomial:</p><p class="math-container">\[(x_1 + x_1x_2)^2 + (2x_1x_2 + x_2)^2 = X^\top \begin{pmatrix}1 & 1 & 0\\0 & 2 & 1\end{pmatrix}^\top \begin{pmatrix}1 & 1 & 0\\0 & 2 & 1\end{pmatrix} X\]</p><h2 id="When-is-nonnegativity-equivalent-to-sum-of-squares-?"><a class="docs-heading-anchor" href="#When-is-nonnegativity-equivalent-to-sum-of-squares-?">When is nonnegativity equivalent to sum of squares ?</a><a id="When-is-nonnegativity-equivalent-to-sum-of-squares-?-1"></a><a class="docs-heading-anchor-permalink" href="#When-is-nonnegativity-equivalent-to-sum-of-squares-?" title="Permalink"></a></h2><p>Determining whether a polynomial is nonnegative is <em>NP-hard</em>. The condition of the previous section was only sufficient, that is, there exists nonnegative polynomials that are not sums of squares. Hilbert showed in 1888 that there are exactly 3 cases for which there is equivalence between the nonnegativity of the polynomials of <span>$n$</span> variables and degree <span>$2d$</span> and the existence of a sum of squares decomposition.</p><ul><li><span>$n = 1$</span> : Univariate polynomials</li><li><span>$2d = 2$</span> : Quadratic polynomials</li><li><span>$n = 2$</span>, <span>$2d = 4$</span> : Bivariate quartics</li></ul><p>The first explicit example of polynomial that was not a sum of squares was given by Motzkin in 1967:</p><p class="math-container">\[x_1^4x_2^2 + x_1^2x_2^4 + 1 - 3x_1^2x_2^2 \geq 0 \quad \forall x\]</p><p>While it is not a sum of squares, it can still be certified to be nonnegative using sum-of-squares programming by identifying it with a rational sum-of-squares decomposition. These facts can be verified numerically using this package as detailed in the <a href="https://github.com/jump-dev/SumOfSquares.jl/blob/master/examples/motzkin.ipynb">motzkin notebook</a>.</p><h3 id="References"><a class="docs-heading-anchor" href="#References">References</a><a id="References-1"></a><a class="docs-heading-anchor-permalink" href="#References" title="Permalink"></a></h3><p>[BPT12] Blekherman, G.; Parrilo, P. A. & Thomas, R. R. <em>Semidefinite Optimization and Convex Algebraic Geometry</em>. Society for Industrial and Applied Mathematics, <strong>2012</strong>.</p><p>[Las09] Lasserre, J. B. <em>Moments, positive polynomials and their applications</em> World Scientific, <strong>2009</strong>.</p><p>[Lau09] Laurent, M. <em>Sums of squares, moment matrices and optimization over polynomials</em> Emerging applications of algebraic geometry, Springer, <strong>2009</strong>, 157-270.</p></article><nav class="docs-footer"><a class="docs-footer-prevpage" href="../">« Index</a><a class="docs-footer-nextpage" href="../variables/">Variables »</a><div class="flexbox-break"></div><p class="footer-message">Powered by <a href="https://github.com/JuliaDocs/Documenter.jl">Documenter.jl</a> and the <a href="https://julialang.org/">Julia Programming Language</a>.</p></nav></div><div class="modal" id="documenter-settings"><div class="modal-background"></div><div class="modal-card"><header class="modal-card-head"><p class="modal-card-title">Settings</p><button class="delete"></button></header><section class="modal-card-body"><p><label class="label">Theme</label><div class="select"><select id="documenter-themepicker"><option value="documenter-light">documenter-light</option><option value="documenter-dark">documenter-dark</option></select></div></p><hr/><p>This document was generated with <a href="https://github.com/JuliaDocs/Documenter.jl">Documenter.jl</a> version 0.27.15 on <span class="colophon-date" title="Friday 1 April 2022 21:34">Friday 1 April 2022</span>. Using Julia version 1.7.2.</p></section><footer class="modal-card-foot"></footer></div></div></div></body></html>