Convex optimization problems involving finite autocorrelation sequences

Brien Alkire (brienalkires.com)
Lieven Vandenberghe (vandenbeee.ucla.edu)

Abstract: We discuss convex optimization problems where some of the variables are constrained to be finite autocorrelation sequences. Problems of this form arise in signal processing and communications, and we describe applications in filter design and system identification. Autocorrelation constraints in optimization problems are often approximated by sampling the corresponding power spectral density, which results in a set of linear inequalities. They can also be cast as linear matrix inequalities via the Kalman-Yakubovich-Popov lemma. The linear matrix inequality formulation is exact, and results in convex optimization problems that can be solved using interior-point methods for semidefinite programming. However, it has an important drawback: to represent an autocorrelation sequence of length n, it requires the introduction of a large number (n(n+1)/2) of auxiliary variables. This results in a high computational cost when general-purpose semidefinite programming solvers are used. We present a more efficient implementation based on duality and on interior-point methods for convex problems with generalized linear inequalities.

Keywords: optimization, convex, signal processing, autocorrelation, interior-point

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Applications -- Science and Engineering (Other )

Citation: Submitted to Mathematical Programming, Series B on January 5, 2001.

Download: [Postscript][PDF]

Entry Submitted: 01/29/2001
Entry Accepted: 01/29/2001
Entry Last Modified: 01/29/2001

Modify/Update this entry