УДК 519.853.4
MSC: 90C26, 90C30, 90C46
DOI: 10.21538/0134-4889-2023-29-3-185-209
Работа выполнена в рамках базового проекта фундаментальных исследований Минобрнауки РФ “Теоретические основы, методы и высокопроизводительные алгоритмы непрерывной и дискретной оптимизации для поддержки междисциплинарных научных исследований” (номер гос. регистрации: 121041300065-9, код проекта FWEW-2021-0003).
Полный текст статьи (Full text)
Статья переведена: ISSN 0081-5438
Proceedings of the Steklov Institute of Mathematics, 2023, Vol. 323, Suppl. 1, pp. S255–S278. (Abstract)
Рассматривается гладкая невыпуклая задача оптимизации, где ограничения равенства и неравенства и целевая функция заданы DC функциями. Сначала исходная задача сводится к задаче без ограничений с помощью теории точного штрафа И.И. Еремина; при этом целевая функция оштрафованной задачи оказывается тоже DC функцией. Далее доказываются необходимые и достаточные условия для минимизирующих последовательностей оштрафованной задачи. На этой основе предложен "теоретический метод" построения минимизирующей последовательности для оштрафованной задачи с фиксированным параметром штрафа и, кроме того, доказана сходимость метода. Исходя из известного метода локального поиска (МЛП) и его свойств, разработана новая схема глобального поиска (СГП), основанная на условиях глобальной оптимальности с варьированием штрафного параметра. При этом последовательность, построенная с использованием СГП, оказывается минимизирующей в "предельной" оштрафованной задаче, а каждый ее терм $z^{k+1}$ оказывается приближенно критическим вектором для МЛП и приближенным решением текущей оштрафованной задачи $(\mathcal{P}_k)\triangleq (\mathcal{P}_{\sigma_k})$. Наконец, при дополнительном условии "приближенной допустимости" построенная последовательность оказывается минимизирующей для исходной задачи с DC ограничениями.
Ключевые слова: DC функция, точный штраф, линеаризованная задача, минимизирующая последовательность, условия глобальной оптимальности, локальный поиск, глобальный поиск, критический вектор, разрешающая аппроксимация
СПИСОК ЛИТЕРАТУРЫ
1. Васильев Ф.П. Методы оптимизации: в 2-х кн. М.: МЦНМО, 2011. 620 с.; 433 с.
2. Васин В.В., Еремин И.И. Операторы и итерационные процессы фейеровского типа: теория и приложения. М.: Изд-во “Институт компьютерных исследований”, 2005. 199 с.
3. Демьянов В.Ф. Условия экстремума и вариационное исчисление. М.: Высшая школа, 2005. 336 с.
4. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. M.: Наука, 1982. 432 с.
5. Еремин И.И. Метод “штрафов” в выпуклом программировании // Докл. АН. 1967. Т. 173, № 4. С. 748–751.
6. Еремин И.И. О методе штрафов в выпуклом программировании // Кибернетика. 1967. № 4. С. 63–67.
7. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. М.: Физматлит, 1976. 192 с.
8. Еремин И.И., Мазуров В.Д. Нестационарные процессы математического программирования. М.: Наука, 1979. 288 с.
9. Еремин И.И. Противоречивые модели оптимального планирования. М.: Наука, 1988. 160 с.
10. Жадан В.Г. Методы оптимизации: ч. I, II. М.: МФТИ, 2015. 270 c.; 320 с.
11. Коннов И.В. Нелинейная оптимизация и вариационные неравенства. Казань: Изд-во Казан. ун-та, 2013. 508 c.
12. Стрекаловский А.С. Элементы невыпуклой оптимизации. Новосибирск: Наука, 2003. 356 с.
13. Стрекаловский А.С., Орлов А.В. Биматричные игры и билинейное программирование. М.: Физматлит, 2007. 224 с.
14. Стрекаловский А.С., Орлов А.В. Линейные и квадратично-линейные задачи двухуровневой оптимизации. Новосибирск: Изд-во СО РАН, 2019. 262 с.
15. Стрекаловский А.С. Новые условия глобальной оптимальности в задаче с d.c. ограничениями // Тр. Ин-та математики и механики УрО РАН. 2019. Т. 25, №1. С. 245–261. doi: 10.21538/0134-4889-2019-25-1-245-261
16. Стрекаловский А.С. Элементы глобального поиска в общей задаче d.c. оптимизации // Итоги науки и техники. Современная математика и ее приложения. Темат. обзоры. 2021. Т. 196. С. 114–127. doi: 10.36535/0233-6723-2021-196-114-127
17. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации : уч. пособие. 2-е изд. М.: Физматлит, 2011. 384 с.
18. Bonnans J.-F., Gilbert J.C., Lemaréchal C., Sagastizábal C.A. Numerical optimization: Theoretical and practical aspects. Berlin; Heidelberg: Springer-Verlag, 2006. 494 p.
19. Burke J. An exact penalization viewpoint of constrained optimization // SIAM J. Control Optim. 1991. Vol. 29, no. 4. P. 968–998. doi: 10.1137/0329054
20. Byrd R., Lopez-Calva G., Nocedal J. A line search exact penalty method using steering rules // Math. Progr. Ser. A. 2012. Vol. 133, no. 1–2. P. 39–73. doi: 10.1007/s10107-010-0408-0
21. Di Pillo G., Lucidi S., Rinaldi F. An approach to constrained global optimization based on exact penalty functions // J. Global Optim. 2012. Vol. 54, no. 2. P. 251–260. doi: 10.1007/s10898-010-9582-0
22. Dur M., Hiriart-Urruty J.B. Testing copositivity with the help of difference-of-convex optimization // Math. Program. Ser. B. 2013. Vol. 140, no. 1. P. 31–43. doi: 10.1007/s10107-012-0625-9
23. Floudas C.A., Pardalos P.M. (eds.) Frontiers in global optimization. Dordrecht: Kluwer Acad. Publ., 2004. 604 p.
24. Fiacco A.V., McCormick G.P. Nonlinear programming: Sequential unconstrained minimization techniques. NY: John Wiley, 1968. 210 p.
25. Gaudioso M., Gruzdeva T.V., Strekalovsky A.S. On numerical solving the spherical separability problem // J. Global Optim. 2016. Vol. 66, no. 1. P. 21–34. doi: 10.1007/s10898-015-0319-y
26. Hiriart-Urruty J.-B. Generalized differentiability, duality and optimization for problems dealing with difference of convex functions // Convexity and Duality in Optimization / ed. J. Ponstein. Ser. Lecture Notes in Economics and Math. Systems, vol. 256. Berlin: Springer-Verlag, 1985. P. 37–69. doi: 10.1007/978-3-642-45610-7_3
27. Hiriart-Urruty J.-B., Lemaréchal C. Convex analysis and minimization algorithms. Berlin: Springer-Verlag, 1993. 418 p.
28. Horst R., Tuy H. Global optimization. Deterministic approaches. Berlin: Springer-Verlag, 1993. 730 p.
29. Kruger A. Error bounds and metric subregularity // Optimization. 2015. Vol. 64, no. 1. P. 49–79. doi: 10.1080/02331934.2014.938074
30. Le Thi H.A., Pham Dinh T., Van Ngai H. Exact penalty and error bounds in DC programming // J. Global Optim. 2012. Vol. 52, no. 3. P. 509–535. doi: 10.1007/s10898-011-9765-3
31. Le Thi H.A., Huynh V.N., Dinh T.P. DC Programming and DCA for general DC programs // Advanced computational methods for knowledge engineering / eds. van T. Do, H. Thi, N. Nguyen. Ser. Advances in Intelligent Systems and Computing, vol. 282. Cham: Springer, 2014. P. 15–35. doi: 10.1007/978-3-319-06569-4_2
32. Mascarenhas W. The BFGS methods with exact line search fails for nonconvex objective functions // Math. Program. Ser. A. 2004. Vol. 99, no. 1. P. 49–61. doi: 10.1007/s10107-003-0421-7
33. Mascarenhas W. On the divergence of line search methods // Comput. Appl. Math. 2007. Vol. 26, no. 1. P. 129–169. doi: 10.1590/S0101-82052007000100006
34. Mascarenhas W. Newton’s iterates can converge to non-stationary points // Math. Program. 2008. Vol. 112, no. 2. P. 327–334. doi: 10.1007/s10107-006-0019-y
35. Nocedal J., Wright S.J. Numerical optimization. NY: Springer, 2006. 634 p.
36. Pang J.S. Three modelling paradigms in mathematical programming // Math. Program. Ser. B. 2010. Vol. 125, no. 2. P. 297–323. doi: 10.1007/s10107-010-0395-1
37. Pang J.S., Razaviyan M., Alvarado A. Computing B-stationary points of nonsmooth DC programs // Math. Oper. Res. 2016. Vol. 42, no. 1. P. 95–118. doi: 10.1287/moor.2016.0795
38. Rockafellar R.T. Convex Analysis. Princeton: Princeton Univ. Press, 1970. 472 p.
39. Strekalovsky A.S. On solving optimization problems with hidden nonconvex structures // Optimization in science and engineering / eds. T.M. Rassias, C.A. Floudas, S. Butenko. NY: Springer, 2014. P. 465–502. doi: 10.1007/978-1-4939-0808-0_23
40. Strekalovsky A.S. On local search in d.c. optimization problems // Appl. Math. Comput. 2015. Vol. 255. P. 73–83. doi: 10.1016/j.amc.2014.08.092
41. Strekalovsky A.S. Local search for nonsmooth DC optimization with DC equality and inequality // Constraints Numerical Nonsmooth Optimization: State of the Art Algorithms / eds. A.M. Bagirov, M. Gaudioso, N. Karmitsa, M.M. Makela, S. Taheri. NY: Springer Internat. Publ., 2020. P. 229–261. doi: 10.1007/978-3-030-34910-3_7
42. Strekalovsky A.S., Minarchenko I.M. A local search method for optimization problem with d.c. inequality constraints // Appl. Math. Model. 2018. Vol. 58. P. 229–244. doi: 10.1016/j.apm.2017.07.031
43. Strekalovsky A.S. Global optimality conditions in nonconvex optimization // J. Optim. Theory Appl. 2017. Vol. 173, no. 3. P. 770–792. doi: 10.1007/s10957-016-0998-7
44. Strekalovsky A.S. Global optimality conditions and exact penalization // Optim. Letters. 2019. Vol. 13, no. 3. P. 597–615. doi: 10.1007/s11590-017-1214-x
45. Strekalovsky A.S.On global optimality conditions for D.C. minimization problems with D.C. constraints // J. Appl. Numer. Optim. 2021. Vol. 3, no. 1. P. 175–196. doi: 10.23952/jano.3.2021.1.10
46. Strekalovsky A.S., Yanulevich M.V. On global search in nonconvex optimal control problems // J. Global Optim. 2016. Vol. 65, no. 1. P. 119–135. doi: 10.1007/s10898-015-0321-4
47. Tuy H. D.C. Optimization: Theory, methods and algorithms // Handbook of Global Optimization / eds. R. Horst and P. M. Pardalos. Dordrecht: Kluwer Acad. Publ., 1995. P. 149–216.
48. Zangwill W. Non-linear programming via penalty functions // Management Science. Ser. A. 1967. Vol. 13, no. 5. P. 344–358. doi: 10.1287/mnsc.13.5.344
49. Zangwill W. Nonlinear programming: a unified approach. Englewood Cliffs: Prentice-Hall, 1969. 356 p.
50. Zaslavski A.J. Exact penalty property in optimization with mixed constraints via variational analysis // SIAM J. Optim. 2013. Vol. 23, no. 1. P. 170–187. doi: 10.1137/120870840
Поступила 28.04.2023
После доработки 1.06.2023
Принята к публикации 5.06.2023
Стрекаловский Александр Сергеевич
д-р физ.-мат. наук, профессор
зав. отделением
Институт динамики систем и теории управления имени В.М. Матросова СО РАН
e-mail: strekal@icc.ru
Ссылка на статью: А.С. Стрекаловский. Минимизирующие последовательности в задаче DC оптимизации с ограничениями // Тр. Ин-та математики и механики УрО РАН. 2023. Т. 29, № 3. С. 185-209
English
A.S. Strekalovsky. Minimizing sequences in a constrained DC optimization problem
A smooth nonconvex optimization problem is considered, where the equality and inequality constraints and the objective function are given by DC functions. First, the original problem is reduced to an unconstrained problem with the help of I.I. Eremin's exact penalty theory, and the objective function of the penalized problem also turns out to be a DC function. Necessary and sufficient conditions for minimizing sequences of the penalized problem are proved. On this basis, a "theoretical method" for constructing a minimizing sequence in a penalized problem with a fixed penalty parameter is proposed and the convergence of the method is proved. The well-known local search method and its properties are used for developing a new global search scheme based on global optimality conditions with varying penalty parameter. The sequence constructed using the global search scheme turns out to be minimizing in the "limit" penalized problem, and each of its terms $z^{k+1}$ turns out to be an approximately critical vector for the local search method and an approximate solution of the current penalized problem $(\mathcal{P}_k)\triangleq (\mathcal{P}_{\sigma_k})$. Finally, under an additional condition of "approximate feasibility", the constructed sequence turns out to be minimizing for the original problem with DC constraints.
Keywords: DC function, exact penalty, linearized problem, minimizing sequence, global optimality conditions, local search, global search, critical vector, resolving approximation
Received April 28, 2023
Revised June 1, 2023
Accepted June 5, 2023
Funding Agency: The research was funded by the Ministry of Science and Higher Education of the Russian Federation within the project “Theoretical foundations, methods, and high-performance algorithms for continuous and discrete optimization to support interdisciplinary research” (no. of state registration 121041300065-9, project code FWEW-2021-0003).
Aleksandr Sergeevich Strekalovsky, Dr. Phys.-Math. Sci., Prof., Matrosov Institute for System Dynamics and Control Theory of the Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: strekal@icc.ru
Cite this article as: A.S. Strekalovsky. Minimizing sequences in a constrained DC optimization problem. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2023, vol. 29, no. 3, pp. 185–209; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2023, Vol. 323, Suppl. 1, pp. S255–S278.
[References -> on the "English" button bottom right]
