This thesis is concerned with efficient interior-point algorithms for two classes of semidefinite programs that have important applications in system identification and control.

We first discuss the problem of minimizing the nuclear norm (sum of singular values) of an affine matrix-valued function. This problem has recently attracted interest as a convex heuristic for rank minimization of structured matrices. The problem can be formulated as a semidefinite program, but the reformulation requires large auxiliary matrix variables, and is expensive to solve by general-purpose interior-point solvers. We show that problem structure in the semidefinite programming formulation can be exploited to develop more efficient implementations of interior-point methods. In the fast implementation, the cost per iteration is reduced to a quartic function of the problem dimensions, ie, comparable to the cost of solving the approximation problem in the Frobenius norm.

The nuclear norm approximation algorithm allows us to examine the effectiveness of the nuclear norm heuristic for rank minimization problems in system realization and identification. For each of these two applications, a variant of a simple subspace algorithm is presented, in which a low-rank matrix approximation is computed by minimizing the nuclear norm of a structured matrix. This technique preserves linear matrix structure in the low-rank approximation, an important advantage over standard approaches based on singular value decomposition. The methods are shown to perform well in experiments with simulated and publicly available benchmark data.

The second class of semidefinite programs is derived from the generalized Kalman-Yakubovich-Popov (KYP) lemma, one of the fundamental theorems in modern control theory. We describe a new algorithm that is based on a reformulation of the problem as a standard form semidefinite program with low-rank structure. This allows the problems to be solved efficiently by existing semidefinite programming packages that exploit low-rank structure. The low-rank formulation is obtained by first expressing the frequency-domain inequality associated with the generalized KYP lemma as a weighted sum-of-squares condition imposed on a rational function, and then converting the constraint into an equivalent finite set of interpolation constraints. A complexity analysis and numerical examples are provided to demonstrate the performance improvement over existing techniques.