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.
Within the use of chordal decompositions in semidefinite programming, there is a history of research going back to 1984 [with over 500 citations] Grone , with a considerable revival @cite_43 @cite_47 @cite_56 @cite_50 in the past two decades. There are important applications in statistics @cite_8 , power systems @cite_0 , and automatic control @cite_16 . Within machine learning, one related techniques have been used in graphical models @cite_9 @cite_51 @cite_48 . For an excellent survey, see @cite_47 .
@cite_8 @cite_48 @cite_9 @cite_56 @cite_0 @cite_43 @cite_50 @cite_47 @cite_16 @cite_51
2114682096 2120340025 2962764388 2071143636 2734507298
We describe algorithms for maximum likelihood estimation of Gaussian graphical models with conditional independence constraints. This problem is also known as covariance selection, and it can be expressed as an unconstrained convex optimization problem with a closed-form solution if the underlying graph is chordal. The focus of the paper is on iterative algorithms for covariance selection with nonchordal graphs. We first derive efficient methods for evaluating the gradient and Hessian of the log-likelihood function when the underlying graph is chordal. The algorithms are formulated as simple recursions on a clique tree associated with the graph. We also show that the gradient and Hessian mappings are easily inverted when the underlying graph is chordal. We then exploit these results to obtain efficient implementations of Newton's method and the conjugate gradient method for large nonchordal graphs, by embedding the graph in a chordal graph. The formalism of probabilistic graphical models provides a unifying framework for capturing complex dependencies among random variables, and building large-scale multivariate statistical models. Graphical models have become a focus of research in many statistical, computational and mathematical fields, including bioinformatics, communication theory, statistical physics, combinatorial optimization, signal and image processing, information retrieval and statistical machine learning. Many problems that arise in specific instances — including the key problems of computing marginals and modes of probability distributions — are best studied in the general setting. Working with exponential family representations, and exploiting the conjugate duality between the cumulant function and the entropy for exponential families, we develop general variational representations of the problems of computing likelihoods, marginal probabilities and most probable configurations. We describe how a wide variety of algorithms — among them sum-product, cluster variational methods, expectation-propagation, mean field methods, max-product and linear programming relaxation, as well as conic programming relaxations — can all be understood in terms of exact or approximate forms of these variational representations. The variational approach provides a complementary alternative to Markov chain Monte Carlo as a general source of approximation methods for inference in large-scale statistical models. Many problems in control theory can be formulated as semidefinite programs (SDPs). For large-scale SDPs, it is important to exploit the inherent sparsity to improve scalability. This paper develops efficient first-order methods to solve SDPs with chordal sparsity based on the alternating direction method of multipliers (ADMM). We show that chordal decomposition can be applied to either the primal or the dual standard form of a sparse SDP, resulting in scaled versions of ADMM algorithms with the same computational cost. Each iteration of our algorithms consists of a projection on the product of small positive semidefinite cones, followed by a projection on an affine set, both of which can be carried out efficiently. Our techniques are implemented in CDCS, an open source add-on to MATLAB. Numerical experiments on large-scale sparse problems in SDPLIB and random SDPs with block-arrow sparse patterns show speedups compared to some common state-of-the-art software packages. A critical disadvantage of primal-dual interior-point methods compared to dual interior-point methods for large scale semidefinite programs (SDPs) has been that the primal positive semidefinite matrix variable becomes fully dense in general even when all data matrices are sparse. Based on some fundamental results about positive semidefinite matrix completion, this article proposes a general method of exploiting the aggregate sparsity pattern over all data matrices to overcome this disadvantage. Our method is used in two ways. One is a conversion of a sparse SDP having a large scale positive semidefinite matrix variable into an SDP having multiple but smaller positive semidefinite matrix variables to which we can effectively apply any interior-point method for SDPs employing a standard block-diagonal matrix data structure. The other way is an incorporation of our method into primal-dual interior-point methods which we can apply directly to a given SDP. In Part II of this article, we will investigate an implementation of such a primal-dual interior-point method based on positive definite matrix completion, and report some numerical results. We consider the problem of designing static feedback gains subject to a priori structural constraints, which is a nonconvex problem in general. Previous work has focused on either characterizing special structures that result into convex formulations, or employing certain techniques to allow convex relaxations of the original problem. In this paper, by exploiting the underlying sparsity properties of the problem, and using chordal decomposition, we propose a scalable algorithm to obtain structured feedback gains to stabilize a large-scale system. We first extend the chordal decomposition theorem for positive semidefinite matrices to the case of matrices with block-chordal sparsity. Then, a block-diagonal Lyapunov matrix assumption is used to convert the design of structured feedback gains into a convex problem, which inherits the sparsity pattern of the original problem. Combining these two results, we propose a sequential design method to obtain structured feedback gains clique-by-clique over a clique tree of the block-chordal matrix, which only needs local information and helps ensure privacy of model data. Several illustrative examples demonstrate the efficiency and scalability of the proposed sequential design method.