Semidefinite programming for discrete optimization and matrix completion problems
From MaRDI portal
Publication:697582
DOI10.1016/S0166-218X(01)00352-3zbMATH Open1060.90059OpenAlexW2023710022MaRDI QIDQ697582FDOQ697582
Authors: Henry Wolkowicz, Miguel F. Anjos 
Publication date: 17 September 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00352-3
Recommendations
- Semidefinite programming in combinatorial optimization
- scientific article; zbMATH DE number 1944141
- Semidefinite programming and combinatorial optimization
- Semidefinite programming and integer programming
- Approximation algorithms and semidefinite programming.
- scientific article; zbMATH DE number 724202
- SDP relaxations for some combinatorial optimization problems
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Matrix relaxations in combinatorial optimization
Cites Work
- CSDP, A C library for semidefinite programming
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- SDPLIB 1.2, a library of semidefinite programming test problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Geometry of Algorithms with Orthogonality Constraints
- A Spectral Bundle Method for Semidefinite Programming
- Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
- On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Self-Scaled Barriers and Interior-Point Methods for Convex Programming
- Primal--Dual Path-Following Algorithms for Semidefinite Programming
- Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
- The Molecule Problem: Exploiting Structure in Global Optimization
- An Interior-Point Method for Semidefinite Programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Geometry of semidefinite Max-Cut relaxations via matrix ranks
- Connections between the real positive semidefinite and distance matrix completion problems
- Positive definite completions of partial Hermitian matrices
- A projected gradient algorithm for solving the maxcut SDP relaxation
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Convex Relaxations of (0, 1)-Quadratic Programming
- Quadratic programming with one negative eigenvalue is NP-hard
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- The sandwich theorem
- Semidefinite programming relaxations for the quadratic assignment problem
- A comparison of the Delsarte and Lovász bounds
- Title not available (Why is that?)
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Maximum rank matrix completion
- Exploiting sparsity in primal-dual interior-point methods for semidefinite programming
- A semidefinite framework for trust region subproblems with applications to large scale minimization
- Title not available (Why is that?)
- Title not available (Why is that?)
- A study of search directions in primal-dual interior-point methods for semidefinite programming
- Title not available (Why is that?)
- The Euclidian Distance Matrix Completion Problem
- Title not available (Why is that?)
- Semidefinite programming relaxation for nonconvex quadratic programs
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets
- Title not available (Why is that?)
- Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices
- Strong Duality for Semidefinite Programming
- Title not available (Why is that?)
- Matrix Completion Theorems
- Solving Euclidean distance matrix completion problems via semidefinite progrmming
- Approximating quadratic programming with bound and quadratic constraints
- Semidefinite programming and combinatorial optimization
- The Gauss-Newton direction in semidefinite programming
- Title not available (Why is that?)
- Copositive realxation for genera quadratic programming
- Determinant Maximization with Linear Matrix Inequality Constraints
- Maximal rank Hermitian completions of partially specified Hermitian matrices.
- On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
- Distance geometry optimization for protein structures
- Semidefinite programming in combinatorial optimization
- Strong duality for a trust-region type relaxation of the quadratic assignment problem
- On Lagrangian relaxation of quadratic matrix constraints
- Title not available (Why is that?)
- Partially specified matrices and operators: classification, completion, applications
- A New Lower Bound Via Projection for the Quadratic Assignment Problem
- A projection technique for partitioning the nodes of a graph
- Title not available (Why is that?)
- The symmetric inverse \(M\)-matrix completion problem
- Inertia possibilities for completions of partial hermitian matrices*
- The combinatorially symmetric P-matrix completion problem
- Semidefinite programming and combinatorial optimization
- Determinantal formulae for matrix completions associated with chordal graphs
- Title not available (Why is that?)
- Completions of inverse \(M\)-matrix patterns
- Title not available (Why is that?)
- A connection between positive semidefinite and Euclidean distance matrix completion problems
- Title not available (Why is that?)
- Matrix Completions, Norms, and Hadamard Products
- Completions of \(M\)-matrix patterns
- Methods for constructing distance matrices and the inverse eigenvalue problem
- Positive semidefinite completions of partial Hermitian matrices
- Positive definite completions and determinant maximization
- Cuts, matrix completions and graph rigidity
- An interior-point method for approximate positive semidefinite completions
- Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
- Polynomial instances of the positive semidefinite and Euclidean distance matrix completion problems
- Eigenvalue bounds versus semidefinite relaxations for the quadratic assignment problem
- A tight bound for the boolean quadratic optimization problem and its use in a branch and bound algorithm1
- Title not available (Why is that?)
- Approximate Semidefinite Matrices in a Linear Variety
- Remarks on a difficult test problem for quadratic boolean programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Some convexity theorems for matrices
Cited In (20)
- A convex optimisation framework for the unequal-areas facility layout problem
- Optimality criteria without constraint qualifications for linear semidefinite problems
- Using the eigenvalue relaxation for binary least-squares estimation problems
- An improved semidefinite programming relaxation for the satisfiability problem
- Title not available (Why is that?)
- A guide to conic optimisation and its applications
- Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons
- Positive semidefinite matrix completions on chordal graphs and constraint nondegeneracy in semidefinite programming
- Convexifiability of continuous and discrete nonnegative quadratic programs for gap-free duality
- A global continuation algorithm for solving binary quadratic programming problems
- An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs
- Conditions for existence of dual certificates in rank-one semidefinite problems
- A note on the Lasserre hierarchy for different formulations of the maximum independent set problem
- Introduction to semidefinite, conic and polynomial optimization
- Conditional quadratic semidefinite programming: examples and methods
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- Structure methods for solving the nearest correlation matrix problem
- Dimensionality reduction of SDPs through sketching
- A semidefinite optimization approach for the single-row layout problem with unequal dimensions
- Global registration of multiple point clouds using semidefinite programming
Uses Software
This page was built for publication: Semidefinite programming for discrete optimization and matrix completion problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q697582)
