Semidefinite programming

From HandWiki
Revision as of 22:57, 6 February 2024 by Steve2012 (talk | contribs) (over-write)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Short description: Subfield of convex optimization

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.[1]

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 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.

Motivation and definition

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 (linear programming) are replaced by semidefiniteness constraints on matrix variables in SDP (semidefinite programming). Specifically, a general semidefinite programming problem can be defined as any mathematical programming problem of the form

[math]\displaystyle{ \begin{array}{rl} {\displaystyle \min_{x^1, \ldots, x^n \in \mathbb{R}^n}} & {\displaystyle \sum_{i,j \in [n]} c_{i,j} (x^i \cdot x^j)} \\ \text{subject to} & {\displaystyle \sum_{i,j \in [n]} a_{i,j,k} (x^i \cdot x^j) \leq b_k} \text{ for all }k \\ \end{array} }[/math]

where the [math]\displaystyle{ c_{i,j}, a_{i,j,k} }[/math], and the [math]\displaystyle{ b_k }[/math] are real numbers and [math]\displaystyle{ x^i \cdot x^j }[/math] is the dot product of [math]\displaystyle{ x^i }[/math] and [math]\displaystyle{ x^j }[/math].

Equivalent formulations

An [math]\displaystyle{ n \times n }[/math] matrix [math]\displaystyle{ M }[/math] is said to be positive semidefinite if it is the Gram matrix of some vectors (i.e. if there exist vectors [math]\displaystyle{ x^1, \ldots, x^n }[/math] such that [math]\displaystyle{ m_{i,j}=x^i \cdot x^j }[/math] for all [math]\displaystyle{ i,j }[/math]). If this is the case, we denote this as [math]\displaystyle{ M \succeq 0 }[/math]. 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 [math]\displaystyle{ \mathbb{S}^n }[/math] the space of all [math]\displaystyle{ n \times n }[/math] real symmetric matrices. The space is equipped with the inner product (where [math]\displaystyle{ {\rm trace} }[/math] denotes the trace):

[math]\displaystyle{ \langle A,B\rangle := {\rm trace}(A^T B) = \sum_{i=1,j=1}^n A_{ij}B_{ij}. }[/math]

We can rewrite the mathematical program given in the previous section equivalently as

[math]\displaystyle{ \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} }[/math]

where entry [math]\displaystyle{ i,j }[/math] in [math]\displaystyle{ C }[/math] is given by [math]\displaystyle{ \frac{c_{i,j} + c_{j,i}}{2} }[/math] from the previous section and [math]\displaystyle{ A_k }[/math] is a symmetric [math]\displaystyle{ n \times n }[/math] matrix having [math]\displaystyle{ i,j }[/math]th entry [math]\displaystyle{ \frac{a_{i,j,k}+a_{j,i,k}}{2} }[/math] from the previous section. Thus, the matrices [math]\displaystyle{ C }[/math] and [math]\displaystyle{ A_k }[/math] 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:

[math]\displaystyle{ \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} }[/math]

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 [math]\displaystyle{ X }[/math] as a diagonal entry ([math]\displaystyle{ X_{ii} }[/math] for some [math]\displaystyle{ i }[/math]). To ensure that [math]\displaystyle{ X_{ii} \geq 0 }[/math], constraints [math]\displaystyle{ X_{ij} = 0 }[/math] can be added for all [math]\displaystyle{ j \neq i }[/math]. As another example, note that for any positive semidefinite matrix [math]\displaystyle{ X }[/math], there exists a set of vectors [math]\displaystyle{ \{ v_i \} }[/math] such that the [math]\displaystyle{ i }[/math], [math]\displaystyle{ j }[/math] entry of [math]\displaystyle{ X }[/math] is [math]\displaystyle{ X_{ij} = (v_i, v_j) }[/math] the scalar product of [math]\displaystyle{ v_i }[/math] and [math]\displaystyle{ v_j }[/math]. 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 [math]\displaystyle{ \{ v_i \} }[/math] can be recovered in [math]\displaystyle{ O(n^3) }[/math] time (e.g., by using an incomplete Cholesky decomposition of X).

Relations to other optimization problems

The space of semidefinite matrices is a convex cone. Therefore, SDP is a special case of conic optimization, which is a special case of convex optimization.

When the matrix C is diagonal, the inner products <C,X> is equivalent to a vector product of the diagonal of C and the diagonal of X. Analogously, when the matrices Ak are diagonal, the corresponding inner products are equivalent to vector products. In these vector products, only the diagonal elements of X are used, so we can add constraints equating the non-diagonal elements of X to 0. The condition [math]\displaystyle{ X \succeq 0 }[/math] is then equivalent to the condition that all diagonal elements of X are non-negative. Then, the resulting SDP becomes a linear program in which the variables are the diagonal elements of X.

Duality theory

Definitions

Analogously to linear programming, given a general SDP of the form

[math]\displaystyle{ \begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle \\ \text{subject to} & \langle A_i, X \rangle = b_i, \quad i = 1,\ldots,m \\ & X \succeq 0 \end{array} }[/math]

(the primal problem or P-SDP), we define the dual semidefinite program (D-SDP) as

[math]\displaystyle{ \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} }[/math]

where for any two matrices [math]\displaystyle{ P }[/math] and [math]\displaystyle{ Q }[/math], [math]\displaystyle{ P \succeq Q }[/math] means [math]\displaystyle{ P-Q \succeq 0 }[/math].

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

[math]\displaystyle{ \langle C, X \rangle - b^T y = \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, }[/math]

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

When the value of the primal and dual SDPs are equal, the SDP is said to satisfy the strong duality property. Unlike linear programs, where every dual linear program has optimal objective equal to the primal objective, not every SDP satisfies strong duality; in general, the value of the dual SDP may lie strictly below the value of the primal, and the P-SDP and D-SDP satisfy the following properties:

(i) Suppose the primal problem (P-SDP) is bounded below and strictly feasible (i.e., there exists [math]\displaystyle{ X_0\in\mathbb{S}^n, X_0\succ 0 }[/math] such that [math]\displaystyle{ \langle A_i,X_0\rangle = b_i }[/math], [math]\displaystyle{ i=1,\ldots,m }[/math]). Then there is an optimal solution [math]\displaystyle{ y^* }[/math] to (D-SDP) and

[math]\displaystyle{ \langle C,X^*\rangle = b^T y^*. }[/math]

(ii) Suppose the dual problem (D-SDP) is bounded above and strictly feasible (i.e., [math]\displaystyle{ \sum_{i=1}^m (y_0)_i A_i \prec C }[/math] for some [math]\displaystyle{ y_0\in\R^m }[/math]). Then there is an optimal solution [math]\displaystyle{ X^* }[/math] 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.[2][3]

Examples

Example 1

Consider three random variables [math]\displaystyle{ A }[/math], [math]\displaystyle{ B }[/math], and [math]\displaystyle{ C }[/math]. A given set of correlation coefficients [math]\displaystyle{ \rho_{AB}, \ \rho_{AC}, \rho_{BC} }[/math] are possible if and only if

[math]\displaystyle{ \begin{pmatrix} 1 & \rho_{AB} & \rho_{AC} \\ \rho_{AB} & 1 & \rho_{BC} \\ \rho_{AC} & \rho_{BC} & 1 \end{pmatrix} \succeq 0. }[/math]

This matrix is called the correlation matrix. Suppose that we know from some prior knowledge (empirical results of an experiment, for example) that [math]\displaystyle{ -0.2 \leq \rho_{AB} \leq -0.1 }[/math] and [math]\displaystyle{ 0.4 \leq \rho_{BC} \leq 0.5 }[/math]. The problem of determining the smallest and largest values that [math]\displaystyle{ \rho_{AC} \ }[/math] can take is given by:

[math]\displaystyle{ \begin{array}{rl} {\displaystyle\min/\max} & x_{13} \\ \text{subject to} & -0.2 \leq x_{12} \leq -0.1\\ & 0.4 \leq x_{23} \leq 0.5\\ & \begin{pmatrix} 1 & x_{12} & x_{13} \\ x_{12} & 1 & x_{23} \\ x_{13} & x_{23} & 1 \end{pmatrix} \succeq 0 \end{array} }[/math]

We set [math]\displaystyle{ \rho_{AB} = x_{12}, \ \rho_{AC} = x_{13}, \ \rho_{BC} = x_{23} }[/math] 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

[math]\displaystyle{ \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 }[/math]

Solving this SDP gives the minimum and maximum values of [math]\displaystyle{ \rho_{AC} = x_{13} \ }[/math] as [math]\displaystyle{ -0.978 }[/math] and [math]\displaystyle{ 0.872 }[/math] respectively.

Example 2

Consider the problem

minimize [math]\displaystyle{ \frac{(c^T x)^2}{d^Tx} }[/math]
subject to [math]\displaystyle{ Ax +b\geq 0 }[/math]

where we assume that [math]\displaystyle{ d^Tx\gt 0 }[/math] whenever [math]\displaystyle{ Ax+b\geq 0 }[/math].

Introducing an auxiliary variable [math]\displaystyle{ t }[/math] the problem can be reformulated:

minimize [math]\displaystyle{ t }[/math]
subject to [math]\displaystyle{ Ax+b\geq 0, \, \frac{(c^T x)^2}{d^Tx}\leq t }[/math]

In this formulation, the objective is a linear function of the variables [math]\displaystyle{ x,t }[/math].

The first restriction can be written as

[math]\displaystyle{ \textbf{diag}(Ax+b)\geq 0 }[/math]

where the matrix [math]\displaystyle{ \textbf{diag}(Ax+b) }[/math] is the square matrix with values in the diagonal equal to the elements of the vector [math]\displaystyle{ Ax+b }[/math].

The second restriction can be written as

[math]\displaystyle{ td^Tx-(c^Tx)^2\geq 0 }[/math]

Defining [math]\displaystyle{ D }[/math] as follows

[math]\displaystyle{ D=\left[\begin{array}{cc}t&c^Tx\\c^Tx&d^Tx\end{array}\right] }[/math]

We can use the theory of Schur Complements to see that

[math]\displaystyle{ D \succeq 0 }[/math]

(Boyd and Vandenberghe, 1996)

The semidefinite program associated with this problem is

minimize [math]\displaystyle{ t }[/math]
subject to [math]\displaystyle{ \left[\begin{array}{ccc}\textbf{diag}(Ax+b)&0&0\\0&t&c^Tx\\0&c^Tx&d^Tx\end{array}\right] \succeq 0 }[/math]

Example 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).[1]:{{{1}}} 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 [math]\displaystyle{ \sum_{(i,j) \in E} \frac{1-v_{i} v_{j}}{2}, }[/math] such that each [math]\displaystyle{ v_i\in\{1,-1\} }[/math].

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:

  1. Relax the integer quadratic program into an SDP.
  2. Solve the SDP (to within an arbitrarily small additive error [math]\displaystyle{ \epsilon }[/math]).
  3. Round the SDP solution to obtain an approximate solution to the original integer quadratic program.

For max cut, the most natural relaxation is

[math]\displaystyle{ \max \sum_{(i,j) \in E} \frac{1-\langle v_{i}, v_{j}\rangle}{2}, }[/math] such that [math]\displaystyle{ \lVert v_i\rVert^2 = 1 }[/math], where the maximization is over vectors [math]\displaystyle{ \{v_i\} }[/math] 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 [math]\displaystyle{ \mathbf{R^n} }[/math]; 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 [math]\displaystyle{ \cos^{-1}\langle v_{i}, v_{j}\rangle }[/math] between the vectors at the endpoints of the edge over [math]\displaystyle{ \pi }[/math]. Comparing this probability to [math]\displaystyle{ (1-\langle v_{i}, v_{j}\rangle)/{2} }[/math], 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. Recently, Prasad Raghavendra has developed a general framework for constraint satisfaction problems based on the unique games conjecture.[4]

Other 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, and in inverse elliptic coefficient problems as convex, non-linear, semidefiniteness constraints.[5] It is also widely used in physics to constrain conformal field theories with the conformal bootstrap.[6]

Run-time complexity

The semidefinite feasibility problem (SDF) is the following decision problem: given an SDP, decide whether it has at least one feasible solution. The exact run-time complexity of this problem is unknown (as of 1997). However, Ramana proved the following:[2]

Approximation algorithms

There are several types of algorithms for approximately solving SDPs. These algorithms output the value of the SDP up to an additive error [math]\displaystyle{ \epsilon }[/math] in time that is polynomial in the program description size and [math]\displaystyle{ \log (1/\epsilon) }[/math].

Ellipsoid method

The ellipsoid method is a general method for convex programming, and can be used in particular to solve SDPs. In the context of SDPs, the ellipsoid method provides the following guarantee.[1]:{{{1}}}Consider an SDP in the following equational form:

[math]\displaystyle{ \begin{array}{rl} {\displaystyle\max_{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} }[/math]

Let L be the affine subspace of matrices in Sn satisfying the m equational constraints; so the SDP can be written as: [math]\displaystyle{ \max_{X\in L} \langle C,X\rangle \text{ subject to } X\succeq 0 }[/math]. 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 Sn is called ε-deep if every matrix Y in L with Frobenius distance at most ε from X satisfies the feasibility condition [math]\displaystyle{ Y\succeq 0 }[/math]. Denote [math]\displaystyle{ v_{deep} := \sup \{\langle C,X\rangle: X \text{ is } \epsilon\text{-deep} \} }[/math]. 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 [math]\displaystyle{ X\succeq 0 }[/math]), and [math]\displaystyle{ \langle C,X^*\rangle \geq v_{deep} -\epsilon }[/math] (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.[1](p23) But in practice, its performance is not so good.

Hazan's algorithm

Elad Hazan[7] has developed a simple algorithm for solving SDPs with the additional constraint that the trace of the variables matrix must be 1. Specifically, his algorithm solves problems of the form:

[math]\displaystyle{ \begin{array}{rl} {\displaystyle\max_{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 \\ & \operatorname{trace}(X) = 1, \\ & X \succeq 0. \end{array} }[/math]

This can be seen as a maximizing a linear objective over the spectraplex.

Let OPT be the optimal value of this problem, and ε>0 a constant. Hazan's algorithm returns one of the following:[1]:{{{1}}}

  • A matrix in the spectraplex such that [math]\displaystyle{ OPT - \langle C,X\rangle \leq 2\epsilon \cdot \|C\| \text{ and } \langle A_i , X\rangle - bi \leq \epsilon\cdot \|A_i\| }[/math] (that is, the solution is approximately optimal and satisfies the linear inequalities approximately);
  • A certificate that there is no feasible solution.

The run-time in the Real RAM model is, with high probability, in [math]\displaystyle{ O\left (\frac{N \cdot \log{n}\cdot \log{m} \cdot log(1/\epsilon)}{\epsilon^3}\right) }[/math], where N is input size (number of nonzero entries in the matrices), n is the number of variables, and m is the number of inequality constraints. Note that the runtime is polynomial in 1/ε rather than log(1/ε). However, in practice it runs quite fast.

Hazan's algorithm uses a sub-routine for solving the feasibility problem - deciding whether a given SDP is feasible:

[math]\displaystyle{ \begin{array}{rl} {\displaystyle \text{find } {X \in \mathbb{S}^n}} & \\ \text{subject to} & \langle A_k, X \rangle \leq b_k, \quad k = 1,\ldots,m \\ & \operatorname{trace}(X) = 1, \\ & X \succeq 0. \end{array} }[/math]

There is an algorithm that, for any given ε>0, returns one of the following:[1]:{{{1}}}

  • An ε-approximately-feasible solution: a solution X in the spectraplex, for which [math]\displaystyle{ \langle A_i , X\rangle - bi \leq \epsilon }[/math] for all i in 1,...,m.
  • A certificate that no feasible solution exists.

The run-time in the Real RAM model is, with high probability, in [math]\displaystyle{ O\left (\frac{N \cdot \log{n}\cdot \log{m} \cdot }{\epsilon^3}\right) }[/math]. The algorithm is applied in a binary search style to find an approximately-optimal solution.

Interior point methods

Most codes are based on interior point methods (CSDP, MOSEK, SeDuMi, SDPT3, DSDP, SDPA). These are robust and efficient for general linear SDP problems, but restricted by the fact that the algorithms are second-order methods and need to store and factorize a large (and often dense) matrix. Theoretically, the state-of-the-art high-accuracy SDP algorithms[8][9] are based on this approach.

First-order methods

First-order methods for conic optimization avoid computing, storing and factorizing a large Hessian matrix and scale to much larger problems than interior point methods, at some cost in accuracy. A first-order method is implemented in the Splitting Cone Solver (SCS).[10] Another first-order method is the alternating direction method of multipliers (ADMM).[11] This method requires in every step projection on the cone of semidefinite matrices.

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 solving methods

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 (SDPLR, ManiSDP).[12]

Approximate methods

Algorithms that solve SDPs approximately have been proposed as well. The main goal of such methods is to achieve lower complexity in applications where approximate solutions are sufficient and complexity must be minimal. A prominent method that has been used for data detection in multiple-input multiple-output (MIMO) wireless systems is Triangular Approximate SEmidefinite Relaxation (TASER),[13] which operates on the Cholesky decomposition factors of the semidefinite matrix instead of the semidefinite matrix. This method calculates approximate solutions for a max-cut-like problem that are often comparable to solutions from exact solvers but in only 10-20 algorithm iterations.

Preprocessing algorithms

Facial reduction algorithms are algorithms used to preprocess SDPs problems by inspecting the constraints of the problem. These can be used to

  • Detect lack of strict feasibility;
  • Delete redundant rows and columns;
  • Reduce the size of the variable matrix.[14]

See also

References

  1. ↑ 1.0 1.1 1.2 1.3 1.4 1.5 Gärtner, Bernd; Matoušek, Jiří (2012), Gärtner, Bernd; Matousek, Jiri, eds., "Semidefinite Programming" (in en), Approximation Algorithms and Semidefinite Programming (Berlin, Heidelberg: Springer): pp. 15–25, doi:10.1007/978-3-642-22015-9_2, ISBN 978-3-642-22015-9, https://doi.org/10.1007/978-3-642-22015-9_2, retrieved 2023-12-31 
  2. ↑ 2.0 2.1 Ramana, Motakuri V. (1997). "An exact duality theory for semidefinite programming and its complexity implications" (in en). Mathematical Programming 77 (1): 129–162. doi:10.1007/BF02614433. ISSN 0025-5610. http://link.springer.com/10.1007/BF02614433. 
  3. ↑ Vandenberghe, Lieven; Boyd, Stephen (1996). "Semidefinite Programming" (in en). SIAM Review 38 (1): 49–95. doi:10.1137/1038003. ISSN 0036-1445. http://epubs.siam.org/doi/10.1137/1038003. 
  4. ↑ Raghavendra, Prasad (2008). "Optimal algorithms and inapproximability results for every CSP?". Proceedings of the fortieth annual ACM symposium on Theory of computing. pp. 245–254. doi:10.1145/1374376.1374414. ISBN 9781605580470. http://doi.acm.org/10.1145/1374376.1374414. 
  5. ↑ Harrach, Bastian (2021), "Solving an inverse elliptic coefficient problem by convex non-linear semidefinite programming" (in en), Optimization Letters 16 (5): 1599–1609, doi:10.1007/s11590-021-01802-4 
  6. ↑ Simmons-Duffin, David (2015-02-06). "A Semidefinite Program Solver for the Conformal Bootstrap". Journal of High Energy Physics 2015 (6): 174. doi:10.1007/JHEP06(2015)174. Bibcode: 2015JHEP...06..174S. 
  7. ↑ Hazan, Elad (2008). Laber, Eduardo Sany; Bornstein, Claudson; Nogueira, Loana Tito et al.. eds. "Sparse Approximate Solutions to Semidefinite Programs" (in en). LATIN 2008: Theoretical Informatics. Lecture Notes in Computer Science (Berlin, Heidelberg: Springer): 306–316. doi:10.1007/978-3-540-78773-0_27. ISBN 978-3-540-78773-0. https://link.springer.com/chapter/10.1007/978-3-540-78773-0_27. 
  8. ↑ Jiang, Haotian; Kathuria, Tarun; Lee, Yin Tat; Padmanabhan, Swati; Song, Zhao (November 2020). "A Faster Interior Point Method for Semidefinite Programming". 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). Durham, NC, USA: IEEE. pp. 910–918. doi:10.1109/FOCS46700.2020.00089. ISBN 978-1-7281-9621-3. https://ieeexplore.ieee.org/document/9317892. 
  9. ↑ Huang, Baihe; Jiang, Shunhua; Song, Zhao; Tao, Runzhou; Zhang, Ruizhe (2021-11-18). "Solving SDP Faster: A Robust IPM Framework and Efficient Implementation". arXiv:2101.08208 [math.OC].
  10. ↑ Brendan O'Donoghue, Eric Chu, Neal Parikh, Stephen Boyd, "Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding", Journal of Optimization Theory and Applications, 2016, pp 1042--1068, https://web.stanford.edu/~boyd/papers/pdf/scs.pdf.
  11. ↑ Wen, Zaiwen, Donald Goldfarb, and Wotao Yin. "Alternating direction augmented Lagrangian methods for semidefinite programming." Mathematical Programming Computation 2.3-4 (2010): 203-230.
  12. ↑ Burer, Samuel; Monteiro, Renato D. C. (2003), "A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization" (in en), Mathematical Programming 95 (2): 329–357, doi:10.1007/s10107-002-0352-8, ISSN 1436-4646 
  13. ↑ Castañeda, O.; Goldstein, T.; Studer, C. (December 2016). "Data Detection in Large Multi-Antenna Wireless Systems via Approximate Semidefinite Relaxation". IEEE Transactions on Circuits and Systems I: Regular Papers 63 (12): 2334–2346. doi:10.1109/TCSI.2016.2607198. ISSN 1558-0806. 
  14. ↑ Zhu, Yuzixuan; Pataki, Gábor; Tran-Dinh, Quoc (2019), "Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs" (in en), Mathematical Programming Computation 11 (3): 503–586, doi:10.1007/s12532-019-00164-4, ISSN 1867-2949, http://link.springer.com/10.1007/s12532-019-00164-4 
  • Lieven Vandenberghe, Stephen Boyd, "Semidefinite Programming", SIAM Review 38, March 1996, pp. 49–95. pdf
  • Monique Laurent, Franz Rendl, "Semidefinite Programming and Integer Programming", Report PNA-R0210, CWI, Amsterdam, April 2002. optimization-online
  • E. de Klerk, "Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications", Kluwer Academic Publishers, March 2002, ISBN:1-4020-0547-4.
  • Robert M. Freund, "Introduction to Semidefinite Programming (SDP), SDP-Introduction

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Semidefinite_programming&oldid=3386188"