In an important paper, Burer recently showed how to reformulate general mixed-binary quadratic optimization problems (QPs) into copositive programs where a linear functional is minimized over a linearly constrained subset of the cone of completely positive matrices. In this note we interpret the implication from a topological point of view, showing that the Minkowski sum … Read more
In this paper, we consider a primal-dual interior point method for solving nonlinear semidefinite programming problems. We propose primal-dual interior point methods based on the unscaled and scaled Newton methods, which correspond to the AHO, HRVW/KSH/M and NT search directions in linear SDP problems. We analyze local behavior of our proposed methods and show their … Read more
In this paper, we analyze mixed 0-1 linear programs under objective uncertainty. The mean vector and the second moment matrix of the nonnegative objective coefficients is assumed to be known, but the exact form of the distribution is unknown. Our main result shows that computing a tight upper bound on the expected value of a … Read more
We consider the complexity of gap-free duals in semidefinite programming. Using the theory of homogeneous cones we provide a new representation of Ramana’s gap-free dual and show that the new formulation has a much better complexity than originally proved by Ramana. Citation COR@L Technical Report, Lehigh University Article Download View On the computational complexity of … Read more
In this paper, we consider the sparse inverse covariance selection problem which is equivalent to structure recovery of a Markov Network over Gaussian variables. We introduce a simple but efficient greedy algorithm, called {\em SINCO}, for solving the Sparse INverse COvariance problem. Our approach is based on coordinate ascent method which naturally preserves the sparsity … Read more
SFSDP is a Matlab package for solving a sensor network localization problem. These types of problems arise in monitoring and controlling applications using wireless sensor networks. SFSDP implements the semidefinite programming (SDP) relaxation proposed in Kim et al. [2009] for sensor network localization problems, as a sparse version of the full semidefinite programming relaxation (FSDP) … Read more
To obtain a primal-dual pair of conic programming problems having zero duality gap, two methods have been proposed: the facial reduction algorithm due to Borwein and Wolkowicz [1,2] and the conic expansion method due to Luo, Sturm, and Zhang [5]. We establish a clear relationship between them. Our results show that although the two methods … Read more
The theta bodies of a polynomial ideal are a series of semidefinite programming relaxations of the convex hull of the real variety of the ideal. In this paper we construct the theta bodies of the vanishing ideal of cycles in a binary matroid. Applied to cuts in graphs, this yields a new hierarchy of semidefinite … Read more
An algorithm for finding sums of hermitian squares decompositions for polynomials in noncommuting variables is presented. The algorithm is based on the “Newton chip method”, a noncommutative analog of the classical Newton polytope method, and semide finite programming. Citation I. Klep and J. Povh. Semide nite programming and sums of hermitian squares of noncommutative polynomials. J. Pure … Read more
We consider linear optimization problems over the cone of copositive matrices. Such conic optimization problems, called {\em copositive programs}, arise from the reformulation of a wide variety of difficult optimization problems. We propose a hierarchy of increasingly better outer polyhedral approximations to the copositive cone. We establish that the sequence of approximations is exact in … Read more