Semidefinite representations for finite varieties

We consider the problem of minimizing a polynomial over a set defined by polynomial equations and inequalities. When the polynomial equations have a finite set of complex solutions, we can reformulate this problem as a semidefinite programming problem. Our semidefinite representation involves combinatorial moment matrices, which are matrices indexed by a basis of the quotient vector space ℝ[x ₁, . . . ,x _n ]/I, where I is the ideal generated by the polynomial equations in the problem. Moreover, we prove the finite convergence of a hierarchy of semidefinite relaxations introduced by Lasserre. Semidefinite approximations can be constructed by considering truncated combinatorial moment matrices; rank conditions are given (in a grid case) that ensure that the approximation solves the original problem to optimality. Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203.     

Some upper and lower bounds on PSD-rank

Positive semidefinite rank (PSD-rank) is a relatively new complexity measure on matrices, with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix M as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.     

Semiconvexity of invariant functions of rectangular matrices

The paper deals with the semiconvexity properties (i.e., the rank 1 convexity, quasiconvexity, polyconvexity, and convexity) of rotationally invariant functions f of matrices. For the invariance with respect to the proper orthogonal group and the invariance with respect to the full orthogonal group coincide. With each invariant f one can associate a fully invariant function of a square matrix of type where It is shown that f has the semi convexity of a given type if and only if has the semiconvexity of that type. Consequently the semiconvex hulls of f can be determined by evaluating the corresponding hulls of and then extending them to matrices by rotational invariance. Received: 10 October 2001 / Accepted: 23 January 2002 // Published online: 6 August 2002 RID="*" ID="*" This research was supported by Grant 201/00/1516 of the Czech Republic.     

Effects of uncertainties in the domain on the solution of Dirichlet boundary value problems

Summary. A domain with possibly non-Lipschitz boundary is defined as a limit of monotonically expanding or shrinking domains with Lipschitz boundary. A uniquely solvable Dirichlet boundary value problem (DBVP) is defined on each of the Lipschitz domains and the limit of these solutions is investigated. The limit function also solves a DBVP on the limit domain but the problem can depend on the sequences of domains if the limit domain is unstable with respect to the DBVP. The core of the paper consists in estimates of the difference between the respective solutions of the DBVP on two close domains, one of which is Lipschitz and the other can be unstable. Estimates for starshaped as well as rather general domains are derived. Their numerical evaluation is possible and can be done in different ways. Received October 16, 2001 / Revised version received January 16, 2002 / Published online: April 17, 2002 RID="*" ID="*" The research was funded partially by the National Science Foundation under the grants NSF–Czech Rep. INT-9724783 and NSF DMS-9802367 RID="**" ID="**" Support for Jan Chleboun coming from the Grant Agency of the Czech Republic through grant 201/98/0528 is appreciated     

Cuts, matrix completions and graph rigidity

This paper brings together several topics arising in distinct areas: polyhedral combinatorics, in particular, cut and metric polyhedra; matrix theory and semidefinite programming, in particular, completion problems for positive semidefinite matrices and Euclidean distance matrices; distance geometry and structural topology, in particular, graph realization and rigidity problems. Cuts and metrics provide the unifying theme. Indeed, cuts can be encoded as positive semidefinite matrices (this fact underlies the approximative algorithm for max-cut of Goemans and Williamson) and both positive semidefinite and Euclidean distance matrices yield points of the cut polytope or cone, after applying the functions 1/π arccos(.) or √. When fixing the dimension in the Euclidean distance matrix completion problem, we find the graph realization problem and the related question of unicity of realization, which leads to the question of graph rigidity. Our main objective here is to present in a unified setting a number of results and questions concerning matrix completion, graph realization and rigidity problems. These problems contain indeed very interesting questions relevant to mathematical programming and we believe that research in this area could yield to cross-fertilization between the various fields involved.     

On approximating complex quadratic optimization problems via semidefinite programming relaxations

In this paper we study semidefinite programming (SDP) models for a class of discrete and continuous quadratic optimization problems in the complex Hermitian form. These problems capture a class of well-known combinatorial optimization problems, as well as problems in control theory. For instance, they include the MAX-3-CUT problem where the Laplacian matrix is positive semidefinite (in particular, some of the edge weights can be negative). We present a generic algorithm and a unified analysis of the SDP relaxations which allow us to obtain good approximation guarantees for our models. Specifically, we give an -approximation algorithm for the discrete problem where the decision variables are k-ary and the objective matrix is positive semidefinite. To the best of our knowledge, this is the first known approximation result for this family of problems. For the continuous problem where the objective matrix is positive semidefinite, we obtain the well-known π /4 result due to Ben-Tal et al. [Math Oper Res 28(3):497–523, 2003], and independently, Zhang and Huang [SIAM J Optim 16(3):871–890, 2006]. However, our techniques simplify their analyses and provide a unified framework for treating those problems. In addition, we show for the first time that the gap between the optimal value of the original problem and that of the SDP relaxation can be arbitrarily close to π /4. We also show that the unified analysis can be used to obtain an Ω(1/ log n)-approximation algorithm for the continuous problem in which the objective matrix is not positive semidefinite. This research was supported in part by NSF grant DMS-0306611.     

On the complexity of computing the handicap of a sufficient matrix

The class of sufficient matrices is important in the study of the linear complementarity problem (LCP)—some interior point methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap.In this paper we show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity bounds of interior point methods are not polynomial in the input size of the LCP problem. We also introduce a semidefinite programming based heuristic, that provides a finite upper bond on the handicap, for the sub-class of P{\mathcal{P}} -matrices (where all principal minors are positive).     

Unitary matrix digraphs and minimum semidefinite rank

For an undirected simple graph G, the minimum rank among all positive semidefinite matrices with graph G is called the minimum semidefinite rank (msr) of G. In this paper, we show that the msr of a given graph may be determined from the msr of a related bipartite graph. Finding the msr of a given bipartite graph is then shown to be equivalent to determining which digraphs encode the zero/nonzero pattern of a unitary matrix. We provide an algorithm to construct unitary matrices with a certain pattern, and use previous results to give a lower bound for the msr of certain bipartite graphs.     

Ramsey-type Theorems with Forbidden Subgraphs

Dedicated to the memory of Paul Erdős   A graph is called H-free if it contains no induced copy of H. We discuss the following question raised by Erdős and Hajnal. Is it true that for every graph H, there exists an such that any H-free graph with n vertices contains either a complete or an empty subgraph of size at least ? We answer this question in the affirmative for a special class of graphs, and give an equivalent reformulation for tournaments. In order to prove the equivalence, we establish several Ramsey type results for tournaments. Received August 22, 1999 RID="*" ID="*" Supported by a USA Israeli BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. RID="†" ID="†" Supported by NSF grant CR-9732101, PSC-CUNY Research Award 663472, and OTKA-T-020914. RID="‡" ID="‡" Supported by TKI grant Stochastics@TUB, and OTKA-T-026203.     

On the minimum semidefinite rank of a simple graph

The minimum semidefinite rank (msr) of a graph is defined to be the minimum rank among all positive semidefinite matrices whose zero/nonzero pattern corresponds to that graph. We recall some known facts and present new results, including results concerning the effects of vertex or edge removal from a graph on msr.     

The Erdős–Pósa Property for Odd Cycles in Highly Connected Graphs

Dedicated to the memory of Paul Erdős In [9] Thomassen proved that a -connected graph either contains k vertex disjoint odd cycles or an odd cycle cover containing at most 2k-2 vertices, i.e. he showed that the Erdős–Pósa property holds for odd cycles in highly connected graphs. In this paper, we will show that the above statement is still valid for 576k-connected graphs which is essentially best possible. Received November 17, 1999 RID="*" ID="*" This work was supported by a post-doctoral DONET grant. RID="†" ID="†" This work was supported by an NSF-CNRS collaborative research grant. RID="‡" ID="‡" This work was performed while both authors were visiting the LIRMM, Université de Montpellier II, France.     

More on generalizations of matrix monotonicity

Following Berman and Plemmons [5], Werner [17], Poole and Barker [13], and others, we investigate some generalizations of matrix monotonicity and consider their relation to MP matrices. We prove some observations on almost monotone, MP, and group monotone matrices. However, of much interest to us is the problem whether a symmetric positive semidefinite matrix is MP if and only if it is monotone on its range. To consider this question we obtain several results on the structure of range monotone matrices.     

Perimeter preserver of matrices over semifields

For a rank-1 matrix A = ab ^t, we define the perimeter of A as the number of nonzero entries in both a and b. We characterize the linear operators which preserve the rank and perimeter of rank-1 matrices over semifields. That is, a linear operator T preserves the rank and perimeter of rank-1 matrices over semifields if and only if it has the form T(A) = U AV, or T(A) = U A ^t V with some invertible matrices U and V. This work was supported by the research grant of the Cheju National University in 2006.     

On stability of the P n mod /P n element for incompressible flow problems

It is well known that finite element spaces used for approximating the velocity and the pressure in an incompressible flow problem have to be stable in the sense of the inf-sup condition of Babuška and Brezzi if a stabilization of the incompressibility constraint is not applied. In this paper we consider a recently introduced class of triangular nonconforming finite elements of nth order accuracy in the energy norm called P _n ^mod elements. For n ≤ 3 we show that the stability condition holds if the velocity space is constructed using the P _n ^mod elements and the pressure space consists of continuous piecewise polynomial functions of degree n. This research has been supported by the Grant Agency of the Czech Republic under the grant No. 201/05/0005 and by the grant MSM 0021620839.     

The Cost of the Missing Bit: Communication Complexity with Help

Dedicated to the Memory of Paul Erdős We generalize the multiparty communication model of Chandra, Furst, and Lipton (1983) to functions with b-bit output (b = 1 in the CFL model). We allow the players to receive up to b - 1 bits of information from an all-powerful benevolent Helper who can see all the input. Extending results of Babai, Nisan, and Szegedy (1992) to this model, we construct families of explicit functions for which bits of communication are required to find the "missing bit", where n is the length of each player's input and k is the number of players. As a consequence we settle the problem of separating the one-way vs. multiround communication complexities (in the CFL sense) for players, extending a result of Nisan and Wigderson (1991) who demonstrated this separation for k = 3 players. As a by-product we obtain lower bounds for the multiparty complexity (in the CFL sense) of new families of explicit boolean functions (not derivable from BNS). The proofs exploit the interplay between two concepts of multicolor discrepancy; discrete Fourier analysis is the basic tool. We also include an unpublished lower bound by A. Wigderson regarding the one-way complexity of the 3-party pointer jumping function. Received November 12, 1998 RID="*" ID="*" Supported in part by NSA grant MSPR-96G-184. RID="†" ID="†" Supported in part by an NSF Graduate Fellowship.     

Fixed point and Bregman iterative methods for matrix rank minimization

The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The tightest convex relaxation of this problem is the linearly constrained nuclear norm minimization. Although the latter can be cast as a semidefinite programming problem, such an approach is computationally expensive to solve when the matrices are large. In this paper, we propose fixed point and Bregman iterative algorithms for solving the nuclear norm minimization problem and prove convergence of the first of these algorithms. By using a homotopy approach together with an approximate singular value decomposition procedure, we get a very fast, robust and powerful algorithm, which we call FPCA (Fixed Point Continuation with Approximate SVD), that can solve very large matrix rank minimization problems (the code can be downloaded from http://www.columbia.edu/~sm2756/FPCA.htm for non-commercial use). Our numerical results on randomly generated and real matrix completion problems demonstrate that this algorithm is much faster and provides much better recoverability than semidefinite programming solvers such as SDPT3. For example, our algorithm can recover 1000 × 1000 matrices of rank 50 with a relative error of 10^?5 in about 3?min by sampling only 20% of the elements. We know of no other method that achieves as good recoverability. Numerical experiments on online recommendation, DNA microarray data set and image inpainting problems demonstrate the effectiveness of our algorithms.     

Singular, nonsingular, and bounded rank completions of ACI-matrices

An affine column independent matrix is a matrix whose entries are polynomials of degree at most 1 in a number of indeterminates where no indeterminate appears with a nonzero coefficient in two different columns. A completion is a matrix obtained by giving values to each of the indeterminates. Affine column independent matrices are more general than partial matrices where each entry is either a constant or a distinct indeterminate. We determine when the rank of all completions of an affine column independent matrix is bounded by a given number, generalizing known results for partial matrices. We also characterize the square partial matrices over a field all of whose completions are nonsingular. The maximum number of free entries in such matrices of a given order is determined as well as the partial matrices with this maximum number of free entries.     

On Copositive Programming and Standard Quadratic Optimization Problems

A standard quadratic problem consists of finding global maximizers of a quadratic form over the standard simplex. In this paper, the usual semidefinite programming relaxation is strengthened by replacing the cone of positive semidefinite matrices by the cone of completely positive matrices (the positive semidefinite matrices which allow a factorization FF ^T where F is some non-negative matrix). The dual of this cone is the cone of copositive matrices (i.e., those matrices which yield a non-negative quadratic form on the positive orthant). This conic formulation allows us to employ primal-dual affine-scaling directions. Furthermore, these approaches are combined with an evolutionary dynamics algorithm which generates primal-feasible paths along which the objective is monotonically improved until a local solution is reached. In particular, the primal-dual affine scaling directions are used to escape from local maxima encountered during the evolutionary dynamics phase.     

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     

Robust Mean-Squared Error Estimation of Multiple Signals in Linear Systems Affected by Model and Noise Uncertainties

This paper is a continuation of the work in [11] and [2] on the problem of estimating by a linear estimator, N unobservable input vectors, undergoing the same linear transformation, from noise-corrupted observable output vectors. Whereas in the aforementioned papers, only the matrix representing the linear transformation was assumed uncertain, here we are concerned with the case in which the second order statistics of the noise vectors (i.e., their covariance matrices) are also subjected to uncertainty. We seek a robust mean-squared error estimator immuned against both sources of uncertainty. We show that the optimal robust mean-squared error estimator has a special form represented by an elementary block circulant matrix, and moreover when the uncertainty sets are ellipsoidal-like, the problem of finding the optimal estimator matrix can be reduced to solving an explicit semidefinite programming problem, whose size is independent of N. The research was partially supported by BSF grant #2002038