Linear, Cone and Semidefinite 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

    Sensitivity analysis for linear changes of the constraint matrix of a linear program

  • bmiftari
  • Quentin Louveaux
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming, Robust Optimization

    Understanding the variation of the optimal value with respect to change in the data is an old problem of mathematical optimisation. This paper focuses on the linear problem f(λ) = min ctx such that (A+λD)x ≤ b, where λ is an unknown parameter that varies within an interval and D is a matrix modifying the … 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

    Accessible Theoretical Complexity of the Restarted Primal-Dual Hybrid Gradient Method for Linear Programs with Unique Optima

  • Zikai Xiong
    • Categories Convex Optimization, Linear Programming, Nonsmooth Optimization Tags , , ,

    \(\) The restarted primal-dual hybrid gradient method (rPDHG) has recently emerged as an important tool for solving large-scale linear programs (LPs). For LPs with unique optima, we present an iteration bound of \(\widetilde{O}\left(\kappa\Phi\cdot\ln\left(\frac{\|w^*\|}{\varepsilon}\right)\right)\), where \(\varepsilon\) is the target tolerance, \(\kappa\) is the standard matrix condition number, \(\|w^*\|\) is the norm of the optimal solution, and … Read more

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

  • Charles Namchaisiri
  • Makoto Yamashita
    • Categories Approximation Algorithms, Convex Optimization, Nonsmooth Optimization, 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

    Immunity to Increasing Condition Numbers of Linear Superiorization versus Linear Programming

  • Jan Schröder
  • Yair Censor
  • Philipp Süss
  • Karl-Heinz Küfer
    • Categories Basic Sciences Applications, Constrained Nonlinear Optimization, Linear Programming Tags , , , , , , ,

    Given a family of linear constraints and a linear objective function one can consider whether to apply a Linear Programming (LP) algorithm or use a Linear Superiorization (LinSup) algorithm on this data. In the LP methodology one aims at finding a point that fulfills the constraints and has the minimal value of the objective function … 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