Linear, Cone and Semidefinite Programming

A Polynomial Time Constraint-Reduced Algorithm for Semidefinite Optimization Problems, with Convergence Proofs

  • Dianne P. O'Leary
  • Sungwoo Park
    • Categories Semi-definite Programming Tags , , , , , , , , ,

    We present an infeasible primal-dual interior point method for semidefinite optimization problems, making use of constraint reduction. We show that the algorithm is globally convergent and has polynomial complexity, the first such complexity result for primal-dual constraint reduction algorithms for any class of problems. Our algorithm is a modification of one with no constraint reduction … Read more

    A Semidefinite Hierarchy for Containment of Spectrahedra

  • Kai Kellner
  • Thorsten Theobald
  • Christian Trabandt
    • Categories Semi-definite Programming Tags , , , , ,

    A spectrahedron is the positivity region of a linear matrix pencil, thus defining the feasible set of a semidefinite program. We propose and study a hierarchy of sufficient semidefinite conditions to certify the containment of a spectrahedron in another one. This approach comes from applying a moment relaxation to a suitable polynomial optimization formulation. The … Read more

    Approximate cone factorizations and lifts of polytopes

  • João Gouveia
  • Pablo A. Parrilo
  • Rekha R. Thomas
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper we show how to construct inner and outer convex approximations of a polytope from an approximate cone factorization of its slack matrix. This provides a robust generalization of the famous result of Yannakakis that polyhedral lifts of a polytope are controlled by (exact) nonnegative factorizations of its slack matrix. Our approximations behave … Read more

    A new semidenite programming relaxation for the quadratic assignment problem and its computational perspectives

  • Etienne de Klerk
  • Renata Sotirov
  • Uwe Truetsch
    • Categories Linear, Cone and Semidefinite Programming Tags ,

    Recent progress in solving quadratic assignment problems (QAPs) from the QAPLIB test set has come from mixed integer linear or quadratic programming models that are solved in a branch-and-bound framework. Semidenite programming bounds for QAP have also been studied in some detail, but their computational impact has been limited so far, mostly due to the … Read more

    Rational sums of hermitian squares of free noncommutative polynomials

  • Kristijan Cafuta
  • Igor Klep
  • Janez Povh
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , , , , , , , ,

    In this paper we consider polynomials in noncommuting variables that admit sum of hermitian squares and commutators decompositions. We recall algorithms for finding decompositions of this type that are based on semidefinite programming. The main part of the article investigates how to find such decomposition with rational coefficients if the original polynomial has rational coefficients. … Read more

    Analysis of Copositive Optimization Based Linear Programming Bounds on Standard Quadratic Optimization

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

    The problem of minimizing a quadratic form over the unit simplex, referred to as a standard quadratic optimization problem, admits an exact reformulation as a linear optimization problem over the convex cone of completely positive matrices. This computationally intractable cone can be approximated from the inside and from the outside by two sequences of nested … Read more

    RSP-Based Analysis for Sparsest and Least $\ell_1hBcNorm Solutions to Underdetermined Linear Systems

  • Yun-Bin Zhao
    • Categories Global Optimization, Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Recently, the worse-case analysis, probabilistic analysis and empirical justification have been employed to address the fundamental question: When does $\ell_1$-minimization find the sparsest solution to an underdetermined linear system? In this paper, a deterministic analysis, rooted in the classic linear programming theory, is carried out to further address this question. We first identify a necessary … Read more

    Polynomial solvability of variants of the trust-region subproblem

  • Daniel Bienstock
  • Alexander Michalka
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , ,

    The trust region subproblem concerns the minimization of a general quadratic over the unit ball in R^n. Extensions to this problem are of interest because of applications to, for example, combinatorial optimization. However the extension obtained by adding an arbitrary family of linear side constraints is NP-hard. In this paper we consider variants of the … Read more

    Optimization of Demand Response Through Peak Shaving

  • D. Craigie
  • Michael J. Todd
  • Andrew B. Philpott
  • Golbon Zakeri
    • Categories Applications - OR and Management Sciences, Linear Programming Tags , ,

    We consider a model in which a consumer of a resource over several periods must pay a per unit charge for the resource as well as a peak charge. The consumer has the ability to reduce his consumption in any period at some given cost, subject to a constraint on the total amount of reduction … Read more

    A polynomial projection algorithm for linear programming

  • Sergei Chubanov
    • Categories Linear Programming

    We propose a polynomial algorithm for linear programming. The algorithm represents a linear optimization or decision problem in the form of a system of linear equations and non-negativity constraints. Then it uses a procedure that either fi nds a solution for the respective homogeneous system or provides the information based on which the algorithm rescales the … Read more