Двойственные и прямо-двойственные методы аффинно-масштабирующего типа для линейных задач полуопределенного программирования тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Орлов, Александр Алексеевич

• Орлов, Александр Алексеевич
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Орлов, Александр Алексеевич

Введение

Список основных обозначений

Глава 1. Постановка задачи. Методы решения и основные примеры.

1.1. Постановка задачи.

1.2. Известные классы численных методов решения задач SDP.;.

1.3. Использование задач SDP в приложениях.

Глава 2. Двойственные методы простой итерации.

2.1. Используемые обозначения и результаты.

2.2. Допустимый итерационный процесс.

2.3. Общий итерационный процесс.

2.4. Невырожденность матрицы Ф(У).

2.5. Алгоритмические операторы и их представления.

2.6. Матрица Якоби.

Глава 3. Двойственный метод Ньютона.

3.1. Итерационный процесс.

3.2. Локальная сходимость метода.

Глава 4. Прямо-двойственные методы Ньютона.

4.1. Прямо-двойственный ньютоновский итерационный процесс в пространстве точек (X,V).

4.2. Прямо-двойственный ньютоновский итерационный процесс в пространстве точек (Х,и).

Глава 5. Численный эксперимент.

Введение диссертации (часть автореферата) на тему «Двойственные и прямо-двойственные методы аффинно-масштабирующего типа для линейных задач полуопределенного программирования»

Линейные задачи полуопределенного программирования (SDP — semidefinite programming) представляют важный раздел математического программирования, активно развивающийся на протяжении последних двух десятилетий. Данные задачи играют существенную роль в таких областях как комбинаторная и квадратичная оптимизация, теория управления, структурная оптимизация, оптимизационные задачи на собственные числа. Поэтому методам решения линейных задач полуопределенного программирования в последнее время уделялось огромное внимание.

Хотя формулировка задачи SDP была дана Р. Беллманом и К. Фаном в 1963 году [4], основные результаты в данной области были получены после появления методов внутренней точки для задач линейного программирования (LP — linear programming). И.И. Дикин в 1967 году [52] впервые рассмотрел метод внутренней точки для задач LP, который впоследствии получил в западной литературе название аффинно-масштабирующего метода. В 1979 году Л. Хачиян [69] предложил метод эллипсоидов для решения задач LP, имеющий полиномиальное время работы. Первый же полиномиальный метод внутренней точки в задачах LP, был предложен Н. Кармаркаром в 1984 году [И]. Впоследствии было предложено много других полиномиальных методов внутренней точки для решения задач LP, из которых наиболее эффективными с вычислительной точки зрения оказались прямо-двойственные методы центрального пути.

Ю. Е. Нестеров и А. С. Немировский, а также Ф. Ализаде впервые обобщили методы внутренней точки на случай задач SDP. В их работах [1] и [30] были предложены прямые и двойственные методы решения.

Следующим этапом развития стало распространение прямо-двойственных методов, главным образом, методов центрального пути, со случая задач LP на задачи SDP. В отличие от задач LP существует множество способов построения ньютоновских направлений движения для прямо-двойственных методов в задачах SDP. Как правило доказательство сходимости таких методов для задач SDP оказывается достаточно сложным. Первыми из появившихся и наиболее часто используемыми на практике являются следующие три направления движения в прямо-двойственных методах: AHO [3], NT [31, 32], HRVW/KSH/M [10, 18, 23].

Рядом авторов были построены семейства направлений поиска решения в прямо-двойственных методах для задач SDP, включающих указанные выше направления как частные случаи, а также дано обоснование сходимости алгоритмов, использующих эти семейства направлений. Наиболее известными семействами являются: MZ [23, 44], KSH [18], МТ [24].

Среди российских авторов помимо Ю. Е. Нестерова и А. С. Неми-ровского следует отметить вклад Б. Т. Поляка, П. С. Щербакова, И. И. Дикина в развитие методов решения задач SDP [50, 51, 67].

В настоящее время теория и методы решения задач SDP достаточно хорошо проработаны, опубликовано несколько монографий [41,16, 5, 38], из которых стоит отметить книгу [41], в которой дан обзор основных результатов, полученных в области полуопределенного программирования к концу предыдущего столетия.

Как уже отмечалось, многие другие оптимизационные задачи могут быть переформулированны или редуцированны к задачам SDP. Различные способы практического применения задач SDP можно найти в книгах [41, 5], а также в обзорных работах [39, 40, 38].

Научная новизна. Все выводы и результаты работы являются оригинальными. Предложенные в работе методы можно отнести к двойственным и прямо-двойственным методам аффинно-масштабирующего типа. В некотором роде, построенные методы являются обобщением барьерно-проективных методов, предложенных ранее Ю.Г. Евтушенко и В.Г. Жаданом в [53] для решения задач линейного программирования, на более сложные линейные задачи полуопределенного программирования.

Хотя рассматриваемые в диссертации методы обладают многими свойствами методов внутренней точки, при их построении совершенно не используется идея барьерных функций. Фактически, методы основываются на специальных способах решения системы необходимых и достаточных условий для пары взаимно двойственных линейных задач полуопределенного программирования.

Цель диссертационной работы:

• Сведение системы оптимальных условий в задаче SDP к системе уравнений с меньшим числом неизвестных путем построения зависимости прямых переменных от двойственных.

• Решение полученной нелинейной системы уравнений методом простой итерации и методом Ньютона. Аналитическое исследование сходимости данных методов.

• Построение прямо-двойственных методов решения задачи SDP, основанных на решении системы оптимальных условии методом Ньютона. Обоснование локальной сходимости построенных методов.

• Проверка работоспособности полученных методов на тестовых задачах.

Работа состоит из введения, пяти основных глав, заключения, списка использованных источников и приложения.

В первой главе рассматривается постановка линейной задачи полуопределенного программирования, приводятся некоторые из известных на данный момент численных методов ее решения, а также примеры сведения различных оптимизационных задач к задачам SDP. В данной главе приводятся условия регулярности ограничений Слейтера и условие строгой комплементарности. Все результаты работы справедливы для случая, когда оба эти условия выполнены. Рассматриваются свойства слабой и сильной двойственности, а также система равенств и неравенств, представляющая собой систему оптимальных условий в задачах SDP.

В данной главе указаны также несколько наиболее популярных алгоритмов решения задач SDP: прямо-двойственные методы аппроксимации центрального пути, методы уменьшающегося потенциала, прямо-двойственные аффинно-масштабирующие методы. Рассмотрены две прикладные задачи (оптимизация собственных значений матрицы и NP-полная задача комбинаторной оптимизации MAX-CUT), при решении которых могут быть использованы задачи SDP.

Кроме того, в первой главе описаны некоторые принципиальные различия между задачами LP и SDP, а также, следуя [27], приводится пример задачи размерности п = 2, на которой известные прямо-двойственные аффинно-масштабирующие методы не сходятся к решению.

Во второй главе построены два алгоритма решения задач SDP, основанные на методе простой итерации. Для получения этих алгоритмов система оптимальных условий задачи SDP записывается в векторном виде, причем при векторизации учитывается, что матричные переменные в прямой и двойственной задачах должны быть симметричными (делается это с помощью специальных элиминационных и дуплицирующих матриц).

Из полученных оптимальных условий затем выводится зависимость прямых переменных от двойственных. Одним из основных результатов главы является теорема, показывающая, что данная зависимость будет корректно определена для класса невырожденных задач. После подстановки полученной зависимости в условие допустимости для прямой задачи, вся система оптимальных условий, за исключением требований положительной полуопределенности матриц прямых и двойственных переменных, сводится к нелинейной системе уравнений относительно двойственных переменных, которая в дальнейшем решается методом простой итерации. Во второй главе были получены два итерационных процесса: допустимый, в котором от начальных точек требуется, чтобы они были допустимыми, и общий, в котором это требование снимается. Доказывается, что для невырожденных задач данные итерационные процессы локально сходятся к решению с линейной скоростью.

В третьей главе по аналогии со второй главой прямые переменные исключаются из системы оптимальных условий, после чего нелинейная система уравнений относительно двойственных переменных решается с использованием метода Ньютона. Основной результат главы составляет доказательство теоремы о том, что полученный итерационный процесс локально сходится к решению со сверхлинейной скоростью для невырожденных задач.

Особенность методов, построенных в четвертой главе, состоит в том, что в них не требуется выражать прямые переменные через двойственные. Векторизованная система оптимальных условий решается методом Ньютона в ее изначальном виде в результате чего получается схема численного метода, в которой одновременно пересчитываются как прямые так и двойственные переменные. Таким образом, полученные в этой главе методы можно отнести к классу прямо-двойственных методов аффинно-масштабирующего типа. Следует отметить, что в сложившейся практике принято считать, что именно прямо-двойственные методы, особенно прямо-двойственные методы центрального пути, являются наиболее эффективными для решения задач SDP. Доказывается, что полученные методы локально сходятся к решению задачи со сверхлинейной скоростью для невырожденных задач.

Пятая глава содержит результаты численных экспериментов, проведенных на тестовых данных. Эксперименты проводились с использованием среды MATLAB на задачах малой и средней размерности. Тестовые задачи генерировались по специальным правилам таким образом, чтобы в результате получалась задача SDP с известным решением. Способы генерации тестовых задач описаны в пятой главе.

Проведенные эксперименты показали, что на тестовых задачах предложенные методы находили приближенное решение за достаточно малое число шагов, при этом, в целом, прямо-двойственные методы показывали чуть более высокую скорость работы.

В заключении сформулированы основные результаты, полученные в диссертации.

В приложении содержатся примеры тестовых задач небольшой размерности.

Главное преимущество методов, предложенных в работе, состоит в том, что для них сохраняется локальная сходимость при переносе с задач линейного программирования на задачи полуопределенного программирования. Как известно, иногда такое обобщение нарушает сходимость [27]. Использование операторов векторизации, элиминационных и дупли-цирующих матриц позволяет обойти проблемы с симметричностью приращений в численных методах решения системы условий оптимальности, а за счет выбора начальной точки и длины шага можно добиться того, чтобы построенные методы являлись методами внутренней точки.

В работе использованы некоторые результаты из теории матриц, в частности, способы работы с операторами векторизации, элиминацион-ными и дуплицирующими матрицами (см. [64, 21, 49, 70]).

Основные результаты диссертации опубликованы в четырех работах [56, 58, 59, 61], а также доложены и обсуждены на следующих конференциях и семинарах:

• 52, 53, 54 научные конференции МФТИ, ноябрь 2009-2011, Москва;

• VI Московская международная конференция по исследованию операций, октябрь 2010, Москва;

• 15я Байкальская международная школа-семинар "Методы оптимизации и их приложения июнь 2011, пос. Листвянка, озеро Байкал;

• VII Всероссийская научная конференция "Математическое моделирование развивающейся экономики и экологии"(ЭКОМОД-2012), июль 2012, Киров.

Список основных обозначений

Мп — п-мерное евклидово пространство; ж1, х2,., хп] — вектор х еЖп с координатами хг, 1 < г ^ п; ж, у) = Хл=1 х%Уг ~ евклидово скалярное произведение;

0П — нулевой п-мерный вектор;

Опт — нулевая матрица размеров п х т; — единичная матрица порядка п;

Ат — транспонированная матрица А;

А~1 — матрица, обратная к А;

А\ — определитель квадратной матрицы А;

А1//2 — квадратный корень матрицы А;

8> — кронекеровское произведение;

Т>п — дуплицирующая матрица;

Сп — элиминационная матрица; а) — диагональная матрица с вектором а на диагонали; <5>п — пространство симметричных матриц порядка п

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Орлов, Александр Алексеевич

Заключение

Итак, в диссертации получены следующие результаты:

1. предложен способ сведения системы оптимальных условий в линейной задаче полуопределенного программирования к системе нелинейных уравнений относительно двойственных переменных.

2. С использованием метода простой итерации предложены два двойственных метода решения полученной системы уравнений: допустимый и общий. Доказано, что эти методы локально сходятся к решению с линейной скоростью.

3. Для указанной системы уравнений относительно двойственных переменных построен двойственный метод решения, основанный на методе Ньютона. Доказана теорема, подтверждающая его локальную сходимость со сверхлинейной скоростью.

4. На основании метода Ньютона построены два прямо-двойственных метода решения линейной задачи полуопределенного программирования, в которых на каждой итерации одновременно пересчитыва-ются значения как прямых, так и двойственных переменных. Для данных методов обоснована локальная сходимость со сверхлинейной скоростью.

5. Проведены вычислительные эксперименты на тестовых задачах (рандомизированные данные малой и средней размерности), которые подтвердили корректность работы данных методов, а также проведен сравнительный анализ скорости их работы.

Отметим также ряд остающихся открытыми вопросов, то есть, направления дальнейших исследований:

1. добавление регулировки длины шага в полученные ньютоновские методы.

2. Разработка эффективного программного комплекса для реализации вычислений по данным методам, в том числе, с использованием параллельных и распределенных вычислений.

3. Проведение экспериментов на задачах большой размерности из библиотеки ББРЫВ [6] и более новой библиотеке, предложенной в [17].

4. Получение точных (либо по крайней мере не слишком завышенных верхних) оценок числа итераций, необходимых методам для построения решения с заданной точностью.

СПИСОК ИСПОЛЬЗОВАННЫХ источников

1. F. Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization // SIAM Journal on Optimization - 1995 - V. 5 - P. 13-51.

2. F. Alizadeh, J.-P.F. Haeberly, M.L. Overton. Complementarity and nondegeneracy in semidefinite programming // Mathematical Programming., Series B. - 1997. - V. 77, № 2. - P. 129-162.

3. F. Alizadeh, J-P.A. Haeberly, and M.L. Overton. Primal-dual interior-point methods for semidefinite programming. Convergence rates, stability and numerical results. // SIAM Journal on Optimization —1998 — V. 8 - P. 746-768.

4. R. Bellman and K. Fan. On systems of linear inequalities in Hermitian matrix variables. // Proceedings of Symposia in Pure Mathematics — 1963 - V. 7.

5. A. Ben-Tal and A. Nemirovsky Lectures on Modern Convex Optimisation: Analysis, Algorithms, Engineering Applications. // MPS-SIAM Series on Optimisation. SIAM, Philadelphia, 2000.

6. B. Borchers. SDPLIB 1.2, A Library of Semidefinite Programming Test Problems. // Optimization Methods and Software. — 1999 — V. 11(1) — P. 683-690.

7. M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. // Journal of Assoc. Comput. Mach. — 1995 -V. 42-P. 1115-1145.

8. M.X. Goemans. Semidefinite programming in combinatorial optimization. // Math. Programming — 1997 — V. 79 — P. 143162.

9. A. J. Goldman and A. W. Tucker. Theory of linear programming. // Linear inequalities and related systems — 1956 — Princeton University Press. Annals of Mathematics Studies — №. 38 — P. 53-97.

10. C. Helmberg, F. Rendí, R. J. Vanderbei, and H. Wolcowicz. An interior-point method for semidefinite programming. // SIAM Journal on Optimization - 1996 - V. 6, № 2 - P. 342-361.

11. N. Karmarkar. A new polynomial-time algorithm for linear programming // Combinatorica - 1984 - V. 4 - P. 373-395.

12. E. de Klerk, J. Peng, C. Roos, and T. Terlaky. A scaled Gauss-Newton primal-dual search direction for semidefinite optimization. // SIAM Journal on Optimization - 2001 — V. 11 № 4 - P. 870-888.

13. E. de Klerk, C. Roos, and T. Terlaky. Infeasible-start semidefinite programming algorithms via self-dual embeddings. // Fields Institute for Research in Mathematical Sciences, Communications Series — 1998 - V. 18 -P. 215-236.

14. E. de Klerk, C. Roos, and T. Terlaky. On primal-dual path-following algorithms in semidefinite programming. // New trends in Mathematical Programming - 1998 — P. 137-157.

15. E. de Klerk, C. Roos, and T. Terlaky. Primal-dual potential reduction methods for semidefinite programming using affine scaling directions. // Appl. Numer. Math. - 1999 - V. 29 - P. 335-360.

16. E. de Klerk. Aspects of Semidefinite Programming. Interior Point Algorithms and Selected Applications // Kluwer Academic Publishers - 2002.

17. E. de Klerk, and R. Sotirov. A new library of structured semidefinite programming instances. // CentER Discussion Paper Tilburg University, The Netherlands, August 2008.

18. M. Kojima, S. Shindoh and S. Hara. Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. // SIAM Journal on Optimization — 1997 — V. 7 — P. 86125.

19. J. B. Lasserre. Linear programming with positive semi-definite matrices. // Tech. Report LAAS-94099, Laboratoire d'Analyse et d'Architecture des Systemes du CNRS — 1995.

20. M. Laurent, F. Rendl. Semidefinite Programming and Integer Programming // Report PNA-R0210, CWI, Amsterdam — 2002.

21. J.R. Magnus. The elimination matrix: some lemmas and applications // SIAM J. Alg. Disc. Meth. - 1980. - V. 1, № 4. - P. 422-449.

22. R. D. C. Monteiro. Polynomial convergence of primal-dual algorithms for semidefinite programming based on Monteiro and Zhang family of directions. // SIAM Journal on Optimization — 1998 — V. 8 — P. 797-812.

23. R. D. C. Monteiro. Primal-dual path-following algorithms for semidefinite programming. // SIAM Journal on Optimization — 1997 — V. 7 — P. 663-678.

24. R. D. C. Monteiro and T. Tsuchiya. Polynomial convergence of a new family of primal-dual algorithms for semidefinite programming. // SIAM Journal on Optimization — 1999 — V. 9 — P. 551-577.

25. R. D. C. Monteiro. Polynomiality of primal-dual algorithms for semidefinite linear complementarity problems based on theKojima-Shindoh-Hara family of directions. // Mathematical Programming — 1999 - V. 84 - P. 39-53.

26. R. D. C. Monteiro and Y. Zhang. A unified analysis for a class of path-following primal-dual interior-point algorithms for semidefinite programming. // Mathematical Programming — 1998 — V. 81 — P. 281-299.

27. M. Muramatsu, R. J. Vanderbei. Primal-dual affine scaling algorithm fails for semidefinite programming. // Mathematics of operations research — 1999 - V. 24 - P. 149-175.

28. Yu. Nesterov and A. Nemirovsky. Interior Point Polynomial Algorithms in Convex Programming // SIAM Publications, SIAM, Philadelphia — 1994 - 405 p.

29. Y. Nesterov and A. Nemirovsky. An interior point method for generalized linear-fractional programming // Math. Programming, Series B. — 1991.

30. Y. Nesterov and A. Nemirovsky. Interior-point polynomial methods in convex programming. //Studies in Applied Mathematics, SIAM, Philadelphia - 1994 — V .13.

31. Y. E. Nesterov and M. J. Todd. Self-scaled barriers and interior-point methods for convex programming // Mathematics of Operations Research - 1997 - V. 22 - P. 1-42.

32. Y. E. Nesterov and M. J. Todd. Primal-dual interior-point methods for self-scaled cones. // SIAM Journal of Optimization — 1998 — V. 8 — P. 324-364.

33. Y.E. Nesterov and B.T. Polyak. Cubic regularization of Newton method and its global performance.// Math. Program., Ser. A — 2006 — V. 108 - P. 177-205.

34. G.Pataki. Cone-LP's and semi-definite programs: facial structure, basic solutions, and the simplex method. // Tech. report, GSIA, Carnegie-Mellon University — 1995.

35. F. Rendl, R. J. Vanderbei, and H. Wolkowicz. Max-min eigenvalue problems, primal-dual interior point algorithms, and trust region subproblems. // Optim. Methods Softw. - 1995 - V. 5 — P. 1-16.

36. M.J. Todd. A study of search directions in primal-dual interior-point methods for semidefinite programming. // Optim. Methods Software — 1999 -V. 11-P. 11-46.

37. M.J. Todd, K.C. Toh, and R.H. Tutuncu. On the Nesterov-Todd direction in semidefinite programming. // SIAM Journal on Optimization — 1998 -V. 8 № 3 - P. 769-796.

38. M.J. Todd. Semidefinite optimization, manuscript // School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, USA - 2001.

39. L. Vandenberghe. Semidefinite programming // SIAM Rev. — 1996. — V. 38. - P. 49-95.

40. L. Vandenberghe and S. Boyd. Applications of semidefinite programming. // Appl. Numer. Math., - 1999 - V. 29 № 3 - P. 283-299.

41. H. Wolkowicz. Handbook of Semidefinite Programming / H. Wolkowicz, R. Saigal, L. Vandenberghe (eds). — Kluwer Academic Publishers, 2000.

- 656 p.

42. H. Wolkowicz. Semidefinite programming approaches to the quadratic assignment problem. // Nonlinear Assignment Problems: Algorithms and Applications - 2000 - V. 7 - P. 143-174.

43. H. Wolkowicz. Duality for semidefinite programming. // Encyclopedia of Optimization. Kluwer Academic Publishers, Boston, 2001.

44. Y. Zhang. On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. // SIAM Journal on Optimization - 1998 - V. 8 - P. 365-386.

45. Арнольд В.И. О матрицах, зависящих от параметров / В.И. Арнольд // УМН. - 1971. - Т. 26, вып. 2(158). - С. 101-114.

46. Необходимое условие в оптимальном управлении /А.П. Афанасьев, В.В. Дикусар, А.А. Милютин, С.В. Чуканов // М.: Наука, 1990.

47. Продолжение траекторий в оптимальном управлении // М.: Эдито-риал УРСС, 2005. - 263 с.

48. Бабынин М.С., Жадан В.Г. Барьерно-проективный метод для полуопределенного программирования. - Сообщения по прикладной математике. М.: ВЦ РАН, 2007.

49. Гантмахер Ф.Р. Теория матриц. — Издание 5-е. / М.: Физматлит, 2004

- 560с.

50. Дикин И.И. Метод внутренних точек в линейном и нелинейном программировании / И.И. Дикин. — М.: URSS, 2009. — 120 с.

51. Дикин И.И. Сходимость последовательности векторов двойственных переменных при исследовании одной задачи полуопределенного программирования // Кибернетика и системный анализ. 2003. № 2. С. 156-163.

52. Дикин И.И. Итеративное решение задач линейного и квадратичного программирования// Докл. АН СССР — 1967. — Т. 174 — №4 - С. 747-748.

53. Евтушенко Ю.Г., Жадан В.Г. Двойственные барьерно-проективные и барьерно-ньютоновские методы для линейного программирования // Журнал вычисл. матем. и матем. физики. — 1994. — Т. 36, № 7.

- С. 30-45.

54. Жадан В.Г. Двойственный мультипликативно-барьерный метод для полуопределенного программирования. М.: ВЦ РАН, 2009.

55. Орлов A.A. О численных методах решения задач полуопределенного программирования и примерах задач, для которых они являются неэффективными// Труды 52-й научной конференции МФТИ, Часть VII, Том 1 / МФТИ - М.-Долгопрудный, 2009,- С. 120-122.

56. Жадан В.Г., Орлов A.A. Двойственный метод Ньютона для линейной задачи полуопределенного программирования // Оптимизация и приложения. - 2010. М.: ВЦ РАН. — С. 87-108.

57. Орлов A.A. Двойственный метод Ньютона для задачи полуопределенного программирования// Труды 53-й научной конференции МФТИ, Часть VII, Том 1 / МФТИ - М.-Долгопрудный, 2010,- С. 75-77

58. Жадан В.Г., Орлов A.A. О сходимости двойственного метода Ньютона для линейной задачи полуопределенного программирования. // Известия Иркутского государственного университета. — 2011. — Т.4

- № 2. - С. 75-90.

59. Жадан В.Г., Орлов A.A. Двойственные методы внутренней точки для линейной задачи полуопределенного программирования. // Журнал вычисл. матем. и матем. физики. — 2011. — Т. 51, № 12. — С. 21582180.

60. Жадан В.Г., Орлов A.A. Допустимый и общий двойственные методы внутренней точки для линейной задачи полуопределенного про-граммирования//Тезисы 15й Байкальской международной школы-семинара "Методы оптимизации и их приложения—Т.2 "Математическое программирование—С. 81-86.

61. Жадан В.Г., Орлов A.A. Допустимый двойственный метод внутренней точки для линейной задачи полуопределенного программирования. // Автоматика и телемеханика. — 2012. — № 2. — С. 25-40.

62. Зоркальцев В.И. Об одном классе алгоритмов внутренних точек / В.И. Зоркальцев // Журнал вычисл. матем. и матем. физики. — 2009.

- Т. 49, № 12. - С. 2114-2130.

63. Измайлов А.Ф., Солодов М.В. Численные методы оптимизации. / М.: Физматлит, 2003.

64. Магнус Я.Р. Матричное дифференциальное исчисление с приложениями к статистике и эконометрике / Я.Р. Магнус, Ч. Нейдеккер. — М.: Физматлит, 2002. — 496 с.

65. Ортега Дж. Итерационные методы решения систем нелинейных уравнений со многими неизвестными / Дж. Ортега, В. Рейнболдт.

- М.: Мир, 1975. - 558 с.

66. Поляк Б.Т. Метод Ньютона и его роль в оптимизации и вычислительной математике.// Труды ИСА РАН. - 2006. — Т. 28, С. 44-62.

67. Поляк Б.Т., Щербаков П.С. Рандомизированный метод решения задач полуопределенного программирования.// Стохастическая оптимизация в информатике. — 2006. - Т. 2, № 1-1, С. 38-70.

68. Тыртышников Е.Е. Матричный анализ и линейная алгебра. М.: Физ-матлит, 2007.

69. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании.// ЖВМ и МФ, 1980, Т.20, № 1. С. 51-69.

70. Хорн Р., Джонсон Ч. Матричный анализ. / М.: Мир, 1989 — 655с.