Nemirovski
From Wikimization
(→Example) |
|||
Line 52: | Line 52: | ||
Assign | Assign | ||
<center><math>\cos(\omega)=\frac{1-\zeta^2}{1+\zeta^2}~,\quad \sin(\omega)=\frac{2\zeta}{1+\zeta^2}</math></center> | <center><math>\cos(\omega)=\frac{1-\zeta^2}{1+\zeta^2}~,\quad \sin(\omega)=\frac{2\zeta}{1+\zeta^2}</math></center> | ||
- | where <math>\zeta\! | + | where <math>\zeta\!=_{\!}\tan(\omega/2)</math>. |
<center><math>\,R(\omega)=\frac{r(0)+2r(1)+2r(2)~+~(2r(0)-12r(2))\zeta^2~+~(r(0)-2r(1)+2r(2))\zeta^4}{(1+\zeta^2)^2}</math></center> | <center><math>\,R(\omega)=\frac{r(0)+2r(1)+2r(2)~+~(2r(0)-12r(2))\zeta^2~+~(r(0)-2r(1)+2r(2))\zeta^4}{(1+\zeta^2)^2}</math></center> | ||
Because the denominator is positive for any <math>N\,</math>, a constraint <math>R(\omega)\!\geq_{\!}0~\,\forall\,\omega\!\in\![-\pi,\pi]</math>, for example, may concern itself only with the numerator which can be factored and stated as an equivalent semidefinite constraint: <math>\forall\,\zeta\!\in_{\!}(-\infty,\infty)</math> | Because the denominator is positive for any <math>N\,</math>, a constraint <math>R(\omega)\!\geq_{\!}0~\,\forall\,\omega\!\in\![-\pi,\pi]</math>, for example, may concern itself only with the numerator which can be factored and stated as an equivalent semidefinite constraint: <math>\forall\,\zeta\!\in_{\!}(-\infty,\infty)</math> |
Revision as of 13:38, 24 November 2011
Semidefinite representable trigonometric polynomial
Hello Arkadi
Regarding page 5 from: Nemirovski lecture
I am trying to understand how the trigonometric polynomial is semidefinite representable simultaneously in both variables and .
Are you sampling the interval from to ?
Jon Dattorro
The answer is no, there is no necessity to sample .
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 and are rational functions of ; you take this as your new variable and get rid of denominators (they are powers of 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 , and nonnegativity of on this segment is equivalent to the nonnegativity of
on the entire axis, and you again can get rid of denominators.
The bottom line is that nonnegativity of trigonometric polynomial of degree on a given segment is equivalent to nonnegativity of another polynomial, of degree not exceeding a known bound , 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 of coefficients of a polynomial of degree come from nonnegative polynomial if and only if there exists a positive semidefinite matrix of size such that,
identically in , one has
(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, comes from a nonnegative polynomial if and only if
where is positive semidefinite.
The bottom line is that is a vector of coefficients, nonnegative on a given segment, of a trigonometric polynomial if and only if there exists a positive semidefinitite matrix such that for certain known matrix and linear map . In other words, the system of constraints expresses equivalently the fact that the trigonometric polynomial with coefficients is nonnegative on a given segment.
Note that this construction is due to Yurii Nesterov.
Example
Minimization of peak time-domain response in filter design works with the autocorrelation function whose Fourier transform is
This can be written equivalently in terms of and : For
Assign
where .
Because the denominator is positive for any , a constraint , for example, may concern itself only with the numerator which can be factored and stated as an equivalent semidefinite constraint:
This matrix is diagonal because there are no odd powers of . A nonnegative main diagonal is therefore necessary and sufficient for positive semidefiniteness; in other words, each and every coefficient of the polynomial in must be nonnegative.
Transformation of the trigonometric polynomial in into a polynomial in can produce coefficients whose dynamic range is quite large. Finite precision numerical computation becomes problematic for large .