In this paper we study various approaches for exploiting symmetries in polynomial optimization problems within the framework of semi definite programming relaxations. Our special focus is on constrained problems especially when the symmetric group is acting on the variables. In particular, we investigate the concept of block decomposition within the framework of constrained polynomial optimization … Read more
Exploiting sparsity has been a key issue in solving large-scale optimization problems. The most time-consuming part of primal-dual interior-point methods for linear programs, second-order cone programs, and semidefinite programs is solving the Schur complement equation at each iteration, usually by the Cholesky factorization. The computational efficiency is greatly affected by the sparsity of the coefficient … Read more
We describe a method of generating a warm-start point for interior point methods in the context of stochastic programming. Our approach exploits the structural information of the stochastic problem so that it can be seen as a structure-exploiting initial point generator. We solve a small-scale version of the problem corresponding to a reduced event tree … Read more
We revisit a regularization technique of Meszaros for handling free variables within interior-point methods for conic linear optimization. We propose a simple computational strategy, supported by a global convergence analysis, for handling the regularization. Using test problems from benchmark suites and recent applications, we demonstrate that the modern code SDPT3 modified to incorporate the proposed … Read more
We consider a family of linear optimization problems over the n-dimensional Klee-Minty cube and show that the central path may visit all of its vertices in the same order as simplex methods do. This is achieved by carefully adding an exponential number of redundant constraints that forces the central path to take at least 2^n-2 … Read more
Recently A. Schrijver derived new upper bounds for binary codes using semidefinite programming. In this paper we adapt this approach to codes on the unit sphere and we compute new upper bounds for the kissing number in several dimensions. In particular our computations give the (known) values for the cases n = 3, 4, 8, … Read more
Adding cuts based on copositive matrices, we propose to improve Lovász’ bound on the clique number and its tightening introduced by McEliece, Rodemich, Rumsey, and Schrijver. Candidates for cheap and efficient copositivity cuts of this type are obtained from graphs with known clique number. The cost of previously established semidefinite programming bound hierarchies rapidly increases … Read more
We introduce a continuous analogue of the Hirsch conjecture and a discrete analogue of the result of Dedieu, Malajovich and Shub. We prove a continuous analogue of the result of Holt and Klee, namely, we construct a family of polytopes which attain the conjectured order of the largest total curvature. Citation AdvOL-Report #2006/09 Advanced Optimization … Read more
An SDP relaxation based method is developed to solve the localization problem in sensor networks using incomplete and inaccurate distance information. The problem is set up to find a set of sensor positions such that given distance constraints are satisfied. The nonconvex constraints in the formulation are then relaxed in order to yield a semidefinite … Read more
We analyze the semidefinite programming (SDP) based model and method for the position estimation problem in sensor network localization and other Euclidean distance geometry applications. We use SDP duality and interior–point algorithm theories to prove that the SDP localizes any network or graph that has unique sensor positions to fit given distance measures. Therefore, we … Read more