Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme |
| |
Authors: | Zhibin Deng Shu-Cherng Fang Qingwei Jin Wenxun Xing |
| |
Institution: | 1. Edward P. Fitts Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC 27695-7906, USA;2. Department of Management Science and Engineering, Zhejiang University, Hangzhou 310058, China;3. Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China |
| |
Abstract: | It is co-NP-complete to decide whether a given matrix is copositive or not. In this paper, this decision problem is transformed into a quadratic programming problem, which can be approximated by solving a sequence of linear conic programming problems defined on the dual cone of the cone of nonnegative quadratic functions over the union of a collection of ellipsoids. Using linear matrix inequalities (LMI) representations, each corresponding problem in the sequence can be solved via semidefinite programming. In order to speed up the convergence of the approximation sequence and to relieve the computational effort of solving linear conic programming problems, an adaptive approximation scheme is adopted to refine the union of ellipsoids. The lower and upper bounds of the transformed quadratic programming problem are used to determine the copositivity of the given matrix. |
| |
Keywords: | Conic programming Copositive Cone of nonnegative quadratic functions Adaptive approximation scheme |
本文献已被 ScienceDirect 等数据库收录! |
|