A new approach to nonconvex optimization

Authors

  • A.S. Strekalovsky
  • A.V. Orlov

Keywords:

невыпуклая оптимизация
условия глобальной оптимальности
локальный поиск
глобальный поиск
вычислительный эксперимент

Abstract

In this paper we propose a new approach based on global optimality conditions for solving continuous nonconvex optimization problems. We present in detail a technique for finding a solution to the following three problems: the problem of polyhedral separability, the problem of solving a system of nonlinear equations, and the problem of finding the Nash equilibrium point in bimatrix games by means of the variational approach using the global search methodology. This work was supported by the Russian Foundation for Basic Research (project No. 05-01-00110) and by the grant of President of Russia (No. MK-6580.2006.1).

New computational technologies

Downloads

Published

2007-05-02

Issue

Vol. 8 (2007): Issue 2.

Section

Section 1. Numerical methods and applications

Author Biographies

A.S. Strekalovsky

Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS)

A.V. Orlov

Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS)

References

  1. Horst R., Tuy H. Global optimization. Deterministic approaches. Berlin: Springer- Verlag, 1993.
  2. Horst R., Pardalos P.M., and Thoai V. Introduction to global optimization. Dordrecht: Kluwer Academic Publishers, 1995.
  3. Floudas C.A., Visweswaran V. Quadratic optimization // Handbook of Global Optimization / Ed. by Horst R., Pardalos P. Dordrecht: Kluwer Academic Publishers, 1995. 224-228.
  4. Tuy H. D.C. Optimization: theory, methods and algorithms // Handbook of Global Optimization / Ed. by Horst R., Pardalos P. Dordrecht: Kluwer Academic Publishers, 1995. 149-216.
  5. Hiriart-Urruty J.-B. Generalized differentiability, duality and optimization for problems dealing with difference of convex functions // Lecture Notes in Economics and Mathematical Systems. Vol. 256. Berlin: Springer-Verlag, 1985. 37-69.
  6. Hiriart-Urruty J.-B., Lemarchal C. Convex analysis and minimization algorithms. Vols. I and II. Berlin: Springer-Verlag, 1993.
  7. Vasilév F.P. Optimization methods. Moscow: Factorial-Press, 2002 (in Russian).
  8. Bazaraa M.S., Shetty C.M. Nonlinear programming. Theory and algorithms. New York: Wiley, 1979.
  9. Strekalovsky A.S. Elements of nonconvex optimization. Novosibirsk: Nauka, 2003 (in Russian).
  10. Strekalovsky A.S. The search for a global maximum of a convex functional on an admissible set // Computational Mathematics and Mathematical Physics. 1993. 33, N 3. 315-328.
  11. Strekalovsky A.S. Extremum problems on complements of convex sets // Cybernetics and System Analysis. 1994. N 1. 88-100.
  12. Strekalovsky A.S. Global optimality conditions for nonconvex optimization // J. of Global Optimization. 1998. 12, N 4. 415-434.
  13. Strekalovsky A.S., Tsevendorj I. Testing the Re-strategy for a reverse convex problem // J. of Global Optimization. 1998. 13, N 1. 61-74.
  14. Strekalovsky A.S., Kuznetsova A.A., and Tsevendorj I. An approach to the solution of integer optimization problems // Computational Mathematics and Mathematical Physics. 1999. 39, N 1. 9-16.
  15. Strekalovsky A.S. One way to construct a global search algorithm for d.c. minimization problems // Nonlinear Optimization and Related Topics. Vol. 36 / Ed. by Pillo G.Di., Giannessi F. Dordrecht: Kluwer Academic Publishers, 2000. 429-443.
  16. Kuznetsova A.A., Strekalovsky A.S. On solving the maximum clique problem // J. of Global Optimization. 2001. 21, N 3. 265-288.
  17. Strekalovsky A.S. On the minimization of the difference of convex functions on a feasible set // Computational Mathematics and Mathematical Physics. 2003. 43, N 3. 380-390.
  18. Strekalovsky A.S. Some remarks on d.c. programming // Optimization and Optimal Control / Ed. by Pardalos P.M., Tseveendorj I., and Enkhbat R. New Jersey- London-Singapore-Hong Kong: World Scientific Publishing Co. 2003. 1. 347-367.
  19. Strekalovsky A.S., Yakovleva T.V. On a local and global search involved in nonconvex optimization problems // Automation and Remote Control. 2004. 65, N 3. 375-387.
  20. Orlov A.V., Strekalovsky A.S. Numerical search for equilibria in bimatrix games // Computational Mathematics and Mathematical Physics. 2005. 45, N 6. 947-960.
  21. Faddeev D.K., Faddeeva V.N. Computational methods of linear algebra. San Francisco: W.H. Freeman and Co., 1963.
  22. Ortega J.M., Reinbolt W.C. Iterative solution of nonlinear equations in several variable. San Diego: Academic Press, 1970.
  23. Demyanov V.F., Vasiliev L.V. Nondifferentiable optimization. New York: Springer-Optimization Software, 1985.
  24. Shor N.Z. Minimization methods of nondifferentiable functions and their applications. Kiev: Naukova Dumka, 1979 (in Russian).
  25. Mikhalevich V.S., Trubin V.A., and Shor N.Z. Optimization problems of production-transportation planning. Moscow: Nauka, 1986 (in Russian).
  26. Roose A., Kulla V., Lomp M., and Meresoo T. Test examples of systems of nonlinear equations. Tallin: Estonian Software and Computer Service Co., 1990.
  27. Astorino A., Gaudioso M. Polyhedral separability through successive LP // Journal of Optimization Theory and Applications. 2002. 112, N 2. 265-293.
  28. Mangasarian O.L. Linear and nonlinear separation of patterns by linear programming // Operations Research. 1965. 13, N 3. 444-452.
  29. Mangasarian O.L., Street W.N., and Wolberg W.H. Breast cancer diagnosis and prognosis via linear programing // Operations Research. 1995. 43, N 4. 570-577.
  30. Mills H. Equilibrium points in finite games // J. of the Society for Industrial and Applied Mathematics. 1960. 8, N 2. 397-402.
  31. Mukhamediev B.M. The solution of bilinear problems and finding the equilibrium situations in bimatrix games // Computational Mathematics and Mathematical Physics. 1978. 18, N 1. 60-66.
  32. McKelvey R.D., McLennan A. Computation of equilibria in finite games // Handbook of Computational Economics. Vol. 1 / Ed. by Amman H.M., Kendrick D.A., and Rust J. Amsterdam: Elseivier, 1996. 87-142.