Semidefinite programming is an extension of linear programming in which the inequality constraints are replaced by linear matrix inequalities. Semidefinite programs (SDPs) share most of the attractive properties of linear programs (convexity, polynomial-time complexity), but are also much more general. Numerous applications have been discovered during the last fifteen years, particularly in systems and control, and several general-purpose software packages have been developed. The proposal is motivated by the limited scalability of current general-purpose software. The objective is to develop specialized methods and software, with an efficiency far exceeding the capabilities of existing solvers, for two classes of SDPs that are of central importance in control and signal processing. The first class are SDPs derived from matrix sum-of-squares characterizations and the Kalman-Yakubovich-Popov lemma. This includes some of the most important applications of SDPs in control. The second class are nuclear norm minimization problems, which are important as convex heuristics for the NP-hard problem of minimizing the rank of a matrix subject to convex constraints. As an application of large-scale nuclear norm optimization, we intend to develop new system identification methods based on convex optimization.
Intellectual merit SDP packages exploit sparsity, following the successful model of linear programming. This approach is less successful in semidefinite programming, for two reasons. First, techniques for exploiting sparsity in SDPs are much less effective than for linear programming. Second, converting a dense structured SDP into a sparse problem usually requires the auxiliary matrix variables and constraints, which greatly increases the problem dimensions. It is therefore of critical importance to develop new strategies for exploiting structure that are not only based on sparsity but incorporate domain-specific knowledge from system theory.
Broader impacts Software based on the research results will be made freely available. This will contribute to a wider adoption of semidefinite programming, especially in the area of system identification. The research results will be integrated in the graduate optimization sequence in the Electrical Engineering Department at UCLA. We also plan to offer undergraduate research opportunities via individual study courses and summer internships, in partnership with the Center of Excellence in Engineering and Diversity at UCLA.
