Nonsmooth minimization problems for the difference of two convex functions

Authors

  • T.V. Gruzdeva Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS) https://orcid.org/0000-0002-4579-3927
  • A.S. Strekalovsky Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS) https://orcid.org/0000-0002-4664-6961
  • A.V. Orlov Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS)
  • O.V. Druzinina «Yandex.Money»

Keywords:

nonconvex optimization, d.c. function, nonsmooth problems, local search, global search strategy, convergence theorems, numerical simulation

Abstract

The global search theory in nonsmooth d.c. minimization problems (the goal function is represented as the difference of two convex functions) is generalized to the nondifferentiable case. Several algorithms of local and global search in problems with nonsmooth goal functions are proposed and their convergence is studied. The proposed algorithms are numerically tested.

Author Biographies

T.V. Gruzdeva

A.S. Strekalovsky

A.V. Orlov

O.V. Druzinina

«Yandex.Money», NBCO LLC
• Senior Researcher

References

  1. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
  2. Еремин И.И., Мазуров Вл.Д., Скарин В.Д., Хачай М.Ю. Математические методы в экономике. Екатеринбург: УрГУ-Центр «Фактория Пресс», 2000.
  3. Васильев Ф.П. Методы оптимизации. М.: Факториал-пресс, 2002.
  4. Измаилов А.Ф., Солодов М.В. Численные методы оптимизации. М.: ФИЗМАТЛИТ, 2005.
  5. Hiriart-Urruty J.-B., Lemarshal C. Convex analysis and minimization algorithms. Berlin: Springer, 1993.
  6. Nocedal J., Wright S.J. Numerical optimization. New York: Springer, 1999.
  7. Horst R., Pardalos P., Thoai N.V. Introduction to global optimization. Dordrecht-Boston-London: Kluwer Academic Publishers, 1995.
  8. Демьянов В.Ф., Васильев Л.В. Недифференцируемая оптимизация. М.: Наука, 1981.
  9. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979.
  10. Шор Н.З. Монотонные модификации r-алгоритмов и их приложения // Кибернетика и системный анализ. 2002. N 6. 74-95.
  11. Ben-Tal A., Nemirovski A. Non-Euclidean restricted memory level method for large-scale convex optimization // Mathematical Programming. 2005. 102, N 3. 407-456.
  12. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.: Наука, 1980.
  13. Михалевич В.С., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования: Модели, методы, алгоритмы. М.: Наука, 1986.
  14. Horst R., Thoai N.V. D.C. Programming: overview // J. of Optimization Theory and Applications. 1999. 103, N 1. 1-43.
  15. Tao P.D., Souad L.B. Algorithms for solving a class of non convex optimization. Methods of subgradients // Fermat Days 85, Mathematics for Optimization / Ed. by J.-B. Hiriart-Urruty. Amsterdam: Elsevier, 1986. 249-271.
  16. Стрекаловский А.С. Элементы невыпуклой оптимизации. Новосибирск: Наука, 2003.
  17. Стрекаловский А.С. О минимизации разности двух выпуклых функций на допустимом множестве // Журн. вычисл. матем. и матем. физики. 2003. 43, N 3. 399-409.
  18. Strekalovsky A.S. On local search in d.c. optimization problems // Optimization Letters. 2011 (submitted).
  19. Стрекаловский А.С., Орлов А.В. Биматричные игры и билинейное программирование. М.: ФИЗМАТЛИТ, 2007.
  20. Стрекаловский А.С., Яковлева Т.В. О локальном и глобальном поиске в невыпуклых задачах оптимизации // Автоматика и телемеханика. 2004. N 3. 23-34.
  21. Мазуркевич Е.О., Петрова Е.Г., Стрекаловский А.С. О численном решении линейной задачи дополнительности // Журн. вычисл. матем. и матем. физики. 2009. 49, N 8. 1385-1398.
  22. Стрекаловский А.С., Орлов А.В., Малышев А.В. Численное решение одного класса задач двухуровневого программирования // Сибирский журнал вычисл. матем. 2010. 13, N 2. 201-212.
  23. Strekalovsky A.S., Orlov A.V., Malyshev A.V. On computational search for optimistic solutions in bilevel problems // J. of Global Optimization. 2010. 48, N 1. 159-172.
  24. Груздева Т.В., Стрекаловский А.С. Локальный поиск в задачах с невыпуклыми ограничениями // Журн. вычисл. матем. и матем. физики. 2007. 47, N 3. 397-413.
  25. Орлов А.В. Численное решение задач билинейного программирования // Журн. вычисл. матем. и матем. физики. 2008. 48, N 2. 237-254.
  26. Васильев И.Л., Климентова К.Б., Орлов А.В. Параллельный глобальный поиск равновесных ситуаций в биматричных играх // Вычислительные методы и программирование. 2007. 8, N 2. 84-94.

Published

20-10-2011

How to Cite

Груздева Т.В., Стрекаловский А.С., Орлов А.В., Дружинина О.В. Nonsmooth Minimization Problems for the Difference of Two Convex Functions // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2011. 12. 384-396

Issue

Section

Section 1. Numerical methods and applications