Linear, Cone and Semidefinite Programming

Quadratic convergence to the optimal solution of second-order conic optimization without strict complementarity

  • Ali Mohammad-Nezhad
  • Tamás Terlaky
    • Categories Second-Order Cone Programming

    Under primal and dual nondegeneracy conditions, we establish the quadratic convergence of Newton’s method to the unique optimal solution of second-order conic optimization. Only very few approaches have been proposed to remedy the failure of strict complementarity, mostly based on nonsmooth analysis of the optimality conditions. Our local convergence result depends on the optimal partition … Read more

    Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs

  • Gabor Pataki
  • Quoc Tran-Dinh
  • Yuzixuan (Melody) Zhu
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Semi-definite Programming

    We introduce Sieve-SDP, a simple algorithm to preprocess semidefinite programs (SDPs). Sieve-SDP belongs to the class of facial reduction algorithms. It inspects the constraints of the problem, deletes redundant rows and columns, and reduces the size of the variable matrix. It often detects infeasibility. It does not rely on any optimization solver: the only subroutine … Read more

    Complete Facial Reduction in One Step for Spectrahedra

  • Stefan Sremac
  • Henry Wolkowicz
  • Hugo J. Woerdeman
    • Categories Convex Optimization, Semi-definite Programming Tags , , ,

    A spectrahedron is the feasible set of a semidefinite program, SDP, i.e., the intersection of an affine set with the positive semidefinite cone. While strict feasibility is a generic property for random problems, there are many classes of problems where strict feasibility fails and this means that strong duality can fail as well. If the … Read more

    Convexification of Queueing Formulas by Mixed-Integer Second-Order Cone Programming: An Application to a Discrete Location Problem with Congestion

  • Ahmadi-Javid Amir
  • Pooya Hoseinpour
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Second-Order Cone Programming

    Mixed-Integer Second-Order Cone Programs (MISOCPs) form a nice class of mixed-inter convex programs, which can be solved very efficiently due to the recent advances in optimization solvers. Our paper bridges the gap between modeling a class of optimization problems and using MISOCP solvers. It is shown how various performance metrics of M/G/1 queues can be … Read more

    Using a Factored Dual in Augmented Lagrangian Methods for Semidefinite Programming

  • Marianna De Santis
  • Franz Rendl
  • Angelika Wiegele
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    In the context of augmented Lagrangian approaches for solving semidefinite programming problems, we investigate the possibility of eliminating the positive semidefinite constraint on the dual matrix by employing a factorization. Hints on how to deal with the resulting unconstrained maximization of the augmented Lagrangian are given. We further propose to use the approximate maximum of … Read more

    Response to “Counterexample to global convergence of DSOS and SDSOS hierarchies”

  • Amir Ali Ahmadi
  • Anirudha Majumdar
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming

    In a recent note [8], the author provides a counterexample to the global convergence of what his work refers to as “the DSOS and SDSOS hierarchies” for polynomial optimization problems (POPs) and purports that this refutes claims in our extended abstract [4] and slides in [3]. The goal of this paper is to clarify that … Read more

    On the Construction of Converging Hierarchies for Polynomial Optimization Based on Certificates of Global Positivity

  • Amir Ali Ahmadi
  • Georgina Hall
    • Categories Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    In recent years, techniques based on convex optimization and real algebra that produce converging hierarchies of lower bounds for polynomial minimization problems have gained much popularity. At their heart, these hierarchies rely crucially on Positivstellens\”atze from the late 20th century (e.g., due to Stengle, Putinar, or Schm\”udgen) that certify positivity of a polynomial on an … Read more

    Improving Efficiency and Scalability of Sum of Squares Optimization: Recent Advances and Limitations

  • Amir Ali Ahmadi
  • Antonis Papachristodoulou
  • Georgina Hall
  • James Saunderson
  • Yang Zheng
    • Categories Convex Optimization, Semi-definite Programming Tags ,

    It is well-known that any sum of squares (SOS) program can be cast as a semidefinite program (SDP) of a particular structure and that therein lies the computational bottleneck for SOS programs, as the SDPs generated by this procedure are large and costly to solve when the polynomials involved in the SOS programs have a … Read more

    Minimizer extraction in polynomial optimization is robust

  • Igor Klep
  • Janez Povh
  • Jurij Volčič
    • Categories Semi-definite Programming Tags , , , , , , , ,

    In this article we present a robustness analysis of the extraction of optimizers in polynomial optimization. Optimizers can be extracted by solving moment problems using flatness and the Gelfand-Naimark-Segal (GNS) construction. Here a modification of the GNS construction is presented that applies even to non-flat data, and then its sensitivity under perturbations is studied. The … Read more

    Tightness of a new and enhanced semidefinite relaxation for MIMO detection

  • Ya-Feng Liu
  • Cheng Lu
  • Wei-Qiang Zhang
  • Shuzhong Zhang
    • Categories Global Optimization Applications, Semi-definite Programming, Telecommunications Tags , , ,

    In this paper, we consider a fundamental problem in modern digital communications known as multi-input multi-output (MIMO) detection, which can be formulated as a complex quadratic programming problem subject to unit-modulus and discrete argument constraints. Various semidefinite relaxation (SDR) based algorithms have been proposed to solve the problem in the literature. In this paper, we … Read more