semidefinite programming

USING SEDUMI 1.02, A MATLAB TOOLBOX FOR OPTIMIZATION OVER SYMMETRIC CONES (Updated for Version 1.05)

Categories Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , , ,

SeDuMi 1.05 is an add-on for MATLAB, which lets you solve optimization problems with linear, quadratic and semidefiniteness constraints. It is possible to have complex valued data and variables in SeDuMi. Moreover, large scale optimization problems are solved efficiently, by exploiting sparsity. This paper describes how to work with this toolbox. CitationOptimization Methods and Software … Read more

A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations

Categories Cutting Plane Approaches, Nonsmooth Optimization, Semi-definite Programming Tags , , , , , ,

The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges … Read more

Simple Efficient Solutions for Semidefinite Programming

Categories Combinatorial Optimization, Nonlinear Systems and Least-Squares, Semi-definite Programming Tags , , , , ,

This paper provides a simple approach for solving a semidefinite program, SDP\@. As is common with many other approaches, we apply a primal-dual method that uses the perturbed optimality equations for SDP, $F_\mu(X,y,Z)=0$, where $X,Z$ are $n \times n$ symmetric matrices and $y \in \Re^n$. However, we look at this as an overdetermined system of … Read more

SDPT3 – a MATLAB software package for semidefinite-quadratic-linear programming, version 3.0

Categories Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , ,

This software package is a MATLAB implementation of infeasible path-following algorithms for solving conic programming problems whose constraint cone is a product of semidefinite cones, second-order cones, and/or nonnegative orthants. It employs a predictor-corrector primal-dual path-following method, with either the HKM or the NT search direction. The basic code is written in Matlab, but key … Read more

Semi-infinite linear programming approaches to semidefinite programming problems

Categories Convex and Nonsmooth Optimization, Infinite Dimensional Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

Interior point methods, the traditional methods for the $SDP$, are fairly limited in the sizes of problems they can handle. This paper deals with an $LP$ approach to overcome some of these shortcomings. We begin with a semi-infinite linear programming formulation of the $SDP$ and discuss the issue of its discretization in some detail. We … Read more

An Independent Benchmarking of SDP and SOCP Solvers

Categories Optimization Software and Modeling Systems, Optimization Software Benchmark Tags , , ,

This work reports the results of evaluating all computer codes submitted to the Seventh DIMACS Implementation Challenge on Semidefinite and Related Optimization Problems. The codes were run on a standard platform and on all the benchmark problems provided by the organizers of the challenge. A total of ten codes were tested on fifty problems in … Read more

On the convergence of the central path in semidefinite optimization

Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , ,

The central path in linear optimization always converges to the analytic center of the optimal set. This result was extended to semidefinite programming by Goldfarb and Scheinberg (SIAM J. Optim. 8: 871-886, 1998). In this paper we show that this latter result is not correct in the absence of strict complementarity. We provide a counterexample, … Read more

Geometry of Semidefinite Max-Cut Relaxations via Ranks

Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

Semidefinite programming (SDP) relaxations are proving to be a powerful tool for finding tight bounds for hard discrete optimization problems. This is especially true for one of the easier NP-hard problems, the Max-Cut problem (MC). The well-known SDP relaxation for Max-Cut, here denoted SDP1, can be derived by a first lifting into matrix space and … Read more

An Interior-Point Perspective on Sensitivity Analysis in Semidefinite Programming

Categories Semi-definite Programming Tags , ,

We study the asymptotic behavior of the interior-point bounds arising from the work of Yildirim and Todd on sensitivity analysis in semidefinite programming in comparison with the optimal partition bounds. For perturbations of the right-hand side vector and the cost matrix, we show that the interior-point bounds evaluated on the central path using the Monteiro-Zhang … Read more

A Computational Study of a Gradient-Based Log-Barrier Algorithm for a Class of Large-Scale SDPs

Categories Combinatorial Optimization, Semi-definite Programming, Unconstrained Optimization Tags , , , ,

The authors of this paper recently introduced a transformation \cite{BuMoZh99-1} that converts a class of semidefinite programs (SDPs) into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods to handle efficiently. Based … Read more