|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Ускорение ньютоновских методов при наличии критических решенийНИР
Accelerating Newton-type methods near critical solutions
- Руководитель НИР: Измаилов А.Ф.
- Участники НИР: Куренной А.С., Родин И.С., Солодов М.В., Усков Е.И.
- Подразделение: Кафедра исследования операций
- Срок исполнения: 1 января 2019 г. - 31 декабря 2021 г.
- Номер договора (контракта, соглашения): 19-51-12003 ННИО_а
- Номер ЦИТИС: АААА-А19-119011190166-8
- Тип: Фундаментальная
- Приоритетное направление научных исследований: Математическая кибернетика, математические методы прогнозирования и исследование операций
- Приоритеты и перспективы НТР Российской Федерации согласно Стратегии НТР РФ: переход к передовым цифровым, интеллектуальным технологиям
- ПН России: Информационно-телекоммуникационные системы
- Направление технологического прорыва России: Стратегические информационные технологии
-
Рубрики ГРНТИ:
- 27.41.41 Алгоритмы решения задач вычислительной и дискретной математики
- 28.29.15 Методы исследования операций
-
Ключевые слова:
ньютоновский метод, поправки второго порядка, оценка расстояния до множества решений, ускорение сходимости, нелинейная система уравнений, критическое решение, глобализация сходимости, 2-регулярность, особое решение, неизолированное решение
singular solution, second-order corrections, globalization of convergence, acceleration of convergence, newton-type method, nonisolated solution, 2-regularity, critical solution, nonlinear system of equations, error bound -
Описание:
Основной целью данного проекта является разработка новых средств, обеспечивающих достаточно быструю сходимость ньютоновских методов несмотря на наличие критических решений. Для достижения этой цели в проекте выделен ряд конкретных основных целей исследования. В случае систем условий оптимальности с неединственным множителем, возникающих из задач условной оптимизации, планируется разработать новые средства, которые, при умеренной трудоемкости, модифицировали бы генерируемые оценки множителей таким образом, чтобы они оставались достаточно удалены от критических множителей. Для систем нелинейных уравнений более общей структуры планируется рассмотреть критические решения, удовлетворяющие определенному условию 2-регулярности. Это слабое условие влечет весьма структурированный характер сходимости и, в частности, должно позволить локально идентифицировать подпространство, где нарушается сверхлинейная сходимость. Обычно это подпространство имеет небольшую размерность. Планируется использовать этот факт для разработки новых алгоритмических средств для ускорения локальной сходимости. Для достижения поставленных целей потребуется также разработка средств для обнаружения факта сходимости к критическому решению. Важнейшей составной частью этих исследований является соединение локальных методов с разумными стратегиями глобализации сходимости, что должно привести к разработке реализуемых практических алгоритмов. Также планируется численное исследование и тестирование разрабатываемых методов.
-
Abstract:
Newton-type methods are one of the central techniques for the efficient solution of systems of nonlinear equations and of related problems. This is due to the fast convergence of these methods under appropriate assumptions. Current research on these methods aims at broadening their applicability to new or more difficult problem classes. An important issue here are problems with nonisolated solutions. A local fast (superlinear) convergence rate has been shown for specially designed Newton-type methods for several problem classes if a suitable Lipschitzian error bound condition is satisfied. Among these methods are stabilized sequential quadratic programming techniques, Levenberg-Marquardt algorithms, and the recent LP-Newton method. However, it is well-recognized that, in the presence of nonisolated solutions, Newton-type methods have a strong tendency to converge to solutions at which such an error bound condition is violated. These solutions are called critical. Several recent attempts to globalize such Newton-type methods face the principal difficulty that they often cannot leave large domains of attraction to critical points. Then, the fast convergence of the Newton-type methods is usually lost, and the advantages of methods specially designed for the case of nonisolated solutions are usually lost. Therefore, the main goal of the project consists in the development and foundation of new techniques to achieve fast local convergence in spite of the presence of critical solutions. To reach this goal we intend to tackle specific main research objectives. In the case of optimality systems with nonunique multipliers, arising from constrained optimization, we intend to develop a new technique that, with a reasonable expense, modifies the generated multiplier estimates so that they are staying sufficiently far away from a critical multiplier. For systems of nonlinear equations with a more general structure, we intend to consider critical solutions satisfying a certain 2-regularity condition. This mild condition enforces a structured convergence pattern, and, in particular, shell allow us to locally identify the subspace where the deterioration of the superlinear convergence takes place. Usually this subspace has a small dimension. We intend to exploit this to construct new algorithmic techniques with the aim of fast local convergence. To support the previous goals we aim at developing tools which certify convergence to a critical solution. A research objective with strong relevance for the impact of our main goal is to embed the local techniques into relevant globalization frameworks, resulting in implementable algorithms. Together with this, a computational study and comparison of the new techniques and algorithms is intended.
-
Планируемые результаты:
1. Новые эффективные модификации ньютоновских методов, позволяющие избегать сходимости к критическим решениям даже из малых окрестностей последних. Этот результат позволит сохранять высокую скорость локальной сходимости ньютоновских методов несмотря на наличие критических решений. Данные модификации планируется получить для систем условий первого порядка опимальности в случае неединственности множителя. Такие системы возникают как условия оптимальности в задачах условной оптимизации и более общих вариационных задачах. 2. Новые эффективные модификации ньютоновских методов, ускоряющие их сходимость в случае сходимости к критическим решениям. В естественных предположениях сходимость ньютоновских методов к критическим решениям происходит лишь с линейной скоростью. Планируется развитие алгоритмических средств и их теоретического обоснования, позволяющих ускорить сходимость, и в идеале получит сверхлинейную сходимость. 3. Эффективные и робастные способы глобализации сходимости разрабатываемых методов. Как указано выше, существующие стратегии глобализации сходимости для существующих стабилизированных методов не могут считаться полностью удовлетворительными при наличии критических решений. Локальные алгоритмы, о которых идет речь в пунктах 1 и 2, потребую развития соответствующих средств глобализации их сходимости. Для задач удовлетворяющих стандартным предположениям, разрабатываемы согласно пп. 1-3 алгоритмы должны иметь робастность и эффективность сопоставимую со стандартными алгоритмами. Вместе с тем, в более слабых предположениях, используемых в этом проекте, ожидаются существенные улучшения по сравнению со стандартными методами.
-
Научный задел:
Российским участникам проекта принадлежат оригинальные результаты по оценкам расстояния до множества решений нелинейных уравнений и вариационных задач, критическим множителям Лагранжа, критическим решениям нелинейных уравнений и вариационных задач, теории 2-регулярности, стабилизированным и регуляризованным ньютоновским методам и глобализации их сходимости, абстрактным ньютоновским схемам, и др. Эти результаты, имеющие непосредственное отношение к тематике проекта, отражены в цитируемых в проекте публикациях (в ряду многих других), в том числе совместных с зарубежным партнером.
- Добавил в систему: Врагова Елена Юрьевна
Соисполнители НИР
| МГУ имени М.В.Ломоносова | Координатор |
Источник финансирования НИР
| грант РФФИ |
Этапы НИР
| # | Сроки | Название |
| 1 | 1 января 2019 г.-31 декабря 2019 г. | Ускорение ньютоновских методов при наличии критических решений |
| Результаты этапа: 1. Для задачи оптимизации с ограничениями-равенствами предложен способ построения промежуточного двойственного приближения, подавляющий известную тенденцию притяжения ньютоновских методов к критическим множителям Лагранжа для таких задач. Именно указанная тенденция является основной причиной нарушения сверхлинейной сходимости ньютоновских методов в случае нарушения регулярности ограничений. Показано, что при выполнении определенных естественных условий получаемое вспомогательное двойственное приближение обладает следующими двумя ключевыми свойствами: расстояние от него до множества множителей оценивается по порядку величиной расстояния от имеющегося прямого приближения то искомой стационарной точки, и при этом расстояние от вспомогательного двойственного приближения до рассматриваемого критического множителя не меньше некоторой положительной константы. В основе предложенного подхода лежит использование специальной стабилизированной подзадачи квадратичного программирования с единственным решением, отвечающий которому множитель Лагранжа обладает указанными ключевыми свойствами. Данная конструкция может рассматриваться как новая реализация концепции двойственной стабилизации в случаях неединственности множителей Лагранжа, но она принципиально отличается от других известных реализаций этой концепции: вместо того, чтобы обеспечивать сходимость получаемых приближений вблизи некритического множителя (как, например, это делается для стабилизированного метода последовательного квадратичного программирования), идея состоит в удерживании вспомогательного приближения вдали от критических множителей, с сохранением нужного «качества» получаемого приближения. 2. Альтернативой изложенному в п. 1 подходу является следующее ключевое соображение: если подавление сходимости к критическому решению проблематично, то можно пытаться ускорить такую сходимость. В результате проведенных исследований, вместо использования поправок второго порядка, потенциал которых оказался весьма ограниченным, было предложено использование других техник ускорения сходимости глобализованного одномерным поиском метода Ньютона к критическим решениям систем нелинейных уравнений, таких, как экстраполяция и оверрелаксация. Ключевой проблемой при этом является обоснование асимптотического принятия полного шага, что, в случае сходимости к особому решению, совершенно не является автоматическим. В рамках проекта было показано, что при определенных требованиях 2-регулярности полный шаг принимается автоматически для начальных точек из некоторой звездной асимптотически плотной относительно искомого решения области. В основе анализа лежит тонкое описание ньютоновского шага и соответствующего характера сходимости вблизи особого решения, удовлетворяющего указанным требованиям. 3. Был проведен анализ свойств сходимости и численное тестирование разработанных в п. 1 и 2 алгоритмов, а также ряда других методов двойственной стабилизации. К последним можно отнести методы модифицированных функций Лагранжа, для которых было показано, что для сохранения их свойств локальной сходимости достаточно на каждой внешней итерации решать две вспомогательные подзадачи квадратичного программирования. Рассмотрен ряд приложений разрабатываемых методов, в том числе к двухуровневым стохастическим задачам оптимизации, и к определенным классам вариационных неравенств. | ||
| 2 | 1 января 2020 г.-31 декабря 2020 г. | Ускорение ньютоновских методов при наличии критических решений |
| Результаты этапа: Получены следующие результаты. 1. Способы построения промежуточного двойственного приближения, позволяющего подавить известную негативную тенденцию притяжения ньютоновских методов к критическим множителям Лагранжа, разработанные ранее для задач оптимизации с ограничениями-равенствами, распространены на задачи оптимизации с ограничениями-неравенствами. Были предложены два альтернативных подхода к этой проблеме: один основан на непосредственной работе с ограничениями-неравенствами при соответствующем контроле активных ограничений подзадач, а второй использует переформулировки ограничений-неравенств в виде равенств с помощью квадратов вспомогательных переменных. Предложено теоретическое обоснование соответствующих двух вариантов стабилизированного метода последовательного квадратичного программирования, снабженного процедурами двойственной модификации. Теоретические свойства подтверждаются многообещающими результатами численного эксперимента. 2. Для задачи оптимизации с ограничениями-равенствами разработана концептуальная схема глобализации сходимости стабилизированного метода последовательного квадратичного программирования, снабженного процедурами подавлением притяжения к критическим множителям Лагранжа, основанная на их комбинировании с методами модифицированных функций Лагранжа. Изучен вопрос применения таких методов для некоторых классов вариационных неравенств и двухуровневых стохастических задач оптимизации. 3. В случае особых (и возможно даже неизолированных) решений нелинейных уравнений сверхлинейная сходимость метода Ньютона обычно не имеет места, но локальная сходимость с линейной скоростью может быть гарантирована из широких областей начальных приближений при разумных предположениях. Был рассмотрен способ глобализации сходимости метода Ньютона посредством одномерного поиска, комбинированный с процедурами экстраполяции и оверрелаксации, позволяющими ускорить сходимость к критическим решениям. Данный подход является альтернативой пописанным выше, направленным на подавление сходимости к критическим решения. Центральную роль при этом играет асимптотическое принятие алгоритмом полного ньютоновского шага, которое было обосновано на первом этапе проекта. 4. Получены результаты об асимптотическом принятии настоящей матрицы Гессе и полного шага метода последовательного квадратичного программирования для задач оптимизации с ограничениями-равенствами, снабженного одномерным поиском для негладкой точной штрафной функции. Специфика этих рассмотрений состоит в том, что не используются стандартные предположения, гарантирующие локальную сверхлинейную сходимость метода. А именно, особое внимание уделено случаю, когда существуют критические множители Лагранжа, и в частности, ни условия регулярности ограничений, ни достаточные условия оптимальности второго порядка не предполагаются выполненными. Полученные результаты создают основу для применения известных техник ускорения сходимости, таких, как экстраполяция, что в итоге дает алгоритм, способный быть более эффективным на задачах с нерегулярными ограничениями, чем стандартный квазиньютоновский метод последовательного квадратичного программирования. Этот тезис подтвержден вычислительным экспериментом. | ||
| 3 | 1 января 2021 г.-31 декабря 2021 г. | Ускорение ньютоновских методов при наличии критических решений |
| Результаты этапа: | ||
Прикрепленные к НИР результаты
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".