Nonsmooth minimization problems for the difference of two convex functions

Authors

  • T.V. Gruzdeva
  • A.S. Strekalovsky
  • A.V. Orlov
  • O.V. Druzinina

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.

New computational technologies

Downloads

Published

2011-10-20

Issue

Vol. 12 (2011): Issue 4.

Section

Section 1. Numerical methods and applications

Author Biographies

T.V. Gruzdeva

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

A.S. Strekalovsky

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

A.V. Orlov

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

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.