Том 25, номер 1, 2019
УДК 519.853.4
MSC: 90C26, 90C30, 90C46
DOI: 10.21538/0134-4889-2019-25-1-245-261
Полный текст статьи (Full text)
В работе рассматривается невыпуклая негладкая задача оптимизации, где целевая функция и ограничения типа равенства и неравенства заданы d.c. функциями (представимыми в виде разности выпуклых функций). При этом исходная задача редуцирована к задаче без ограничений с помощью теории точного штрафа. Затем оштрафованная задача представлена как задача d.c. минимизации без ограничений, для которой разрабатывается новый математический инструментарий в виде условий глобальной оптимальности (УГО), которые сводят невыпуклую задачу к семейству линеаризованных (выпуклых) задач. Кроме того, из полученных УГО следует негладкая форма теоремы Каруша — Куна — Таккера (ККТ) для исходной задачи. При этом УГО обладают конструктивным (алгоритмическим) свойством, позволяющим “выйти” из локальных ям и стационарных (критических) точек исходной задачи. Эффективность УГО демонстрируется примерами.
Ключевые слова: d.c. функция, точный штраф, линеаризованная задача, условия глобальной оптимальности, функция Лагранжа, множители Лагранжа, ККТ-вектор
СПИСОК ЛИТЕРАТУРЫ
1. Еремин И.И. Метод “штрафов” в выпуклом программировании // Докл. АН. 1967. Т. 173, № 4. С. 748–751.
2. Zangwill W. Non-linear programming via penalty functions // Management Science. 1967. Vol. 13. P. 344–358.
3. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. Москва: Физматлит, 1976. 192 с.
4. Васильев Ф.П. Методы оптимизации: в 2-х кн. Москва: МЦНМО, 2011. Кн. 1: 620 с.; кн. 1: 433 с.
5. Nocedal J., Wright S.J. Numerical optimization. N Y: Springer, 2006. 634 p.
6. Bonnans J.-F., Gilbert J.C., Lemar$\acute{\mathrm{e}}$chal C., Sagastiz$\acute{\mathrm{a}}$bal C.A. Numerical optimization: Theoretical and practical aspects. Berlin; Heidelberg: Springer-Verlag, 2006. 494 p.
7. Hiriart-Urruty J.-B., Lemar$\acute{\mathrm{e}}$chal C. Convex analysis and minimization algorithms. Berlin: Springer-Verlag, 1993. 418 p. doi: 10.1007/978-3-662-02796-7
8. Clarke F.H. Optimization and nonsmooth analysis. N Y: Wiley-Interscience, 1983. 308 p.
9. 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
10. 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
11. Di Pillo G., Lucidi S., Rinaldi F. A derivative-free algorithm for constrained global optimization based on exact penalty functions // J. Optim. Theory Appl. 2015. Vol. 164, no. 3. P. 862–882. doi: 10.1007/s10957-013-0487-1
12. Le Thi H.A., Huynh V.N., Dinh T.P. DC programming and DCA for general DC programs // Advanced Computational Methods for Knowledge Engineering. Advances in Intelligent Systems and Computing / eds. van T. Do, H. Thi, N. Nguyen. Cham: Springer, 2014. Vol. 282. P. 15–35. doi: 10.1007/978-3-319-06569-4_2
13. 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
14. Frontiers in global optimization / eds. C. A. Floudas, P. M. Pardalos. Dordrecht: Kluwer Acad. Publ., 2004. 604 p.
15. Horst R., Tuy H. Global optimization. Deterministic approaches. Berlin: Springer-Verlag, 1993. 730 p.
16. Tuy H. D.c. Optimization: Theory, methods and algorithms // Handbook of Global Optimization / eds. R. Horst, P.M. Pardalos. Dordrecht: Kluwer Acad. Publ., 1995. P. 149–216.
17. Rockafellar R.T. Convex analysis. Princeton: Princeton Univ. Press, 1970. 472 p.
18. Rockafellar R.T. Lagrange multipliers and optimality // SIAM Review. 1993. Vol. 35, no. 2. P. 183–238. doi: 10.1137/1035044
19. Демьянов В. Ф. Условия экстремума и вариационное исчисление. Москва: Высшая школа, 2005. 336 с.
20. Hiriart-Urruty J.-B. Generalized differentiability, duality and optimization for problems dealing with difference of convex functions // Convexity and duality in optimization. Berlin: Springer-Verlag, 1985. P. 37–69. (Lecture notes in economics and mathematical systems; vol. 256). doi: 10.1007/978-3-642-45610-7_3
21. Стрекаловский А.С. Элементы невыпуклой оптимизации. Новосибирск: Наука, 2003. 356 с.
22. Byrd R., Lopez-Calva G., Nocedal J. A line search exact penalty method using steering rules // Math. Programming. Ser. A. 2012. Vol. 133, no. 1-2. P. 39–73. doi: 10.1007/s10107-010-0408-0
23. Byrd R., Marazzi M., Nocedal J. On the convergence of Newton iterations to non-stationary points // Math. Programming. Ser. A. 2004. Vol. 99, no. 1. P. 127–148. doi: 10.1007/s10107-003-0376-8
24. Hiriart-Urruty J.-B. Optimisation et analyse convex. Paris: Presses Universitaires de France, 1998. 384 p.
25. 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. N Y: Springer, 2014. P. 465–502. doi: 10.1007/978-1-4939-0808-0_23
26. Strekalovsky A.S. Global optimality conditions for optimal control problems with functions of A.D. Alexandrov // J. Optim. Theory Appl. 2013. Vol. 159, no. 2. P. 297–321. doi: 10.1007/s10957-013-0355-z
27. Strekalovsky A.S. Global optimality conditions and exact penalization // Optim. Lett. 2017. P. 1–19. doi: 10.1007/s11590-017-1214-x
28. 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
29. 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
30. Стрекаловский А.С. О минимизации разности выпуклых функций на допустимом множестве // Журн. вычисл. математики и мат. физики. 2003. Т. 43, № 3. С. 399–409.
31. Strekalovsky A.S., Minarchenko I.M. A local search method for optimization problem with d.c. inequality constraints // Appl. Math. Modelling. 2018. Vol. 58. P. 229–244. doi: 10.1016/j.apm.2017.07.031
Поступила 5.12.2018
После доработки 8.02.2019
Принята к публикации 11.02.2019
Стрекаловский Александр Сергеевич
д-р физ.-мат. наук, профессор
зав. отделением
Института динамики систем и теории управления имени В.М. Матросова СО РАН
г. Иркутск
e-mail: strekal@icc.ru
Ссылка на статью: Стрекаловский А.С. Новые условия глобальной оптимальности в задаче c d.c. ограничениями // Тр. Ин-та математики и механики УрО РАН. 2019. Т. 25, № 1. С. 245-261.
Cite this article as: A.S. Strekalovsky. New global optimality conditions in a problem with d.c. constraints, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2019, vol. 25, no. 1, pp. 245-261.
English
A.S. Strekalovsky. New global optimality conditions in a problem with d.c. constraints
The paper addresses a nonconvex nonsmooth optimization problem with the cost function and equality and inequality constraints given by d.c. functions, i.e., functions representable as the difference of convex functions. The original problem is reduced to a problem without constraints with the help of exact penalization theory. Then the penalized problem is represented as a d.c. minimization problem without constraints, for which new mathematical tools are developed in the form of global optimality conditions (GOCs). The GOCs reduce the nonconvex problem in question to a family of linearized (convex) problems and are used to derive a nonsmooth form of the Karush–Kuhn–Tucker theorem for the original problem. In addition, the GOCs possess a constructive (algorithmic) property, which makes it possible to leave the local pits and stationary (critical) points of the original problem. The effectiveness of the GOCs is demonstrated with examples.
Keywords: d.c. function, exact penalty, linearized problem, global optimality conditions, Lagrange function, Lagrange multipliers, KKT-vector
Received December 15, 2018
Revised February 8, 2019
Accepted February 11, 2019
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
[References -> on the "English" button bottom right]
