Interior-point methods for convex problems involving finite autocorrelation sequences

Professor Lieven Vandenberghe, Electrical Engineering Department, University of California at Los Angeles

Many of the linear matrix inequalities (LMIs) in systems and control are derived from the positive real (or the bounded real) lemma. These LMIs involve an auxiliary matrix variable, introduced to express a semi-infinite frequency-domain inequality as a convex constraint in a finite-dimensional space with a finite number of variables. The number of auxiliary variables introduced this way is often very large compared to the number of original optimization variables, and this fact has important consequences for the computational efficiency of interior-point methods, since the amount of work per iteration grows as the cube of the number of variables. In this talk we consider a special case: the constraint that a vector of length n forms a finite autocorrelation sequence. We discuss the geometry of this constraint, and describe a few applications in signal processing. We then show that these problems can be solved using interior-point methods at a cost of roughly O(n^3) flops per iteration, which is much lower than the cost of general purpose algorithms for LMI problems (O(n^6) flops per iteration).