In semidefinite programming (SDP), a number of pre-processing techniques have been developed including chordal-completion procedures, which reduce the dimension of individual constraints by exploiting sparsity therein, and facial reduction, which reduces the dimension of the problem by removing redundant rows and columns. This paper suggest that these work in a complementary manner and that facial reduction should be used after chordal-completion procedures. In computational experiments on SDP instances from the SDPLib, a benchmark, and structured instances from polynomial and binary quadratic optimisation, we show that such two-step pre-processing with a standard interior-point method outperforms the interior point method, with or without the traditional pre-processing.
The sensor network localization (SNL) problem in embedding dimension @math consists of locating the positions of wireless sensors, given only the distances between sensors that are within radio range and the positions of a subset of the sensors (called anchors). Current solution techniques relax this problem to a weighted, nearest, (positive) semidefinite programming (SDP) completion problem by using the linear mapping between Euclidean distance matrices (EDM) and semidefinite matrices. The resulting SDP is solved using primal-dual interior point solvers, yielding an expensive and inexact solution. This relaxation is highly degenerate in the sense that the feasible set is restricted to a low dimensional face of the SDP cone, implying that the Slater constraint qualification fails. Cliques in the graph of the SNL problem give rise to this degeneracy in the SDP relaxation. In this paper, we take advantage of the absence of the Slater constraint qualification and derive a technique for the SNL problem, with exact data, that explicitly solves the corresponding rank restricted SDP problem. No SDP solvers are used. For randomly generated instances, we are able to efficiently solve many huge instances of this NP-hard problem to high accuracy by finding a representation of the minimal face of the SDP cone that contains the SDP matrix representation of the EDM. The main work of our algorithm consists in repeatedly finding the intersection of subspaces that represent the faces of the SDP cone that correspond to cliques of the SNL problem.  Recent breakthroughs have been made in the use of semi-definite programming and its application to real polynomial solving. For example, the real radical of a zero dimensional ideal, can be determined by such approaches. Some progress has been made on the determination of the real radical in positive dimension by Ma, Wang and Zhi[5, 4]. Such work involves the determination of maximal rank semidefinite matrices. Existing methods are computationally expensive and have poorer accuracy on larger examples. In previous work we showed that regularity in the form of the Slater constraint qualification (strict feasibility) fails for the moment matrix in the SDP feasibility problem[6]. We used facial reduction to obtain a smaller regularized problem for which strict feasibility holds. However we did not have a theoretical guarantee that our methods, based on facial reduction and Douglas-Rachford iteration ensured the satisfaction of the maximum rank condition. Our work is motivated by the problems above. We discuss how to compute the moment matrix and its kernel using facial reduction techniques where the maximum rank property can be guaranteed by solving the dual problem. The facial reduction algorithms on the primal form is presented. We give examples that exhibit for the first time additional facial reductions beyond the first which are effective in practice with much better accuracy than SeDuMi(CVX). We develop a monomial basis selection procedure for sum-of-squares (SOS) programs based on facial reduction. Using linear programming and polyhedral approximations, the proposed technique finds a face of the SOS cone containing the feasible set of a given SOS program. The identified face in turn identifies a set of monomials that can be used to convert the SOS program into a semidefinite program (SDP). The technique can be viewed as a generalization of standard parsing algorithms for monomial basis selection. As we illustrate with examples, the proposed method can lead to smaller SDPs that are simpler to solve.  We present two algorithms for large-scale noisy low-rank Euclidean distance matrix completion problems, based on semidefinite optimization. Our first method works by relating cliques in the graph of the known distances to faces of the positive semidefinite cone, yielding a combinatorial procedure that is provably robust and partly parallelizable. Our second algorithm is a first-order method for maximizing the trace---a popular low-rank inducing regularizer---in the formulation of the problem with a constrained misfit. Both of the methods output a point configuration that can serve as a high-quality initialization for local optimization techniques. Numerical experiments on large-scale sensor localization problems illustrate the two approaches. Abstract Various parameters of graphs connected to sparse matrix factorization and other applications can be approximated using an algorithm of . that finds vertex separators of graphs. The approximate values of the parameters, which include minimum front size, treewidth, pathwidth, and minimum elimination tree height, are no more than O (log n ) (minimum front size and treewidth) and O (log 2 n ) (pathwidth and minimum elimination tree height) times the optimal values. In addition, we show that unless P = NP there are no absolute approximation algorithms for any of the parameters. The present paper was inspired by the work of Kuhn and Tucker [1]. These authors transformed a certain class of constrained maximum problems into equivalent saddle value (minimax) problems. Their work seems to hinge on the consideration of still a third type of problem. A very simple but illustrative form of this problem is the following: let ( x ; ) positive orthant of some finite dimensional Euclidean space, and let f and g be real valued functions of x with the property that whenever ( f 0, )then also ( g 0; ) under what conditions can one then conclude that 3 a non-negative constant u such that uf ( g; ; for ; all ;x 0 ? )  We introduce Sieve-SDP, a simple facial reduction algorithm to preprocess semidefinite programs (SDPs). Sieve-SDP inspects the constraints of the problem to detect lack of strict feasibility, deletes redundant rows and columns, and reduces the size of the variable matrix. It often detects infeasibility. It does not rely on any optimization solver: the only subroutine it needs is Cholesky factorization, hence it can be implemented in a few lines of code in machine precision. We present extensive computational results on several problem collections from the literature, with many SDPs coming from polynomial optimization. Minimization of the nuclear norm is often used as a surrogate, convex relaxation, for finding the minimum rank completion (recovery) of a partial matrix. The minimum nuclear norm problem can be solved as a trace minimization semidefinite programming problem, (SDP). The SDP and its dual are regular in the sense that they both satisfy strict feasibility. Interior point algorithms are the current methods of choice for these problems. This means that it is difficult to solve large scale problems and difficult to get high accuracy solutions. In this paper we take advantage of the structure at optimality for the minimum nuclear norm problem. We show that even though strict feasibility holds, the facial reduction framework can be successfully applied to obtain a proper face that contains the optimal set, and thus can dramatically reduce the size of the final nuclear norm problem while guaranteeing a low-rank solution. We include numerical tests for both exact and noisy cases. In all cases we assume that knowledge of a target rank is available. How ro initialize an algorithm to solve an optimization problem is of great theoretical and practical importance. In the simplex method for linear programming this issue is resolved by either the two-phase approach or using the so-called big M technique. In the interior point method, there is a more elegant way to deal with the initialization problem. Viz. the self-dual embedding technique proposed by Ye, Todd and Mizuno [30]. For linear programming this technique makes it possible to identify an optimal solution or conclude the problem to be infeasible unbounded by solving tts embedded self-dual problem The embedded self-dual problem has a trivial initial solution and has the same stmctare as the original problem. Hence. it eliminates the need to consider the initialization problem at all. In this paper, we extend this approach to solve general conic convex programming, including semidefinite programmng. Since a nonlinear conic convex programming problem may lack the so-called strict complementarity prop... We observe that Sturm's error bounds readily imply that for semidefinite feasibility problems, the method of alternating projections converges at a rate of @math O(k-12d+1-2), where d is the singularity degree of the problem--the minimal number of facial reduction iterations needed to induce Slater's condition. Consequently, for almost all such problems (in the sense of Lebesgue measure), alternating projections converge at a worst-case rate of @math O(1k). Conic optimization, or cone programming, is a subfield of convex optimization that includes linear, second-order cone, and semidefinite programming as special cases. While conic optimization problems arise in a diverse set of fields (including machine learning, robotics, and finance), efficiently solving them remains an active area of research. Developing methods that detect and exploit useful structure-such as symmetry, sparsity, or degeneracy-is one research topic. Such methods include facial and symmetry reduction, which have been successful in several applications, often reducing solve time by orders of magnitude. Nevertheless, theoretical and practical barriers preclude their general purpose use: to our knowledge, no solver uses facial or symmetry reduction as an automatic preprocessing step. This thesis addresses some of these barriers in three parts: the first develops more practical facial reduction techniques, the second proposes a more powerful and computationally efficient generalization of symmetry reduction (which we call Jordan reduction), and the third specializes techniques to convex relaxations of polynomial optimization problems. Throughout, we place emphasis on semidefinite programs and, more generally, optimization problems over symmetric cones. We also present computational results. 