К условию R-регулярности в математическом программировании
https://doi.org/10.29235/1561-2430-2019-55-3-309-318
Аннотация
Исследуется условие R-регулярности (Error Bound) в задачах математического программирования, которое играет важную роль в анализе сходимости численных алгоритмов оптимизации, что подтверждается многочисленными публикациями, и в то же время является достаточно общим условием регулярности (constraint qualification), обеспечивающим справедливость необходимых условий оптимальности Куна – таккера в задачах математического программирования. В статье представлены новые достаточные условия наличия R-регулярности в задачах математического программирования, а также показано, что известные необходимые условия не являются достаточными. Полученные достаточные условия позволяют доказать наличие R-регулярности у довольно широкого класса множеств, в том числе и у таких, для которых не выполняются другие известные условия.
Об авторах
Д. Е. Бережнов
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
Беларусь
Бережнов Даниил Евгеньевич – ассистент, кафедра информатики
ул. П. Бровки, 6, 220013, г. Минск, Республика Беларусь
Л. И. Минченко
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
Беларусь
Минченко Леонид Иванович – доктор физико-математических наук, профессор, профессор кафедры информатики
ул. П. Бровки, 6220013, г. Минск, Республика Беларусь
Список литературы
1. Hoffman, A. J. On approximate solutions of systems of linear inequalities / A. J. Hoffman // J. Res. Natl. Bureau Stand. – 1952. – Vol. 49, № 4. – P. 263–265. https://doi.org/10.6028/jres.049.027
2. Robinson, S. M. Stability theory for systems of inequality constraints. Part I: linear systems / S. M. Robinson // SIAM J. Numer. Anal. – 1975. – Vol. 12, № 5. – P. 754–769. https://doi.org/10.1137/0712056
3. Федоров, В. В. Численные методы максимина / В. В. Федоров. – М.: Наука, 1979. – 280 c.
4. Ioffe, A. D. Regular points of Lipschitz functions / A. D. Ioffe // Trans. Am. Math. Soc. – 1979. – Vol. 251. – P. 61–69. https://doi.org/10.1090/s0002-9947-1979-0531969-6
5. Luderer, B. Multivalued Analysis and Nonlinear Programming Problems with Perturbations / B. Luderer, L. Minchenko, T. Satsura. – Dordrecht: Kluwer Acad. Publ., 2002. – 220 p. https://doi.org/10.1007/978-1-4757-3468-3
6. Pang J. S. Error bounds in mathematical programming / J. S. Pang // Math. Program. – 1997. – Vol. 79, № 1/3. – P. 299– 332. https://doi.org/10.1007/bf02614322
7. Wu, Z. L. Sufficient conditions for error bounds / Z. L. Wu, J. J. Ye // SIAM J. Optim. – 2001. – Vol. 12, № 2. – P. 421– 435. https://doi.org/10.1137/s1052623400371557
8. Bosch, P. Sufficient conditions for error bounds and applications / P. Bosch, A. Jourani, R. Henrion // Appl. Math. Optim. – 2004. – Vol. 50, № 2. – P. 161–181. https://doi.org/10.1007/s00245-004-0799-5
9. Error bounds: Necessary and sufficient conditions / M. J. Fabian [et al.] // Set-Valued and Variational Analysis. – 2010. – Vol. 18, № 2. – P. 121–149. https://doi.org/10.1007/s11228-010-0133-0
10. Minchenko, L. I. On relaxed constant rank regularity condition in mathematical programming / L. I. Minchenko, S. M. Stakhovski // Optimization. – 2011. – Vol. 60, № 4. – P. 429–440. https://doi.org/10.1080/02331930902971377
11. Minchenko, L. Parametric nonlinear programming problems under relaxed constant rank regularity condition / L. Minchenko, S. Stakhovski // SIAM J. Optim. – 2011. – Vol. 21, № 1. – P. 314–332. https://doi.org/10.1137/090761318
12. Minchenko, L. On error bounds for quasinormal programs / L. Minchenko, A. Tarakanov // J. Optim. Theory Appl. – 2011. – Vol. 148, № 3. – P. 571–579. https://doi.org/10.1007/s10957-010-9768-0
13. Минченко, Л. И. К обобщению условия регулярности Мангасаряна – Фромовица / Л. И. Минченко, С. М. Стаховский // Докл. БГУИР. – 2010. – № 8. – С. 104–109.
14. Kruger, A. Y. On relaxing the Mangasarain – Fromovitz constaint qualication / A. Y. Kruger, L. I. Minchenko, J. V. Outrata // Positivity. – 2014. – Vol. 18, №1. – P. 1–17. ttps://doi.org/10.1007/s11117-013-0238-4
15. Two new weak constraint qualifications and applications / R. Andreani [et. al.] // SIAM J. Optim. – 2012. – Vol. 22, № 3. – P. 1109–1125. https://doi.org/10.1137/110843939
16. Guo, L. New results on constraint qualifications for nonlinear extremum problems and extensions / L. Guo, J. Zhang, G.-H. Lin // J. Optim. Theory Appl. – 2014. – Vol. 163, № 3. – P. 737–754. https://doi.org/10.1007/s10957-013-0510-6
17. Ye, J. J. Verifiable sufficient conditions for the error bound property of second-order cone complementarity problems / J. J. Ye, J. Zhou // Math. Program. – 2018. – Vol. 171, № 1/2. – P. 361–395. https://doi.org/10.1007/s10107-017-1193-9
18. Mangasarian, O. L. The Fritz-John necessary optimality conditions in presence of equality and inequality constraints / O. L. Mangasarian, S. Fromovitz // J. Math. Anal. Appl. – 1967. – Vol. 17, № 1. – P. 37–47. https://doi.org/10.1016/0022-247x(67)90163-1
19. Janin, R. Direction derivative of the marginal function in nonlinear programming / R. Janin // Math. Program. Study. – 1984. – Vol. 21. – P. 127–138.
20. Лещев, Е. А. Слабо регулярные задачи математического программирования / А. Е. Лещев, Л. И. Минченко // Вес. Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 2014. – № 2. – С. 64–70.
21. Bertsekas, D. P. The relation between pseudonormality and quasiregularity in constrained optimization / D. P. Bertsekas, A. E. Ozdaglar // Optim. Methods Software. – 2004. – Vol. 19, № 5. – P. 493–506. https://doi.org/10.1080/10556780410001709420
22. Кларк, Ф. Оптимизация и негладкий анализ / Ф. Кларк. – М.: Наука, 1988. – 280 с.
23. Mordukhovich, B. S. Variational Analysis and Generalized Differentiation I. Basic Theory / B. S. Mordukhovich. – Berlin: Springer, 2005. – 1057 p. https://doi.org/10.1007/3-540-31247-1
24. Rockafellar, R. T. Variational Analysis / R. T. Rockafellar, R. J.-B. Wets. – Berlin: Springer, 1998. – 749 p. https://doi.org/10.1007/978-3-642-02431-3
25. Гороховик, В. В. Конечномерные задачи оптимизации / В. В. Гороховик. – Минск: Изд. центр БГУ, 2007. – 239 c.
26. Minchenko, L. On strong and weak second-order necessary optimality conditions for nonlinear programming / L. Minchenko, A. Leschov // Optimization. – 2016. – Vol. 65, № 9. – P. 1693–1702. https://doi.org/10.1080/02331934.2016.1179300
Рецензия
Просмотров: 964
Послать статью по эл. почте 