mathematicsВестник российских университетов. МатематикаRussian Universities Reports. Mathematics2686-96672782-3342Тамбовский государственный университет имени Г.Р. Державина10.20310/1810-0198-2019-24-126-150-165mathematics-263Research ArticleСТАТЬИARTICLESГибридная глобализация сходимости метода последовательного квадратичного программирования, стабилизированного вдоль подпространстваHybrid globalization of convergence of subspace-stabilized sequential quadratic programming methodЖурбенкоНиколай ГеоргиевичZhurbenkoNikolay G.zhurbnick@gmail.comИзмаиловАлексей ФеридовичIzmailovAlexey F.izmaf@ccas.ruУсковЕвгений ИвановичUskovEvgeniy I.akurennoy@cs.msu.ruИнститут кибернетики им. В. М. Глушкова НАН УкраиныРоссияV. M. Glushkov Institute of Cybernetics of NAS of UkraineRussian FederationФГБОУ ВО ≪Московский государственный университет им. М. В. Ломоносова≫РоссияLomonosov Moscow State UniversityRussian FederationФГБОУ ВО ≪Тамбовский государственный университет им. Г.Р. Державина≫РоссияDerzhavin Tambov State UniversityRussian Federation20190307201924126150165Copyright © Журбенко Н.Г., Измаилов А.Ф., Усков Е.И., 20192019Журбенко Н.Г., Измаилов А.Ф., Усков Е.И.Zhurbenko N.G., Izmailov A.F., Uskov E.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://mathematics.elpub.ru/jour/article/view/263

Локальная сверхлинейная сходимость стабилизированного метода последовательного квадратичного программирования устанавливается при очень слабых предположениях, не включающих в себя никакие условия регулярности ограничений. Однако, все попытки глобализации сходимости этого метода неминуемо сталкиваются с принципиальными трудностями, связанными с поведением этого метода при относительной удаленности текущей итерации от решений. А именно, стабилизированный метод последовательного квадратичного программирования имеет тенденцию генерировать длинные последовательности коротких шагов перед тем, как проявляется его сверхлинейная сходимость. В связи с этим был предложен метод последовательного квадратичного программирования, стабилизированный вдоль подпространства, обладающий лучшим «полулокальным» поведением, а значит, лучше приспособленный для разработки на его основе практических алгоритмов. В данной работе предлагаются два способа гибридной глобализации сходимости этого метода: алгоритм с возвратами и алгоритм с рекордами. Приводятся теоретические результаты о глобальной сходимости и скорости сходимости данных алгоритмов, а также результаты сравнительного численного тестирования.

Local superlinear convergence of the stabilized sequential quadratic programming method is established under very weak assumptions not involving any constraint qualification conditions. However, all attempts to globalize convergence of this method inevitably face principal difficulties related to the behavior of this method when the iterates are still relatively far from solutions. Specifically, the stabilized sequential quadratic programming method has a tendency to generate long sequences of short steps before its superlinear convergence shows up. To that end, the so-called subspace-stabilized sequential quadratic programming method has been proposed, demonstrating better “semi-local” behavior, and hence, more suitable for development of practical algorithms on its basis. In this work we propose two techniques for hybrid globalization of convergence of this method: algorithm with backups, and algorithm with records.We provide theoretical results on convergence and rate of convergence of these algorithms, as well as some results of their numerical testing.

последовательное квадратичное программированиевырожденные решениянекритический множитель Лагранжадвойственная стабилизацияглобализация сходимостиsequential quadratic programmingdegenerate solutionsnoncritical Lagrange multiplierdual stabilizationglobalization of convergenceReferencesA. F. Izmailov, M. V. Solodov, Newton-Type Methods for Optimization and Variational Problems, Springer Series in Operations Research and Financial Engineering, Cham: Springer, 2014.A. F. Izmailov, M. V. Solodov, Newton-Type Methods for Optimization and Variational Problems, Springer Series in Operations Research and Financial Engineering, Cham: Springer, 2014.А. Ф. Измаилов, М. В. Солодов, Численные методы оптимизации, 2-е изд., перераб. и доп., Физматлит, М., 2008.А. Ф. Измаилов, М. В. Солодов, Численные методы оптимизации, 2-е изд., перераб. и доп., Физматлит, М., 2008.S. J. Wright, “Superlinear convergence of a stabilized SQP method to a degenerate solution”, Comput. Optim. Appl., 11 (1998), 253-275.S. J. Wright, “Superlinear convergence of a stabilized SQP method to a degenerate solution”, Comput. Optim. Appl., 11 (1998), 253-275.A. F. Izmailov, M. V. Solodov, “Stabilized SQP revisited”, Math. Program., 133 (2012), 93-120.A. F. Izmailov, M. V. Solodov, “Stabilized SQP revisited”, Math. Program., 133 (2012), 93-120.А. Ф. Измаилов, А. М. Крылова, Е. И. Усков, “Гибридная глобализация стабилизированного метода последовательного квадратичного программирования”, Теоретические и прикладные задачи нелинейного анализа, ВЦ РАН, М., 2011, 47-66.А. Ф. Измаилов, А. М. Крылова, Е. И. Усков, “Гибридная глобализация стабилизированного метода последовательного квадратичного программирования”, Теоретические и прикладные задачи нелинейного анализа, ВЦ РАН, М., 2011, 47-66.P. E. Gill, D.P. Robinson, “A primal-dual augmented Lagrangian”, Comput. Optim. Appl., 51 (2012), 1-25.P. E. Gill, D.P. Robinson, “A primal-dual augmented Lagrangian”, Comput. Optim. Appl., 51 (2012), 1-25.P. E. Gill, D.P. Robinson, “A globally convergent stabilized SQP method”, SIAM J. Optim. Appl., 23 (2013), 1983-2010.P. E. Gill, D.P. Robinson, “A globally convergent stabilized SQP method”, SIAM J. Optim. Appl., 23 (2013), 1983-2010.D. Fernandez, E. A. Pilotta, G. A. Torres, “An inexact restoration strategy for the globalization of the sSQP method”, Comput. Optim. Appl., 54 (2013), 595-617.D. Fernandez, E. A. Pilotta, G. A. Torres, “An inexact restoration strategy for the globalization of the sSQP method”, Comput. Optim. Appl., 54 (2013), 595-617.A. F. Izmailov, M. V. Solodov, E. I. Uskov, “Combining stabilized SQP with the augmented Lagrangian algorithm”, Comput. Optim. Appl., 62 (2015), 33-73.A. F. Izmailov, M. V. Solodov, E. I. Uskov, “Combining stabilized SQP with the augmented Lagrangian algorithm”, Comput. Optim. Appl., 62 (2015), 33-73.A. F. Izmailov, M. V. Solodov, E. I. Uskov, “Globalizing stabilized sequential quadratic programming method by smooth primal-dual exact penalty function”, J. Optim. Theory. Appl., 69 (2016), 148-178.A. F. Izmailov, M. V. Solodov, E. I. Uskov, “Globalizing stabilized sequential quadratic programming method by smooth primal-dual exact penalty function”, J. Optim. Theory. Appl., 69 (2016), 148-178.P. E. Gill, V. Kungurtsev, D.P. Robinson, “A stabilized SQP method: global convergence”, IMA Journal of Numerical Analysis, 37 (2017), 407-443.P. E. Gill, V. Kungurtsev, D.P. Robinson, “A stabilized SQP method: global convergence”, IMA Journal of Numerical Analysis, 37 (2017), 407-443.P. E. Gill, V. Kungurtsev, D.P. Robinson, “A stabilized SQP method: superlinear convergence”, Math. Program., 163 (2017), 369-410.P. E. Gill, V. Kungurtsev, D.P. Robinson, “A stabilized SQP method: superlinear convergence”, Math. Program., 163 (2017), 369-410.A. F. Izmailov, E. I. Uskov, “Subspace-stabilized sequential quadratic programming”, Comput. Optim. Appl., 67 (2017), 129-154.A. F. Izmailov, E. I. Uskov, “Subspace-stabilized sequential quadratic programming”, Comput. Optim. Appl., 67 (2017), 129-154.E. M. E. Mostafa, L. N. Vicente, S. J. Wright, “Numerical behavior of a stabilized SQP method for degenerate NLP problems”, Global Optimization and Constraint Satisfaction., Lecture Notes in Computer Science 2861., Springer, Berlin, 2003, 123-141.E. M. E. Mostafa, L. N. Vicente, S. J. Wright, “Numerical behavior of a stabilized SQP method for degenerate NLP problems”, Global Optimization and Constraint Satisfaction., Lecture Notes in Computer Science 2861., Springer, Berlin, 2003, 123-141.A. F. Izmailov, M. V. Solodov, “Newton-type methods for optimization problems without constraint qualifications”, SIAM J. Optim., 15 (2004), 210-228.A. F. Izmailov, M. V. Solodov, “Newton-type methods for optimization problems without constraint qualifications”, SIAM J. Optim., 15 (2004), 210-228.J. Nocedal, S. J. Wright, Numerical Optimization, Second ed., Springer, New York, 2006.J. Nocedal, S. J. Wright, Numerical Optimization, Second ed., Springer, New York, 2006.A. F. Izmailov, M. V. Solodov, “On attraction of Newton-type iterates to multipliers violating second-order sufficiency conditions”, Math. Program., 117 (2009), 271-304.A. F. Izmailov, M. V. Solodov, “On attraction of Newton-type iterates to multipliers violating second-order sufficiency conditions”, Math. Program., 117 (2009), 271-304.E. D. Dolan, J. J. More, “Benchmarking optimization software with performance profiles”, Math. Program., 91 (2002), 201-213.E. D. Dolan, J. J. More, “Benchmarking optimization software with performance profiles”, Math. Program., 91 (2002), 201-213.

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