[en] We study the problem of finding a local minimum of a multilinear function E over the discrete set {0, 1}(n). The search is achieved by a gradient-like system in [0, 1](n) with cost function E. Under mild restrictions on the metric, the stable attractors of the gradient-like system are shown to produce solutions of the problem, even when they are not in the vicinity of the discrete set {0, 1}(n). Moreover, the gradient-like system connects with interior point methods for linear programming and with the analog neural network studied by Vidyasagar (IEEE Trans. Automat. Control 40 (8) (1995) 1359), in the same context. (C) 2004 Elsevier B.V. All rights reserved.
Disciplines :
Computer science Engineering, computing & technology: Multidisciplinary, general & others
Author, co-author :
Absil, P.-A.; Université Catholique de Louvain - UCL > INMA
Sepulchre, Rodolphe ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Language :
English
Title :
Continuous dynamical systems that realize discrete optimization on the hypercube
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
Balas E., Mazzola J.B. Nonlinear 0-1 programming: I. Linearization techniques. Math. Programming. 30:1984;1-21.
Bayer D.A., Lagarias J.C. The nonlinear geometry of linear programming. II. Legendre transform coordinates and central trajectories. Trans. Amer. Math. Soc. 314(2):1989;527-581.
Bruck J., Blaum M. Neural networks, error-correcting codes, and polynomials over the binary n-cube. IEEE Trans. Inform. Theory. 35(5):1989;976-987.
Faybusovich L. Hamiltonian structure of dynamical systems which solve linear programming problems. Physica D. 53:1991;217-232.
Hammer P.L., Rudeanu S. Boolean Methods in Operation Research and Related Areas. 1968;Springer, Berlin.
Harant J., Pruchnewski A., Voigt M. On dominating sets and independent sets of graphs. Combin. Probab. Comput. 8(6):1999;547-553.
Hopfield J.J. Neural networks and physical systems with emergent collective computational abilities. Proc. Nat. Acad. Sci. USA. 79:1982;2554-2558.
Hopfield J.J. Neurons with graded response have collective computational capabilities like those of two-state neurons. Proc. Nat. Acad. Sci. USA. 81:1984;3088-3092.
Khalil H.K. Nonlinear Systems. Second Edition:1996;Prentice-Hall, Englewood Cliffs, NJ.
Kurdyka K., Mostowski T., Parusiński A. Proof of the gradient conjecture of R. Thom. Ann. of Math. (2). 152(3):2000;763-792.
Lojasiewicz S. Ensembles semi-analytiques. 1965;Inst. Hautes Études Sci. Bures-sur-Yvette.
S. Lojasiewicz, Sur les trajectoires du gradient d'une fonction analytique, in: Seminari di Geometria 1982-1983, Università di Bologna, Istituto di Geometria, Dipartimento di Matematica, 1984, pp. 115-117.
Schäffer A.A., Yannakakis M. Simple local search problems that are hard to solve. SIAM J. Comput. 20(1):1991;56-87.
Vidyasagar M. Minimum-seeking properties of analog neural networks with multilinear objective functions. IEEE Trans. Automat. Control. 40(8):1995;1359-1375.
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.