Новый подход к невыпуклой оптимизации

Авторы

  • А.С. Стрекаловский
  • А.В. Орлов

Ключевые слова:

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

Аннотация

В работе предлагается новый подход к решению непрерывных невыпуклых задач оптимизации, основанный на условиях глобальной оптимальности. Детально представлена методика решения трех задач: задачи о полиэдральной отделимости, систем нелинейных уравнений и отыскания ситуации равновесия по Нэшу в биматричных играх посредством вариационного подхода с использованием методологии глобального поиска.

Новые вычислительные технологии

Загрузки

Опубликован

2007-05-02

Выпуск

Том 8 (2007): Выпуск 2.

Раздел

Раздел 1. Вычислительные методы и приложения

Авторы

А.С. Стрекаловский

Институт динамики систем и теории управления имени В.М. Матросова СО РАН (ИДСТУ СО РАН)
ул. Лермонтова, 134, 664033, Иркутск

А.В. Орлов

Институт динамики систем и теории управления имени В.М. Матросова СО РАН (ИДСТУ СО РАН)
ул. Лермонтова, 134, 664033, Иркутск

Библиографические ссылки

  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.