This article describes a generalization of the PBM method by Ben-Tal and Zibulevsky to convex semidefinite programming problems. The algorithm used is a generalized version of the Augmented Lagrangian method. We present details of this algorithm as implemented in a new code PENNON. The code can also solve second-order conic programming (SOCP) problems, as well … Read more
We study approximation bounds for the SDP relaxation of quadratically constrained quadratic optimization: min f^0(x) subject to f^k(x)
Primal-dual interior-point methods (IPMs) have shown their power in solving large classes of optimization problems. However, at present there is still a gap between the practical behavior of these algorithms and their theoretical worst-case complexity results, with respect to the strategies of updating the duality gap parameter in the algorithm. The so-called small-update IPMs enjoy … Read more
We consider the global minimization of a multivariate polynomial on a semi-algebraic set \Omega defined with polynomial inequalities. We then compare two hierarchies of relaxations, namely, LP-relaxations based on products of the original constraints, in the spirit of the RLT procedure of Sherali and Adams and recent SDP (semi definite programming) relaxations introduced by the … Read more
We consider the general nonlinear optimization problem in 0-1 variables and provide an explicit equivalent positive semidefinite program in $2^n-1$ variables. The optimal values of both problems are identical. From every optimal solution of the former one easily find an optimal solution of the latter and conversely, from every solution of the latter one may … Read more
A user-friendly free Matlab package for defining Linear Matrix Inequality (LMI) problems. It acts as an interface for the Self-Dual-Minimisation package SeDuMi developed by Jos F. Sturm. The functionalities of SeDuMi Interface are the following: (1) Declare an LMI problem. Five Matlab functions allow to define completely an LMI problem which can be characterised by … Read more
A form p on R^n (homogeneous n-variate polynomial) is called positive semidefinite (psd) if it is nonnegative on R^n. In other words, the zero vector is a global minimizer of p in this case. The famous 17th conjecture of Hilbert (later proven by Artin) is that a form p is psd if and only if … Read more
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. Citation Optimization Methods and … Read more
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
We study convex conic optimization problems in which the right-hand side and the cost vectors vary linearly as a function of a scalar parameter. We present a unifying geometric framework that subsumes the concept of the optimal partition in linear programming (LP) and semidefinite programming (SDP) and extends it to conic optimization. Similar to the … Read more