Итерационные методы решения задач математического программирования со специальной структурой тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение.

Глава 1. Методы решения узкоблочных задач.

1.1. Алгоритм, основанный на методе симплексных погружений.

1.1.1. Вычислительная схема метода.

1.1.2. Модификация метода для узкоблочных ЗМП.

1.2. Алгоритм, основанный на методе Дикина.

1.2.1. Вычислительная схема метода Дикина.

1.2.2. Алгоритм решения узкоблочных ЗЛП.

1.3. Алгоритм, основанный на методе Кармаркара.

1.3.1. Краткое описание метода.

1.3.2. Модификация метода Кармаркара для узкоблочных задач.

1.4. Алгоритм, основанный на методе Ринальди.

1.4.1. Краткое описание метода.

1.4.2. Алгоритм решения узкоблочных ЗЛП.

1.5. Сравнение трудоемкости методов решения узкоблочных задач.

Глава 2. Методы решения задач с блочной и ленточной структурой.

2.1. Вычислительные схемы, основанные на методе симплексных погружений.

2.2. Вычислительные схемы, основанные на методе Дикина

2.2.1. Алгоритм решения блочных задач.

2.2.2. Алгоритм решения задач с ленточной структурой

2.3. Вычислительные схемы, основанные на методе Кармаркара.

2.4. Вычислительные схемы, основанные на методе Ринальди.

2.5. Сравнение трудоемкости методов решения блочных и ленточных задач.

Глава 3. Исследование устойчивости предложенных методов

3.1. Исследование устойчивости метода Дикина.

3.1.1. Оценка погрешности решения СЛУ методом квадратного корня.

3.1.2. Определение гарантированной точности вычисления выражения Sn = Л bjCjdj.

3.1.3. Оценка точности итерации метода Дикина.

3.2. Исследование устойчивости метода Кармаркара.

3.2.1. Гарантированная точность обращения матрицы по формуле одноранговой модификации.

3.2.2. Оценка точности итерации метода Кармаркара

3.3. Устойчивая модификация метода Дикина.

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

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

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

В работе [8] приводится модель функционирования региона, расположенного вдоль магистральной реки, зарегулированной плотинами гидроэлектростанций. Показано, что эта задача сводится к задаче математического программирования, матрица ограничений которой для 20 - 30 производителей и двух гидростанций имеет более Ю10 элементов.

Часто ЗЛП имеет большую размерность из - за того, что изучаемая система представляет собой совокупность однотипных, многократно повторяющихся во времени или пространстве подсистем, слабо связанных между собой. Такая структура типична для многих практических задач. Классическим примером таких задач являются различные производственно - транспортные задачи, в которых предприятия - поставщики связаны ограничениями на общие ресурсы и удовлетворение потребительского спроса.

Основополагающими для развития методов декомпозиции являются работы Дж. Данцига, Ф. Вулфа, И Корнай и Т. Липтака (см. [18], [33], [51]). Ими были предложены два основных декомпозиционных подхода, которые в настоящее время стали классическими и носят имена авторов. В этих подходах метод решения представляет собой итеративный процесс, на каждой итерации которого решаются так называемые координирующая и локальная задачи. Локальная задача состоит из ряда независимых подзадач, соответствующих каждому блоку. Решение координирующей задачи основано на методе последовательного улучшения плана в линейном программировании [31], [52], [9]. В подходе Данцига - Вулфа за основу принимается разбиение матрицы ЗЛП по строкам. Этот принцип декомпозиции повлек за собой многочисленный поток работ. В одних из них использовались различные методы решения координирующей задачи, например, сокращения невязок, одновременного решения прямой и двойственной задач и т. д. (см. [9], [23], [25], [33], [51]). Метод декомпозиции оказался также эффективным при решении задач транспортного типа [15]. В других работах принцип декомпозиции Данцига - Вулфа распространялся на нелинейные задачи ([16], [33], [44], [50], [51]).

В методе Корнай - Липтака [32] за основу берется разбиение линейных ограничений задачи по столбцам. Интересным представляется метод, в основу которого положен аналогичный принцип декомпозиции, наиболее подробно изложенный в [34].

Наряду с указанными основными декомпозиционными подходами впоследствии были разработаны другие принципиальные схемы разложения. Это - декомпозиция на основе релаксации ограничений, разложение, связанное с агрегированием переменных, параметрическая декомпозиция и т. д. (см. [35], [44], [51]).

В качестве обзорных работ по методам декомпозиции можно привести [10], [33], [51].

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

В 1964 - 1966 г.г. в отделе математической экономики ИМ СО РАН были предложены алгоритмы ([42], [23], [25]), сочетающие идеи декомпозиции с прямыми методами. Эксперименты подтвердили эффективность этих методов по сравнению с декомпозиционными методами [24, 49]. Последние алгоритмы основываются на методе последовательного улучшения плана [31]. С тех пор появились новые методы, имеющие полиномиальную трудоемкость.

В 1979 г. Л. Хачияном [48] был опубликован первый алгоритм с полиномиальной трудоемкостью для решения ЗЛП. Появившиеся с тех пор алгоритмы с такой трудоемкостью условно можно разбить на два типа: к первому типу отнесем алгоритмы, в которых допустимая область аппроксимируется эллипсоидами, а ко второму - алгоритмы, в которых допустимая область аппроксимируется симплексами. Наиболее известным среди алгоритмов первого типа является алгоритм, предложенный Н. Кармаркаром [66]. Численные эксперименты, описанные в [54, 75], подтвердили его эффективность. Статья Кармаркара породила огромный поток работ, посвященных различным вариантам метода внутренней точки. В [66], [61] приводятся варианты метода Кармаркара, в которых обращение матрицы на каждой итерации осуществляется с помощью одноранговой модификации.

Алгоритм Кармаркара сформулирован для ЗЛП с однородной системой ограничений на симплексе. Кроме того, предполагается, что оптимальное значение целевой функции равно нулю. В [60] приводится вариант метода внутренней точки, позволяющий избавиться от последнего условия. Существует несколько путей приведения задачи в стандартной форме к виду, когда для ее решения можно использовать алгоритм Кармаркара, [55], [58], [72], [78]. В данной работе будет использован алгоритм Ринальди, так как он сформулирован для ЗЛП именно того вида, который рассматривается в работе (см. Постановку задачи). Кроме того, в этой модификации не происходит увеличения размерности решаемой задачи.

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

В [77] приведен вариант алгоритма Кармаркара для решения задач квадратичного программирования.

Существует множество модификаций алгоритма Кармаркара, в которых шаг итеративного процесса осуществляется вдоль линейной комбинации двух основных направлений: направление спуска для целевой функции в преобразованном пространстве и направление "центральч ного пути", см., например, [28], [29], [62], [68], [69], [70]. Проективный метод в общем случае требует 0(nL) итераций, тогда как метод центрального пути - 0(y/nL) итераций. В настоящей работе будет рассматриваться исходный проективный метод Кармаркара с использованием одноранговой модификации для обращения матриц.

В настоящее время имеются заделы по решению задач большой размерности методами внутренней точки. В работах [57] и [71] рассматриваются модификации алгоритма Кармаркара для решения разреженных задач большой размерности, но произвольной структуры. В [73] предполагается, что матрица ограничений имеет некоторую специальную структуру без уточнения, какого именно вида. При модификации используются идеи метода декомпозиции Данцига-Вулфа. В [56] приведена модификация метода Кармаркара для блочно -диагональной и "starcase"матрицы ограничений. При этом также используются идеи метода декомпозиции. К сожалению, в работах, посвященных данной теме, исследование эффективности полученных алгоритмов проводится только экспериментально.

И. И. Дикин показал [21], что формулы, реализующие модификацию, предложенную Бернсом, практически совпадают с формулами, реализующими его метод, предложенный в 1967 г. [19], [20], [1], [22]. Поэтому в работе была также построена модификация метода Дикина для ЗЛП со специальной структурой. Для этого метода, к сожалению, до сих пор не доказана полиномиальная трудоемкость. Существуют модификации метода Дикина [63, 64], имеющие полиномиальную трудоемкость, однако в данной работе эти модификации не рассматриваются. Причиной служит то, что для этих модификаций учет структуры матрицы ограничений ЗЛП будет менее эффективным, чем для изначального метода Дикина. Это происходит из-за того, что, как и в методе Кармаркара, необходимо матрицу вида (ААт)~г, не имеющую уже специальной структуры, умножать на векторы и другие матрицы.

Рассматривается также метод, в котором допустимая область аппроксимируется симплексами. Это метод симплексов, изложенный в [5]. Трудоемкость этого метода не превосходит трудоемкости других методов данного типа.

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

Другой подход, предложенный С. К. Годуновым [13, 14], заключается в использовании параметров конкретной машины: наименьшего машинного числа, большего нуля, и числа е\ такого, что 1 + е\ ~ наименьшее машинное число, большее 1. Этот подход был использован Р. А. Звягиной при оценке погрешности решения систем линейных уравнений с блочно - диагональными матрицами [26] и М. А. Яковлевой при вычислении сингулярных чисел двухдиагональной матрицы [53]. В данной работе при оценке гарантированной точности решения задач линейного программирования также используется подход С. К. Годунова.

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

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

Апробация работы

Результаты докладывались на следующих конференциях:

1. XXXIV международная научная конференция " Студент и научно-технический прогресс", Новосибирск, 1996г.

2. Второй Сибирский Конгресс по Прикладной и Индустриальной Математике , Новосибирск, 25 -30 июня 1996 г.

3. XXXV международная научная конференция "Студент и научно-технический прогресс". Новосибирск, 1997 г.

4. Проблемы Оптимизации и Экономические Приложения . Омск, 1-5 июля 1997 г.

6. Международной Сибирской Конференции по Исследованию Операций. Новосибирск, 22-27 июня 1998 г.

7. XI -я Всероссийская конференция "Математическое программирование и приложения". Екатеринбург. 22-26 февраля 1999 г.

8. "Проблемы Теоретической Кибернетики". Нижний Новгород. 17 - 22 мая 1999 г.

9. Международная конференция "Дискретный анализ и исследование операций". Новосибирск. 26 июня - 1 июля 2000 г.

10. XII Байкальская международная конференция "Методы оптимизации и их приложения". Иркутск, Байкал, 24 июня - 1 июля 2001 г.

Структура и объем работы

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

Заключение

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

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

2. Выполнена оценка гарантированной точности методов Кармаркара и Дикина для решения задач линейного программирования.

3. Установлено преимущество предложенной модификации метода Дикина для узкоблочных и блочных задач.

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

Предложенный в настоящей работе инструментарий оказался применим и для решения известного класса прикладных задач - производственно-транспортной задачи [6, 40].

1. Анцыз С. М., Дикин И.И. Об одном численном методе решения задачи линейного программирования и некоторых его обобщений. // Управляемые системы, 1969. Вып.З. Новосибирск: Ин-т математики СО РАН СССР.

2. Анцыз С.М., Гайзлер М.В. Модификация метода Дикина для решения задач со специальной структурой. Второй Сибирский Конгресс по Прикладной и Индустриальной Математике. Новосибирск, 1996. Тезисы докладов. С. 131.

3. Анцыз С.М., Гайзлер М. В. О задачах математического программирования со специальной структурой. Проблемы Оптимизации и Экономические Приложения . Омск, 1997 г. Международная конференция, тезисы докладов. С. 16.

4. Анцыз С. М., Пудoea М. В. Методы внутренней точки для решения задач со специальной структурой. Новосибирск: Изд-во ИМ СО РАН. 1997 г. 27 с. (Препринт / РАН Сиб. отд-е. Институт математики; № 44).

5. Ащепков JI. Т., Белов Б. И., Булатов В. П. Методы решения задач математического программирования и оптимального управления. Новосибирск: Наука, 1984.

6. Бахтин А. Е., Пастухов Н. Ф. Об одном композиционном методе построения и анализа оптимальных производственнотранспортных планов. // "Оптимизация развития и размещения промышленного производства". Н-к: Наука, 1974. С. 62-86.

7. Белоусов Е. Г., Андронов В. Г. Разрешимость и устойчивость задач полиномиального программирования. М.: Изд-во МГУ, 1993.

8. Болдина Н. В. Об одной модели функционирования и развития региона. // Материалы конференции " Дискретный анализ и исследование операций". Новосибирск, 2000 г. С. 205.

9. Булавский В. А., Звягина Р. А., Яковлева М. А. Численные методы линейного программирования: специальные задачи. М.: Наука, 1977.

10. Верина JI. Ф., Танаев В. С. Декомпозиционные подходы к решению задач математического программирования (обзор). // Экономика и Мат. Методы, 1975. Т. XI. Вып. 6, с. 1160-1172.

11. Воеводин В. В. Численные методы алгебры. Теория и алгорифмы. М.: Наука, 1966.

12. Воеводин В. В. Ошибки округления и устойчивость в прямых методах линейной алгебры. М.: Изд-во МГУ, 1969.

13. Годунов С. К. Решение систем линейных уравнений. Новосибирск: Наука, 1980.

14. Годунов С. К. и др. Гарантированная точность решения систем линейных уравнений в евклидовых пространствах. Новосибирск: Наука, 1988.

15. Голъштейн Е. Г., Немировский А. С., Соколов Н. А. Новый алгоритм двойственной декомпозиции с приложением к задачам транспортного типа. // Экономика и Мат. Методы, 1994, Т. 30, № 2. С. 127-136.

16. Голъштейн Е. Г. Двойственный декомпозиционный метод решения общей задачи дробно-линейного программирования. // Экономика и Мат. Методы, 1999. Т. 35, № 1. С. 80-87.

17. Гранберг А. Г. Оптимизация территориальных пропорций народного хозяйства. М.: Экономика, 1973. 246 с.

18. Данциг Дж. Линейное программирование, его применение и обобщения. М.:" Прогресс", 1966.

19. Дикин И. И., Зоркалъцев В. И. Итеративное решение задач математического программирования. Новосибирск: Наука, 1980.

20. Дикин И.И., Попова О. М. Поиск внутренней допустимой точки системы линейных ограничений. Иркутск: Изд -во СЭИ СО РАН, 1995 г. (Препринт / РАН. Сиб. отд-е. СЭИ)

21. Дикин И.И. Letter to the editor. //Math. Program. 1988. Vol. 41, P. 393-394.

22. Дикин И.И., Попова О. М. Исследование и ускорение сходимости алгоритмов метода внутренних точек. Новосибирск: Наука. СО РАН, 1997.

23. Звягина Р. А. Задачи линейного программирования с блочно-диагональными матрицами. // Оптимальное планирование: сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1964. Вып. 2. С. 50-61.

24. Звягина Р. А. Программа реализации на М-20 модифицированного симплекс метода с узкоблочной матрицей. // Оптимальное планирование: сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1966. Вып. 4. С. 63-124.

25. Звягина Р. А. Об общем методе решения задач линейного программирования блочной структуры. // Оптимизация: сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1971. Вып. 1(18). С. 22-40.

26. Звягина Р. А. Об оценке погрешности в системе с клеточным разбиением матрицы. // Оптимизация: сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1984. Вып. 34(51). С. 76-87.

27. Зоркалъцев В. И. Обоснование алгоритмов внутренних точек // Журнал вычислительной математики и математической физики, 1999. Т. 39. № 2. С. 208-221.

28. Зоркалъцев В. И., Филатов А. Ю. Новые алгоритмы оптимизации в конусе центрального пути. // Дискретный анализ и исследование операций, 1999. Серия 2. Т. 6. № 1. С. 33-42.

29. Зоркалъцев В. И. Алгоритмы оптимизации в конусе центрального пути. // Журнал вычислительной математики и математической физики, 2000. Т. 40. № 2. С. 318-327.

30. Ильин В. П. Методы неполной факторизации для решения алгебраических систем. М.: Наука, 1995.

31. Канторович Л. В. Экономический рассчет наилучшего использования ресурсов. М., Изд-во АН СССР, 1959.

32. Корнай ИЛиптак Т. Планирование на двух уровнях. / В кн. "Применение математики в экономических исследованиях", т. 3. М.: Мысль, 1965.

33. Лэсдон Л. С. Оптимизация больших систем. М.: Наука, 1975.

34. Макаров В. ЛМаршак В. Д. Модели функционирования отраслевых систем М.: Экономика, 1979.

35. Первозванский А. А., Гайцгори В. Г. Декомпозиция, агрегирование и приближенная оптимизация. М.: Наука, 1979.

36. Писсанецки С. Технология разреженных матриц. М.: Мир, 1988.

37. Пудова М.В. О коэффициенте уменьшения трудоемкости для задач со специальной структурой. Международная Сибирская Конференция по Исследованию Операций. Новосибирск, 1998. Тезисы докладов. С. 46.

38. Пудова М.В. О коэффициенте уменьшения трудоемкости некоторых алгоритмов для задач со специальной структурой. Проблемы Теоретической Кибернетики. Нижний Новгород, 1999. Тезисы докладов. С. 194.

39. Пудова М.В. О коэффициенте уменьшения трудоемкости для задач со специальной структурой. Международная Сибирская Конференция по Исследованию Операций. Новосибирск, 2000. Тезисы докладов. С. 106.

40. Пудова М. В. Решение производственно-транспортных задач методами внутренней точки. XII Международная конференция "Методы оптимизации и их приложения". Иркутск. Байкал. 2001 г. Т. 1-"Математическое программирование". С. 43-47.

41. Пудова М. В. Устойчивая модификация метода Дикина. // Применение математических методов в исследовании динамических процессов: сб. науч. тр. (под ред А. Т. Семенова). Новосибирск: НГА-ЭиУ, 2002. С. 63-83.

42. Рубинштейн Г. Ш. О решении задач линейного программирования большого объема. // Оптимальное планирование: сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1966. Вып. 2. С. 3-22.

43. Схрейвер А. Теория линейного и целочисленного программирования. М.: Мир, 1991.

44. Танаев В. С. Декомпозиция и агрегирование в задачах математического программирования. Минск, 1987.

45. Треногин В. А. Функциональный анализ. М.: Наука, 1993.

46. Уилкинсон Дж. X. Алгебраическая проблема собственных значений. М.: Наука, 1970.

47. Фаддеева В. Н., Колотилина JI. Ю. Вычислительные методы линейной алгебры: набор матриц для тестирования. Ленинград, 1982.

48. Хачиян JI. Г. Полиномиальный алгоритм для задач линейного программирования. Докл АН СССР. 1979. № 20. С. 191-194.

49. Шмырев В. И. Контроль исходных данных для программы, реализующей модифицированный симплекс метод с узкоблочной матрицей. // Оптимальное планирование: сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1966. Вып. 4. С. 125-136.

50. Шор Н. 3., Соломон Д. И. Декомпозиционные методы в дробно -линейном программировании. Кишинев, 1989.

51. Цурков В. И. Декомпозиция в задачах большой размерности. М.: Наука, 1981.

52. Юдин Д. Б., Голъштейн Е. Г. Линейное программирование. Теория и конечные методы. М.: Физматгиз, 1963.

53. Яковлева М. И. Вычисление сингулярных чисел базисной матрицы в двухкомпонентных задачах линейного программирования. // Оптимизация: сб. науч. тр. Новосибирск: Ин-т математики СО АН СССР, 1984. Вып. 31(48). С. 74-89.

54. Adler I., Resende M. G., Veiga G., Karmakar N. An implementation of Karmakar's algorithm for linear programming// Math. Program. 1984. V. 44. N 3. P. 297-337.

55. Bernes E. K. A variation on Karmarkar's algorithm for solving programming problems // Math. Program. 1986. V. 36. N 2. P. 174182.

56. Choi I. C., Goldfarb D. Exploiting special structure in a primal-dual path-following algorithm // Math. Program. 1993. V. 58. N 2. P. 3353.

57. Fujisawa K., Kojima M., Nakata K. Exploiting sparsity in primal-dual interior-point methods for semidefinite programming. // Math. Program. 1997. V. 79. N 2. P. 235-255.

58. Gay D. A variant of Karmarkar's linear programming algorithm for problems in standart form. // Math. Program. 1987. V. 37. N 1. P. 81-90.

59. Goldfarb D., Mehrotra S. A relaxed version of Karmarkar's method 11 Math. Program. 1988. V. 40. N 3. P. 289-315.

60. Goldfarb D., Mehrotra S. Relaxed variant of Karmarkar's algorithm for linear programming with unknown optimal objective value. // Math. Program. 1988. V. 40. N 2. P. 183-195.

61. Gonzaga С. C. Polinomial affine algorithms for linear programming. 11 Math. Program. 1990. V. 49. N 2. P. 7-21.

62. Gonzaga С. C. An algorithm for Solving Linear Programming Problems in 0(пъЬ) Operations, in: Progress in Mathematical Programming: Interior-Point and Related Methods, N. Megiddo, ed., Springer-Verlag. New York, 1989. P. 1-28.

63. Jansen В., Roos С., Terlaky Т. A polynomial primal-dual Dikin-type algorithm for linear programming. // Delft University of Texnology, The Netherlands, 1993. To appear in Journal of Optimisation Theory and Applications. Report N 93-36. 30 P.

64. Dikin I.I., Roos C. Convergence of the dual variables for the primal affine scaling method with unit steps in the homogeneous case. // J. Optimisation Theory and Applications, 1997. V. 95. N. 2. P. 305-321.

65. Flippo О. E., A. H. J. Rinnooy Kan. Decomposition in general mathematical programming. // Math. Program. 1993. V. 60. N 3. P. 361-381.

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

67. Kojima M., Mizuno S., Yoshise A. A primal-dual interior-point algorithm for linear programming, in: Progress in Mathematical Programming: Interior-Point and Related Methods, N. Megiddo, ed., Springer-Verlag. New York, 1989. P. 29-47.

68. Kojima M., Mizuno S., Yoshise A. An 0(л/пЬ) iteration potential reduction algorithm for linear complementarity problems. // Math. Program. 1991. V. 50. N 3. P. 331-343.

69. Megiddo N. Pathways to the Optimal Set in Linear Programming, in: Progress in Mathematical Programming: Interior-Point and Related Methods, N. Megiddo, ed., Springer-Verlag. New York, 1989. P. 131158.

70. Monteiro R., Adler I. Interior path-following primal-dual algorithms. Pt 1 : Linear programming. // Math. Program. 1989. V. 44. N 1. P. 27-41.

71. Shanno D. F. Computing Karmarkar projections quicly. j I Math. Program. 1988. V. 41. N 1. P. 61-71.

72. Rinaldi G. A projective method for linear programming with box-type constrains // Algorithmica. 1986. N 1. P. 517-527.

73. Todd M. J. Exploiting special structure in Karmarkar's linear programming algorithm. // Math. Program. 1988. V. 41. N 1. P. 97113.

74. Todd M. J., Burrell B. P. An extension of Karmarkar's algorithm for linear programming using dual variables. // Algorithmica. 1986. N 1. P. 409-424.

75. Vanderbei R. JCarpenter I. J. Symmetric indefinite systems for interior point methods// Math. Program. 1993. V. 58. N 1. P. 1-33.

76. Vanderbei R. J., Meketon M. S., Freedman B. A. A modifications of Karmarkar's linear programming algorithm. // Algorithmica. 1986. N 1. P. 395-401.

77. Ye Y. An Extention of Karmarkar's Algorithm and the Trust Region Method for Quadratic Programming, in: Progress in Mathematical Programming: Interior-Point and Related Methods, N. Megiddo, ed., Springer-Verlag. New York, 1989. P. 49-63.

78. Ye Y., Kojima M. Recovering optimal dual solutions in Karmarkar's polinomial algorithm for linear programming. // Math. Program. 1987. V. 39. N. 3. P. 305-317.