When is the linear image of a closed convex cone closed? We present very simple, and intuitive necessary conditions, which 1) unify, and generalize seemingly disparate, classical sufficient conditions: polyhedrality of the cone, and “Slater” type conditions; 2) are necessary and sufficient, when the dual cone belongs to a class, that we call nice cones. … Read more
A new initialization or `Phase I’ strategy for feasible interior point methods for linear programming is proposed that computes a point on the primal-dual central path associated with the linear program. Provided there exist primal-dual strictly feasible points — an all-pervasive assumption in interior point method theory that implies the existence of the central path … Read more
It is well known that the robust counterpart introduced by Ben-Tal and Nemirovski [2] increases the numerical complexity of the solution compared to the original problem. Kocvara, Nemirovski and Zowe therefore introduced in [9] an approximation algorithm for the special case of robust material optimization, called cascading. As the title already indicates, we will show … Read more
We provide a sufficient condition on a class of compact basic semialgebraic sets K for their convex hull to have a lifted semidefinite representation (SDr). This lifted SDr is explicitly expressed in terms of the polynomials that define K. Examples are provided. For convex and compact basic semi-algebraic sets K defined by concave polynomials, we … Read more
VSDP is a MATLAB software package for rigorously solving semidefinite programming problems. It expresses these problems in a notation closely related to the form given in textbooks and scientific papers. Functions for computing verified forward error bounds of the true optimal value and verified certificates of feasibility and infeasibility are provided. All rounding errors due … Read more
In this paper, we give a recursive formula for optimal dual barrier functions on homogeneous cones. This is done in a way similar to the primal construction of Guler and Tuncel by means of the dual Siegel cone construction of Rothaus. We use invariance of the primal barrier function with respect to a transitive subgroup … Read more
We study Semidefinite Programming, \SDPc relaxations for Sensor Network Localization, \SNLc with anchors and with noisy distance information. The main point of the paper is to view \SNL as a (nearest) Euclidean Distance Matrix, \EDM, completion problem and to show the advantages for using this latter, well studied model. We first show that the current … Read more
In this paper we give a lower bound for the least distortion embedding of a distance regular graph into Euclidean space. We use the lower bound for finding the least distortion for Hamming graphs, Johnson graphs, and all strongly regular graphs. Our technique involves semidefinite programming and exploiting the algebra structure of the optimization problem … Read more
In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov’s optimal method \cite{Nest83-1,Nest05-1}, Nesterov’s smooth approximation scheme \cite{Nest05-1}, and Nemirovski’s prox-method \cite{Nem05-1}, and propose a variant of Nesterov’s optimal method which has … Read more
We present a two phase interior point decomposition framework for solving semidefinite (SDP) relaxations of sparse maxcut, stable set, and box constrained quadratic programs. In phase 1, we suitably modify the {\em matrix completion} scheme of Fukuda et al. \cite{fukuda_et_al} to preprocess an existing SDP into an equivalent SDP in the block-angular form. In phase … Read more