Testing copositivity with the help of difference-of-convex optimization

Mirjan Dür (1) , Jean-Baptiste Hiriart-Urruty (2)

1 Department of Mathematics [Trier]
2 IMT - Institut de Mathématiques de Toulouse UMR5219

We consider the problem of minimizing an indefinite quadratic form over the nonnegative orthant, or equivalently, the problem of deciding whether a symmetric matrix is copositive. We formulate the problem as a difference of convex functions problem. Using conjugate duality, we show that there is a one-to-one correspondence between their respective critical points and minima. We then apply a subgradient algorithm to approximate those critical points and obtain an efficient heuristic to verify non-copositivity of a matrix.

Domaines: Mathématiques [math]

Mirjan Dür, Jean-Baptiste Hiriart-Urruty. Testing copositivity with the help of difference-of-convex optimization. Mathematical Programming, 2013, 140, pp.31-43. ⟨10.1007/s10107-012-0625-9⟩. ⟨hal-00965850⟩