ИСТИНА |
Войти в систему Регистрация |
|
ИСТИНА ИНХС РАН |
||
На данный момент хорошо известно, что если множество множителей Лагранжа, отвечающих стационарной точке задачи условной оптимизации, состоит более чем из одного элемента, это множество часто включает в себя особые множители, называемые критическими. Это специальное подмножество множества множителей Лагранжа во многом определяет свойства устойчивости рассматриваемого решения при параметрических возмущениях, а также поведение ньютоновских методов вблизи таких решений: именно критические множители «ответственны» за разрушение свойств сверхлинейной сходимости ньютоновских методов в случае неединственности множителя. Критичность множителя Лагранжа можно эквивалентным образом охарактеризовать как нарушение в его окрестности локальной липшицевой оценки расстояния до множества прямо-двойственных решений через естественную невязку системы условий первого порядка оптимальности, и это понимание критичности служит основой для распространения данной концепции на более общие вариационные задачи, начиная с общих систем нелинейных уравнений без какой-либо прямо-двойственной оптимизационной специфики. Все это представляет особый интерес в тех случаях, когда рассматриваемое решение является неизолированным (и, в частности, особым). Проект посвящен изучению особых свойств устойчивости критических решений вариационных задач, а также изучению влияния критичности на поведение ньютоновских и других численных методов, и, в частности, объяснению и разработке средств подавления наблюдаемого на практике эффекта притяжения ньютоновских методов к критическим решениям из широких областей начальных точек. Эти построения должны стать основой для разработки действительно эффективных практических алгоритмов поиска неизолированных решений.
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.
МГУ имени М.В.Ломоносова | Координатор |
грант РФФИ |
# | Сроки | Название |
1 | 1 января 2017 г.-31 декабря 2017 г. | Критические решения вариационных задач |
Результаты этапа: Получена новая теорема о накрывании для нелинейных отображений на выпуклом замкнутом конусе при возможном невыполнении условия регулярности Робинсона, допускающая возможную неизолированность решения. Получены условия, гарантирующие, что накрываемое множество является широким. Эти результаты были применены для анализа устойчивости возможно неизолированных решений вариационных задач различных классов: комплементарных задач, систем Каруша-Куна-Таккера, задач поиска обобщенных равновесий Нэша. Получены условия локальной сходимости (возмущенных) ньютоновских методов к критическому решению системы нелинейных уравнений из широких областей начальных приближений, допускающие неизолированность рассматриваемого решения. Предложен метод последовательно квадратичного программирования, стабилизированный вдоль подпространства, локально подавляющий эффект притяжения к критическим множителям Лагранжа, и имеющий преимущества перед известными стратегиями двойственной стабилизации. Разработана модификации глобализованного метода Ньютона с подзадачами линейного программирования, позволяющая в случае кусочно-гладких уравнений избегать сходимости к стационарным точкам для ветвей, не являющимся решениями. | ||
2 | 1 января 2018 г.-31 декабря 2018 г. | Критические решения вариационных задач |
Результаты этапа: 1. Предложена концепция критичности решения для уравнений с ограничениями в виде включения в выпуклое замкнутое множество, а также для связанных с этой постановкой комплементарных и равновесных задач. С одной стороны, эта концепция имеет в своей основе нарушение фундаментального свойства метрической субрегулярности, т.е. локальной липшицевой оценки расстояния до множества решений. С другой стороны, она активно использует понимание критичности решения, полученное ранее для обычных уравнений (без ограничений), а еще ранее для множителей Лагранжа. Получены новые результаты об устойчивости критических решений задач указанных классов, а также о типичной неустойчивости некритических решений. 2. Показано, что при естественных предположениях, которые могут выполняться только в критических решениях нелинейных уравнений с ограничениями, ньютоновские методы широкого класса имеют тенденцию сходиться именно к этому решению, даже если оно неизолировано. Установлена точная линейная оценка скорости сходимости. Примечательно, что помимо базового метода Ньютона, эти результаты применимы к ряду методов, снабженных специальными стабилизирующими механизмами, и предназначенных именно для случая неизолированных решений. Тем самым показано, что замечательные свойства локальной сходимости таких методов часто не проявляются на практике из-за притяжения к критическим решениям, где теории их сходимости не работают. Типичными объектами применения данных результатов являются переформулировки комплементарных задач. 3. Проведены эксперименты, демонстрирующие, что локальный метод Левенберга-Марквардта для системы Лагранжа задачи оптимизации с неединственным множителем, отвечающим данной стационарной точке, может существенно превосходить даже методы специально разработанные для поиска таких решений таких систем (такие, как стабилизированный метод последовательного квадратичного программирования). Предложена оптимизационная схема глобализации сходимости метода, которая, в отличие от его традиционных глобализаций, имеет большую тенденцию сходимости к решениям задачи оптимизации, а не к любым ее стационарным точкам. Обоснована глобальная сходимость и сверхлинейная скорость сходимости предложенного алгоритма в слабых предположениях. Теоретические результаты подтверждены вычислительным экспериментом. | ||
3 | 1 января 2019 г.-31 декабря 2019 г. | Критические решения вариационных задач |
Результаты этапа: 1. Разработаны новые средства подавления эффекта притяжения ньютоновских методов к критическим решениям нелинейных уравнений, без ограничений и с ограничениями. Речь идет о методах, использующих специальные модификации приближений, генерируемых стандартными алгоритмами. Разработаны экономичные способ вычисления таких модификаций, которые, с одной стороны, согласованы с качеством имеющегося приближения, а с другой стороны, позволяют удерживать модифицированные приближения «на отдалении» от критических решений. Полученные таким образом алгоритмы обладают сверхлинейной сходимостью, несмотря на наличие критических решений. 2. Предложены способы глобализации сходимости модифицированных методов. 3. Разработаны способы ускорения сходимости ньютоновских методов к критическим решениям нелинейных уравнений. 4. Разработанных в рамках проекта методы реализованы для конкретных классов задач, в которых естественным образом возникают неизолированные (прямые или двойственные) решения: для различных равновесных задач, включая обобщенное равновесие Нэша; для задач оптимизации с равновесными ограничениями; и др. |
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".