On Minimization of a Quadratic Binary Functional

Abstract

The problem of minimization of a quadratic functional depending on great number of binary variables is examined. 3 variants of minimization procedure are studied with the aid of computer simulation for spin-glass matrices. It is shown that under other equal conditions evident superiority has the maximal dynamics (the greedy algorithm). The dependence of the results on a distance between start points and the ground state is investigated. It is determined that the character of distribution of local minima depends on this distance crucially.

17 pages, 16 figures

References in corpus (4)

• Hysteretic optimization for the Sherrington-Kirkpatrick spin glass
• A hierarchical approach for computing spin glass ground states
• Numerical study of ground state energy fluctuations in spin glasses
• Global minimization of a quadratic functional: neural network approach