4. sdpsol: A Parser/Solver for Semidefinite Programs with Matrix Structure

Shao-Po Wu, Stephen BoydSociety 2000 · DOI · OpenAlex

Abstract

4.1 Introduction This chapter describes a parser/solver for a class of linear matrix inequality (LMI) problems, the so-called max-det problems. 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 program (SDP) problems or determinant maximization problems (max-det problems). These problems often have matrix structure, which 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 chapter, 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.
BibTeX
@inproceedings{wu2000sdpsol,
  author = {Shao-Po Wu and Stephen Boyd},
  title = {{4. sdpsol: A Parser/Solver for Semidefinite Programs with Matrix Structure}},
  booktitle = {Society},
  year = {2000},
  doi = {10.1137/1.9780898719833.ch4},
}

Loading related content...

Figure