Amitsur–Levitzki theorem: Difference between revisions

Revision as of 08:11, 20 August 2013

Sum-of-squares optimization techniques have been successfully applied by researchers in the control engineering field.^[1]^[2]^[3]

Optimization problem

A sum-of-squares program is an optimization problem with a linear cost and a particular type of constraint on the decision variables. These constraints are of the form that when the decision variables are used as coefficients in certain polynomials, those polynomials should have the polynomial SOS property. The problem can be expressed as:

\min_{u \in ℝ^{n}} c^{T} u

subject to

a_{k, 0} (x) + a_{k, 1} (x) u_{1} + \dots + a_{k, n} (x) u_{n} \in SOS (k = 1, \dots, N_{s}) .

Here "SOS" represents the class of SOS polynomials. The vector $c \in ℝ^{n}$ and polynomials ${a_{k, j}}$ are given as part of the data for the optimization problem. The quantities $u \in ℝ^{n}$ are the decision variables. SOS programs can be converted to semidefinite programs (SDPs) using the connection between SOS polynomials and positive-semidefinite matrices.

Sum-of-squares background

A polynomial $p$ is a sum of squares (SOS) if there exist polynomials ${f_{i}}_{i = 1}^{m}$ such that $p = \sum_{i = 1}^{m} f_{i}^{2}$ . For example,

p = x^{2} - 4 x y + 7 y^{2}

is a sum of squares since

p = f_{1}^{2} + f_{2}^{2}

where

f_{1} = (x - 2 y) and f_{2} = \sqrt{3} y .

Note that if $p$ is a sum of squares then $p (x) \geq 0$ for all $x \in ℝ^{n}$ . Detailed descriptions of polynomial SOS are available.^[4]^[5]^[6]

Quadratic forms can be expressed as $p (x) = x^{T} Q x$ where $Q$ is a symmetric matrix. Similarly, polynomials of degree ≤ 2d can be expressed as

p (x) = z (x)^{T} Q z (x),

where the vector $z$ contains all monomials of degree $\leq d$ . This is known as the Gram matrix form. An important fact is that $p$ is SOS if and only if there exists a symmetric and positive-semidefinite matrix $Q$ such that $p (x) = z (x)^{T} Q z (x)$ . This provides a connection between SOS polynomials and positive-semidefinite matrices.

Software tools

SOSTOOLS, licensed under the GNU GPL. The reference guide is available at arXiv:1310.4716 [math.OC].

References

↑ Tan, W., Packard, A., 2004. "Searching for control Lyapunov functions using sums of squares programming". In: Allerton Conf. on Comm., Control and Computing. pp. 210–219.
↑ Tan, W., Topcu, U., Seiler, P., Balas, G., Packard, A., 2008. Simulation-aided reachability and local gain analysis for nonlinear dynamical systems. In: Proc. of the IEEE Conference on Decision and Control. pp. 4097–4102.
↑ A. Chakraborty, P. Seiler, and G. Balas, “Susceptibility of F/A-18 Flight Controllers to the Falling-Leaf Mode: Nonlinear Analysis,” AIAA Journal of Guidance, Control, and Dynamics, Vol.34 No.1, 2011, 73–85.
↑ Parrilo, P., (2000) Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology.
↑ Parrilo, P. (2003) "Semidefinite programming relaxations for semialgebraic problems". Mathematical Programming Ser. B 96 (2), 293–320.
↑ Lasserre, J. (2001) "Global optimization with polynomials and the problem of moments". SIAM Journal on Optimization, 11 (3), 796{817.

[1] Tan, W., Packard, A., 2004. "Searching for control Lyapunov functions using sums of squares programming". In: Allerton Conf. on Comm., Control and Computing. pp. 210–219.

[2] Tan, W., Topcu, U., Seiler, P., Balas, G., Packard, A., 2008. Simulation-aided reachability and local gain analysis for nonlinear dynamical systems. In: Proc. of the IEEE Conference on Decision and Control. pp. 4097–4102.

[3] A. Chakraborty, P. Seiler, and G. Balas, “Susceptibility of F/A-18 Flight Controllers to the Falling-Leaf Mode: Nonlinear Analysis,” AIAA Journal of Guidance, Control, and Dynamics, Vol.34 No.1, 2011, 73–85.

[4] Parrilo, P., (2000) Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology.

[5] Parrilo, P. (2003) "Semidefinite programming relaxations for semialgebraic problems". Mathematical Programming Ser. B 96 (2), 293–320.

[6] Lasserre, J. (2001) "Global optimization with polynomials and the problem of moments". SIAM Journal on Optimization, 11 (3), 796{817.

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 1: / Line 1: @@
-Mariam is what folks get in touch with me and I thoroughly dig that title. To [http://Photo.net/gallery/tag-search/search?query_string=lift+weights lift weights] is the only interest my spouse doesn't approve of. Details processing is what I do in my working day occupation. Maryland is in which our [http://Www.Thefreedictionary.com/residence residence] is. I've been doing work on my internet site for some time now. Check out it out below: http://mjihye.nayana.com/xe/?document_srl=915940<br><br>
+'''Sum-of-squares optimization''' techniques have been successfully applied by researchers in the [[control engineering]] field.<ref>Tan, W., Packard, A., 2004. "[http://jagger.me.berkeley.edu/papers/weehong_3.pdf Searching for control Lyapunov functions using sums of squares programming]". In: ''Allerton Conf. on Comm., Control and
+Computing''. pp. 210&ndash;219.</ref><ref>Tan, W., Topcu, U., Seiler, P., Balas, G., Packard, A., 2008. Simulation-aided
+reachability and local gain analysis for nonlinear dynamical systems. In:
+Proc. of the IEEE Conference on Decision and Control. pp. 4097–4102.</ref><ref>A. Chakraborty, P. Seiler, and G. Balas, “Susceptibility of F/A-18 Flight Controllers to the Falling-Leaf Mode: Nonlinear Analysis,” AIAA Journal of Guidance, Control, and Dynamics, Vol.34 No.1, 2011, 73–85.</ref>
-my web blog: [http://mjihye.nayana.com/xe/?document_srl=915940 oakley oil rig sunglasses]
+==Optimization problem==
+A sum-of-squares program is an optimization problem with a linear cost and a particular type of constraint on the decision variables. These constraints are of the form that when the decision variables are used as coefficients in certain [[polynomials]], those polynomials should have the [[polynomial SOS]] property. The problem can be expressed as:
+:<math> \min_{u\in\R^n} c^T u  </math>
+subject to
+:<math> a_{k,0}(x) + a_{k,1}(x)u_1 + \cdots + a_{k,n}(x)u_n \in \text{SOS}
+\quad (k=1,\ldots, N_s).</math>
+Here "SOS" represents the class of SOS polynomials.
+The vector <math>c\in \R^n </math> and polynomials <math>\{ a_{k,j} \} </math> are given as
+part of the  data for the optimization problem. The quantities <math>u\in \R^n </math> are the decision variables.
+SOS programs can be converted to [[semidefinite programming|semidefinite programs]] (SDPs) using the
+connection between SOS polynomials and [[positive-semidefinite matrix|positive-semidefinite matrices]].
+==Sum-of-squares background==
+A polynomial <math> p </math> is a ''sum of squares'' (''SOS'') if there exist polynomials <math> \{f_i\}_{i=1}^m </math>
+such that  <math> p = \sum_{i=1}^m f_i^2 </math>.  For example,
+:<math>p=x^2 - 4xy + 7y^2</math>
+is a sum of squares since
+:<math> p = f_1^2 + f_2^2</math>
+where
+:<math>f_1 = (x-2y)\text{ and  }f_2 = \sqrt{3}y.</math>
+Note that if <math> p </math> is a sum of squares
+then <math>p(x) \ge 0 </math> for all <math> x \in \R^n</math>. Detailed descriptions of [[polynomial SOS]] are available.<ref>Parrilo, P., (2000) ''Structured semidefinite programs and semialgebraic geometry
+methods in robustness and optimization''. Ph.D. thesis, California
+Institute of Technology.</ref><ref>
+Parrilo, P. (2003) "Semidefinite programming relaxations for semialgebraic
+problems". ''[[Mathematical Programming]]'' Ser. B 96 (2), 293–320.</ref><ref>
+Lasserre, J. (2001) "Global optimization with polynomials and the problem of
+moments". ''SIAM Journal on Optimization'', 11 (3), 796{817.</ref>
+[[Quadratic forms]] can be expressed as <math> p(x)=x^T Q x</math> where <math> Q </math> is a symmetric matrix.  Similarly, polynomials of degree&nbsp;≤&nbsp;2''d'' can be expressed as
+:<math> p(x)=z(x)^T Q z(x) ,</math>
+where the vector <math>z</math> contains all monomials of degree <math> \le d </math>.  This is known as the [[Gram matrix]] form.  An important fact is that
+<math> p </math> is SOS if and only if there exists a symmetric and [[positive-semidefinite matrix]] <math> Q </math> such that <math>p(x)=z(x)^T Q z(x) </math>.
+This provides a connection between SOS polynomials and positive-semidefinite matrices.
+== Software tools ==
+* [http://www.cds.caltech.edu/sostools/ SOSTOOLS], licensed under the [[GNU GPL]].  The reference guide is available at [http://arxiv.org/abs/1310.4716 arXiv:1310.4716 <nowiki>[</nowiki>math.OC<nowiki>]</nowiki>].
+== References ==
+<references/>
+<!--- After listing your sources please cite them using inline citations and place them after the information they cite. Please see http://en.wikipedia.org/wiki/Wikipedia:REFB for instructions on how to add citations. --->
+[[Category:Mathematical optimization]]
+[[Category:Real algebraic geometry]]