In this paper, we study polynomial-time interior-point algorithms in view of information geometry. We introduce an information geometric structure for a conic linear program based on a self-concordant barrier function. Riemannian metric is defined with the Hessian of the barrier function. We introduce two connections $\nabla$ and $\nabla^*$ which roughly corresponds to the primal and … Read more
In this paper, we analyze two popular semidefinite programming \SDPb relaxations for quadratically constrained quadratic programs \QCQPb with matrix variables. These are based on \emph{vector-lifting} and on \emph{matrix lifting} and are of different size and expense. We prove, under mild assumptions, that these two relaxations provide equivalent bounds. Thus, our results provide a theoretical guideline … Read more
The following question arises in stochastic programming: how can one approximate a noisy convex function with a convex quadratic function that is optimal in some sense. Using several approaches for constructing convex approximations we present some optimization models yielding convex quadratic regressions that are optimal approximations in $L_1$, $L_\infty$ and $L_2$ norm. Extensive numerical experiments … Read more
The main topic addressed in this paper is trace-optimization of polynomials in noncommuting (nc) variables: given an nc polynomial f, what is the smallest trace f(A) can attain for a tuple of matrices A? A relaxation using semidefinite programming (SDP) based on sums of hermitian squares and commutators is proposed. While this relaxation is not … Read more
We consider the problem of minimizing a polynomial on the hypercube [0,1]^n and derive new error bounds for the hierarchy of semidefinite programming approximations to this problem corresponding to the Positivstellensatz of Schmuedgen (1991). The main tool we employ is Bernstein approximations of polynomials, which also gives constructive proofs and degree bounds for positivity certificates … Read more
The cone of Completely Positive (CP) matrices can be used to exactly formulate a variety of NP-Hard optimization problems. A tractable relaxation for CP matrices is provided by the cone of Doubly Nonnegative (DNN) matrices; that is, matrices that are both positive semidefinite and componentwise nonnegative. A natural problem in the optimization setting is then … Read more
Given linear matrix inequalities (LMIs) L_1 and L_2, it is natural to ask: (Q1) when does one dominate the other, that is, does L_1(X) PsD imply L_2(X) PsD? (Q2) when do they have the same solution set? Such questions can be NP-hard. This paper describes a natural relaxation of an LMI, based on substituting matrices … Read more
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 … Read more
The SDPA (SemiDefinite Programming Algorithm) Project launched in 1995 has been known to provide high-performance packages for solving large-scale Semidefinite Programs (SDPs). SDPA Ver. 6 solves efficiently large-scale dense SDPs, however, it required much computation time compared with other software packages, especially when the Schur complement matrix is sparse. SDPA Ver. 7 is now completely … Read more
We consider the positive semidefinite (psd) matrices with binary entries, along with the corresponding integer polytopes. We begin by establishing some basic properties of these matrices and polytopes. Then, we show that several families of integer polytopes in the literature — the cut, boolean quadric, multicut and clique partitioning polytopes — are faces of binary … Read more