Semi-definite Programming

Analytic Formulas for Alternating Projection Sequences for the Positive Semidefinite Cone and an Application to Convergence Analysis

  • Hiroyuki Ochiai
  • Yoshiyuki Sekiguchi
  • Hayato Waki
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

    \(\) We derive analytic formulas for the alternating projection method applied to the cone \(S^n_+\) of positive semidefinite matrices and an affine subspace. More precisely, we find recursive relations on parameters representing a sequence constructed by the alternating projection method. By applying these formulas, we analyze the alternating projection method in detail and show that … Read more

    Application of the Lovász-Schrijver Operator to Compact Stable Set Integer Programs

  • Federico Battista
  • Fabrizio Rossi
  • Stefano Smriglio
    • Categories 0-1 Programming, Combinatorial Optimization, Semi-definite Programming Tags , ,

    \(\)The Lov\’asz theta function $\theta(G)$ provides a very good upper bound on the stability number of a graph $G$. It can be computed in polynomial time by solving a semidefinite program (SDP), which also turns out to be fairly tractable in practice. Consequently, $\theta(G)$ achieves a hard-to-beat trade-off between computational effort and strength of the … Read more

    On the strength of Burer’s lifted convex relaxation to quadratic programming with ball constraints

  • Fatma Kılınç-Karzan
  • Shengding Sun
    • Categories Convex Optimization, Quadratic Programming, Semi-definite Programming

    We study quadratic programs with m ball constraints, and the strength of a lifted convex relaxation for it recently proposed by Burer (2024). Burer shows this relaxation is exact when m=2. For general m, Burer (2024) provides numerical evidence that this lifted relaxation is tighter than the Kronecker product based Reformulation Linearization Technique (RLT) inequalities … Read more

    A combinatorial approach to Ramana’s exact dual for semidefinite programming

  • Gabor Pataki
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    Thirty years ago, in a seminal paper Ramana derived an exact dual for Semidefinite Programming (SDP). Ramana’s dual has the following remarkable features: i) it assumes feasibility of the primal, but it does not make any regularity assumptions, such as strict feasibility ii) its optimal value is the same as the optimal value of the … Read more

    Granularity for mixed-integer polynomial optimization problems

  • Carl Eggen
  • Oliver Stein
  • Stefan Volkwein
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , , ,

    Finding good feasible points is crucial in mixed-integer programming. For this purpose we combine a sufficient condition for consistency, called granularity, with the moment-/sos-hierarchy from polynomial optimization. If the mixed-integer problem is granular, we obtain feasible points by solving continuous polynomial problems and rounding their optimal points. The moment-/sos-hierarchy is hereby used to solve those … Read more

    A Facial Reduction Algorithm for Standard Spectrahedra

  • Haesol Im
    • Categories Convex Optimization, Semi-definite Programming

    Facial reduction is a pre-processing method aimed at reformulating a problem to ensure strict feasibility. The importance of constructing a robust model is widely recognized in the literature, and facial reduction has emerged an attractive approach for achieving robustness. In this note, we outline a facial reduction algorithm for a standard spectrahedra, the intersection of … Read more

    A Subgradient Projection Method with Outer Approximation for Solving Semidefinite Programming Problems

  • Nagisa Sugishita
  • Miguel F. Anjos
    • Categories Convex Optimization, Semi-definite Programming Tags , ,

    We explore the combination of subgradient projection with outer approximation to solve semidefinite programming problems. We compare several ways to construct outer approximations using the problem structure. The resulting approach enjoys the strengths of both subgradient projection and outer approximation methods. Preliminary computational results on the semidefinite programming relaxations of graph partitioning and max-cut show … Read more

    Robust System Identification: Finite-sample Guarantees and Connection to Regularization

  • Hyuk Park
    • Categories Control Applications, Robust Optimization, Semi-definite Programming Tags , ,

    We address the problem of identifying a stable linear time-invariant system from a single sample trajectory. The least squares estimate (LSE) is a commonly used algorithm for this purpose. However, LSE may exhibit poor identification errors when the number of samples is small. To mitigate the issue, we introduce the robust LSE, which integrates robust … Read more

    Tighter yet more tractable relaxations and nontrivial instance generation for sparse standard quadratic optimization

  • Immanuel M. Bomze
  • Bo Peng
  • Yuzhou Qiu
  • E. Alper Yildirim
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Semi-definite Programming Tags , , , ,

    The Standard Quadratic optimization Problem (StQP), arguably the simplest among all classes of NP-hard optimization problems, consists of extremizing a quadratic form (the simplest nonlinear polynomial) over the standard simplex (the simplest polytope/compact feasible set). As a problem class, StQPs may be nonconvex with an exponential number of inefficient local solutions. StQPs arise in a … Read more

    Exploiting Sign Symmetries in Minimizing Sums of Rational Functions

  • Jie Wang
  • Feng Guo
    • Categories Constrained Nonlinear Optimization, Global Optimization Applications, Semi-definite Programming Tags , , , ,

    This paper is devoted to the problem of minimizing a sum of rational functions over a basic semialgebraic set. We provide a hierarchy of sum of squares (SOS) relaxations that is dual to the generalized moment problem approach due to Bugarin, Henrion, and Lasserre. The investigation of the dual SOS aspect offers two benefits: 1) … Read more