Semidefinite programming algorithms for convex optimization over nonnegative polynomials with applications in control and signal processing.

University Of California-Los Angeles, Los Angeles CA

Investigators

Abstract

Semidefinite programming algorithms for convex optimization over nonnegative polynomials with applications in control andsignal processing During the last .fteen years semide.nite programming has developed into an important numerical tool for a variety of engineering applications, in particular in control and signal processing. At the same time, advances in semide.nite programming algorithms have resulted in several high-quality and freely available semide.nite programming software packages. These general-purpose solvers exploit some (sparse) problem structure, and can solve fairly large problem instances. However, for control and signal processing applications, which often involve matrix variables and dense linear matrix inequality constraints, there remains a substantial gap between the capabilities of the best solvers and the requirements for applications in practice. The main goal of this proposal is to narrow this gap, by developing fast algorithms for some speci.c classes of semide.nite programs that are important in control and signal processing. The proposal focuses on semide.nite programs in which the coe.cient matrices can be expressed as di.erent linear combinations of a small set of low-rank matrices. This type of structure is common and includes the important class of semide.nite programs derived from sum-of-squares representations of nonnegative polynomials. A second goal of the project is to investigate new applications of semide.nite programming to graphical modeling and time series analysis, and in particular the estimation of linear models with conditional independence constraints on pairs of variables. Intellectual merit The project will result in improved algorithms and software for solving important classes of semide.nite programming problems, by combining techniques from system theory (nonnegative polynomials), numerical analysis (discrete transforms and orthogonal polynomials) and optimization (interior-point methods). Broader impacts Software based on the research results will be made freely available, which will contribute to a more widespread adoption of semide.nite programming techniques. The results will be integrated in the graduate optimization sequence in the Electrical Engineering Department at UCLA. We also plan to o.er undergraduate research opportunitiesvia summer internships. The undergraduate student researchers will be recruited through the Center of Excellence in Engineering and Diversity (CEED) at UCLA, with the goal of increasing the number of CEED undergraduates interested in graduate study.