Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision
type: Item
instance of: scholarly article
title: Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision
zbMATH Open document ID: 1267.65060
author: Immanuel M. Bomze
author: Gabriele Eichfelder
published in: Mathematical Programming. Series A. Series B
publication date: 2013-05-06T00:00:00Z
review text: The paper introduces difference-of-convex based approaches to copositivity testing. The authors propose an algorithm to detect copositivity of a given symmetric matrix which combines linear programming and convex quadratic programming technology with spectral information. Three copositivity tests are presented. The algorithm either provides a guarantee for copositivity, or delivers a violating vector as a certificate for non-copositivity. For the branch and bound algorithm, the choice of spectral difference-of-convex decomposition and a robustification step are discussed. Some empirical tests results are presented on randomly generated matrices, and checking copositivity on the maximum clique problem.
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 90C22
Mathematics Subject Classification ID: 15B48
Mathematics Subject Classification ID: 90C20
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 6160889
zbMATH Keywords: conic optimization
zbMATH Keywords: linear optimization
zbMATH Keywords: quadratic optimization
zbMATH Keywords: numerical examples
zbMATH Keywords: copositivity testing
zbMATH Keywords: algorithm
zbMATH Keywords: branch and bound algorithm
zbMATH Keywords: spectral difference-of-convex decomposition
MaRDI profile type: Publication
full work available at URL: s10107-012-0543-x
OpenAlex ID: W2088564876
cites work: Criteria for copositive matrices using simplices and barycentric coordinates
cites work: Q4942383
cites work: Block pivoting and shortcut strategies for detecting copositivity
cites work: Global escape strategies for maximizing quadratic forms over a simplex
cites work: On standard quadratic optimization problems
cites work: Linear-Time Copositivity Detection for Tridiagonal Matrices and Extension to Block-Tridiagonality
cites work: Perron-Frobenius property of copositive matrices, and a block copositivity criterion
cites work: Copositive optimization -- recent developments and applications
cites work: Q3145799
cites work: Undominated d.c. decompositions of quadratic functions and applications to branch-and-bound approaches
cites work: New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability
cites work: Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization
cites work: Algorithmic copositivity detection by simplicial partition
cites work: On the copositive representation of binary and continuous nonconvex quadratic programs
cites work: Copositive Programming
cites work: Q3198800
cites work: Using copositivity for global optimality criteria in concave quadratic programming problems
cites work: Approximation of the stability number of a graph via copositive programming
cites work: Q3843714
cites work: Q5328177
cites work: Q5503714
cites work: Foundations of Set-Semidefinite Optimization
cites work: Q5592263
cites work: Two remarks on copositive matrices
cites work: The copositive completion problem
cites work: On copositive matrices with -1, 9, 1 entries
cites work: Introduction to global optimization
cites work: Q4889854
cites work: On generalized bisection of 𝑛-simplices
cites work: A copositivity probe
cites work: On convergence of the simplicial branch-and-bound algorithm based on \(\omega\)-subdivisions
cites work: Finiteness result for the simplicial branch-and-bound algorithm based on \(\omega\)-subdivisions
cites work: Some NP-complete problems in quadratic and nonlinear programming
cites work: Copositive realxation for genera quadratic programming
cites work: Convex programs with an additional reverse convex constraint
cites work: Criteria for copositive matrices
cites work: Quadratic-programming criteria for copositive matrices
cites work: Algorithms for determining the copositivity of a given symmetric matrix
cites work: Depth-first simplicial partition for copositivity detection, with an application to MaxClique
DOI: 10.1007/S10107-012-0543-X
description: scientific article; zbMATH DE number 6160889