vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2019-55-3-309-318vestifm-400Research ArticleМАТЕМАТИКАMATHEMATICSК условию R-регулярности в математическом программированииError Bound property in mathematical programmingБережновД. Е.BerezhnovD. E.

Бережнов Даниил Евгеньевич – ассистент, кафедра информатики

ул. П. Бровки, 6, 220013, г. Минск, Республика Беларусь

Daniil E. Berezhnov – Assistant of the Department of Informatics

6, P. Brovka Str., 220013, Minsk, Republic of Belarus

daniilberezhnov@gmail.comМинченкоЛ. И.MinchenkoL. I.

Минченко Леонид Иванович – доктор физико-математических наук, профессор, профессор кафедры информатики

ул. П. Бровки, 6220013, г. Минск, Республика Беларусь

Leonid I. Minchenko – Dr. Sc. (Physics and Mathematics), Professor, Professor of the Department of Informatics

6, P. Brovka Str., 220013, Minsk, Republic of Belarus

inform@bsuir.byБелорусский государственный университет информатики и радиоэлектроникиBelarusian State University of Informatics and Radioelectronics201904102019553309318Copyright © Бережнов Д.Е., Минченко Л.И., 20192019Бережнов Д.Е., Минченко Л.И.Berezhnov D.E., Minchenko L.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/400

Исследуется условие R-регулярности (Error Bound) в задачах математического программирования, которое играет важную роль в анализе сходимости численных алгоритмов оптимизации, что подтверждается многочисленными публикациями, и в то же время является достаточно общим условием регулярности (constraint qualification), обеспечивающим справедливость необходимых условий оптимальности Куна – таккера в задачах математического программирования. В статье представлены новые достаточные условия наличия R-регулярности в задачах математического программирования, а также показано, что известные необходимые условия не являются достаточными. Полученные достаточные условия позволяют доказать наличие R-регулярности у довольно широкого класса множеств, в том числе и у таких, для которых не выполняются другие известные условия.

This article is devoted to the Error Bound property (also named R-regularity) in mathematical programming problems. This property plays an important role in analyzing the convergence of numerical optimization algorithms, a topic covered by multiple publications, and at the same time it is a relatively generic constraint qualification that guarantees the satisfaction of the necessary Kuhn – Tucker optimality conditions in mathematical programming problems. In the article, new sufficient conditions for the error bound property are described, and it’s also shown that several known necessary conditions are insufficient. The sufficient conditions obtained can be used to prove the regularity of a large class of sets including sets that cannot be proven regular by other known constraints.

математическое программированиеусловия регулярностиError Boundmathematical programmingconstraint qualificationsError BoundReferencesHoffman, 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.027Hoffman A. J. On approximate solutions of systems of linear inequalities. Journal of Research of the National Bureau of Standards, 1952, vol. 49, no. 4, pp. 263–265. https://doi.org/10.6028/jres.049.027Robinson, 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/0712056Robinson S. M. Stability theory for systems of inequality constraints. Part I: linear systems. SIAM Journal on Numerical Analysis, 1975, vol. 12, no. 5, pp. 754–769. https://doi.org/10.1137/0712056Федоров, В. В. Численные методы максимина / В. В. Федоров. – М.: Наука, 1979. – 280 c.Fedorov V. V. Numerical Methods of Maximin. Moscow, Nauka Publ., 1979. 280 p. (in Russian).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-6Ioffe A. D. Regular points of Lipschitz functions. Transactions of the American Mathematical Society, 1979, vol. 251, pp. 61–69. https://doi.org/10.1090/s0002-9947-1979-0531969-6Luderer, 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-3Luderer B., Minchenko L., Satsura T. Multivalued Analysis and Nonlinear Programming Problems with Perturbations. Dordrecht, Kluwer Acad. Publ., 2002, 220 p. https://doi.org/10.1007/978-1-4757-3468-3Pang 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/bf02614322Pang J. S. Error bounds in mathematical programming. Mathematical Programming, 1997, vol. 79, no. 1–3, pp. 299– 332. https://doi.org/10.1007/bf02614322Wu, 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/s1052623400371557Wu Z. L., Ye J. J. Sufficient conditions for error bounds. SIAM Journal on Optimization, 2001, vol. 12, no. 2, pp. 421–435. https://doi.org/10.1137/s1052623400371557Bosch, 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-5Bosch P., Jourani A., Henrion R. Sufficient conditions for error bounds and applications. Applied Mathematics and Optimization, 2004, vol. 50, no. 2, pp. 161–181. https://doi.org/10.1007/s00245-004-0799-5Error 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-0Fabian M. J., Henrion R., Kruger A. Y., Outrata J. V. Error Bounds: Necessary and Sufficient Conditions. Set-Valued and Variational Analysis, 2010, vol. 18, no. 2, pp. 121–149. https://doi.org/10.1007/s11228-010-0133-0Minchenko, 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/02331930902971377Minchenko L. I., Stakhovski S. M. On relaxed constant rank regularity condition in mathematical programming. Optimization, 2011, vol. 60, no. 4, pp. 429–440. https://doi.org/10.1080/02331930902971377Minchenko, 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/090761318Minchenko L., Stakhovski S. Parametric nonlinear programming problems under relaxed constant rank regularity condition. SIAM Journal on Optimization, 2011, vol. 21, no. 1, pp. 314–332. https://doi.org/10.1137/090761318Minchenko, 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-0Minchenko L., Tarakanov A. On error bounds for quasinormal programs. Journal of Optimization Theory and Applications, 2011, vol. 148, no. 3, pp. 571–579. https://doi.org/10.1007/s10957-010-9768-0Минченко, Л. И. К обобщению условия регулярности Мангасаряна – Фромовица / Л. И. Минченко, С. М. Стаховский // Докл. БГУИР. – 2010. – № 8. – С. 104–109.Minchenko L. I., Stakhovskii S. M. On the generalization of the Mangasarian-Fromovitz constraint. Doklady BGUIR, 2010, vol. 8, pp. 104–109 (in Russian).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-4Kruger A. Y., Minchenko L. I., Outrata J. V. On relaxing the Mangasarain–Fromovitz constaint qualication. Positivity, 2014, vol. 18, no. 1, pp. 1–17. ttps://doi.org/10.1007/s11117-013-0238-4Two 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/110843939Andreani R., Haeser G., Schuverdt M. L., Silva P. J. S. Two new weak constraint qualifications and applications. SIAM Journal on Optimization, 2012, vol. 22, no. 3, pp. 1109–1125. https://doi.org/10.1137/110843939Guo, 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-6Guo L., Zhang J., Lin G.-H. New results on constraint qualifications for nonlinear extremum problems and extensions. Journal of Optimization Theory and Applications, 2014, vol. 163, no. 3, pp. 737–754. https://doi.org/10.1007/s10957-013-0510-6Ye, 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-9Ye J. J., Zhou J. Verifiable sufficient conditions for the error bound property of second-order cone complementarity problems. Mathematical Programming, 2018, vol. 171, no. 1–2, pp. 361–395. https://doi.org/10.1007/s10107-017-1193-9Mangasarian, 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-1Mangasarian O. L., Fromovitz S. The Fritz-John necessary optimality conditions in presence of equality and inequality constraints. Journal of Mathematical Analysis and Applications, 1967, vol. 17, no. 1, pp. 37–47. https://doi.org/10.1016/0022-247x(67)90163-1Janin, R. Direction derivative of the marginal function in nonlinear programming / R. Janin // Math. Program. Study. – 1984. – Vol. 21. – P. 127–138.Janin R. Direction derivative of the marginal function in nonlinear programming. Mathematical Programming Study, 1984, vol. 21, pp. 127–138. https://doi.org/10.1007/bfb0121214Лещев, Е. А. Слабо регулярные задачи математического программирования / А. Е. Лещев, Л. И. Минченко // Вес. Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 2014. – № 2. – С. 64–70.Leshchev E. A., Minchenko L. I. Weakly regular mathematical programming problems. Vestsі Natsyianal’nai aka- demіі navuk Belarusі. Seryia fіzіka-matematychnykh navuk = Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics series, 2014, vol. 2, pp. 64–70 (in Russian).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/10556780410001709420Bertsekas D. P., Ozdaglar A. E. The relation between pseudonormality and quasiregularity in constrained optimization. Optimization Methods and Software, 2004, vol. 19, no. 5, pp. 493–506. https://doi.org/10.1080/10556780410001709420Кларк, Ф. Оптимизация и негладкий анализ / Ф. Кларк. – М.: Наука, 1988. – 280 с.Clarke F. Optimization and non-smooth analysis. New York, Willey, 1983. 280 p.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-1Mordukhovich B. S. Variational Analysis and Generalized Differentiation I. Basic Theory. Berlin, Springer, 2005. 1057 p. https://doi.org/10.1007/3-540-31247-1Rockafellar, 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-3Rockafellar R. T., Wets R. J.-B. Variational Analysis. Berlin, Springer, 1998, 749 p. https://doi.org/10.1007/978-3-642-02431-3Гороховик, В. В. Конечномерные задачи оптимизации / В. В. Гороховик. – Минск: Изд. центр БГУ, 2007. – 239 c.Gorokhovik V. V. Finite Dimensional Optimization Problems. Minsk, BSU Publishing Center, 2007. 239 p. (in Russian).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.1179300Minchenko L., Leschov A. On strong and weak second-order necessary optimality conditions for nonlinear programming. Optimization, 2016, vol. 65, no. 9, pp. 1693–1702. https://doi.org/10.1080/02331934.2016.1179300

The authors declare that there are no conflicts of interest present.