ИСТИНА |
Войти в систему Регистрация |
|
ИСТИНА ИНХС РАН |
||
Распространение концепции критического решения и связанных с ней теорий на более общие и новые классы вариационных задач, включая уравнения с неполиэдральными ограничениями, имеющие важные приложения к полуопределенным и конусным комплементарным задачам, а также на негладкие, полугладкие, кусочно-гладкие ураневния (с ограничениями), и уравнения со локально липшицевой первой производной, но возможно без вторых производных. Применение полученных результатов для исследования оценок расстояния до решений и поведения ньютоновских методов для задач оптимизации с комплементарными ограничениями, с исчезающими ограничениями, задач поиска обобщенного равновесия Нэша, других важных классов задач.
The concept of a critical solution of smooth (constrained) nonlinear equations, constrained optimization problems, and complementarity problems, proved to be very useful for understanding the stability pattern of singular (and in particular nonisolated) solutions, and the behavior of Newton-type methods near them. The project aims at extensions of this concept and the related theories to more general and new variational problem classes, including equations with non-polyhedral constraints, with important applications to semidefinite and cone complementarity problems. Another direction of devlopment of criticality concept is concerned with reducing smoothness assumptions, in order to cover nonsmooth, semismooth, and piecewice smooth (constrained) equations, and equations with locally Lipschitzian first derivatives but possibly without second derivatives. This will provide unified tools for treating error bounds and Newton-type methods for mathematical programs with complementarity constraints, with vanishing constraints, generalized Nash equilbrium problems, and other important problem classes.
1. Концепция критического решения и разработка соответствующих теорий устойчивости и локальной сходимости ньютоновских методов для новых классов вариационных задач, включая уравнения с неполиэдральными ограничениями. Научная и прикладная значимость этих результатов связана, в частности, с потенциальными приложениями к полуопределенным и конусным комплементарным задачам. 2. Концепция критического решения и разработка соответствующих теорий устойчивости и локальной сходимости для негладких, полугладких, кусочно-гладких уравнения (с ограничениями), и уравнений со локально липшицевой первой производной, но возможно без вторых производных. Эти результаты дадут универсальные средства для работы с различными переформулировками систем уравнений и неравенств, включающих условия комплементарности. 3. Применение полученных результатов для исследования оценок расстояния до решений и поведения ньютоновских методов для задач оптимизации с комплементарными ограничениями, с исчезающими ограничениями, задач поиска обобщенного равновесия Нэша, других важных классов задач.
1. Получены новые результаты о накрывании для нелинейных отображений на замкнутом выпуклом множестве при возможном невыполнении условия регулярности Робинсона, a также соответствующие результаты об устойчивости решений нелинейных уравнений с ограничениями вида включения в произвольное множество с указанными свойствами. Предложены более слабые условия, гарантирующие устойчивость данного решения по отношению к широким классам возмущений, или иными словами гарантирующие свойство накрывания большого множества. В отличие от известных результатов такого рода, здесь не используются предположения коничности множества, что допускает значительно более широкий круг приложений. В основе полученных результатов лежат соответствующие обобщения концепции 2-регулярности, недавние результаты о точках совпадения отображений метрических пространств, а также новая конструкция внутренней аппроксимации касательного конуса к выпуклому множеству. Научная и прикладная значимость этих результатов связана, в частности, с потенциальными приложениями к полуопределенным и конусным комплементарным задачам. 2. Получен утвердительный ответ на давний открытый вопрос нелинейного анализа относительно существования непрерывного однозначного селектора у правого обратного к локально липшицевому отображению. Более того, в получен более общий результат, дающий условия существования непрерывного селектора не только локально, но и на заданном шаре с центром в рассматриваемой точке. Наконец, устремлением радиуса этого шара к бесконечности, получена глобальная теорема об обратной функции, которая содержит (по существу) известную теорему Адамара о глобальном гомеоморфизме для гладких отображений и более общую теорему Пурсо для локально липшицевых отображений. 3. Разработаны новые способы преодоления негативного влияния притяжения ньютоновских методов к критическим решениям на скорость сходимости прямо-двойственных ньютоновских методов. Независимо от конкретного рассматриваемого метода, для задач оптимизации с ограничениями-равенствами предлагается новая локальная техника подавления притяжения к критическим множителям Лагранжа. Подход состоит в замене двойственных приближений, генерируемых методом, специальной функцией прямых приближений. При некоторых естественных предположениях эта функция дает аппроксимацию множителя Лагранжа, качество которой согласуется с расстоянием от прямого приближения до соответствующей стационарной точки, и при этом должным образом отстоящую от рассматриваемого критического множителя Лагранжа. Ускоряющий эффект этой техники демонстрируется вычислительным экспериментом для стабилизированного метода последовательного квадратичного программирования, а также метода Левенберга-Марквардта и метода Ньютона с подзадачами линейного программирования. 4. Получены результаты об асимптотическом принятии полного ньютоновского шага при сходимости глобализованного одномерным поиском метода Ньютона к критическим решениям нелинейных уравнений. На этой основе получены результаты об асимптотическом принятии настоящей матрицы Гессе функции Лагранжа и полного шага методом последовательного квадратичного программирования для задачи оптимизации с ограничениями-равенствами, глобализованным одномерным поиском для негладкой точной штрафной функции. Анализ основан на условии 2-регулярности по направлениям из подпространства нулей первой производной, которое может естественным образом выполняться в особых (и даже неизолированных) решениях, которые являются критическими. Ключевым ингредиентом анализа является тонкая характеризация шага метода Ньютона в рассматриваемых обстоятельствах. Данные результаты позволяют обоснованно применять в сочетании с глобализацией сходимости известные техники ускорения сходимости ньютоновских методов к особым решениям, такие, как экстраполяция и оверрелаксация. 5. Предложены обобщения концепции критического решения и связанных с ней теоретических результатов об оценках расстояния на негладкие уравнения, в том числе с дополнительными ограничениями. Получены характеризации оценок расстояния до множества решений через инструментарий обобщенного дифференцирования и средства вариационного анализа. 6. Установлены условия локальной сходимости широких классов кусочных ньютоновских методов к особым решениям кусочно-гладких уравнений из широких областей начальных точек, а также условия асимптотического принятия полного шага глобализованными одномерным поиском версиями таких методов. Выявляемый при этом специальный характер линейной локальной сходимости данных методов к критическим решениям дает возможности для повышения этой скорости. Рассмотрены приложения полученных результатов к различным переформулировкам комплементарных задач: негладким без ограничений (на основе функции минимума в роли функции дополнительности) и гладким с ограничениями (на основе произведения Адамара). 7. Проведено численное исследование асимптотического принятия настоящей матрицы Гессе и полного шага методом последовательного квадратичного программирования для задачи оптимизации с ограничениями-неравенствами, глобализованным одномерным поиском для негладкой точной штрафной функции, при сходимости к критическим множителям Лагранжа. Указанные свойства позволяют применять в сочетании с глобализацией известные техники ускорения сходимости ньютоновских методов к особым решениям, такие, как экстраполяция, эффект от который был также подтвержден численным экспериментом. 8. Получены условия, гарантирующие устойчивость данного решения системы нелинейных уравнений по отношению к широким классам возмущений. Основное внимание уделено случаю, когда система имеет пониженную гладкость (имеет липшицевы первые производные, но не вторые производные, или является кусочно гладкой), а рассматриваемое решение является в некотором смысле особым, и поэтому свойства устойчивости такого решения не гарантируются никакими стандартными средствами анализа. Полученные результаты применяются к кусочно-гладким переформулировкам комплементарных задач.
МГУ имени М.В.Ломоносова | Координатор |
грант РФФИ |
# | Сроки | Название |
1 | 1 января 2020 г.-31 декабря 2020 г. | Оценки расстояния до решений вариационных задач и ньютоновские методы |
Результаты этапа: Получены новые результаты о накрывании для нелинейных отображений на замкнутом выпуклом множестве при возможном невыполнении условия регулярности Робинсона, a также соответствующие результаты об устойчивости решений нелинейных уравнений с ограничениями вида включения в произвольное множество с указанными свойствами. Предложены более слабые условия, гарантирующие устойчивость данного решения по отношению к широким классам возмущений, или иными словами гарантирующие свойство накрывания большого множества. В отличие от известных результатов такого рода, здесь не используются предположения коничности множества, что допускает значительно более широкий круг приложений. В основе полученных результатов лежат соответствующие обобщения концепции 2-регулярности, недавние результаты о точках совпадения отображений метрических пространств, а также новая конструкция внутренней аппроксимации касательного конуса к выпуклому множеству. Научная и прикладная значимость этих результатов связана, в частности, с потенциальными приложениями к полуопределенным и конусным комплементарным задачам. Получен утвердительный ответ на давний открытый вопрос нелинейного анализа относительно существования непрерывного однозначного селектора у правого обратного к локально липшицевому отображению. Более того, в получен более общий результат, дающий условия существования непрерывного селектора не только локально, но и на заданном шаре с центром в рассматриваемой точке. Наконец, устремлением радиуса этого шара к бесконечности, получена глобальная теорема об обратной функции, которая содержит (по существу) известную теорему Адамара о глобальном гомеоморфизме для гладких отображений и более общую теорему Пурсо для локально липшицевых отображений. Разработаны новые способы преодоления негативного влияния притяжения ньютоновских методов к критическим решениям на скорость сходимости прямо-двойственных ньютоновских методов. Независимо от конкретного рассматриваемого метода, для задач оптимизации с ограничениями-равенствами предлагается новая локальная техника подавления притяжения к критическим множителям Лагранжа. Подход состоит в замене двойственных приближений, генерируемых методом, специальной функцией прямых приближений. При некоторых естественных предположениях эта функция дает аппроксимацию множителя Лагранжа, качество которой согласуется с расстоянием от прямого приближения до соответствующей стационарной точки, и при этом должным образом отстоящую от рассматриваемого критического множителя Лагранжа. Ускоряющий эффект этой техники демонстрируется вычислительным экспериментом для стабилизированного метода последовательного квадратичного программирования, а также метода Левенберга-Марквардта и метода Ньютона с подзадачами линейного программирования. | ||
2 | 1 января 2021 г.-31 декабря 2021 г. | Оценки расстояния до решений вариационных задач и ньютоновские методы |
Результаты этапа: Получены результаты об асимптотическом принятии полного ньютоновского шага при сходимости глобализованного одномерным поиском метода Ньютона к критическим решениям нелинейных уравнений. На этой основе получены результаты об асимптотическом принятии настоящей матрицы Гессе функции Лагранжа и полного шага методом последовательного квадратичного программирования для задачи оптимизации с ограничениями-равенствами, глобализованным одномерным поиском для негладкой точной штрафной функции. Анализ основан на условии 2-регулярности по направлениям из подпространства нулей первой производной, которое может естественным образом выполняться в особых (и даже неизолированных) решениях, которые являются критическими. Ключевым ингредиентом анализа является тонкая характеризация шага метода Ньютона в рассматриваемых обстоятельствах. Данные результаты позволяют обоснованно применять в сочетании с глобализацией сходимости известные техники ускорения сходимости ньютоновских методов к особым решениям, такие, как экстраполяция и оверрелаксация. Предложены обобщения концепции критического решения и связанных с ней теоретических результатов об оценках расстояния на негладкие уравнения, в том числе с дополнительными ограничениями. Получены характеризации оценок расстояния до множества решений через инструментарий обобщенного дифференцирования и средства вариационного анализа. Установлены условия локальной сходимости широких классов кусочных ньютоновских методов к особым решениям кусочно-гладких уравнений из широких областей начальных точек, а также условия асимптотического принятия полного шага глобализованными одномерным поиском версиями таких методов. Выявляемый при этом специальный характер линейной локальной сходимости данных методов к критическим решениям дает возможности для повышения этой скорости. Рассмотрены приложения полученных результатов к различным переформулировкам комплементарных задач: негладким без ограничений (на основе функции минимума в роли функции дополнительности) и гладким с ограничениями (на основе произведения Адамара). | ||
3 | 1 января 2022 г.-31 декабря 2022 г. | Оценки расстояния до решений вариационных задач и ньютоновские методы |
Результаты этапа: Проведено численное исследование асимптотического принятия настоящей матрицы Гессе и полного шага методом последовательного квадратичного программирования для задачи оптимизации с ограничениями-неравенствами, глобализованным одномерным поиском для негладкой точной штрафной функции, при сходимости к критическим множителям Лагранжа. Указанные свойства позволяют применять в сочетании с глобализацией известные техники ускорения сходимости ньютоновских методов к особым решениям, такие, как экстраполяция, эффект от который был также подтвержден численным экспериментом. Получены условия, гарантирующие устойчивость данного решения системы нелинейных уравнений по отношению к широким классам возмущений. Основное внимание уделено случаю, когда система имеет пониженную гладкость (имеет липшицевы первые производные, но не вторые производные, или является кусочно гладкой), а рассматриваемое решение является в некотором смысле особым, и поэтому свойства устойчивости такого решения не гарантируются никакими стандартными средствами анализа. Полученные результаты применяются к кусочно-гладким переформулировкам комплементарных задач. Получены новые результаты о скорости сходимости методов штрафных функций в слабых предположениях. |
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".