![]() | ||
Mit 6 854 spring 2016 lecture 19 semidefinite programming maxcut
Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (an objective function is a user-specified function that the user wants to minimize or maximize) over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron.
Contents
- Mit 6 854 spring 2016 lecture 19 semidefinite programming maxcut
- Semidefinite programming and its applications to approximation algorithms
- Initial motivation
- Equivalent formulations
- Definitions
- Weak duality
- Strong duality
- Example 1
- Example 2
- Example 3 Goemans Williamson MAX CUT approximation algorithm
- Algorithms
- Interior point methods
- First order methods
- Bundle method
- Other
- Applications
- References
Semidefinite programming is a relatively new field of optimization which is of growing interest for several reasons. Many practical problems in operations research and combinatorial optimization can be modeled or approximated as semidefinite programming problems. In automatic control theory, SDPs are used in the context of linear matrix inequalities. SDPs are in fact a special case of cone programming and can be efficiently solved by interior point methods. All linear programs can be expressed as SDPs, and via hierarchies of SDPs the solutions of polynomial optimization problems can be approximated. Semidefinite programming has been used in the optimization of complex systems. In recent years, some quantum query complexity problems have been formulated in terms of semidefinite programs.
Semidefinite programming and its applications to approximation algorithms
Initial motivation
A linear programming problem is one in which we wish to maximize or minimize a linear objective function of real variables over a polytope. In semidefinite programming, we instead use real-valued vectors and are allowed to take the dot product of vectors; nonnegativity constraints on real variables in LP are replaced by semidefiniteness constraints on matrix variables in SDP. Specifically, a general semidefinite programming problem can be defined as any mathematical programming problem of the form
Equivalent formulations
An
Denote by
We can rewrite the mathematical program given in the previous section equivalently as
where entry
Note that if we add slack variables appropriately, this SDP can be converted to one of the form
For convenience, an SDP may be specified in a slightly different, but equivalent form. For example, linear expressions involving nonnegative scalar variables may be added to the program specification. This remains an SDP because each variable can be incorporated into the matrix
Definitions
Analogously to linear programming, given a general SDP of the form
(the primal problem or P-SDP), we define the dual semidefinite program (D-SDP) as
where for any two matrices
Weak duality
The weak duality theorem states that the value of the primal SDP is at least the value of the dual SDP. Therefore, any feasible solution to the dual SDP lower-bounds the primal SDP value, and conversely, any feasible solution to the primal SDP upper-bounds the dual SDP value. This is because
where the last inequality is because both matrices are positive semidefinite, and the result of this function is sometimes referred to as duality gap.
Strong duality
Under a condition known as Slater's condition, the value of the primal and dual SDPs are equal. This is known as strong duality. Unlike for linear programs, however, not every SDP satisfies strong duality; in general, the value of the dual SDP may lie strictly below the value of the primal.
(i) Suppose the primal problem (P-SDP) is bounded below and strictly feasible (i.e., there exists
(ii) Suppose the dual problem (D-SDP) is bounded above and strictly feasible (i.e.,
Example 1
Consider three random variables
Suppose that we know from some prior knowledge (empirical results of an experiment, for example) that
we set
Solving this SDP gives the minimum and maximum values of
Example 2
Consider the problem
minimizewhere we assume that
Introducing an auxiliary variable
In this formulation, the objective is a linear function of the variables
The first restriction can be written as
where the matrix
The second restriction can be written as
Defining
We can use the theory of Schur Complements to see that
(Boyd and Vandenberghe, 1996)
The semidefinite program associated with this problem is
minimizeExample 3 (Goemans-Williamson MAX CUT approximation algorithm)
Semidefinite programs are important tools for developing approximation algorithms for NP-hard maximization problems. The first approximation algorithm based on an SDP is due to Michel Goemans and David P. Williamson (JACM, 1995). They studied the MAX CUT problem: Given a graph G = (V, E), output a partition of the vertices V so as to maximize the number of edges crossing from one side to the other. This problem can be expressed as an integer quadratic program:
MaximizeUnless P = NP, we cannot solve this maximization problem efficiently. However, Goemans and Williamson observed a general three-step procedure for attacking this sort of problem:
- Relax the integer quadratic program into an SDP.
- Solve the SDP (to within an arbitrarily small additive error
ϵ ). - Round the SDP solution to obtain an approximate solution to the original integer quadratic program.
For MAX CUT, the most natural relaxation is
This is an SDP because the objective function and constraints are all linear functions of vector inner products. Solving the SDP gives a set of unit vectors in
Since the original paper of Goemans and Williamson, SDPs have been applied to develop numerous approximation algorithms. Recently, Prasad Raghavendra has developed a general framework for constraint satisfaction problems based on the Unique Games Conjecture.
Algorithms
There are several types of algorithms for solving SDPs. These algorithms output the value of the SDP up to an additive error
Interior point methods
Most codes are based on interior point methods (CSDP, SeDuMi, SDPT3, DSDP, SDPA). Robust and efficient for general linear SDP problems. Restricted by the fact that the algorithms are second-order methods and need to store and factorize a large (and often dense) matrix.
First-order methods
First-order methods for conic optimization avoid storing and factorizing a large Hessian matrix and scale to much larger problems than interior point methods, at some cost in accuracy. Implemented in the SCS solver.
Bundle method
The code ConicBundle formulates the SDP problem as a nonsmooth optimization problem and solves it by the Spectral Bundle method of nonsmooth optimization. This approach is very efficient for a special class of linear SDP problems.
Other
Algorithms based on augmented Lagrangian method (PENSDP) are similar in behavior to the interior point methods and can be specialized to some very large scale problems. Other algorithms use low-rank information and reformulation of the SDP as a nonlinear programming problem (SPDLR).
Applications
Semidefinite programming has been applied to find approximate solutions to combinatorial optimization problems, such as the solution of the max cut problem with an approximation ratio of 0.87856. SDPs are also used in geometry to determine tensegrity graphs, and arise in control theory as LMIs.