Sdpsol: A Parser/Solver for Semidefinite Programs with Matrix Structure

S.-P. Wu and S. Boyd

Chapter 4 of Recent Advances in LMI Methods for Control, L. El Ghaoui and S.-I. Niculescu, editors, SIAM, pages 79-91, 2000.
Shorter version: Design and implementation of a parsersolver for SDPs with matrix structure, Proceedings of the 1996 IEEE International Symposium on Computer-Aided Control System Design (CACSD)/, pp.240-245, 1996.

A variety of analysis and design problems in control, communication and information theory, statistics, combinatorial optimization, computational geometry, circuit design, and other fields can be expressed as semidefinite programming problems (SDPs) or determinant maximization problems (max-det problems). These problems often have matrix structure, i.e., some of the optimization variables are matrices. This matrix structure has two important practical ramifications: first, it makes the job of translating the problem into a standard SDP or max-det format tedious, and, second, it opens the possibility of exploiting the structure to speed up the computation. In this paper we describe the design and implementation of sdpsol, a parser/solver for SDPs and max-det problems. sdpsol allows problems with matrix structure to be described in a simple, natural, and convenient way. Moreover, it allows algorithms to exploit problem structure to gain efficiency. Although the current implementation of sdpsol exploits only block-diagonal structure in the solution algorithm, the language and parser were designed with exploiting general matrix structure in mind.