О сходимости двойственного метода Ньютона для линейной задачи полуопределенного программирования
| Авторы: | В. Г. Жадан, А. А. Орлов |
| Аннотация: | В статье рассматривается двойственный метод Ньютона для линейной задачи полуопределенного программирования. В предположении о строгой дополнительности решениий прямой и двойственных задач доказывается его локальная сходимость со сверхлинейной скоростью. |
| Ключевые слова: | полуопределенное программирование, двойственная задача, метод Ньютона, локальная сходимость |
| УДК: | 518.517 |
| Литература: |
1. Арнольд В. И. О матрицах, зависящих от параметров / В. И. Арнольд // УМН. – 1971. – Т. 26, вып. 2(158). – С. 101–114. 2. Дикин И. И. Метод внутренних точек в линейном и нелинейном программировании / И. И. Дикин. – М. : URSS, 2009. – 120 c. 3. Евтушенко Ю. Г. Двойственные барьерно-проективные и барьерноньютоновские методы для линейного программирования / Ю. Г. Евтушенко, В. Г. Жадан // Журн. вычисл. математики и мат. физики. – 1994. – Т. 36, № 7. – С. 30–45. 4. Жадан В. Г. Двойственный метод Ньютона для линейной задачи полуопределенного программирования / В. Г.Жадан, А. А. Орлов // Оптимизация и приложения. – М. : ВЦ РАН, 2010. – С. 87–108. 5. Зоркальцев В. И. Об одном классе алгоритмов внутренних точек / В. И. Зоркальцев // Журн. вычисл. математики и мат. физики. – 2009. – Т. 49, № 12. – С. 2114–2130. 6. Магнус Я. Р. Матричное дифференциальное исчисление с приложениями к статистике и эконометрике / Я. Р. Магнус, Ч. Нейдеккер. – М. : Физматлит, 2002. – 496 с. 7. Ортега Дж. Итерационные методы решения систем нелинейных уравнений со многими неизвестными / Дж. Ортега, В. Рейнболдт. – М. : Мир, 1975. – 558 с. 8. Alizadeh F. Complementarity and nondegeneracy in semidefinite programming / F. Alizadeh, J.-P. F. Haeberly, M. L. Overton // Mathematical Programming. Series B. – 1997. – Vol. 77, N 2. – P. 129–162. 9. De Klerk E. Aspects of Semidefinite Programming. Interior Point Algorithms and Selected Applications / E. de Klerk. – Kluwer Academic Publishers, 2004. – 283 p. 10. Magnus J. R. The elimination matrix: some lemmas and applications / J.R. Magnus, H. Neudecker // SIAM J. Alg. Disc. Meth. – 1980. – Vol. 1, N 4. – P. 422–449. 11. Nesterov Yu. E. Interior Point Polynomial Algorithms in Convex Programming / Yu. E. Nesterov, A. S. Nemirovski. – SIAM Publications, SIAM, Philadelphia, 1994. – 405 p. 12. Vandenberghe L. Semidefinite programming / L. Vandenberghe, S. Boyd // SIAM Rev. – 1996. – Vol. 38. – P. 49–95. 13. Handbook of Semidefinite Programming / eds. H. Wolkowicz, R. Saigal, L. Vandenberghe. – Kluwer Academic Publishers, 2000. – 656 p. |