Эффективная реализация ускоренного метода решения вариационных неравенств

• Опубліковано в: : Системні дослідження та інформаційні технології
• Дата: 2014
• Автори: Александрова, В.М., Соболенко, Л.А.
• Формат: Стаття
• Мова: Russian
• Опубліковано: Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2014
• Теми: Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/85559
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Эффективная реализация ускоренного метода решения вариационных неравенств / В.М. Александрова, Л.А. Соболенко // Системні дослідження та інформаційні технології. — 2014. — № 3. — С. 119-129. — Бібліогр.: 15 назв. — рос.

Построен нелокально сходящийся алгоритм решения вариационных неравенств с сильно монотонным оператором и выпуклыми ограничениями-неравенствами, обладающий высокой скоростью сходимости. Метод основан на совмещении глобального алгоритма первого порядка, использующего итерационную последовательность в пространстве прямых переменных, с методом Ньютона решения системы Куна-Таккера вариационных неравенств в окрестности решения. Выполнена эффективная реализация предложенного алгоритма. Рассмотрены вычислительные аспекты, связанные с двумя трудоемкими подзадачами сформулированного алгоритма — задачей квадратичного программирования и решением системы нелинейных равенств. Реализация метода опробована на решении вариационных неравенств с непотенциальным оператором. Проведен сравнительный анализ работы ускоренного алгоритма и алгоритма первого порядка. Высокая скорость сходимости предложенного алгоритма подтверждена результатами вычислительного эксперимента. Побудовано нелокально збіжний алгоритм розв’язання варіаційних нерівностей з сильно монотонним оператором і опуклими обмеженнями-нерівностями, що має високу швидкість збіжності. Метод грунтується на поєднанні глобального алгоритму першого порядку, що використовує ітераційну послідовність у просторі прямих змінних, з методом Ньютона розв’язання системи Куна-Таккера варіаційних нерівностей в околі розв’язку. Виконано ефективну реалізацію запропонованого алгоритму. Розглянуто обчислювальні аспекти, пов’язані з двома трудомісткими підзадачами сформульованого алгоритму — задачею квадратичного програмування і розв’язанням системи нелінійних рівностей. Реалізація методу випробувана на розв’язанні варіаційних нерівностей з непотенційним оператором. Проведено порівняльний аналіз роботи прискореного алгоритму та алгоритму першого порядку. Висока швидкість збіжності запропонованого алгоритму підтверджено результатами обчислювального експерименту. A nonlocally converging algorithm for solving variational inequalities with strongly monotone operator and convex constraints-inequalities has been constructed. The algorithm has a high rate of convergence. The method is based on a combination of the global first-order algorithm that uses an iterative sequence in the space of direct variables with Newton's method of solving the Kuhn-Tucker conditions of variational inequalities in the neighborhood of the solution. The effective implementation of the proposed algorithm has been performed. The computational aspects associated with the two time-consuming subtasks of a presented algorithm — the quadratic programming problem and solving a system of nonlinear equations have been considered. The implementation of the method has been tested by solving the variational inequalities with a nonpotential operator. A comparative analysis of the accelerated algorithm and the first order algorithm has been performed. The high convergence of the proposed algorithm has been confirmed by the results of computational experiments.