Efficient algorithms for optimization over positive polynomials

This thesis describes efficient implementations of a form of linear semi-infinite programming (LSIP). Previous studies about LSIP are formulated using Semi-Definite Programming (SDP), which can be computationally expensive. Algorithms for directly solving LSIP have also been published, but these too are computationally expensive. In this thesis we consider a linear semi-infinite program:;max aTr.;s.t R(pi) ≥ 0 (1).;where R(pi) is the Fourier transform of and the constraints are formed with positive trigonometric polynomials. Problem (1) can be considered as a special case of LSIP and can be solved directly based on simplex method without parameterizing to a semi-definite programming (SDP).;In this thesis, we introduce a simplex-based LSIP algorithm which falls under the general class of cutting plane algorithms used in convex programming. We also exploit the relations between nonnegative trigonometric polynomials and Chebyshev-Vandermonde (CV) systems. By implementing published fast algorithms for CV systems in simplex, we expect to speed up the convergence time of the LSIP algorithm. In chapter 1, characterization of the LSIP and other basic knowledge are presented. Methodology of the simplex-based LSIP, together with other existing algorithms including the SDP solvers and an Lagrange-based LSIP algorithm carried out in the thesis, are specified in chapter 2. Numerical results of the algorithms are shown in chapter 3. The results show that simplex-based LISP algorithms are significantly more efficient than existing SDP solvers and Lagrange-based LSIP in both execution time and memory usage. Simplex-based LSIP algorithms can handle problems of any size efficiently, while most SDP solvers are based on interior-point methods which have the disadvantage of high complexity. Semidefinite programming solutions also have a limit on the size of the problem that can be solved.