Nemirovski - Revision history

Ranjelin at 05:52, 7 June 2026

2026-06-07T05:52:36Z

←Older revision		Revision as of 05:52, 7 June 2026
Line 28:		Line 28:

	Now, the vector <math>p=[p_0; . . . ;p_{2D}]</math> of coefficients of a polynomial of degree <math>\leq2D</math> come from nonnegative polynomial if and only if there exists a positive semidefinite matrix <math>\,Y</math> of size <math>\,D+1</math> such that,		Now, the vector <math>p=[p_0; . . . ;p_{2D}]</math> of coefficients of a polynomial of degree <math>\leq2D</math> come from nonnegative polynomial if and only if there exists a positive semidefinite matrix <math>\,Y</math> of size <math>\,D+1</math> such that,
-	identically in <math>t\,</math>, one has	+	identically in <math>t\,,\,</math> one has

	<center><math>p_0+p_1t+...+p_{2D}t^{2D}=\,[1,t,t^2,...,t^D]Y[1;t;t^2;...;t^D]</math></center>		<center><math>p_0+p_1t+...+p_{2D}t^{2D}=\,[1,t,t^2,...,t^D]Y[1;t;t^2;...;t^D]</math></center>

Ranjelin at 05:46, 7 June 2026

2026-06-07T05:46:55Z

←Older revision		Revision as of 05:46, 7 June 2026
Line 27:		Line 27:


-	Now, the vector <math>p=[p_0; . . . ;p_{2D}]</math> of coefficients of a polynomial of degree <math>\leq2D</math> come from nonnegative polynomial if and only if there exists a positive semidefinite matrix <math>\,Y</math> of size <math>\,D\!+\!1</math> such that,	+	Now, the vector <math>p=[p_0; . . . ;p_{2D}]</math> of coefficients of a polynomial of degree <math>\leq2D</math> come from nonnegative polynomial if and only if there exists a positive semidefinite matrix <math>\,Y</math> of size <math>\,D+1</math> such that,
	identically in <math>t\,</math>, one has		identically in <math>t\,</math>, one has

Line 34:		Line 34:
	(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, <math>\,p</math> comes from a nonnegative polynomial if and only if		(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, <math>\,p</math> comes from a nonnegative polynomial if and only if

-	<center><math>p_{\ell\,}=\!\sum_{i+j=\ell}Y_{ij}</math>   for all <math>\ell</math></center>	+	<center><math>p_{\ell\,}=\!\sum_{i\,+j=\ell}Y_{ij}</math>   for all <math>\ell</math></center>

	where <math>[Y_{ij}]_{0\leq i,j\leq D}</math> is positive semidefinite.		where <math>[Y_{ij}]_{0\leq i,j\leq D}</math> is positive semidefinite.

Ranjelin at 23:47, 6 May 2026

2026-05-06T23:47:16Z

←Older revision		Revision as of 23:47, 6 May 2026
Line 51:		Line 51:
	<center><math>R(\omega)=r(0)\,+\,2r(1)\cos(\omega)\,+\,2r(2)\cos(\omega)^2\,-\,2r(2)\sin(\omega)^2\,</math></center>		<center><math>R(\omega)=r(0)\,+\,2r(1)\cos(\omega)\,+\,2r(2)\cos(\omega)^2\,-\,2r(2)\sin(\omega)^2\,</math></center>
	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\!=_{\!}\tan(\omega/2)</math>.		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>
-	<center><math>\mathbf{[}\,1~~\zeta~~\zeta^2\,\mathbf{]}\left[\begin{array}{ccc}r(0)+2r(1)+2r(2)&&\mathbf{0}\\&2r(0)-12r(2)\\\mathbf{0}&&r(0)-2r(1)+2r(2)\end{array}\right]\left[\begin{array}{c}1\\\zeta\\\zeta^2\end{array}\right]\succeq\,0</math></center>	+	<center><math>\mathbf{[}\,1\;\;\zeta\;\;\zeta^2\,\mathbf{]}\left[\begin{array}{ccc}r(0)+2r(1)+2r(2)&&\mathbf{0}\\&2r(0)-12r(2)\\\mathbf{0}&&r(0)-2r(1)+2r(2)\end{array}\right]\left[\begin{array}{c}1\\\zeta\\\zeta^2\end{array}\right]\succeq\,0</math></center>
	This matrix is diagonal because there are no odd powers of <math>\zeta\,</math>.		This matrix is diagonal because there are no odd powers of <math>\zeta\,</math>.
	A nonnegative main diagonal is therefore necessary and sufficient for positive semidefiniteness;		A nonnegative main diagonal is therefore necessary and sufficient for positive semidefiniteness;

Ranjelin: /* Semidefinite representable trigonometric polynomial */

2016-11-08T00:38:17Z

Semidefinite representable trigonometric polynomial

←Older revision		Revision as of 00:38, 8 November 2016
Line 27:		Line 27:


-	Now, the vector <math>p=[p_0;~~\cdots~~;p_{2D}]</math> of coefficients of a polynomial of degree <math>\leq2D</math> come from nonnegative polynomial if and only if there exists a positive semidefinite matrix <math>\,Y</math> of size <math>\,D\!+\!1</math> such that,	+	Now, the vector <math>p=[p_0; . . . ;p_{2D}]</math> of coefficients of a polynomial of degree <math>\leq2D</math> come from nonnegative polynomial if and only if there exists a positive semidefinite matrix <math>\,Y</math> of size <math>\,D\!+\!1</math> such that,
	identically in <math>t\,</math>, one has		identically in <math>t\,</math>, one has

-	<center><math>p_0+p_1t+~~\cdots~~+p_{2D}t^{2D}=\,[1,t,t^2,~~\cdots~~,t^D]Y[1;t;t^2;~~\cdots~~;t^D]</math></center>	+	<center><math>p_0+p_1t+...+p_{2D}t^{2D}=\,[1,t,t^2,...,t^D]Y[1;t;t^2;...;t^D]</math></center>

	(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, <math>\,p</math> comes from a nonnegative polynomial if and only if		(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, <math>\,p</math> comes from a nonnegative polynomial if and only if

Ranjelin: /* Semidefinite representable trigonometric polynomial */

2011-12-05T06:23:23Z

Semidefinite representable trigonometric polynomial

←Older revision		Revision as of 06:23, 5 December 2011
Line 27:		Line 27:


-	Now, the vector <math>p=[p_0;\cdots;p_{2D}]</math> of coefficients of a polynomial of degree <math>\~~leq\!2D~~</math> come from nonnegative polynomial if and only if there exists a positive semidefinite matrix <math>\,Y</math> of size <math>\,D\!+\!1</math> such that,	+	Now, the vector <math>p=[p_0;\cdots;p_{2D}]</math> of coefficients of a polynomial of degree <math>\leq2D</math> come from nonnegative polynomial if and only if there exists a positive semidefinite matrix <math>\,Y</math> of size <math>\,D\!+\!1</math> such that,
	identically in <math>t\,</math>, one has		identically in <math>t\,</math>, one has

Line 39:		Line 39:


-	The bottom line is that <math>\,q</math> is a vector of coefficients, nonnegative on a given segment, of a trigonometric polynomial if and only if there exists a positive semidefinitite matrix <math>\,Y</math> such that <math>\,Bq=A(Y)</math> for certain known matrix <math>\,B</math> and linear map <math>Y\!\mapsto\!A(Y)</math>. In other words, the system of constraints <math>Bq\!=\!A(Y),~Y\!\succeq0</math> expresses equivalently the fact that the trigonometric polynomial with coefficients <math>\,q</math> is nonnegative on a given segment.	+	The bottom line is that <math>\,q</math> is a vector of coefficients, nonnegative on a given segment, of a trigonometric polynomial if and only if there exists a positive semidefinitite matrix <math>\,Y</math> such that <math>\,Bq=A(Y)</math> for certain known matrix <math>\,B</math> and linear map <math>Y\!\mapsto\!A(Y)</math>. In other words, the system of constraints <math>Bq\!=\!A(Y),\,\,Y\!\succeq0</math> expresses equivalently the fact that the trigonometric polynomial with coefficients <math>\,q</math> is nonnegative on a given segment.

Ranjelin at 20:38, 24 November 2011

2011-11-24T20:38:26Z

←Older revision		Revision as of 20:38, 24 November 2011
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\!~~\triangleq_~~{\!}\tan(\omega/2)</math>.	+	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>

Kwokwah: /* Example */

2010-10-25T11:27:42Z

Example

←Older revision		Revision as of 11:27, 25 October 2010
Line 54:		Line 54:
	where <math>\zeta\!\triangleq_{\!}\tan(\omega/2)</math>.		where <math>\zeta\!\triangleq_{\!}\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>
	<center><math>\mathbf{[}\,1~~\zeta~~\zeta^2\,\mathbf{]}\left[\begin{array}{ccc}r(0)+2r(1)+2r(2)&&\mathbf{0}\\&2r(0)-12r(2)\\\mathbf{0}&&r(0)-2r(1)+2r(2)\end{array}\right]\left[\begin{array}{c}1\\\zeta\\\zeta^2\end{array}\right]\succeq\,0</math></center>		<center><math>\mathbf{[}\,1~~\zeta~~\zeta^2\,\mathbf{]}\left[\begin{array}{ccc}r(0)+2r(1)+2r(2)&&\mathbf{0}\\&2r(0)-12r(2)\\\mathbf{0}&&r(0)-2r(1)+2r(2)\end{array}\right]\left[\begin{array}{c}1\\\zeta\\\zeta^2\end{array}\right]\succeq\,0</math></center>
	This matrix is diagonal because there are no odd powers of <math>\zeta\,</math>.		This matrix is diagonal because there are no odd powers of <math>\zeta\,</math>.

Kwokwah: /* Example */

2010-10-25T11:25:51Z

Example

←Older revision		Revision as of 11:25, 25 October 2010
Line 49:		Line 49:
	This can be written equivalently in terms of <math>\cos(\omega)\,</math> and <math>\sin(\omega)\,</math>:		This can be written equivalently in terms of <math>\cos(\omega)\,</math> and <math>\sin(\omega)\,</math>:
	For <math>\,N\!=_{\!}3</math>		For <math>\,N\!=_{\!}3</math>
-	<center><math>R(\omega)=r(0) + 2r(1)\cos(\omega) + 2r(2)\cos(\omega)^2 - 2r(2)\sin(\omega)^2\,</math></center>	+	<center><math>R(\omega)=r(0)\,+\,2r(1)\cos(\omega)\,+\,2r(2)\cos(\omega)^2\,-\,2r(2)\sin(\omega)^2\,</math></center>
	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>

Kwokwah: /* Example */

2010-10-25T11:22:24Z

Example

←Older revision		Revision as of 11:22, 25 October 2010
Line 47:		Line 47:
	[http://www.convexoptimization.com/wikimization/index.php/Filter_design_by_convex_iteration#Minimum_peak_time-domain_response_by_Optimization Minimization of peak time-domain response] in filter design works with the autocorrelation function <math>r\,</math> whose Fourier transform is		[http://www.convexoptimization.com/wikimization/index.php/Filter_design_by_convex_iteration#Minimum_peak_time-domain_response_by_Optimization Minimization of peak time-domain response] in filter design works with the autocorrelation function <math>r\,</math> whose Fourier transform is
	<center><math>R(\omega) = r(0)+\!\sum\limits_{n=1}^{N-1}2r(n)\cos(\omega n)</math></center>		<center><math>R(\omega) = r(0)+\!\sum\limits_{n=1}^{N-1}2r(n)\cos(\omega n)</math></center>
-	~~Define~~	+	This can be written equivalently in terms of <math>\cos(\omega)\,</math> and <math>\sin(\omega)\,</math>:
-	~~<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\!\triangleq\!\tan~~(\omega/2)</math>.	+
	For <math>\,N\!=_{\!}3</math>		For <math>\,N\!=_{\!}3</math>
		+	<center><math>R(\omega)=r(0) + 2r(1)\cos(\omega) + 2r(2)\cos(\omega)^2 - 2r(2)\sin(\omega)^2\,</math></center>
		+	Assign
		+	<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\!\triangleq_{\!}\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>

Cslaw: /* Example */

2010-10-25T10:37:11Z

Example

←Older revision		Revision as of 10:37, 25 October 2010
Line 49:		Line 49:
	Define		Define
	<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\triangleq\tan(\omega/2)</math>.	+	where <math>\zeta\!\triangleq\!\tan(\omega/2)</math>.
-	For <math>\,N\!=_{\!}2</math>	+	For <math>\,N\!=_{\!}3</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>