Ефективна реалізація прискореного методу розв’язання варіаційних нерівностей

V. М. Aleksandrova, L. А. Sоbolenko

Анотація


Побудовано нелокально збіжний алгоритм розв’язання варіаційних нерівностей з сильно монотонним оператором і опуклими обмеженнями-нерівностями, що має високу швидкість збіжності. Метод грунтується на поєднанні глобального алгоритму першого порядку, що використовує ітераційну послідовність у просторі прямих змінних, з методом Ньютона розв’язання системи Куна-Таккера варіаційних нерівностей в околі розв’язку. Виконано ефективну реалізацію запропонованого алгоритму. Розглянуто обчислювальні аспекти, пов’язані з двома трудомісткими підзадачами сформульованого алгоритму — задачею квадратичного програмування і розв’язанням системи нелінійних рівностей. Реалізація методу випробувана на розв’язанні варіаційних нерівностей з непотенційним оператором. Проведено порівняльний аналіз роботи прискореного алгоритму та алгоритму першого порядку. Висока швидкість збіжності запропонованого алгоритму підтверджено результатами обчислювального експерименту.

 


Повний текст:

PDF (Русский)

Посилання


Facchinei F., Pang J.-S. Finite-Dimensional Variational Inequalities and Complementarity, Volume I. — Springer, 2003. — 728 p.

Facchinei F., Pang J.-S. Finite-Dimensional Variational Inequalities and Complementarity, Volume II. — Springer, 2003. — 702 p.

Xiao B., Harker P.T. A nonsmooth Newton method for variational inequalities, I:Theory // Math.Progr. — 1994. — 65, № 2. — P. 151–194.

Bakushinskiy YA. M., Polyak B. T. O reshenii variatsionnykh neravenstv // Dokl. АN SSSR. — 1974. — 219, № 5, — S. 1038–1041.

Panin V.M., Аleksandrova V.M. Nelokal’nyy kvazin’yutonovskiy metod resheniya vypuklykh variatsionnykh neravenstv // Kibernetika i sistem. analiz. — 1994. — № 6. — S. 78–91.

Fukushima, M. Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems // Math. Progr. — 1992. — 53, № 2. — P. 99–110.

Аleksandrova V.M., SHubenkova I.А. Ob usovershenstvovanii metoda resheniya variatsionnykh neravenstv // Kibernetika i sistemnyy analiz. — 2013. — № 2. — S. 150–156.

Danilin YU.M., SHubenkova I.А. Optimizatsiya i resheniye vypuklykh variatsionnykh neravenstv // Systemni doslidzhennya ta informatsiyni tekhnolohiyi. — 2003. — # 3. — S. 66–74.

Pshenichnyy B.N. Metod linearizatsii. — M.: Nauka, 1983. — 136 s.

Sobolenko L.А. Uskorennyye modifikatsii metoda linearizatsii. — Dep. VINITI 7525. — V.89. — 1989. — 35 s.

Аleksandrova V.M. Uskorennyy metod resheniya variatsionnykh neravenstv // Teoriya optimal’nykh resheniy. — Kiyev: In-t kibernetiki im. V.M. Glushkova NАN Ukrainy, 1995. — S. 8–13.

Gill F., Myurrey K., Rayt M. Prakticheskaya optimizatsiya. — M.: Mir, 1985. — 509 s.

Goldfarb D, Idnani A. A numerically stable dual method for solving strictly convex quadratic problem // Math. Progr. — 1983. — 27, № 1. — P. 1–33.

Fukushima M. A relaxed projection method for variational inequalitities // Math. Progr. — 1986. — 35, № 1. — P. 58–70.

Taji K., Fukushima M., Ibaraki T. A globally convergent Newton method for solving strongly monotone variational inequalities // Math. Progr. — 1993. — 58, № 3. — P. 369–383.


Пристатейна бібліографія ГОСТ


1. Facchinei F., Pang J.-S. Finite-Dimensional Variational Inequalities and Complementarity, Volume I. — Springer, 2003. — 728 p.

2. Facchinei F., Pang J.-S. Finite-Dimensional Variational Inequalities and Complementarity, Volume II. — Springer, 2003. — 702 p.

3. Xiao B., Harker P.T. A nonsmooth Newton method for variational inequalities, I:Theory // Math.Progr. — 1994. — 65, № 2. — P. 151–194.

4. Бакушинский Я. М., Поляк Б. Т. О решении вариационных неравенств // Докл. АН СССР. — 1974. — 219, № 5, — С. 1038–1041.

5. Панин В.М., Александрова В.М. Нелокальный квазиньютоновский метод решения выпуклых вариационных неравенств // Кибернетика и систем. анализ. — 1994. — № 6. — С. 78–91.

6. Fukushima, M. Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems // Math. Progr. — 1992. — 53, № 2. — P. 99–110.

7. Александрова В.М., Шубенкова И.А. Об усовершенствовании метода решения вариационных неравенств // Кибернетика и системный анализ. — 2013. — № 2. — С. 150–156.

8. Данилин Ю.М., Шубенкова И.А. Оптимизация и решение выпуклых вариационных неравенств // Системні дослідження та інформаційні технології. — 2003. — № 3. — С. 66–74.

9. Пшеничный Б.Н. Метод линеаризации. — М.: Наука, 1983. — 136 с.

10. Соболенко Л.А. Ускоренные модификации метода линеаризации. — Деп. ВИНИТИ 7525. — В.89. — 1989. — 35 с.

11. Александрова В.М. Ускоренный метод решения вариационных неравенств // Теория оптимальных решений. — Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 1995. — С. 8–13.

12. Гилл Ф., Мюррей К., Райт М. Практическая оптимизация. — М.: Мир, 1985. — 509 с.

13. Goldfarb D, Idnani A. A numerically stable dual method for solving strictly convex quadratic problem // Math. Progr. — 1983. — 27, № 1. — P. 1–33.

14. Fukushima M. A relaxed projection method for variational inequalitities // Math. Progr. — 1986. — 35, № 1. — P. 58–70.

15. Taji K., Fukushima M., Ibaraki T. A globally convergent Newton method for solving strongly monotone variational inequalities // Math. Progr. — 1993. — 58, № 3. — P. 369–383.



Посилання

  • Поки немає зовнішніх посилань.