Nemirovski

From Wikimization

(Difference between revisions)
Jump to: navigation, search

Cslaw (Talk | contribs)
(New page: the answer is no, there is no necessity to sample <math>\Delta</math>. The construction is like this. The nonnegativity of a trigonometric polynomial on a segment is equivalent to the n...)
Next diff →

Revision as of 13:45, 23 October 2010

the answer is no, there is no necessity to sample LaTeX: \Delta.


The construction is like this. The nonnegativity of a trigonometric polynomial on a segment is equivalent to the nonnegativity of an algebraic polynomial on another segment since LaTeX: \sin(k\phi) and LaTeX: \cos(k\phi) are rational functions of LaTeX: \tan(\phi/2); you take this LaTeX: \tan as your new variable and get rid of denominators (they are powers of LaTeX: (1+\tan^2(\phi/2)) which does not affect positivity of the polynomial).


Now, nonnegativity of an algebraic polynomial on a segment reduces to nonnegatiivity of another algebraic polynomial on the entire axis. Indeed, w.l.o.g. we can assume that the segment in question is [-1,1], and nonnegativity of LaTeX: P(t) on this segment is equivalent to the nonnegativity of LaTeX: P(2t/(1+t^2)) on the entire axis, and you again can get rid of denominators.


The bottom line is that nonnegativity of trigonometric polynomial of degree d on a given segment is equivalent to nonnegativity of another polynomial, of degree not exceeding a known bound 2D, on the entire axis. The crucial fact is that the coefficients of the resulting polynomial, as follows from the construction, are affine functions of the coefficients of the initial polynomial.


Now, the vector LaTeX: p=[p_0;\cdots;p_{2D}] of coefficients of a polynomial of degree LaTeX: \leq 2D come from nonnegative polynomial if and only if there exists a positive semidefinite matrix LaTeX: Y of size D+1 such that identically in LaTeX: t one has LaTeX: p_0+p_1t+\cdots+p_{2D}t^{2D} = [1,t,t^2,\cdots,t^D]Y[1;t;\cdots;t^D] (this is an immediate corollary of the fact that a polynomial which is nonnegative on the entire axis is sum of squares of other polynomials). Thus, LaTeX: p comes from a nonnegative polynomial if and only if LaTeX: p_\ell=\sum_{i+j=\ell} Y_{ij} for all LaTeX: \ell, where LaTeX: [Y_{ij}]_{0\leq i,j\leq D} is positive semidefinite.


The bottom line is that LaTeX: q is a vector of coefficients of nonnegative on a given segment trigonometric polynomial if and only if there esists a positive semidefinitite matrix LaTeX: Y such that LaTeX: Bq= A(Y) for certain known matrix LaTeX: B and linear map LaTeX: Y\mapsto A(Y). In other words, the system of constraints LaTeX: Bq=A(Y), Y\succeq0 expresses equivalently the fact that the trigonometric polynomial with coefficients LaTeX: q is nonnegative on a given segment. Note that this construction is due to Yurii Nesterov.

Retrieved from "http://www.convexoptimization.com/wikimization/index.php/Nemirovski"
Personal tools