Convex optimization over non-negative polynomials : structured algorithms and applications
(2003)
Files
Details
- Authors
- Supervisors
- Abstract
- Convex optimization has been a very dynamic field of research for the last decade; renewed interest in this area was motivated by the seminal research monograph of Nesterov and Nemirovskii (1994), which proved that a wide class of convex optimization problems can be solved efficiently with polynomial-time interior-point methods. Although this fundamental result allows us to formulate and to solve numerous problems in mathematical engineering, the underlying problem structure is often disregarded in the solution methods. This thesis focuses on conic optimization problems involving non-negative matrix polynomials and moment spaces. Such problems are frequent in practice, enjoy a particular structure and thus deserve special attention. A novel convex approach to these optimization problems that relies on parametrizing the spaces of interest with semidefinite matrices has been proposed. As the dual problems involve structured matrices, convolution and displacement-rank techniques have been exploited in order to obtain specific dual algorithms whose main feature is the appropriate use of the problem structure. Consequently, these algorithms enjoy the best worst-case complexity estimate known in the literature for solving this class of problems. In addition, the representation of non-negative polynomials with spectral factors yields quadratic optimization problems. Although these problems are usually hard to solve, a convexity condition that makes them easier to solve has been identified. Several new classes of easy quadratic optimization problems have also been pointed out; they are related to non-negative polynomials and interpolation constraints. Many applications in various research fields (mechanical engineering, probability theory and statistics, systems and control, signal processing...) benefit from our results. A few relevant examples have been completely investigated. In conclusion, this work highlights the importance of obtaining convex formulations and of using the problem structure to obtain efficient algorithms.
- Affiliations
Citations
Hachez, Y. (2003). Convex optimization over non-negative polynomials : structured algorithms and applications. https://hdl.handle.net/2078.5/124206