Semi-definite Programming

Performance Estimation for Smooth and Strongly Convex Sets

  • Alan Luner
  • Benjamin Grimmer
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

    We extend recent computer-assisted design and analysis techniques for first-order optimization over structured functions–known as performance estimation–to apply to structured sets. We prove “interpolation theorems” for smooth and strongly convex sets with Slater points and bounded diameter, showing a wide range of extremal questions amount to structured mathematical programs. Prior function interpolation theorems are recovered … Read more

    Spanning and Splitting: Integer Semidefinite Programming for the Quadratic Minimum Spanning Tree Problem

  • Frank de Meijer
  • Melanie Siebenhofer
  • Renata Sotirov
  • Angelika Wiegele
    • Categories (Mixed) Integer Nonlinear Programming, Network Optimization, Semi-definite Programming Tags , , , ,

    In the quadratic minimum spanning tree problem (QMSTP) one wants to find the minimizer of a quadratic function over all possible spanning trees of a graph. We give two formulations of the QMSTP as mixed-integer semidefinite programs exploiting the algebraic connectivity of a graph. Based on these formulations, we derive a doubly nonnegative relaxation for … Read more

    Connectivity via convexity: Bounds on the edge expansion in graphs

  • Timotej Hrga
  • Melanie Siebenhofer
  • Angelika Wiegele
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    Convexification techniques have gained increasing interest over the past decades. In this work, we apply a recently developed convexification technique for fractional programs by He, Liu and Tawarmalani (2024) to the problem of determining the edge expansion of a graph. Computing the edge expansion of a graph is a well-known, difficult combinatorial problem that seeks … Read more

    Dual Spectral Projected Gradient Method for Generalized Log-det Semidefinite Programming

  • Charles Namchaisiri
  • Makoto Yamashita
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    Log-det semidefinite programming (SDP) problems are optimization problems that often arise from Gaussian graphic models. A log-det SDP problem with an l1-norm term has been examined in many methods, and the dual spectral projected gradient (DSPG) method by Nakagaki et al.~in 2020 is designed to efficiently solve the dual problem of the log-det SDP by … Read more

    Exact SDP relaxations for a class of quadratic programs with finite and infinite quadratic constraints

  • Naohiko Arima
  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Cone Programming, Semi-definite Programming Tags , , ,

    We investigate exact semidefinite programming (SDP) relaxations for the problem of minimizing a nonconvex quadratic objective function over a feasible region defined by both finitely and infinitely many nonconvex quadratic inequality constraints (semi-infinite QCQPs). Specifically, we present two sufficient conditions on the feasible region under which the QCQP, with any quadratic objective function over the … Read more

    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