Mathematical Aspects of Neuro-Dynamics for Combinatorial Optimization

Yoshinori UESAKA

Mathematical Aspects of Neuro-Dynamics for Combinatorial Optimization

Yoshinori UESAKA

Full Text Views

0

Cite this

Summary :

Hopfield's neural networks are known to have a potentiality to solve combinatorial optimization problems. It is however found that the networks often fail to get the optimum solution. The present paper intends to clarify the exact cause of such failure from a mathematical point of view. A normal form of the objective function to be minimized is introduced. It is shown that almost all of combinatorial optimization problems can be reduced to minimum search problems of real-valued quadratic functions of two-valued variables excluding linear terms. A dynamical system, which is implemented by an idealized neural network consisting of massively connected neurons, is induced from the extension of the objective function to a multidimensional Euclidean space. The asymptotically stable states of this dynamical system are shown to lie in the vertices of a hyper cube that correspond to minimal points of the objective function. Hence, if the initial state were rightly selected, then the state of the dynamical system would approach to the minimum point of the objective function, and the corresponding optimization problem could be completely solved. This indicates that only the problem how to find a right initial state remains to be investigated. Through computer simulation, a conjecture on initial state selection is given such that the probability for the minimum search with a randomly selected initial state from the hyper cube, of which center is located at the origin of the state space, to be successful converges to 1 as the cube becomes 0 in size.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E74-A No.6 pp.1368-1372

Publication Date: 1991/06/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section INVITED PAPER (Special Issue on Nonlinear Theory and Its Applications)

Category

Authors

Yoshinori UESAKA

Keyword

Cite this

Copy

Yoshinori UESAKA, "Mathematical Aspects of Neuro-Dynamics for Combinatorial Optimization" in IEICE TRANSACTIONS on Fundamentals, vol. E74-A, no. 6, pp. 1368-1372, June 1991, doi: .
Abstract: Hopfield's neural networks are known to have a potentiality to solve combinatorial optimization problems. It is however found that the networks often fail to get the optimum solution. The present paper intends to clarify the exact cause of such failure from a mathematical point of view. A normal form of the objective function to be minimized is introduced. It is shown that almost all of combinatorial optimization problems can be reduced to minimum search problems of real-valued quadratic functions of two-valued variables excluding linear terms. A dynamical system, which is implemented by an idealized neural network consisting of massively connected neurons, is induced from the extension of the objective function to a multidimensional Euclidean space. The asymptotically stable states of this dynamical system are shown to lie in the vertices of a hyper cube that correspond to minimal points of the objective function. Hence, if the initial state were rightly selected, then the state of the dynamical system would approach to the minimum point of the objective function, and the corresponding optimization problem could be completely solved. This indicates that only the problem how to find a right initial state remains to be investigated. Through computer simulation, a conjecture on initial state selection is given such that the probability for the minimum search with a randomly selected initial state from the hyper cube, of which center is located at the origin of the state space, to be successful converges to 1 as the cube becomes 0 in size.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e74-a_6_1368/_p

Copy

@ARTICLE{e74-a_6_1368,
author={Yoshinori UESAKA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Mathematical Aspects of Neuro-Dynamics for Combinatorial Optimization},
year={1991},
volume={E74-A},
number={6},
pages={1368-1372},
abstract={Hopfield's neural networks are known to have a potentiality to solve combinatorial optimization problems. It is however found that the networks often fail to get the optimum solution. The present paper intends to clarify the exact cause of such failure from a mathematical point of view. A normal form of the objective function to be minimized is introduced. It is shown that almost all of combinatorial optimization problems can be reduced to minimum search problems of real-valued quadratic functions of two-valued variables excluding linear terms. A dynamical system, which is implemented by an idealized neural network consisting of massively connected neurons, is induced from the extension of the objective function to a multidimensional Euclidean space. The asymptotically stable states of this dynamical system are shown to lie in the vertices of a hyper cube that correspond to minimal points of the objective function. Hence, if the initial state were rightly selected, then the state of the dynamical system would approach to the minimum point of the objective function, and the corresponding optimization problem could be completely solved. This indicates that only the problem how to find a right initial state remains to be investigated. Through computer simulation, a conjecture on initial state selection is given such that the probability for the minimum search with a randomly selected initial state from the hyper cube, of which center is located at the origin of the state space, to be successful converges to 1 as the cube becomes 0 in size.},
keywords={},
doi={},
ISSN={},
month={June},}

Copy

TY - JOUR
TI - Mathematical Aspects of Neuro-Dynamics for Combinatorial Optimization
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1368
EP - 1372
AU - Yoshinori UESAKA
PY - 1991
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E74-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 1991
AB - Hopfield's neural networks are known to have a potentiality to solve combinatorial optimization problems. It is however found that the networks often fail to get the optimum solution. The present paper intends to clarify the exact cause of such failure from a mathematical point of view. A normal form of the objective function to be minimized is introduced. It is shown that almost all of combinatorial optimization problems can be reduced to minimum search problems of real-valued quadratic functions of two-valued variables excluding linear terms. A dynamical system, which is implemented by an idealized neural network consisting of massively connected neurons, is induced from the extension of the objective function to a multidimensional Euclidean space. The asymptotically stable states of this dynamical system are shown to lie in the vertices of a hyper cube that correspond to minimal points of the objective function. Hence, if the initial state were rightly selected, then the state of the dynamical system would approach to the minimum point of the objective function, and the corresponding optimization problem could be completely solved. This indicates that only the problem how to find a right initial state remains to be investigated. Through computer simulation, a conjecture on initial state selection is given such that the probability for the minimum search with a randomly selected initial state from the hyper cube, of which center is located at the origin of the state space, to be successful converges to 1 as the cube becomes 0 in size.
ER -