Attraction area of minima in quadratic binary optimization
Iakov Karandashev, Boris Kryzhanovsky · Optical Memory and Neural Networks · 2014
The paper deals with the problem of quadratic functional minimization in the space of binary variables. We analyze the efficiency of the random search procedure used in binary minimization and show that the radius of the attraction area of a minimum directly depends on its depth: the deeper the minimum, the greater its radius of attraction. Thus, the probability of finding a minimum during random search grows exponentially with depth of the minimum.