Convex optimization problems involving autocorrelation sequences.

摘要

Semidefinite programming (SDP) has remained an active area of research since the late 1980s when interior-point methods for solving SDPs were introduced. As a result, many general-purpose SDP solvers are now available, and a wide variety of applications have been discovered in the fields of statistics, structural design, electrical engineering, and combinatorial optimization. For example, researchers have found ways to solve as SDPs some problems in control for which analytical solutions do not exist. However, the techniques used to formulate a problem as an SDP often result in the introduction of large numbers of auxiliary variables. This has an important consequence for interior-point methods, since the amount of work per iteration grows at least as the cube of the number of variables, which limits the size of the problems that can be solved in practice. One approach to overcome these limitations is to develop methods for exploiting problem structure. The aim of this dissertation is to demonstrate how interior-point methods may be developed to exploit structure in a useful class of SDPs, namely, SDPs involving autocorrelation sequences. Particular attention will be given to problems involving finite length sequences. Problems of this form arise in control, signal processing, and communications. A finite sequence constraint can be cast as a linear matrix inequality (LMI) via the Positive Real (PR) lemma. However, it has an important drawback: to represent a sequence of length n, it requires the introduction of n (n + 1)/2 auxiliary variables. This results in a high computational cost when general-purpose SDP solvers are used. A more efficient implementation based on duality and interior-point methods is presented. We also discuss optimization problems involving an entropy-rate function. Problems of this form arise in applications in speech synthesis and in estimation problems, and involve infinite length sequences. We describe an application to estimation, and develop efficient method s for solving these problems using results from duality. In summary, we demonstrate how interior-point methods may be developed to exploit structure in useful classes of SDPs. It is our belief that similar gains in efficiency are possible in other problem classes.