Handbook of Semidefinite Programming

Semidefinite programming refers to optimization problems that can be expressed in the form minimize C•X subject to A _i •X = b _i for all i=1, . . . , m(1.1.1) X≻0 where the variable is X∈S ⁿ , the space of real symmetric nxn matrices.

This introductory chapter serves as a reference to keep the handbook self-contained in particular for non-experts. We state basic definitions, review concepts from linear algebra that relate to semi-definite optimization, and summarize special results from convex analysis for symmetric matrices. It is our intention to state each result in a simple language, and therefore we limit our attention to the case of real symmetric matrices. For each result references are given where a discussion can be found, and in many cases also interesting counterparts for complex or nonsymmetric matrices.

Consider the primal-dual pair of optimization problems where

Consider the optimization problem Min f(x) subject to G(x) ≺0, (4.1.1) x∈ ^C where C is a convex closed cone in the Euclidean space ℝ ⁿ , f : ℝ ⁿ → ℝ and G : ℝ ⁿ → Y is a mapping from ℝ ⁿ into the space Y := S ^m of m x m symmetric matrices.

Most semidefinite programming algorithms found in the literature require strictly feasible starting points (X° ≻ 0, S° ≻ 0) for the primal and dual problems respectively. So-called ‘big-M’ methods (see e.g. [807]) are often employed in practice to obtain feasible starting points.

We consider a semidefinite programming problem (SDP) of the form where b ∈ R ^m is given, and F is an affine map from y∈ R ^m to S ⁿ .

We study a system of mixed linear, positive semidefinite (PSD) and second order cone (SOC) constraints: where b is a given vector in ℜ ^N , A is a linear subspace of ℜ ^N , and K ⊂ ℜ ^N is a Cartesian product of second order cones and positive semidefinite cones.

This is the first of three chapters in this book dealing with polynomial time complexity of interior point algorithms for semidefinite programming (SDP). As such it deals with, in a sense, the easiest class of algorithms for which polynomial time convergence can be established. More precisely, we present a “recipe” whereby polynomial time convergence proofs in linear programming (LP) can be extended “word-by-word” to analogous proofs in SDP. Our presentation closely follows [21].

We start with an abstract definition of interior-point methods. These are the methods of solving convex optimization problems by generating a sequence of points which lies in the relative interior of a convex set defined by the difficult constraints (see [797]). In this definition, we are thinking about a formulation of the underlying problem in which one has a maximal set of linear equality constraints and some convex set constraint. The fundamental idea of interior-point algorithms goes back at least to Frisch [257] and to Fiacco and McCormick [230]. However, almost all of the new interior-point algorithms have their foundations in Karmarkar’s seminal work [404]. Karrnarkar’s work introduced many ingredients of the interior-point algorithms with polynomial iteration complexity that have been studied extensively since 1984. These algorithms possess polynomial bounds on the number of arithmetic operations required to solve a linear programming (LP) problem. In this chapter, we will be content with the bounds on the number of iterations. To date, it is not known whether even the SDP feasibility problem belongs to the class of decision problems solvable in polynomial time (assuming rational data and using the “bit model” on a Turing machine).

In this chapter we study interior-point primal-dual path-following algorithms for solving the semidefinite programming (SDP) problem. In contrast to linear programming, there are several ways one can define the Newton-type search directions used by these algorithms. We discuss several ways in which this can done by motivating and introducing several search directions and families of directions. Polynomial convergence results for short- and long-step path-following algorithms using the Monteiro and Zhang family of directions are derived in detail; similar results are only surveyed, without proofs, for the Kojima, Shindoh and Hara family and the Monteiro and Tsuchiya family.

In the last ten years the study of interior point methods dominated algorithmic research in semidefinite programming. Only recently interest in nonsmooth optimization methods revived again, the impetus coming from two different directions. On the one hand alternative possibilities were sought to solve structured large scale semidefinite programs which were not amenable to current interior point codes [338], on the other hand new developments in the second order theory of nonsmooth convex optimization suggested the specialization of these theoretic techniques to semidefinite programming [597, 598]. We present these new methods under the common framework of bundle methods and survey the underlying theory as well as some implementational aspects. In order to illustrate the efficiency and potential of the algorithms we also present numerical results.

In this section we investigate various ways to derive semidefinite relaxations of combinatorial optimization problems. We start out with a generic way to obtain an SDP relaxation for problems in binary variables. The key step is to linearize quadratic functions in the original vector x ∈ ℝ ⁿ through a new n×n matrix X, see also Chapter 13.

Quadratically constrained quadratic programs, denoted Q²P, are an important modelling tool, e.g.: for hard combinatorial optimization problems, Chapter 12; and SQP methods in nonlinear programming, Chapter 20. These problems are too hard to solve in general. Therefore, relaxations such as the Lagrangian relaxation are used. The dual of the Lagrangian relaxation is the SDP relaxation. Thus SDP has enabled us to efficiently solve the Lagrangian relaxation and find good approximate solutions for these hard, possibly nonconvex, Q²P. This area has generated a lot of research recently. This has resulted in many strong and elegant theorems that describe the strength/performance of the bounds obtained from solving relaxations of these Q²P.

It has been long recognized that SDP constraints, i.e., Linear Matrix Inequalities (LMIs), arise naturally and frequently in the analysis of the solution of finite-dimensional differential equations that model control systems.

Consider a mechanical construction C with M < ∞ degrees of freedom; thus, virtual displacements of C are specified by vectors w ∈ IR^M. The potential energy capacitated by C under a displacement w is assumed to be a nonnegative quadratic function 1/2 w^T Qw of the displacement (“linearly elastic construction”), Q being a symmetric positive semidefinite matrix characterizing C; this matrix is assumed to depend linearly on the vector t of design variables: Q = Q(t).

Problems involving moments of random variables arise naturally in many areas of mathematics, economics, and operations research. Let us give some examples that motivate the present paper.

Models and Information Matrix. Most of the results in experimental design theory are related to the linear regression models: where the observation y is a random variable, E and Var stand for expectation and variance, respectively.

In the matrix completion problem we are given a partial symmetric real matrix A with certain elements specified or fixed and the rest are unspecified or free; and, we are asked whether A can be completed to satisfy a given property (P) by assigning certain values to its free elements. In this chapter, we are interested in the following two completion problems: the positive semidefinite matrix completion problem corresponding to (P) being the positive semi-defmiteness (PSD) property; and the Euclidean distance matrix completion problem corresponding to (P) being the Euclidean distance (ED) property. (We concentrate on the latter problem. A survey of the former is given in [373]. The relationships between the two is discussed in e.g. [465, 464, 380].)

Many semidefinite optimization problems are reformulations of problems that are initially derived from certain eigenvalue bounds. As examples we discuss the problems of minimizing the largest eigenvalue of a symmetric matrix, and, more generally, a weighted sum of the κ largest eigenvalues of a symmetric matrix, or the largest generalized eigenvalue of a symmetric matrix pencil. In extension to the theory in Chapter 1 of this book, we summarize some known theoretical results on eigenvalues of symmetric matrices. These results can be used to reformulate eigenvalue problems such that the problems involve smooth functions only—for the constraints as well as for the objective function—and that convexity is preserved if possible.

A proven approach for unconstrained minimization of a function, f(x), x ∈ ℜ ⁿ , is to build and solve a quadratic model at a local estimate x ^(k) i.e. apply the trust region method. In this paper we propose a direct extension of this modeling approach to constrained minimization. A local quadratic model of both the objective function and the constraints is built. This model is too hard to solve, so it is relaxed using the Lagrangian dual, which is then solved by semidefinite programming techniques. The key ingredient in this approach is the equivalence between the Lagrangian and semidefinite relaxations.