Linear, Cone and Semidefinite Programming

Block-iterative algorithms with diagonally scaled oblique projections for the linear feasibility problem

  • Yair Censor
  • Tommy Elfving
    • Categories Convex Optimization, Linear Programming Tags , , , , ,

    We formulate a block-iterative algorithmic scheme for the solution of systems of linear inequalities and/or equations and analyze its convergence. This study provides as special cases proofs of convergence of (i) the recently proposed Component Averaging (CAV) method of Censor, Gordon and Gordon ({\it Parallel Computing}, 27:777–808, 2001), (ii) the recently proposed Block-Iterative CAV (BICAV) … Read more

    A Dynamic Large-Update Primal-Dual Interior-Point Method for Linear Optimization

  • Jiming Peng
  • Tamás Terlaky
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , ,

    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

    Semidefinite programming vs LP relaxations for polynomial programming

  • Jean-Bernard Lasserre
    • Categories Global Optimization Theory, Linear Programming, Semi-definite Programming

    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

    An explicit equivalent positive semidefinite program for nonlinear 0-1 programs

  • Jean-Bernard Lasserre
    • Categories 0-1 Programming, Other Topics, Semi-definite Programming

    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

    User’s Guide for SeDuMi Interface 1.01

  • Didier Henrion
  • Yann Labit
  • Dimitri Peaucelle
    • Categories Control Applications, Semi-definite Programming Tags , , ,

    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

    Products of positive forms, linear matrix inequalities, and Hilbert 17-th problem for ternary forms

  • Etienne de Klerk
  • Dmitrii V. Pasechnik
    • Categories Global Optimization Theory, Semi-definite Programming Tags , ,

    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

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

  • Jos F. Sturm
    • 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

  • Christoph Helmberg
    • 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

    Unifying optimal partition approach to sensitivity analysis in conic optimization

  • E. Alper Yildirim
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    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