semidefinite programming

Semidefinite programming (SDP) is a subfield of mathematical programming concerned with the optimization of a linear objective function (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. 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 and (convex) quadratic programs can be expressed as SDPs, and the sum of squares hierarchy of SDPs can approximate the solutions of polynomial optimization problems. 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 (SDP) is a subfield of mathematical programming concerned with the optimization of a linear objective function (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. 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 and (convex) quadratic programs can be expressed as SDPs, and the sum of squares hierarchy of SDPs can approximate the solutions of polynomial optimization problems. 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. An n \times n matrix M is said to be positive semidefinite if it is the Gram matrix of some vectors (i.e. if there exist vectors x^1, \ldots, x^n such that m_{i,j}=x^i \cdot x^j for all i,j ). If this is the case, we denote this as M \succeq 0 . Note that there are several other equivalent definitions of being positive semidefinite, for example, positive semidefinite matrices are self-adjoint matrices that have only non-negative eigenvalues. Denote by \mathbb{S}^n the space of all n \times n real symmetric matrices. The space is equipped with the inner product (where {\rm trace} denotes the trace): \langle A,B\rangle := {\rm trace}(A^T B) = \sum_{i=1,j=1}^n A_{ij}B_{ij}. We can rewrite the mathematical program given in the previous section equivalently as \begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle \\ \text{subject to} & \langle A_k, X \rangle \leq b_k, \quad k = 1,\ldots,m \\ & X \succeq 0. \end{array} where entry i,j in C is given by \frac{c_{i,j} + c_{j,i}}{2} from the previous section and A_k is a symmetric n \times n matrix having i,j th entry \frac{a_{i,j,k}+a_{j,i,k}}{2} from the previous section. Thus, the matrices C and A_k are symmetric and the above inner products are well-defined. Note that if we add slack variables appropriately, this SDP can be converted to an equational form: \begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle \\ \text{subject to} & \langle A_k, X \rangle = b_k, \quad k = 1,\ldots,m \\ & X \succeq 0. \end{array} 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 X as a diagonal entry ( X_{ii} for some i ). To ensure that X_{ii} \geq 0 , constraints X_{ij} = 0 can be added for all j \neq i . As another example, note that for any positive semidefinite matrix X , there exists a set of vectors \{ v_i \} such that the i , j entry of X is X_{ij} = (v_i, v_j) the scalar product of v_i and v_j . Therefore, SDPs are often formulated in terms of linear expressions on scalar products of vectors. Given the solution to the SDP in the standard form, the vectors \{ v_i \} can be recovered in O(n^3) time (e.g., by using an incomplete Cholesky decomposition of X). \text{subject to} & \langle A_i, X \rangle = b_i, \quad i = 1,\ldots,m \\ & X \succeq 0 \end{array} (the primal problem or P-SDP), we define the dual semidefinite program (D-SDP) as \begin{array}{rl} {\displaystyle\max_{y \in \mathbb{R}^m}} & b^T y \\ \text{subject to} & {\displaystyle\sum_{i=1}^m} y_i A_i \preceq C \end{array} where for any two matrices P and Q , P \succeq Q means P-Q \succeq 0 . = \langle C, X \rangle - \sum_{i=1}^m y_i b_i = \langle C, X \rangle - \sum_{i=1}^m y_i \langle A_i, X \rangle = \langle C - \sum_{i=1}^m y_i A_i, X \rangle \geq 0, where the last inequality is because both matrices are positive semidefinite, and the result of this function is sometimes referred to as duality gap. A_i,X_0\rangle = b_i , i=1,\ldots,m ). Then there is an optimal solution y^* to (D-SDP) and \langle C,X^*\rangle = b^T y^*. (ii) Suppose the dual problem (D-SDP) is bounded above and strictly feasible (i.e., \sum_{i=1}^m (y_0)_i A_i \prec C for some y_0\in\R^m ). Then there is an optimal solution X^* to (P-SDP) and the equality from (i) holds. A sufficient condition for strong duality to hold for a SDP problem (and in general, for any convex optimization problem) is the Slater's condition. It is also possible to attain strong duality for SDPs without additional regularity conditions by using an extended dual problem proposed by Ramana. We set \rho_{AB} = x_{12}, \ \rho_{AC} = x_{13}, \ \rho_{BC} = x_{23} to obtain the answer. This can be formulated by an SDP. We handle the inequality constraints by augmenting the variable matrix and introducing slack variables, for example \mathrm{tr}\left(\left(\begin{array}{cccccc} 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\end{array}\right)\cdot\left(\begin{array}{cccccc} 1 & x_{12} & x_{13} & 0 & 0 & 0\\ x_{12} & 1 & x_{23} & 0 & 0 & 0\\ x_{13} & x_{23} & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & s_{1} & 0 & 0\\ 0 & 0 & 0 & 0 & s_{2} & 0\\ 0 & 0 & 0 & 0 & 0 & s_{3}\end{array}\right)\right)=x_{12} + s_{1}=-0.1 Solving this SDP gives the minimum and maximum values of \rho_{AC} = x_{13} \ as -0.978 and 0.872 respectively. D=\left[\begin{array}{cc}t&c^Tx\\c^Tx&d^Tx\end{array}\right] We can use the theory of Schur Complements to see that D \succeq 0 (Boyd and Vandenberghe, 1996) The semidefinite program associated with this problem is minimize t subject to \left[\begin{array}{ccc}\textbf{diag}(Ax+b)&0&0\\0&t&c^Tx\\0&c^Tx&d^Tx\end{array}\right] \succeq 0 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: Maximize \sum_{(i,j) \in E} \frac{1-v_{i} v_{j}}{2}, such that each v_i\in\{1,-1\} . Unless 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. (This can also be derived using the first level of the sum of squares hierarchy.) Solve the SDP (to within an arbitrarily small additive error \epsilon ). Round the SDP solution to obtain an approximate solution to the original integer quadratic program. For max cut, the most natural relaxation is \max \sum_{(i,j) \in E} \frac{1-\langle v_{i}, v_{j}\rangle}{2}, such that \lVert v_i\rVert^2 = 1 , where the maximization is over vectors \{v_i\} instead of integer scalars. 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 \mathbf{R^n} ; since the vectors are not required to be collinear, the value of this relaxed program can only be higher than the value of the original quadratic integer program. Finally, a rounding procedure is needed to obtain a partition. Goemans and Williamson simply choose a uniformly random hyperplane through the origin and divide the vertices according to which side of the hyperplane the corresponding vectors lie. Straightforward analysis shows that this procedure achieves an expected approximation ratio (performance guarantee) of 0.87856 - ε. (The expected value of the cut is the sum over edges of the probability that the edge is cut, which is proportional to the angle \cos^{-1}\langle v_{i}, v_{j}\rangle between the vectors at the endpoints of the edge over \pi . Comparing this probability to (1-\langle v_{i}, v_{j}\rangle)/{2} , in expectation the ratio is always at least 0.87856.) Assuming the unique games conjecture, it can be shown that this approximation ratio is essentially optimal. Since the original paper of Goemans and Williamson, SDPs have been applied to develop numerous approximation algorithms. Subsequently, Prasad Raghavendra has developed a general framework for constraint satisfaction problems based on the unique games conjecture. In the Turing machine model, SDF is in NP iff it is in co-NP. Therefore, SDF is not NP-complete unless NP=coNP. In the Blum–Shub–Smale machine model, SDF is in the intersection of NP and co-NP. \text{subject to} & \langle A_k, X \rangle = b_k, \quad k = 1,\ldots,m \\ & X \succeq 0. \end{array} Let L be the affine subspace of matrices in S n satisfying the m equational constraints; so the SDP can be written as: \max_{X\in L} \langle C,X\rangle \text{ subject to } X\succeq 0 . Suppose all coefficients in the SDP are rational numbers. Let R be an explicitly given upper bound on the maximum Frobenius norm of a feasible solution, and ε>0 a constant. A matrix X in S n is called ε-deep if every matrix Y in L with Frobenius distance at most ε from X satisfies the feasibility condition Y\succeq 0 . Denote v_{deep} := \sup \{\langle C,X\rangle: X \text{ is } \epsilon\text{-deep} \} . The ellipsoid returns one of the following outputs: A matrix X* in L (that is, satisfying all linear equality constraints exactly), such that the Frobenius distance between X* and some feasible solution is at most ε (that is, approximately satisfying the inequality constraint X\succeq 0 ), and \langle C,X^*\rangle \geq v_{deep} -\epsilon (that is, approximately optimal objective value). A certificate that the problem has no ε-deep solutions (that is, the problem is approximately infeasible). The run-time is polynomial in the binary encodings of the inputs and in log(R/ε), in the Turing machine model. Note that, in general, R may be doubly-exponential in n. In that case, the run-time guarantee of the ellipsoid method is exponential in n. But in most applications, R is not so huge. In these cases, the ellipsoid method is the only known method that guarantees polynomial runtime in the Turing machine model. But in practice, its performance is not so good.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1371574435 under CC BY-SA 4.0; modifications have been made.