Linear, Cone and Semidefinite Programming

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

    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

    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

    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

    Robust Sensitivity Analysis for Linear Programming with Ellipsoidal Perturbation

  • Ruotian Gao
  • Wenxun Xing
    • Categories Applications - OR and Management Sciences, Linear Programming, Robust Optimization Tags , , ,

    Given an originally robust optimal decision and allowing perturbation parameters of the linear programming problem to run through a maximum uncertainty set controlled by a variable of perturbation radius, we do robust sensitivity analysis for the robust linear programming problem in two scenarios. One is to keep the original decision still robust optimal, the other … Read more

    Maintaining a Basis Matrix in the Linear Programming Interior Point Method

  • Jacek Gondzio
  • Lukas Schork
    • Categories Linear Programming Tags , , , ,

    To precondition the normal equation system from the linear programming (LP) interior point method, basis preconditioners choose a basis matrix dependent on column scaling factors. Two criteria for choosing the basis matrix are compared which yield a maximum volume or maximum weight basis. Finding a maximum volume basis requires a combinatorial effort, but it gives … Read more

    Worst-case convergence analysis of gradient and Newton methods through semidefinite programming performance estimation

  • Etienne de Klerk
  • François Glineur
  • Adrien B. Taylor
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    We provide new tools for worst-case performance analysis of the gradient (or steepest descent) method of Cauchy for smooth strongly convex functions, and Newton’s method for self-concordant functions. The analysis uses semidefinite programming performance estimation, as pioneered by Drori en Teboulle [Mathematical Programming, 145(1-2):451–482, 2014], and extends recent performance estimation results for the method of … Read more