On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods
From MaRDI portal
Publication:359624
DOI10.1007/s10107-012-0628-6zbMath1282.90121OpenAlexW1979596467MaRDI QIDQ359624
Frédéric Roupin, Jérôme Malick
Publication date: 12 August 2013
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-012-0628-6
semidefinite programmingcombinatorial optimizationnonlinear programming0-1 quadratic programmingquasi-NewtonLagrangian duality
Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items
Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster, Solving \(k\)-cluster problems to optimality with semidefinite programming, Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods, A generalized computing paradigm based on artificial dynamic models for mathematical programming, Improved semidefinite bounding procedure for solving max-cut problems to optimality, Quadratic Combinatorial Optimization Using Separable Underestimators, An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating, Unnamed Item, Copositive Relaxation Beats Lagrangian Dual Bounds in Quadratically and Linearly Constrained Quadratic Optimization Problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Handbook on semidefinite, conic and polynomial optimization
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
- Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
- Some numerical experiments with variable-storage quasi-Newton algorithms
- The spherical constraint in Boolean quadratic programs
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- Computing a nearest symmetric positive semidefinite matrix
- Seizure warning algorithm based on optimization and nonlinear dynamics
- From linear to semidefinite programming: an algorithm to obtain semidefinite relaxations for bivalent quadratic problems
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- Solving \(k\)-cluster problems to optimality with semidefinite programming
- A nonsmooth version of Newton's method
- Computational aspects of a branch and bound algorithm for quadratic zero- one programming
- Partial Lagrangian relaxation for general quadratic programming
- Numerical Study of Semidefinite Bounds for the k-cluster Problem
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Numerical Optimization
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Solving Graph Bisection Problems with Semidefinite Programming
- CSDP, A C library for semidefinite programming
- A Spectral Bundle Method for Semidefinite Programming
- An Interior-Point Method for Semidefinite Programming
- Combining semidefinite and polyhedral relaxations for integer programs
- Exploiting Sparsity in SDP Relaxation for Sensor Network Localization
- Regularization Methods for Semidefinite Programming
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Numerical optimization. Theoretical and practical aspects. Transl. from the French
- Different Formulations for Solving the HeaviestK-Subgraph Problem
