On Copositive Programming and Standard Quadratic Optimization Problems |
| |
Authors: | Immanuel M Bomze Mirjam Dür Etienne de Klerk Cornelis Roos Arie J Quist Tamás Terlaky |
| |
Institution: | (1) ISDS, Universität Wien, Austria;(2) Department of Statistics, Vienna University of Economics, Austria;(3) Faculty ITS/TWI/SSOR, Delft University of Technology, The Netherlands;(4) Department of Computing and Software, McMaster University Hamilton, Ontario, Canada |
| |
Abstract: | A standard quadratic problem consists of finding global maximizers of a quadratic form over the standard simplex. In this paper, the usual semidefinite programming relaxation is strengthened by replacing the cone of positive semidefinite matrices by the cone of completely positive matrices (the positive semidefinite matrices which allow a factorization FF
T where F is some non-negative matrix). The dual of this cone is the cone of copositive matrices (i.e., those matrices which yield a non-negative quadratic form on the positive orthant). This conic formulation allows us to employ primal-dual affine-scaling directions. Furthermore, these approaches are combined with an evolutionary dynamics algorithm which generates primal-feasible paths along which the objective is monotonically improved until a local solution is reached. In particular, the primal-dual affine scaling directions are used to escape from local maxima encountered during the evolutionary dynamics phase. |
| |
Keywords: | Copositive programming Global maximization Positive semidefinite matrices Standard quadratic optimization |
本文献已被 SpringerLink 等数据库收录! |
|