Exploiting sparsity in semidefinite programming via matrix completion II: implementation and numerical results

 In Part I of this series of articles, we introduced a general framework of exploiting the aggregate sparsity pattern over all data matrices of large scale and sparse semidefinite programs (SDPs) when solving them by primal-dual interior-point methods. This framework is based on some results about positive semidefinite matrix completion, and it can be embodied in two different ways. One is by a conversion of a given sparse SDP having a large scale positive semidefinite matrix variable into an SDP having multiple but smaller positive semidefinite matrix variables. The other is by incorporating a positive definite matrix completion itself in a primal-dual interior-point method. The current article presents the details of their implementations. We introduce new techniques to deal with the sparsity through a clique tree in the former method and through new computational formulae in the latter one. Numerical results over different classes of SDPs show that these methods can be very efficient for some problems. Received: March 18, 2001 / Accepted: May 31, 2001 Published online: October 9, 2002 RID="⋆" ID="⋆"The author was supported by The Ministry of Education, Culture, Sports, Science and Technology of Japan. Key Words. semidefinite programming – primal-dual interior-point method – matrix completion problem – clique tree – numerical results Mathematics Subject Classification (2000): 90C22, 90C51, 05C50, 05C05     

Exploiting sparsity in primal-dual interior-point methods for semidefinite programming

The Helmberg-Rendl-Vanderbei-Wolkowicz/Kojima-Shindoh-Hara/Monteiro and Nesterov-Todd search directions have been used in many primal-dual interior-point methods for semidefinite programs. This paper proposes an efficient method for computing the two directions when the semidefinite program to be solved is large scale and sparse.     

Extermal positive semidefinite matrices with given sparsity pattern

We prove a conjecture of Helton, Pierce and Rodman about the connection between the ranks of matrices generating extreme rays in the cone of positive semidefinite matrices with a given sparsity pattern and the amount of fill-in for the specific sparsity pattern. We also present a necessary condition on the given sparsity pattern for the existence of a rank k extermal in the cone.     

Half thresholding eigenvalue algorithm for semidefinite matrix completion

The semidefinite matrix completion(SMC) problem is to recover a low-rank positive semidefinite matrix from a small subset of its entries. It is well known but NP-hard in general. We first show that under some cases, SMC problem and S1/2relaxation model share a unique solution. Then we prove that the global optimal solutions of S1/2regularization model are fixed points of a symmetric matrix half thresholding operator. We give an iterative scheme for solving S1/2regularization model and state convergence analysis of the iterative sequence.Through the optimal regularization parameter setting together with truncation techniques, we develop an HTE algorithm for S1/2regularization model, and numerical experiments confirm the efficiency and robustness of the proposed algorithm.     

Multivariate Gaussians,semidefinite matrix completion,and convex algebraic geometry

We study multivariate normal models that are described by linear constraints on the inverse of the covariance matrix. Maximum likelihood estimation for such models leads to the problem of maximizing the determinant function over a spectrahedron, and to the problem of characterizing the image of the positive definite cone under an arbitrary linear projection. These problems at the interface of statistics and optimization are here examined from the perspective of convex algebraic geometry.     

复半正定矩阵的奇异值不等式

用Mn表示所有复矩阵组成的集合.对于A∈Mn,σ(A)=(σ1(A),…,σn(A)),其中σ1(A)≥…≥σn(A)是矩阵A的奇异值.本文给出证明:对于任意实数α,A,B∈Mn为半正定矩阵,优化不等式σ(A-|α|B) wlogσ(A+αB)成立,改进和推广了文[5]的结果.     

Bounds on linear PDEs via semidefinite optimization

Using recent progress on moment problems, and their connections with semidefinite optimization, we present in this paper a new methodology based on semidefinite optimization, to obtain a hierarchy of upper and lower bounds on linear functionals defined on solutions of linear partial differential equations. We apply the proposed method to examples of PDEs in one and two dimensions, with very encouraging results. We pay particular attention to a PDE with oblique derivative conditions, commonly arising in queueing theory. We also provide computational evidence that the semidefinite constraints are critically important in improving the quality of the bounds, that is, without them the bounds are weak. Research supported by the SMA-MI Talliance. Research partially supported by the SMA-MIT alliance and an NSF predoctoral fellowship.     

Robust linear optimization under matrix completion

Linear programming models have been widely used in input-output analysis for analyzing the interdependence of industries in economics and in environmental science.In these applications,some of the entries of the coefficient matrix cannot be measured physically or there exists sampling errors.However,the coefficient matrix can often be low-rank.We characterize the robust counterpart of these types of linear programming problems with uncertainty set described by the nuclear norm.Simulations for the input-output analysis show that the new paradigm can be helpful.     

The unique square root of a positive semidefinite matrix

An easy way to present the uniqueness of the square root of a positive semidefinite matrix is given.     

Further relationship between second-order cone and positive semidefinite matrix cone

It is well known that second-order cone (SOC) programming can be regarded as a special case of positive semidefinite programming using the arrow matrix. This paper further studies the relationship between SOCs and positive semidefinite matrix cones. In particular, we explore the relationship to expressions regarding distance, projection, tangent cone, normal cone and the KKT system. Understanding these relationships will help us see the connection and difference between the SOC and its PSD reformulation more clearly.     

The moment problem for continuous positive semidefinite linear functionals

Let τ be a locally convex topology on the countable dimensional polynomial ${\mathbb{R}}$ -algebra ${\mathbb{R} [\underline{X}] := \mathbb{R} [X_1, \ldots, X_{n}]}$ . Let K be a closed subset of ${\mathbb{R} ^{n}}$ , and let ${M := M_{\{g_1, \ldots, g_s\}}}$ be a finitely generated quadratic module in ${\mathbb{R} [\underline{X}]}$ . We investigate the following question: When is the cone Psd(K) (of polynomials nonnegative on K) included in the closure of M? We give an interpretation of this inclusion with respect to representing continuous linear functionals by measures. We discuss several examples; we compute the closure of ${M = \sum \mathbb{R} [\underline{X}]^{2}}$ with respect to weighted norm-p topologies. We show that this closure coincides with the cone Psd(K) where K is a certain convex compact polyhedron.     

Stability analysis for point delay fractional description models via linear matrix inequalities

This paper is devoted to linear parameter systems under linear fractional representations (LFR) of parameter-dependent nonlinear systems with real–rational nonlinearities and point-delayed dynamics. The robust global asymptotic stability of the system either independent of or dependent on the delay sizes is investigated. The associate matrix inequalities are related to the time-derivatives of appropriate Lyapunov functions at all the vertices of the polytope which contains the parameterized uncertainties.     

Stability analysis for point delay fractional description models via linear matrix inequalities

This paper is devoted to linear parameter systems under linear fractional representations (LFR) of parameter-dependent nonlinear systems with real-rational nonlinearities and point-delayed dynamics. The robust global asymptotic stability of the system either independent of or dependent on the delay sizes is investigated. The associate matrix inequalities are related to the time-derivatives of appropriate Lyapunov functions at all the vertices of the polytope which contains the parameterized uncertainties.     

Dynamic system methods for solving mixed linear matrix inequalities and linear vector inequalities and equalities

A novel idea is proposed for solving a system of mixed linear matrix inequalities and linear vector inequalities and equalities. First, the problem is converted into an unconstrained minimization problem with a continuously differentiable convex objective function. Then, a continuous-time dynamic system and a discrete-time dynamic system are proposed for solving it. Under some mild conditions, the proposed dynamic systems are shown to be globally convergent to a solution of the problem. The merits of the methods refer to their simple numerical implementations and capability for handling nonstrict LMIs easily. In addition, the methods are promising in neural circuits realization, and therefore have potential applications in many online control problems. Several numerical examples are presented to illustrate the performance of the methods and substantiate the theoretical results.     

Minimum norm solution to the positive semidefinite linear complementarity problem

In this article, we present an algorithm to compute the minimum norm solution of the positive semidefinite linear complementarity problem. We show that its solution can be obtained using the alternative theorems and a convenient characterization of the solution set of a convex quadratic programming problem. This problem reduces to an unconstrained minimization problem with once differentiable convex objective function. We propose an extension of Newton's method for solving the unconstrained optimization problem. Computational results show that convergence to high accuracy often occurs in just a few iterations.     

Around Choi inequalities for positive linear maps

We show an inequality for unital positive linear maps Φ interpolating Choi’s inequality (p=0) with a recent result of Bourin and Ricard (r=1):