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
A novel global optimization method based on an Augmented Lagrangian framework is introduced for continuous constrained nonlinear optimization problems. At each outer iteration the method requires the $\varepsilon$-global minimization of the Augmented Lagrangian with simple constraints. Global convergence to an $\varepsilon$-global minimizer of the original problem is proved. The subproblems are solved using the $\alpha$BB … 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
Given a weighted undirected graph $G=(V,E)$, a tree (respectively tour) cover of an edge-weighted graph is a set of edges which forms a tree (resp. closed walk) and covers every other edge in the graph. The tree (resp. tour) cover problem is of finding a minimum weight tree (resp. tour) cover of $G$. Arkin, Halld\’orsson … Read more
We present a method to approximate the solution mapping of parametric constrained optimization problems. The approximation, which is of the spectral stochastic finite element type, is represented as a linear combination of orthogonal polynomials. Its coefficients are determined by solving an appropriate finite-dimensional constrained optimization problem. We show that, under certain conditions, the latter problem … Read more
Three primal-dual interior-point algorithms for homogeneous cone programming are presented. They are a short-step algorithm, a large-update algorithm, and a predictor-corrector algorithm. These algorithms are described and analyzed based on a characterization of homogeneous cone via T-algebra. The analysis show that the algorithms have polynomial iteration complexity. CitationDivision of Mathematical Sciences, Nanyang Technological University, December … Read more