Abstract
The paper deals with the binary minimization of a quadratic functional. Typically the problem is NP-hard and the organization of the quadratic functional landscape in space of multiple binary variables even without constraints is not currently understood. We tackle the problem with the classical Hopfield neural network and show theoretically the exponential dependence between the energy and the attraction area of a minimum. As a consequence we propose a new algorithm using matrix transformation to cope with the problem. The matrix that gave birth to the functional is replaced by a new mix-matrix. This change of the objective function brings about a sharp increase in the minimization algorithm efficiency: the chances to find a global minimum grow as exp(αN) where N is the dimensionality of the problem, and the energy spectrum of minima being found shifts considerably to the deep side so that the average of the spectrum differs from the energy of the global minimum by only 4–6% (subject to the type of matrix).
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Karandashev, Y.M. and Kryzhanovsky, B.V., Binary optimization: efficient increasing of global minimum basin of attraction, Opt. Mem. Neural Networks (Inform. Opt.), 2010, vol. 19, no. 2, pp. 110–125.
Liers, F., Junger, M., Reinelt, G., and Rinaldi, G., Computing Exact Ground States of Hard Ising Spin Glass Problems by Branch-and-Cut, in New Optimization Algorithms in Physics, Hartmann, A., Rieger, H., Eds., Berlin: Wiley-VCH, 2004, pp. 47–68.
Goemans, M.X. and Williamson, D.P., 878-approximation algorithms for MAXCUT and MAX2SAT, ACM Symposium on Theory of Computing, 1994.
Bellare, M., Goldreich, O., and Sudan, M., Free bits, PCPs and non-approximability, towards tight on fundations of computer science, IEEE Comput. Soc., 1995, pp. 422–431.
Rendl, F., Rinaldi, G., and Wiegele, A., Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Math. Programming, 2010, vol. 121, no. 2, p. 307.
Wiegele, A., Nonlinear optimization techniques applied to combinatorial optimization problems, Ph.D. Dissertation, Klagenfurt: Alpen-Adria-Universität, 2006.
Hopfield, J.J., Neural Networks and physical systems with emergent collective computational abilities, Proc. Nat. Acad. Sci. USA, 1981, vol. 79, pp. 2554–2558.
Hopfield, J.J. and Tank, D.W., Neural computation of decisions in optimization problems, Biological Cybernetics, 1985, vol. 52, pp. 141–152.
Fu, Y. and Anderson, P.W., Application of statistical mechanics to NP-complete problems in combinatorial optimization, J. Phys., Ser. A, 1986, vol. 19, pp. 1605–1620.
Poggio, T. and Girosi, F., Regularization algorithms for learning that are equivalent to multilayer networks, Science, 1990, vol. 247, pp. 978–982.
Mulder, S. and Wunsch, D., II, A Million city traveling salesman problem solution by divide and conquer clustering and adaptive resonance neural networks, Neural Networks, 2003, vol. 16, no. 5–6, pp. 827–832.
Wu, F. and Tam, P.K.S., A neural network methodology of quadratic optimization, Int. J. Neural Systems, 1999, vol. 9, no. 2, pp. 87–93.
Pinkas, G. and Dechter, R., Improving connectionist energy minimization, J. Artificial Inteligence Res., 1995, vol. 3, no. 195, pp. 23–48.
Kryzhanovskii, B.V., Magomedov, B.M., and Mikaelyan, A.L., A relation between the depth of a local minimum and the probability of its detection in the generalized Hopfield model, Dokl. Math., 2005, vol. 72, no. 3, pp. 986–990.
Kryzhanovsky, B. and Magomedov, B., Application of domain neural network to optimization tasks, Lect. Notes Comput. Sci., 2005, vol. 3697, pp. 397–403.
Hartmann, A.K. and Rieger, H., New Optimization Algorithms in Physics, Berlin: Wiley-VCH, 2004.
Duch, W. and Korczak, J., Optimization and global minimization methods suitable for neural networks, KMK UMK Technical Report, 1/99; Neural Computing Surveys, 1998; http://www.is.umk.pl/~duch/cv/papall.html.
Hartmann, A.K. and Rieger, H., Optimization Algorithms in Physics, Berlin: Wiley-VCH, 2001.
Litinskii, L.B., Eigenvalue problem approach to discrete minimization, Lect. Notes Comput. Sci., 2005, vol. 3697, pp. 405–410.
Smith, K.A., Neural networks for combinatorial optimization: a review of more than a decade of research, Informs J. Comput., 1999, vol. 11, no. 1, pp. 15–34.
Joya, G., Atencia, M., and Sandoval, F., Hopfield neural networks for optimization: study of the different dynamics, Neurocomputing, 2002, vol. 43, pp. 219–237.
Litinskii, L.B. and Magomedov, B.M., Global minimization of a quadratic functional: neural networks approach, Pat. Rec. Image Analysis, 2005, vol. 15, no. 1, pp. 80–82.
Boettecher, S., Extremal optimization for Sherrington-Kirkpatrick spin glasses, Eur. Phys. J., Ser. B, 2005, vol. 46, pp. 501.
Kryzhanovsky, B.V., Magomedov, B.M., and Fonarev, A.B., On the probability of finding local minima in optimization problems, in Proc. of IJCNN, 2006, pp. 5888–5892.
Kryzhanovsky, B.V. and Kryzhanovsky, V.M., The shape of a local minimum and the probability of its detection in random search, Lect. Notes Electric. Eng., 2009, vol. 24, pp. 51–61.
Karandashev, I. and Kryzhanovsky, B., Increasing the attraction area of the global minimum in the binary optimization problem, J. Glob. Optim., 2013, vol. 56, no. 3, pp. 1167–1185.
Karandashev, I. and Kryzhanovsky, B., Attraction area of minima in quadratic binary optimization, Opt. Mem. Neural Networks (Inform. Opt.), 2014, vol. 23, no. 2, pp. 84–88.
Houdayer, J. and Martin, O.C., Hierarchical approach for computing spin glass ground states, Phys. Rev., Ser. E, 2001, vol. 64, no. 056704.
Marti, R., Duarte, A., and Laguna, M., Advanced scatter search for the max-cut problem, Informs J. Comput., 2009, vol. 1, no. 21, pp. 26–38.
Burer, S., Monteiro, R.D.C., and Zhang, Y., Rank-two relaxation heuristics for max-cut and other binary quadratic programs, SIAM J. Optimization, 2000, vol. 12, pp. 503–521.
Kryzhanovsky, B.V., Expansion of a matrix in terms of external products of configuration vectors, Opt. Mem. Neural Networks (Inform. Opt.), 2008, vol. 17, no. 1, pp. 62–68.
Author information
Authors and Affiliations
Corresponding author
About this article
Cite this article
Karandashev, I., Kryzhanovsky, B. Matrix transformation method in quadratic binary optimization. Opt. Mem. Neural Networks 24, 67–81 (2015). https://doi.org/10.3103/S1060992X1502006X
Received:
Published:
Issue Date:
DOI: https://doi.org/10.3103/S1060992X1502006X