Skip to main content
SpringerLink
Log in

Matrix representation and gradient flows for NP-hard problems

  • Contributed Papers
  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

Over the past decade, a number of connections between continuous flows and numerical algorithms were established. Recently, Brockett and Wong reported a connection between gradient flows on the special orthogonal groupLO(n) and local search solutions for the assignment problem. In this paper, we describe a uniform formulation for certain NP-hard combinatorial optimization problems in matrix form and examine their connection with gradient flows onLO(n). For these problems, there is a correspondence between the so-called 2-opt solutions and asymptotically stable critical points of an associated gradient flow.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bayer, D. A., andLagarias, J. C.,The Nonlinear Geometry of Linear Programming, Parts 1 and 2, Transactions of American Mathematical Society, Vol. 314, pp. 499–526, 1989 and Vol. 314, pp. 527–581, 1989.

    Google Scholar 

  2. Bloch, A. M.,Steepest Descent, Linear Programming, and Hamiltonian flows, Mathematical Developments Arising from Linear Programming, Edited by J. C. Lagarias and M. J. Todd, Contemporary Mathematics, Vol. 114, pp. 297–308, 1990.

    Google Scholar 

  3. Brockett, R. W.,Dynamical Systems That Sort and Solve Linear Programming Problems, Linear Algebra and Its Applications, Vol. 146, pp. 79–91, 1991.

    Article  Google Scholar 

  4. Brockett, R. W.,Least Squares Matching Problems, Linear Algebra and Its Applications, Vol. 122, pp. 761–777, 1989.

    Article  Google Scholar 

  5. Brockett, R. W., andWong, W. S.,A Gradient Flow for the Assignment Problem, New Trends in Systems Theory, Edited by G. Conte and B. Wyman, Birkhäuser, Boston, pp. 170–177, 1991.

    Google Scholar 

  6. Chu, M. T.,On the Continuous Realization of Iterative Processes, SIAM Review, Vol. 30, pp. 375–389, 1988.

    Article  Google Scholar 

  7. Deift, T., Nanda, T., andTomei, C.,Differential Equations for the Symmetric Eigenvalue Problems, SIAM Journal on Numerical Analysis, Vol. 20, pp. 1–22, 1983.

    Article  Google Scholar 

  8. Faybusovich, L.,Hamiltonian Structure of Dynamical Systems Which Solve Linear Programming Problems, Physica D, Vol. 53, pp. 217–232, 1991.

    Google Scholar 

  9. Faybusovich, L.,Dynamical Systems Which Solve Optimization Problems with Linear Constraints, IMA Journal of Mathematical Control and Information, Vol. 8, pp. 135–149, 1991.

    Google Scholar 

  10. Symes, W. W.,Hamiltonian Group Actions and Integrable Systems, Physica D, Vol. 1, pp. 339–376, 1980.

    Google Scholar 

  11. Symes, W. W.,The QR Algorithm and Scattering for the Nonperiodic Toda Lattice, Physica D, Vol. 4, pp. 275–280, 1982.

    Google Scholar 

  12. Watkins, D. S., andElsner, L.,On Rutishauser's Approach to Self-Similar Flows, SIAM Journal on Matrix Analysis and Applications, Vol. 11, pp. 301–311, 1990.

    Article  Google Scholar 

  13. Karmarkar, N.,An Interior-Point Approach to NP-Complete Problems, Part 1, Mathematical Developments Arising from Linear Programming, Edited by J. C. Lagarias and M. J. Todd, Contemporary Mathematics, Vol. 114, pp. 297–308, 1990.

    Google Scholar 

  14. Kamath, A. P., Karmarkar, N. K., Ramakrishnan, K., andResende, M. G. C.,Computational Experience with an Interior-Point Algorithm on the Satisfiability Problems, Annals of Operations Research, Vol. 25, pp. 43–58, 1990.

    Google Scholar 

  15. Karmarkar, N. K., Ramakrishnan, K., andResende, M. G. C.,An Interior-Point Algorithm to Solve Computationally Difficult Set-Covering Problems, Mathematical Programming, Vol. 52B, pp. 597–618, 1991.

    Article  Google Scholar 

  16. Karmarkar, N. K., andThakur, S. A.,An Interior-Point Approach to Tensor Optimization Problems with Application to Upper Bounds in Integer Quadratic Optimization Problems, Proceedings of the 2nd Conference on Integer Programming and Combinatorial Optimization, pp. 406–420, 1992.

  17. Spivey, W. A., andThrall, R. M.,Linear Optimization, Holt, Rinehart, and Winston, New York, New York, 1970.

    Google Scholar 

  18. Johnson, D. S., Papadimitriou, C. H., andYannakakis, M.,How Easy Is Local Search?, Journal of Computer and System Sciences, Vol. 37, pp. 79–100, 1988.

    Article  Google Scholar 

  19. Schäffer, A., andYannakakis, M.,Simple Local Search Problems That Are Hard to Solve, SIAM Journal on Computing, Vol. 20, pp. 56–87, 1991.

    Article  Google Scholar 

  20. Milnor, J.,Morse Theory, Princeton University Press, Princeton, New Jersey, 1969.

    Google Scholar 

  21. Davies, T. V., andJames, E. M.,Nonlinear Differential Equations, Addison-Wesley Publishing Company, Reading, Massachusetts, 1966.

    Google Scholar 

  22. Wu, N. L.,Analog Combinatorial Optimization, Final Year Student Report, Chinese University of Hong Kong, 1992.

Download references

Author information

Authors and Affiliations

  1. Department of Information Engineering, Chinese University of Hong Kong, Shatin, New Territories, Hong Kong

    W. S. Wong (Reader)

Authors
  1. W. S. Wong
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by W. B. Gong

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wong, W.S. Matrix representation and gradient flows for NP-hard problems. J Optim Theory Appl 87, 197–220 (1995). https://doi.org/10.1007/BF02192047

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02192047

Key Words

Search

Navigation