Positive semidefinite zero forcing

The positive semidefinite zero forcing number _Z+(G)${\mathrm{Z}}_{+}(G)$ of a graph G was introduced in Barioli et al. (2010) [4]. We establish a variety of properties of _Z+(G)${\mathrm{Z}}_{+}(G)$: Any vertex of G   can be in a minimum positive semidefinite zero forcing set (this is not true for standard zero forcing). The graph parameters tw(G)$\mathrm{tw}(G)$ (tree-width), _Z+(G)${\mathrm{Z}}_{+}(G)$, and Z(G)$\mathrm{Z}(G)$ (standard zero forcing number) all satisfy the Graph Complement Conjecture (see Barioli et al. (2012) [3]). Graphs having extreme values of the positive semidefinite zero forcing number are characterized. The effect of various graph operations on positive semidefinite zero forcing number and connections with other graph parameters are studied.     

A condition for the convexity of the norm-numerical range of a matrix

Let v be a norm on Cⁿ, and let a be a matrix which has a v-Hermitian decomposition. (1) The v-numerical range of a is convex. (This generalizes the Hausdorff-Toeplitz theorem.) In fact, the v-numerical range is equal to the field of values of a matrix similar to a. (2) If the Hermitian and v-Hermitian decompositions of a coincide, then the v-numerical range of a and the field of values of a are the same. This follows from detailed information about the boundary of the range.     

A self-concordance property for nonconvex semidefinite programming

The paper considers nonconvex quadratic semidefinite problems. This class arises, for instance, as subproblems in the sequential semidefinite programming algorithm for solving general smooth nonlinear semidefinite problems. We extend locally the concept of self-concordance to problems that satisfy a weak version of the second order sufficient optimality conditions.     

Positive semidefinite germs in real analytic surfaces

We find all real analytic surface germs in on which every positive semidefinite function germ is a sum of squares (in fact, of two squares) of analytic function germs. Received: 9 January 2001 / Published online: 24 September 2001     

Positive semidefinite matrix completions on chordal graphs and constraint nondegeneracy in semidefinite programming

Let G=(V,E) be a graph. In matrix completion theory, it is known that the following two conditions are equivalent: (i) G is a chordal graph; (ii) Every G-partial positive semidefinite matrix has a positive semidefinite matrix completion. In this paper, we relate these two conditions to constraint nondegeneracy condition in semidefinite programming and prove that they are each equivalent to (iii) For any G-partial positive definite matrix that has a positive semidefinite completion, constraint nondegeneracy is satisfied at each of its positive semidefinite matrix completions.     

Testing the nullspace property using semidefinite programming

Recent results in compressed sensing show that, under certain conditions, the sparsest solution to an underdetermined set of linear equations can be recovered by solving a linear program. These results either rely on computing sparse eigenvalues of the design matrix or on properties of its nullspace. So far, no tractable algorithm is known to test these conditions and most current results rely on asymptotic properties of random matrices. Given a matrix A, we use semidefinite relaxation techniques to test the nullspace property on A and show on some numerical examples that these relaxation bounds can prove perfect recovery of sparse solutions with relatively high cardinality.     

Positive semidefinite quadratic forms on unitary matrices

Let

     

Positive curvature property for some hypoelliptic heat kernels

In this note, we look at some hypoelliptic operators arising from nilpotent rank 2 Lie algebras. In particular, we concentrate on the diffusion generated by three Brownian motions and their three Lévy areas, which is the simplest extension of the Laplacian on the Heisenberg group H. In order to study contraction properties of the heat kernel, we show that, as in the case of the Heisenberg group, the restriction of the sub-Laplace operator acting on radial functions (which are defined in some precise way in the core of the paper) satisfies a non-negative Ricci curvature condition (more precisely a CD(0,∞) inequality), whereas the operator itself does not satisfy any CD(r,∞) inequality. From this we may deduce some useful, sharp gradient bounds for the associated heat kernel.     

Algorithms for positive semidefinite factorization

This paper considers the problem of positive semidefinite factorization (PSD factorization), a generalization of exact nonnegative matrix factorization. Given an m-by-n nonnegative matrix X and an integer k, the PSD factorization problem consists in finding, if possible, symmetric k-by-k positive semidefinite matrices \(\{A^1,\ldots ,A^m\}\) and \(\{B^1,\ldots ,B^n\}\) such that \(X_{i,j}=\text {trace}(A^iB^j)\) for \(i=1,\ldots ,m\), and \(j=1,\ldots ,n\). PSD factorization is NP-hard. In this work, we introduce several local optimization schemes to tackle this problem: a fast projected gradient method and two algorithms based on the coordinate descent framework. The main application of PSD factorization is the computation of semidefinite extensions, that is, the representations of polyhedrons as projections of spectrahedra, for which the matrix to be factorized is the slack matrix of the polyhedron. We compare the performance of our algorithms on this class of problems. In particular, we compute the PSD extensions of size \(k=1+ \lceil \log _2(n) \rceil \) for the regular n-gons when \(n=5\), 8 and 10. We also show how to generalize our algorithms to compute the square root rank (which is the size of the factors in a PSD factorization where all factor matrices \(A^i\) and \(B^j\) have rank one) and completely PSD factorizations (which is the special case where the input matrix is symmetric and equality \(A^i=B^i\) is required for all i).     

Bounds for codes by semidefinite programming

Delsarte’s method and its extensions allow one to consider the upper bound problem for codes in two-point homogeneous spaces as a linear programming problem with perhaps infinitely many variables, which are the distance distribution. We show that using as variables power sums of distances, this problem can be considered as a finite semidefinite programming problem. This method allows one to improve some linear programming upper bounds. In particular, we obtain new bounds of one-sided kissing numbers.     

Optimality conditions for nonconvex semidefinite programming

This paper concerns nonlinear semidefinite programming problems for which no convexity assumptions can be made. We derive first- and second-order optimality conditions analogous to those for nonlinear programming. Using techniques similar to those used in nonlinear programming, we extend existing theory to cover situations where the constraint matrix is structurally sparse. The discussion covers the case when strict complementarity does not hold. The regularity conditions used are consistent with those of nonlinear programming in the sense that the conventional optimality conditions for nonlinear programming are obtained when the constraint matrix is diagonal. Received: May 15, 1998 / Accepted: April 12, 2000?Published online May 12, 2000     

A rounding procedure for semidefinite optimization

Mohammad-Nezhad and Terlaky studied the identification of the optimal partition for semidefinite optimization. An approximation of the optimal partition was obtained from a bounded sequence of solutions on, or in a neighborhood of the central path. We use the approximation of the optimal partition in a rounding procedure to generate an approximate maximally complementary solution. From an interior solution, sufficiently close to the optimal set, the procedure rounds to a conic feasible solution, while the equality constraints are slightly violated.     

A sensitivity result for semidefinite programs

We study the sensitivity of solutions of linear semidefinite programs under small arbitrary perturbations of the data. We present an elementary and self-contained proof of the differentiability of the solutions as functions of the perturbations, and we characterize the derivative as the solution of a system of linear equations.     

Compact range property and operators on -algebras

We prove that a Banach space has the compact range property (CRP) if and only if, for any given -algebra , every absolutely summing operator from into is compact. Related results for -summing operators () are also discussed as well as operators on non-commutative -spaces and -summing operators.

     

Strengthened semidefinite programming bounds for codes

We give a hierarchy of semidefinite upper bounds for the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in n; this is based on a result of de Klerk et al. (Math Program, 2006) about the regular ∗-representation for matrix ∗-algebras. The Delsarte bound for A(n,d) is the first bound in the hierarchy, and the new bound of Schrijver (IEEE Trans. Inform. Theory 51:2859–2866, 2005) is located between the first and second bounds in the hierarchy. While computing the second bound involves a semidefinite program with O(n ⁷) variables and thus seems out of reach for interesting values of n, Schrijver’s bound can be computed via a semidefinite program of size O(n ³), a result which uses the explicit block-diagonalization of the Terwilliger algebra. We propose two strengthenings of Schrijver’s bound with the same computational complexity. Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203.     

A homotopy method for nonlinear semidefinite programming

In this paper, for solving the nonlinear semidefinite programming problem, a homotopy is constructed by using the parameterized matrix inequality constraint. Existence of a smooth path determined by the homotopy equation, which starts from almost everywhere and converges to a Karush–Kuhn–Tucker point, is proven under mild conditions. A predictor-corrector algorithm is given for numerically tracing the smooth path. Numerical tests with nonlinear semidefinite programming formulations of several control design problems with the data contained in COMPl _e ib are done. Numerical results show that the proposed algorithm is feasible and applicable.