On the copositive representation of binary and continuous nonconvex quadratic programs
From MaRDI portal
Publication:2391001
DOI10.1007/s10107-008-0223-zzbMath1180.90234OpenAlexW2078600458MaRDI QIDQ2391001
Publication date: 24 July 2009
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-008-0223-z
Convex programming (90C25) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20)
Related Items
Linear transformation based solution methods for non-convex mixed integer quadratic programs, On the accuracy of uniform polyhedral approximations of the copositive cone, On the Convexification of Constrained Quadratic Optimization Problems with Indicator Variables, Lifting for Simplicity: Concise Descriptions of Convex Sets, Matrix Relaxations in Combinatorial Optimization, Continuous quadratic programming formulations of optimization problems on graphs, Multi-standard quadratic optimization: Interior point methods and cone programming reformulation, Computable representations for convex hulls of low-dimensional quadratic forms, Copositivity cuts for improving SDP bounds on the clique number, Conic approximation to quadratic optimization with linear complementarity constraints, Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions, SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY, The Maximum k-Colorable Subgraph Problem and Related Problems, Interplay of non-convex quadratically constrained problems with adjustable robust optimization, An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix, Immobile indices and CQ-free optimality criteria for linear copositive programming problems, Necessary and sufficient conditions for copositive tensors, An exact completely positive programming formulation for the discrete ordered median problem: an extended version, A survey of hidden convex optimization, Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures, Completely positive factorization by a Riemannian smoothing method, A new perspective on low-rank optimization, The boosted DC algorithm for linearly constrained DC programming, Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods, An exact quadratic programming approach based on convex reformulation for seru scheduling problems, A simplified completely positive reformulation for binary quadratic programs, Least Squares Approximation to the Distribution of Project Completion Times with Gaussian Uncertainty, Optimization under uncertainty and risk: quadratic and copositive approaches, Completely Positive Binary Tensors, (Global) optimization: historical notes and recent developments, Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems, Performance comparison of two recently proposed copositivity tests, Approximation hierarchies for copositive cone over symmetric cone and their comparison, Graph isomorphism: physical resources, optimization models, and algebraic characterizations, On Integrality in Semidefinite Programming for Discrete Optimization, A Geometrical Analysis on Convex Conic Reformulations of Quadratic and Polynomial Optimization Problems, Equilibrium modeling and solution approaches inspired by nonconvex bilevel programming, Hermitian completely positive matrices, Sparse conic reformulation of structured QCQPs based on copositive optimization with applications in stochastic optimization, Completely positive tensors in the complex field, Strengthened SDP relaxation for an extended trust region subproblem with an application to optimal power flow, New bounds for nonconvex quadratically constrained quadratic programming, Lagrangian duality in convex conic programming with simple proofs, Copositive programming via semi-infinite optimization, Conic formulation of QPCCs applied to truly sparse QPs, Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes, Factorization and cutting planes for completely positive matrices by copositive projection, Quadratic optimization over one first-order cone, Disruption Risk Mitigation in Supply Chains: The Risk Exposure Index Revisited, Locating a discrete subtree of minimum variance on trees: new strategies to tackle a very hard problem, A completely positive representation of \(0\)-\(1\) linear programs with joint probabilistic constraints, Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques, Testing copositivity via mixed-integer linear programming, Exploiting partial correlations in distributionally robust optimization, Solving Quadratic Programming by Cutting Planes, A guide to conic optimisation and its applications, Correlation matrices, Clifford algebras, and completely positive semidefinite rank, Completely positive and copositive program modelling for quadratic optimization problems, Analytical expressions of copositivity for fourth-order symmetric tensors, Contribution of copositive formulations to the graph partitioning problem, A note on convex reformulation schemes for mixed integer quadratic programs, Convex quadratic relaxations of nonconvex quadratically constrained quadratic programs, Foundations of Set-Semidefinite Optimization, Convexifiability of continuous and discrete nonnegative quadratic programs for gap-free duality, Nonconvex min-max fractional quadratic problems under quadratic constraints: copositive relaxations, A hierarchy of semidefinite relaxations for completely positive tensor optimization problems, A Complete Semidefinite Algorithm for Detecting Copositive Matrices and Tensors, Copositivity tests based on the linear complementarity problem, Copositive Programming, Quadratic optimization over a polyhedral cone, Optimality conditions for linear copositive programming problems with isolated immobile indices, An Efficient Inexact ABCD Method for Least Squares Semidefinite Programming, A copositive Farkas lemma and minimally exact conic relaxations for robust quadratic optimization with binary and quadratic constraints, Reformulation of the Quadratic Multidimensional Knapsack Problem as Copositive/Completely Positive Prorams, A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations, Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices, Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls, Robust Quadratic Programming with Mixed-Integer Uncertainty, Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting, Depth-first simplicial partition for copositivity detection, with an application to MaxClique, A semidefinite relaxation algorithm for checking completely positive separable matrices, The Discrete Moment Problem with Nonconvex Shape Constraints, Lower bounds on matrix factorization ranks via noncommutative polynomial optimization, A Newton-bracketing method for a simple conic optimization problem, Copositive Relaxation Beats Lagrangian Dual Bounds in Quadratically and Linearly Constrained Quadratic Optimization Problems, Unnamed Item, A Convergent 3-Block SemiProximal Alternating Direction Method of Multipliers for Conic Programming with 4-Type Constraints, A gentle, geometric introduction to copositive optimization, Completely positive reformulations for polynomial optimization, On Degenerate Doubly Nonnegative Projection Problems, Distributionally Robust Chance Constrained Geometric Optimization, Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme, Mathematical optimization ideas for biodiversity conservation, Can you cover your shadows?, SPN completable graphs, Cutting planes for semidefinite relaxations based on triangle-free subgraphs, Extension of completely positive cone relaxation to moment cone relaxation for polynomial optimization, Conic relaxations for semi-supervised support vector machines, Distributionally robust mixed integer linear programs: persistency models with applications, Computing the distance between the linear matrix pencil and the completely positive cone, The difference between \(5\times 5\) doubly nonnegative and completely positive matrices, Zero-one completely positive matrices and the \(\mathcal A(R, S)\) classes, On conic QPCCs, conic QCQPs and completely positive programs, Bounding the separable rank via polynomial optimization, Completely positive tensor recovery with minimal nuclear value, Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems, A computational study for bilevel quadratic programs using semidefinite relaxations, Stochastic nonlinear resource allocation problem, On monotonicity and search strategies in face-based copositivity detection algorithms, Triangle-free graphs and completely positive matrices, On the exactness of sum-of-squares approximations for the cone of \(5 \times 5\) copositive matrices, A polynomial-time algorithm for computing low CP-rank decompositions, Copositive matrices with circulant zero support set, LP-based tractable subcones of the semidefinite plus nonnegative cone, On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets, Erratum to: ``On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets, A factorization method for completely positive matrices, Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems, Moment approximations for set-semidefinite polynomials, Exact computable representation of some second-order cone constrained quadratic programming problems, On convex relaxations for quadratically constrained quadratic programming, Semidefinite approximations for quadratic programs over orthogonal matrices, A note on set-semidefinite relaxations of nonconvex quadratic programs, A primal barrier function phase I algorithm for nonsymmetric conic optimization problems, Completely positive reformulations of polynomial optimization problems with linear constraints, A fresh CP look at mixed-binary QPs: new formulations and relaxations, On the stable solution of large scale problems over the doubly nonnegative cone, Copositivity and constrained fractional quadratic problems, Interiors of completely positive cones, Cardinality constrained portfolio selection problem: a completely positive programming approach, Separating doubly nonnegative and completely positive matrices, Separation and relaxation for cones of quadratic forms, Copositive optimization -- recent developments and applications, Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization, An improved algorithm to test copositivity, An algorithm for determining copositive matrices, Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision, Completely positive and completely positive semidefinite tensor relaxations for polynomial optimization, Representing quadratically constrained quadratic programs as generalized copositive programs, Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation, A note on Burer's copositive representation of mixed-binary QPs, Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming, Computing symmetric nonnegative rank factorizations, On the computational complexity of membership problems for the completely positive cone and its dual, Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods, Exceptional family and solvability of copositive complementarity problems, Binary positive semidefinite matrices and associated integer polytopes, Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017, The \(\mathcal A\)-truncated \(K\)-moment problem, Quadratic optimization over a second-order cone with linear equality constraints, Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques, Analysis of copositive optimization based linear programming bounds on standard quadratic optimization, SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints, Chance constrained \(0-1\) quadratic programs using copulas, Approximation hierarchies for the cone of flow matrices, Copositivity and sparsity relations using spectral properties, On reduced semidefinite programs for second order moment bounds with applications, An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints, A semidefinite algorithm for completely positive tensor decomposition, Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems, Binary quadratic optimization problems that are difficult to solve by conic relaxations, A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides, A robust Lagrangian-DNN method for a class of quadratic optimization problems, On cones of nonnegative quartic forms, Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems, Burer's key assumption for semidefinite and doubly nonnegative relaxations, Geometry of the copositive and completely positive cones, Globally solving nonconvex quadratic programming problems via completely positive programming, Quadratic factorization heuristics for copositive programming, Notoriously hard (mixed-)binary QPs: empirical evidence on new completely positive approaches, Optimizing a polyhedral-semidefinite relaxation of completely positive programs, Convex reformulation for binary quadratic programming problems via average objective value maximization, Gaddum's test for symmetric cones, Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons, Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations, Completely positive semidefinite rank, Simplified semidefinite and completely positive relaxations, A proximal DC approach for quadratic assignment problem, Polyhedral approximations of the semidefinite cone and their application, Building a completely positive factorization, A data-driven distributionally robust bound on the expected optimal value of uncertain mixed 0-1 linear programming, A new conic approach to semisupervised support vector machines, Quadratic optimization with switching variables: the convex hull for \(n=2\), A polynomial-time interior-point method for circular cone programming based on kernel functions, A modified simplex partition algorithm to test copositivity, Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming, An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs, Two-stage stochastic standard quadratic optimization, Strong duality for general quadratic programs with quadratic equality constraints, Optimization hierarchy for fair statistical decision problems, A note on completely positive relaxations of quadratic problems in a multiobjective framework, Ideal formulations for constrained convex optimization problems with indicator variables, A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
Uses Software
Cites Work
- Unnamed Item
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- Maximum stable set formulations and heuristics based on continuous optimization
- Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
- A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
- A PTAS for the minimization of polynomials of fixed degree over the simplex
- Computable representations for convex hulls of low-dimensional quadratic forms
- Approximation of the Stability Number of a Graph via Copositive Programming
- On the Shannon capacity of a graph
- An Adaptive Linear Approximation Algorithm for Copositive Programs
- Maxima for Graphs and a New Proof of a Theorem of Turán
- Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
- A Copositive Programming Approach to Graph Partitioning
- On Cones of Nonnegative Quadratic Functions
- On copositive programming and standard quadratic optimization problems
