On monotonicity and search traversal in copositivity detection algorithms
Eligius MT Hendrix(eligiusuma.es)
Abstract: Matrix copositivity has an important theoretical background. Over the last decades, the use of algorithms to check copositivity has made a big progress. Methods are based on spatial branch and bound, transformation to Mixed Integer Programming, implicit enumeration of KKT points or face-based search. Our research question focuses on exploiting the mathematical properties of the relative interior minima of the standard quadratic program (StQP) and monotonicity. We derive several theoretical properties related to convexity and monotonicity of the standard quadratic function over faces of the unit simplex and illustrate with numerical instances that exploiting monotonicity in algorithms may speed up the search. For face-based algorithms the question is what traversal through the face graph of the unit simplex is more appropriate for which matrix instance.
Keywords: Copositive matrix, Unit simplex, monotone, face.
Category 1: Global Optimization (Other )
Category 2: Nonlinear Optimization (Quadratic Programming )
Category 3: Integer Programming ((Mixed) Integer Nonlinear Programming )
Citation: Universidad de Málaga, 3 April 2020
Entry Submitted: 04/03/2020
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|