Optimization Online


Gaddum's test for symmetric cones

Michael Orlitzky (michael***at***orlitzky.com)

Abstract: A real symmetric matrix "A" is copositive if the inner product if Ax and x is nonnegative for all x in the nonnegative orthant. Copositive programming has attracted a lot of attention since Burer showed that hard nonconvex problems can be formulated as completely-positive programs. Alas, the power of copositive programming is offset by its difficulty: simple questions like "is this matrix copositive?" have complicated answers. In 1958, Jerry Gaddum proposed a recursive procedure to check if a given matrix is copositive by solving a series of matrix games. It is easy to implement and conceptually simple. Copositivity generalizes to cones other than the nonnegative orthant. If K is a proper cone, then the linear operator L is copositive on K if the inner product of L(x) and x is nonnegative for all x in K. Little is known about these operators in general. We extend Gaddum's test to self-dual and symmetric cones, thereby deducing criteria for copositivity in those settings.

Keywords: copositivity, copositive programming, linear games, conic optimization, Euclidean Jordan algebra

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Complementarity and Variational Inequalities

Category 3: Other Topics (Game Theory )

Citation: Journal of Global Optimization (2020) https://link.springer.com/article/10.1007%2Fs10898-020-00960-6


Entry Submitted: 12/16/2019
Entry Accepted: 12/17/2019
Entry Last Modified: 10/28/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