Linear, Cone and Semidefinite Programming

Computational Enhancements in Low-Rank Semidefinite Programming

  • Samuel Burer
  • Changhui Choi
    • Categories Semi-definite Programming

    We discuss computational enhancements for the low-rank semidefinite programming algorithm, including the extension to block semidefinite programs, an exact linesearch procedure, and a dynamic rank reduction scheme. A truncated Newton method is also introduced, and several preconditioning strategies are proposed. Numerical experiments illustrating these enhancements are provided. Citation Manuscript, Department of Mangagement Sciences, University of … Read more

    A direct formulation for sparse PCA using semidefinite programming

  • Alexandre d'Aspremont
  • Laurent El Ghaoui
  • Michael I. Jordan
  • G. R. G. Lanckriet
    • Categories Finance and Economics, Semi-definite Programming, Statistics Tags , ,

    We examine the problem of approximating, in the Frobenius-norm sense, a positive, semidefinite symmetric matrix by a rank-one matrix, with an upper bound on the cardinality of its eigenvector. The problem arises in the decomposition of a covariance matrix into sparse factors, and has wide applications ranging from biology to finance. We use a modification … Read more

    Invariance and efficiency of convex representations

  • Chek Beng Chua
  • Levent Tunçel
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , , ,

    We consider two notions for the representations of convex cones: $G$-representation and lifted-$G$-representation. The former represents a convex cone as a slice of another; the latter allows in addition, the usage of auxiliary variables in the representation. We first study the basic properties of these representations. We show that some basic properties of convex cones … Read more

    Solving Lift-and-Project Relaxations of Binary Integer Programs

  • Samuel Burer
  • Dieter Vandenbussche
    • Categories 0-1 Programming, Linear, Cone and Semidefinite Programming Tags , , , ,

    We propose a method for optimizing the lift-and-project relaxations of binary integer programs introduced by Lov\’asz and Schrijver. In particular, we study both linear and semidefinite relaxations. The key idea is a restructuring of the relaxations, which isolates the complicating constraints and allows for a Lagrangian approach. We detail an enhanced subgradient method and discuss … Read more

    Primal-Dual Interior-Point Algorithms for Semidefinite Optimization Based on a Simple Kernel Function

  • Y.Q. Bai
  • Cornelis Roos
  • G. Q. Wang
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    Interior-point methods (IPMs) for semidefinite optimization (SDO) have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, J.Peng et al. introduced so-called self-regular kernel (and barrier) functions and designed primal-dual interior-point algorithms based on self-regular proximity for linear optimization (LO) problems. They have also extended the approach for LO to SDO. In … Read more

    Universal Duality in Conic Convex Optimization

  • Dianne P. O'Leary
  • Simon P. Schurr
  • AndrĂ© L. Tits
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    Given a primal-dual pair of linear programs, it is well known that if their optimal values are viewed as lying on the extended real line, then the duality gap is zero, unless both problems are infeasible, in which case the optimal values are +infinity and -infinity. In contrast, for optimization problems over nonpolyhedral convex cones, … Read more

    Pointillism via Linear Programming

  • Robert Bosch
  • Adrianne Herman
    • Categories Airline Optimization, Applications - Science and Engineering, Linear Programming Tags ,

    Pointillism is a painting technique in which the painter places dots of paint on the canvas in such a way that they blend together into desired forms when viewed from a distance. In this brief note, we describe how to use linear programming to construct a pointillist portrait. Citation Dept. of Mathematics, Oberlin College, Oberlin, … Read more

    A semidefinite programming based polyhedral cut and price algorithm for the maxcut problem

  • Kartik Krishnan
  • John E. Mitchell
    • Categories Branch and Cut Algorithms, Semi-definite Programming Tags , , ,

    We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linear programming problem, which is solved within an interior point cutting plane algorithm in a dual setting; this constitutes the pricing (column generation) phase of the … Read more

    Implementation of Infinite Dimensional Interior Point Method for Solving Multi-criteria Linear-Quadratic Control Problem

  • Leonid Faybusovich
  • Takashi Tsuchiya
  • Thanasak Mouktonglang
    • Categories Control Applications, Infinite Dimensional Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    We describe an implementation of an infinite-dimensional primal-dual algorithm based on the Nesterov-Todd direction. Several applications to both continuous and discrete-time multi-criteria linear-quadratic control problems and linear-quadratic control problem with quadratic constraints are described. Numerical results show a very fast convergence (typically, within 3-4 iterations) to optimal solutions Citation Preprint, May, 2004, University of Notre … Read more

    Sensitivity analysis for linear optimization problem with fuzzy data in the objective function

  • Stephan Dempe
  • Tatiana Starostina
    • Categories Linear Programming, Robust Optimization Tags , ,

    Linear programming problems with fuzzy coefficients in the objective function are considered. Emphasis is on the dependence of the optimal solution from linear perturbations of the membership functions of the objective function coefficients as well as on the computation of a robust solution of the fuzzy linear problem if the membership functions are not surely … Read more