ИСТИНА

На данный момент хорошо известно, что если множество множителей Лагранжа, отвечающих стационарной точке задачи условной оптимизации, состоит более чем из одного элемента, это множество часто включает в себя особые множители, называемые критическими. Это специальное подмножество множества множителей Лагранжа во многом определяет свойства устойчивости рассматриваемого решения при параметрических возмущениях, а также поведение ньютоновских методов вблизи таких решений: именно критические множители «ответственны» за разрушение свойств сверхлинейной сходимости ньютоновских методов в случае неединственности множителя. Критичность множителя Лагранжа можно эквивалентным образом охарактеризовать как нарушение в его окрестности локальной липшицевой оценки расстояния до множества прямо-двойственных решений через естественную невязку системы условий первого порядка оптимальности, и это понимание критичности служит основой для распространения данной концепции на более общие вариационные задачи, начиная с общих систем нелинейных уравнений без какой-либо прямо-двойственной оптимизационной специфики. Все это представляет особый интерес в тех случаях, когда рассматриваемое решение является неизолированным (и, в частности, особым). Проект посвящен изучению особых свойств устойчивости критических решений вариационных задач, а также изучению влияния критичности на поведение ньютоновских и других численных методов, и, в частности, объяснению и разработке средств подавления наблюдаемого на практике эффекта притяжения ньютоновских методов к критическим решениям из широких областей начальных точек. Эти построения должны стать основой для разработки действительно эффективных практических алгоритмов поиска неизолированных решений.

At the moment it is well known that if the set of Lagrange multipliers corresponding to the stationary point of the conditional optimization problem consists of more than one element, this set often includes singular factors called critical ones. This special subset of the set of Lagrange multipliers largely determines the stability properties of the solution under parametric perturbations, and also the behavior of Newtonian methods near such solutions: it is the critical factors that are "responsible" for the destruction of the properties of the superlinear convergence of Newtonian methods in the case of nonuniqueness of the factor. The criticality of the Lagrange multiplier can be described in an equivalent way as a violation in its neighborhood of a local Lipschitz estimate of the distance to a set of direct dual solutions via the natural discrepancy of the first order optimality system, and this understanding of criticality serves as the basis for extending this concept to more general variational problems, systems of non-linear equations without any direct-dual optimization specificity. All this is of special interest in those cases when the considered solution is not isolated (and, in particular, special). The project is devoted to the study of the special stability properties of critical solutions of variational problems, as well as to the study of the influence of criticality on the behavior of Newtonian and other numerical methods, and in particular to the explanation and development of means for suppressing the effect observed in practice of attraction of Newtonian methods to critical solutions from wide ranges of initial points. These constructions should become the basis for developing really effective practical algorithms for searching for non-isolated solutions.

1. Концепция критических решений систем нелинейных уравнений и более общих вариационных задач, включая комплементарные задачи, системы необходимых условий первого порядка для решений задач оптимизации и равновесных задач, и др. Теория устойчивости критических решений и теория локальной сходимости ньютоновских и других методов к таким решениям. 2. «Практичные» численные методы решения нелинейных уравнений и более общих вариационных задач, позволяющие подавлять эффект притяжения к критическим решениям, и сохраняющие высокую скорость сходимости в случае неизолированных решений. 3. «Практичные» методы поиска решений задач конкретных классов, в которых естественным образом возникают неизолированные решения: различных равновесных задач, включая обобщенное равновесие Нэша; задач оптимизации с равновесными ограничениями; и др.

Понятие критического множителя Лагранжа было введено в работе Измаилов А.Ф. Об аналитической и вычислительной устойчивости критических множителей Лагранжа // ЖВМ и МФ. 2005. Т. 45, N 6. С. 966-982. Там же был впервые отмечен эффект притяжения ньютоновских методов к критическим множителям Лагранжа. Дальнейшие результаты такого рода были получены в следующих работах: Izmailov A.F., Solodov M.V. On attraction of Newton-type iterates to multipliers violating second-order sufficiency conditions // Math. Program. 2009. V. 117, N 1-2. P. 271-304. Izmailov A.F., Solodov M.V. Examples of dual behaviour of Newton-type methods on optimization problems with degenerate constraints // Comput. Optim. Appl. 2009. V. 42, N 2. P. 231-264. Izmailov A.F., Solodov M.V. On attraction of linearly constrained Lagrangian methods and of stabilized and quasi-Newton SQP methods to critical multipliers // Math. Program. 2011. 126. N 2. 231-257. Измаилов А.Ф. О предельных свойствах двойственных траекторий метода множителей Лагранжа // ЖВМ и МФ. 2011. 51. N 1. 3-23. Измаилов А.Ф., Крылова А.М., Усков Е.И. Гибридная глобализация стабилизированного метода последовательного квадратичного программирования // Теоретические и прикладные задачи нелинейного анализа. М. ВЦ РАН. 2011. С. 47-66. Измаилов А.Ф., Усков Е.И. О влиянии критических множителей Лагранжа на скорость сходимости метода множителей // ЖВМ и МФ. 2012. Т. 52, N 11. С. 1959-1975. Теоретические результаты об устойчивости критических множителей Лагранжа были получены в следующих работах: Izmailov A.F. Solution sensitivity for Karush-Kuhn-Tucker systems with nonunique Lagrange multipliers // Optimization. 2010. V. 59, N 5. P. 747-775. Izmailov A.F., Kurennoy A.S., Solodov M.V. A note on upper Lipschitz stability, error bounds, and critical multipliers for Lipschitz-continuous KKT systems // Math. Program. 2013. V. 142. P. 591-604.