Copositive Programming by Simplicial Partition

Article type: Research Article

Authors: Žilinskas, Julius

Affiliations: Vilnius University, Institute of Mathematics and Informatics, Akademijos 4, LT-08663 Vilnius, Lithuania, e-mail: [email protected]

Abstract: Copositivity plays an important role in combinatorial and quadratic optimization since setting up a linear optimization problem over the copositive cone leads to exact reformulations of combinatorial and quadratic programming problems. A copositive programming problem may be approached checking copositivity of several matrices built with different values of the variable and the solution is the extreme value for which the matrix is copositive. However, this approach has some shortcomings. In this paper, we develop a simplicial partition algorithm for copositive programming to overcome the shortcomings. The algorithm has been investigated experimentally on a number of problems.

Keywords: simplicial partition, copositive programming, copositive matrices

Journal: Informatica, vol. 22, no. 4, pp. 601-614, 2011