Optimization Online


On monotonicity and search traversal in copositivity detection algorithms

Eligius MT Hendrix(eligius***at***uma.es)
Boglarka G.- Toth(boglarka***at***inf.szte.hu)
Leocadio G Casado(leo***at***ual.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

Download: [PDF]

Entry Submitted: 04/03/2020
Entry Accepted: 04/03/2020
Entry Last Modified: 04/03/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society