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

• 成果类型: Article
• 署名作者: Duer, Mirjam; Hiriart-Urruty, Jean-Baptiste
• 署名单位: Universitat Trier; Universite de Toulouse; Universite Toulouse III - Paul Sabatier
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0625-9
• 发表日期: 2013
• 页码: 31-43
• 关键词: quadratic-forms; Duality

摘要

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.