Методы решения задач линейной оптимизации большой размерности тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Моллаверди Насер
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Москва
МЕСТО ЗАЩИТЫ
|
||||
|
2005
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
Моллаверди Насер
МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОЙ ОПТИМИЗАЦИИ БОЛЬШОЙ
РАЗМЕРНОСТИ
01.01.09 — Дискретная математика и математическая кибернетика
Автореферат диссертации на соискание ученой степени кандидата физико-математических наук
Москва — 2005
Работа выполнена на Факультете вычислительной математики и кибернетики МГУ им М В Ломоносова и в Вычислительном центре им. А. А. Дородницына Российской Академии наук.
Научные руководители:
Официальные оппоненты-
Ведущая организация-
член-корр. РАН, доктор физико-
математических наук,
профессор
(О. Г. Евтушенко,
кандидат физико-математических наук А. И. Голиков
доктор физико-математических наук,
профессор
А. В. Лотов,
кандидат физико-математических наук У. X. Малков
Институт системного анализа Российской Академии наук
Защита состоится "У" ауеЛЛ 2005 в ч. 30 мин. на заседании диссертационного совета Д 002.017.02 при Вычислительном центре им А.А Дородницына РАН по адресу: 119991, г. Москва, ул. Вавилова, дом 40, тел: 135-24-89.
С диссертацией можно ознакомиться в библиотеке ВЦ РАН. Автореферат разослан " Ы» 03 2005.
Ученый секретарь Диссертационного совета Д 002.017.02 при ВЦ РАН
доктор физико -математических наук ^ Рязанов В. В
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Объект исследования и актуальность темы. Теории и методам решения задач линейного программирования (ЛП) и систем линейных неравенств посвящено огромное количество исследований. Огромный интерес к задачам ЛП определяется прежде всего их экономической содержательностью, многочисленными практическими приложениями и применением в качестве вспомогательных процедур в некоторых численных методах нелинейной оптимизации. Несмотря на продолжающееся повышение производительности вычислительной техники, всегда актуальным остается возможность решения задач линейной оптимизации большой размерности.
Первоначально исследования в области численных методов ЛП концентрировались в основном на симплекс-методе. Далее разрабатывались разнообразные итерационные методы, а примерно с середины 80-х годов внимание многих исследователей переключилось на методы внутренних точек.
В работах советских математиков в 70-х годах активно разрабатывался подход к задачам ЛП, основанный на использовании метода внешних штрафных функций (квадратичная функция штрафа). Хорошо известны работы в этом направлении, которые проводились А.С.Антипиным, Ф П.Васильевым, Е.Г Гольштейном, И.И.Ереминым, Б.Т.Поляком, Б.С.Разумихиным, Н.В.Третьяковым и др. исследователями из МГУ, ИПУ, ЦЭМИ, ВЦ РАН. Примерно в это же время в США близкие исследования проводились О.Мангасарьяном и его сотрудниками. В их работах основное внимание уделялось нахождению нормальных решений в задачах ЛП, т.е. решений, обладающих минимальной евклидовой нормой. Широкое распространение этот подход в то время не получил. Только в последнее время появились свидетельства о его перспективности с вычислительной точки зрения.
Это связано с использованием быстро сходящегося обобщенного метода Ньютона для безусловной минимизации выпуклой кусочно квадратичной непрерывно дифференцируемой штрафной функции. У нее не существует матрицы Гессе. Но для такой штрафной функции можно построить обобщенный метод Ньютона, введя обобщенную матрицу Гессе. В работах О.Мангасарьяна, К.Канзова и др. доказана ^нсчная глобальная судимость обобщенного мето-
í VI ^
герй>}»г
Ж*
{¿.¡¡стс
да Ньютона для минимизации выпуклой кусочно квадратичной функции. Минимизация этой штрафной функции, примененной к двойственной задаче ЛП, дает возможность получить точное нормальное (с минимальной евклидовой нормой) решение прямой задачи, начиная с некоторого конечного значения коэффициента штрафа.
Заметим, что, как правило, большие задачи ЛП имеют неединственное решение. Указанные методы представляют ценность тем, что дают различные решения в случае неединственности. Так, симплекс-метод дает решение, которое принадлежит вершине многогранного множества. Методы внутренней точки сходятся к решению, в котором выполнено условие строгой дополняющей нежесткости. Метод квадратичной штрафной функции, будучи примененным к двойственной задаче, дает возможность получить нормальное решение прямой задачи при конечном значении коэффициента штрафа.
Весьма актуальным является обобщение метода квадратичной штрафной функции для получения проекции произвольной точки на множество решений прямой или двойственной задач ЛП. Задача нахождения проекции заданной точки на множество решений часто может иметь важный содержательный смысл для приложений. Так, пусть известен некоторый оптимальный план, который из-за изменившихся условий уже не только не оптимальный, но может быть и недопустимым. Желательно найти такой новый оптимальный план, который был бы ближайшим к старому.
В связи с вышеизложенным целью диссертационной работы является разработка методов решения задач линейного программирования с большим числом переменных (несколько десятков миллионов переменных), нахождение проекции заданной точки на множество решений задачи ЛП, программная реализация и проведение вычислительных экспериментов.
В соответствии с целью исследования были поставлены следующие конкретные задачи:
1. Разработать метод нахождения проекции заданной точки на множество решений прямой задачи ЛП с большим числом неотрицательных переменных (несколько десятков миллионов) и средним числом ограничений типа равенств (несколько тысяч);
2. Разработать метод нахождения проекции заданной точки на мно-
жество решений двойственной задачи ЛП с большим числом переменных (несколько миллионов) и средним числом ограничений типа неравенств (несколько тысяч);
3. Исследовать методы нахождения проекции точки на множество решений задачи ЛП, получить оценку порогового значения коэффициента штрафа, начиная с которого в результате однократной максимизации вспомогательной функции получается проекция заданной точки;
4. Используя обобщенный метод Ньютона, реализовать в системе MATLAB предложенные методы решения задач ЛП большой размерности;
5 Провести вычислительные эксперименты с разработанными программами в системе MATLAB и выполнить сравнение с работой доступных коммерческих и исследовательских пакетов решения задач ЛП;
К методам исследования, примененным в данной работе, относятся: теория и численные методы оптимизации, линейная алгебра, программирование в системе MATLAB.
Научная новизна:
1. Предложены новые методы нахождения проекции заданной точки на множество решений прямой и заданной точки на множество решений двойственной задач ЛП, в которых обобщаются идеи квадратичных штрафных функций.
2. Получены формулы для определения пороговой величины коэффициента штрафа, начиная с которого проекция заданной точки на множество решений задачи ЛП получается в результате однократной максимизации вспомогательной функции. Если положительный коэффициент штрафа меньше пороговой величины, то предлагаемые итерационные процессы сходятся за конечное число шагов к некоторым решениям прямой и двойственной задач ЛП
3. Методы реализованы в системе MATLAB. Для решения вспомогательных задач безусловной максимизации использован обобщенный метод Ньютона.
4 Методы апробированы на многочисленных тестовых задачах большой размерности (до пятидесяти миллионов переменных) и с умеренным количеством ограничений (до четырех тысяч). Время решения таких задач на Pentium IV с тактовой частотой 2,6 ГГц и оперативной памятью 1Гб, состав-
ляло от нескольких десятков до нескольких тысяч секунд.
5. Сравнительный анализ предложенных методов решения задач ЛП с доступными коммерческими и исследовательскими пакетами показал, что для задач невысокой размерности предложенные методы дают примерно такие же результаты и превосходят эти пакеты на задачах очень большой размерности.
Теоретическая и практическая ценность данной работы состоит в том, что разработаны, исследованы и программно реализованы методы решения задач линейного программирования большой размерности, которые позволяют из множества решений задачи ЛП выделять проекцию заданной точки.
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на: Всероссийской конференции "Математическое программирование и приложения"(Екатеринбург, 2003 г.), Всероссийской конференции "Алгоритмический анализ неустойчивых за-дач"(Екатеринбург, 2004 г.), на научных семинарах ВЦ РАН, на научном семинаре факультета ВМиК МГУ по оптимизации под рук. Ф.П.Васильева и А.С.Антипина.
Публикации. По теме диссертации опубликовано четыре работы.
Объем и структура работы. Диссертация состоит из введения, трех глав, заключения и списка литературы Общий объем работы составляет 95 страниц, включая 9 рисунков, 12 таблиц и список литературы из 61 наименования ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении показана актуальность проблемы и приведен краткий обзор содержания работы.
В главе 1 предлагается метод решения прямой задачи ЛП с большим числом неотрицательных переменных и средним числом ограничений-равенств В §1.1 рассматривается задача нахождения проекции заданной точки на множество решений прямой задачи. Вместо обычной кусочно квадратичной штрафной функции предлагается использовать вспомогательную функцию, сходную с модифицированной функцией Лагранжа.
Пусть задана прямая задача ЛП в стандартной форме:
/, = шт стх, X = {х £ Яп : Ах = Ь, х > 0„}.
Двойственная к ней имеет вид:
/, = тах Ьти, и = {и £ В™ : А1 и < с}. (£>)
иеи
Произвольное решение прямой задачи (Р) обозначим через х*, а произвольное решение двойственной задачи (£>) обозначим через и,
Пусть задан произвольный вектор х € В.п Рассмотрим задачу нахождения проекции х, этой точки х на множество решений Х„ прямой задачи (Р)
1-\\х,-х\^ = тт1-\\х-х\\\ (1)
X. = {х € Я" : Ах = Ъ, стх = /„, х > 0„}.
Здесь и всюду ниже, если не оговорено иное, используется евклидова норма векторов.
Двойственная задача к (1) заключается в решении следующей задачи максимизации:
тах тах [ЬТр - 1||(* + Атр - /?с)+||2 - /?/, + 1||*||2]. (2)
Решив задачу (2), найдем оптимальные р и /?, после их подстановки в формулу
х = {х + Атр - (Зс)+ (3)
получаем проекцию х„, т.е. решение задачи (1) Здесь а+ обозначает вектор а, у которого все отрицательные компоненты заменены на нули.
К сожалению, задача безусловной оптимизации (2) содержит неизвестную априори величину /„ - оптимальное значение целевой функции задачи ЛП. Однако задачу (2) можно упростить, избавившись от этого недостатка Для этого вместо (2) предлагается решать следующую упрощенную задачу безусловной максимизации:
Д = тах 5(р, /?,£), (4)
ре я™
где вектор х и скаляр /? фиксированы, а функция 8(р,@,х) определена следующим образом:
5(р,)М) = Ътр - \\\{х + Атр - Ш?- (5)
Введем некоторые обозначения. Без потери общности предположим, что первые I компонент проекции х, строго больше нуля. В соответствии с этим предположением представим векторы х,, х и с, а также матрицу А в виде
где 7 - произвольное число. Индексное множество а определено следующим образом: а = {/-1-1 < г < п : {и, = — А^и^У > 0} и введено обозначение: 5 = + — х1) Следующая теорема устанавливает, что /3»
при некоторых предположениях является пороговым значением коэффициента штрафа /3.
Теорема 1.1. Пусть множество решений X, задачи (Р) непусто, ранг матрицы А[, соответствующий ненулевым компонентам вектора х«, равен т. Тогда при любом /3 > 0, проекция точки х на множество решений X, прямой задачи (Р) определяется по формуле
где р(/3) - решение задачи безусловной максимизации (4)-
Эта теорема позволяет заменить задачу (2), содержащую априори неизвестное число /», на задачу (4), в которой вместо этого числа фигурирует полуинтервал [/?,, +оо), что существенно проще с вычислительной точки зрения Очевидно, что значение найденное из формулы (7), может быть отрицательным. В этом случае расстояние от заданной проектируемой точки до множества решений прямой задачи совпадает с расстоянием от этой точки до допустимого множества прямой задачи. В этом же параграфе показана связь задачи безусловной максимизации (4) вспомогательной функции с методами регуляризации и квадратичного штрафа, примененного к двойственной задаче (Г>) Подставляя найденную проекцию во вспомогательную функцию 8(р,/3,х) и максимизируя ее по р при любом /3 > 0, находим некоторое
¿7 = [£'Л АТ = СТ = {с'\ с"т], А = [А1 I Л,], (6)
где х' > 0/, х^ — 0,1, ¿ = п — 1. Определим
(7)
£. = {£ + Атр(р) - /?с)+,
(8)
точное решение двойственной задачи ЛП, что утверждается в следующей теореме 1.2.
Теорема 1.2. Пусть множество решений Xt задачи ЛП (Р) непусто. Тогда для любых /3 > 0 и х = х, 6Х, точное решение двойственной задачи (И) находится по формуле и* =р(0)/0, где р(/3) - точка, доставляющая максимум функции 5(р, /3, х,).
Для иллюстрации работы теоремы 1.2 обратимся к методу внешнего квадратичного штрафа, примененному к двойственной задаче (£>), т.е рассмотрим задачу
тах{Ьти-§||(Лти-с)+||2}. (9)
Оказывается, что можно получить точное решение и„ двойственной задачи (£>), не устремляя в (9) коэффициент штрафа /? к +оо. Если в задаче (9) положительный коэффициент штрафа /3 > /?», то согласно теореме 1.1 по формуле (8), в которой х = 0„, находим нормальное решение х, прямой задачи (Р). Согласно теореме 1.2 далее следует решить задачу безусловной максимизации:
тах {ЬТи - |||(х. + /3(Ати - с))+1|2}- (Ю)
В результате ее решения получаем решение и{(3) = и, е (/, двойственной задачи (£)) при любом 0 > 0. Отметим, что задача (10) не сложнее, чем задача (9). Таким образом, решая только две задачи безусловной максимизации, можно получить точные решения прямой и двойственной задач ЛП, если в задаче (9) взять положительный коэффициент штрафа /3 > /3».
В §1.2 приводится итерационный метод одновременного нахождения решений прямой и двойственной задач ЛП. В этом методе не требуется знать пороговое значение коэффициента штрафа. Но если выбранное значение коэффициента меньше порогового значения, то метод за конечное число шагов находит некоторое решение прямой задачи, а не проекцию начальной точки на множество решений прямой задачи ЛП.
Предлагается использовать для одновременного решения прямой и двойственной задач ЛП следующий итерационный процесс:
Хк+1 = (хк + Атрм - /Зс)+, (11)
где параметр (3 фиксирован, а вектор рк+1 определяется из решения следующей задачи безусловной максимизации:
рк+1 € аг§тахредт {Ьтр - + Атр - /Зс)+||2}. (12)
Этот итерационный процесс является конечным и дает точное решение прямой задачи (Р) и точное решение двойственной задачи (Р).
Теорема 1.3. Пусть множество решений Хг прямой задачи (Р) непусто. Тогда при любом /3 > 0 и при любой начальной точке хо итерационный процесс (11), (12) сходится к х* € Х„ за конечное число шагов и}. Формула и* = Ри+г/Р дает точное решение двойственной задачи (В).
Заметим, что хш = х„ € X« является проекцией точки на множество решений X» задачи (Р).
При некоторых дополнительных предположениях приводится простое доказательство сходимости метода (И), (12) и в §1.3 - доказательство конечной сходимости.
Безусловная максимизация в (4) и (12) может выполняться любым методом, например методом сопряженного градиента. Но, как показал О.Мангасарьян, для безусловной максимизации вогнутой дифференцируемой кусочно квадратичной функции особенно эффективен обобщенный метод Ньютона. В §1.4 приводятся сведения об обобщенном методе Ньютона, который рекомендуется применять для безусловной максимизации вспомогательной функции, если в прямой задаче ЛП задано среднее число ограничений (до 4 тысяч). Обобщенный метод Ньютона для данной задачи глобально сходится за конечное число шагов. В последнем параграфе первой главы предложенный подход переносится на задачу нахождения проекции заданной точки на множество решений систем линейных уравнений с неотрицательными переменными.
В главе 2 рассматривается подход к решению двойственной задачи ЛП с большим числом переменных (до нескольких миллионов) и средним числом ограничений-неравенств (до 4 тысяч). Ищется проекция заданной точки на множество решений двойственной задачи ЛП. Из множества решений £/, двойственной задачи (V) выделим решение й», ближайшее в евклидовой норме к некоторому заданному вектору и, т.е. найдем единственное решение й.
задачи строго выпуклого квадратичного программирования.
{/, = {иеГ : Ати < с, Ьти = /.}.
1ТТ1
Здесь /, - оптимальное значение целевой функции задачи ЛП (£))
Как и в случае задачи (2), двойственная к (13) задача содержит неизвестную априори величину /, - оптимальное значение целевой функции задачи Л П. Однако эту двойственную задачу также можно упростить, избавившись от этой трудности, и решать следующую упрощенную задачу максимизации на положительном ортанте-
где вектор й и коэффициент штрафа а фиксированы, а функция Б {у, а, и) определена следующим образом:
Для того чтобы привести оценку порогового значения коэффициента штрафа, введем некоторые обозначения. Будем считать, что прямая задача ЛП (Р) имеет единственное, быть может, вырожденное решение х„. В этом решении х^ > 0) - совокупность положительных компонент, причем I < то. В случае невырожденного решения I — т. Обозначим индексное множество, соответствующее положительным компонентам вектора х», через I,. Если х„ -вырожденное решение, то двойственная задача ЛП (й) имеет неединственное решение. Матрицу ограничений А = ^ В • N | представим в соответствии с разбиением вектора-невязок V, = с — АТй, ограничений двойственной задачи (£>) на нулевые Т] = = и положительные V? > компонен-
ты, где к = 1 + з<т, ¿ = п — к. Используя это разбиение, представим вектор х» в виде х1 — [х^Т В свою очередь, матрица В представлена
в соответствии с разбиением вектора х^ на положительные и нулевые х^ компоненты, т.е. В = ^ В1 \ В$ В силу единственности решения я* матрица В состоит из к < тп линейно независимых столбцов, т.е. ее ранг равен
1\ = тах Б(у, а, й)
(14)
5(у, а, й) = —сту - йт(аЬ - Ау) - |||аЬ - Ау\\2. (15)
к Для дальнейшего потребуется вектор г] 6 определенный следующим образом- т] = (Вт5)_1(св — Втй). Заметим, что если к = тп, то вектор т] легко приводится к виду 77 = В_1(й, — й) Кроме того, определим следующую величину
Г тах Д. если ^ ф 0 , а* = I (х'] (16)
I 7 > —оо, если = 0 ,
где 7 - произвольное число.
Теорема 2.1. Пусть множество решений V, задачи £) непусто, ранг матрицы В, соответствующей нулевым компонентам вектора-невязок V* двойственных ограничений, вычисленных в решении й„, равен к < т. Решение й, задачи (13) представимо в виде
й, = й+Вт) = й+ Вьт)1 + В8 г?5,
где г/5 < 05, а решение [у, а] двойственной задачи к (13) представимо в виде
> о*, гЛ = о* (17)
при любом а, удовлетворяющем условию а > а,.
Следующая теорема является аналогом теоремы 1.1. Теорема 2.2. Пусть выполнены условия теоремы 2.1. Тогда при любом а > а,, где а* определяется формулой (16), проекция точки й на множество решений II* двойственной задачи (Б) определяется по формуле
й* = й + аЬ — Ау(а), (18)
где у (а) - решение задачи максимизации (Ц).
Величина порогового значения а, может быть отрицательной Также имеется аналог теоремы 1.2. Если известна какая-нибудь точка и» € £/*, то можно получить решение прямой задачи (Р) после однократного решения задачи максимизации (14).
Теорема 2.3. Пусть множество решений С/, задачи ЛП (В) непусто Тогда для любых а > 0 и « = и, £ [/, точное решение прямой задачи
,УВ =
У1
У3
ах.
(Р) находится по формуле ж, = у(а)/а, где у(а) - точка, доставляющая максимум функции S(y,a,ut).
В этом же параграфе показана связь введенной вспомогательной задачи (14), (15) с методами регуляризации и квадратичным штрафом, примененным к прямой задаче ЛП.
В §2.2 приводится итерационный метод одновременного решения прямой и двойственной задач ЛП, для которого не требуется превышения порогового значения коэффициента а,, если не требуется найти проекцию начальной точки на множество решений двойственной задачи.
Рассмотрен следующий итерационный процесс:
uk+i=Uk + ab-Ayi+1. (19)
Здесь параметр а фиксирован, а вектор уь+\ определяется из решения следующей задачи минимизации на положительном ортанте.
уы € arg min {cTy + иЦаЪ - Ау) + Ьей - Ау\\2}. (20)
у€К5. £
Этот итерационный процесс является конечным и дает точное решение прямой задачи (Р) и точное решение двойственной задачи (D).
Теорема 2.4. Пусть множество решений U„ двойственной задачи (D) непусто. Тогда при любом а > 0 и при любой начальной точке щ итерационный процесс (19) сходится к и» 6 U, за конечное число шагов V. Формула х, = i/a дает точное решение прямой задачи (Р).
Глава 3 посвящена программной реализации и вычислительным экспериментам. В §3.1 приведено описание генераторов задач ЛП и систем линейных уравнений с неотрицательными переменными. Для систем, генерируемых случайным образом, были известны нормальные решения. Приводятся программы генераторов задач, написанные для системы MATLAB. В §3 2 приводится описание программы EGM1 - итерационного метода из первой главы, реализованного в системе MATLAB, в §3.3 - результаты численных экспериментов с программой EGM1. Численные эксперименты на компьютере PENTIUM-IV с 1Гб оперативной памятью со случайно сгенерированными задачами ЛП показали высокую эффективность метода при решении задач
ЛП с большим числом неотрицательных переменных (решались задачи до 50 миллионов переменных) и средним числом ограничений-равенств (до 4 тысяч). Время решения таких задач составляло от нескольких десятков до нескольких тысяч секунд. Высокая эффективность этих расчетов объясняется тем, что основная вычислительная трудность предлагаемого метода приходится на решение вспомогательной задачи безусловной максимизации, которая решается обобщенным методом Ньютона. Ее размерность определяется количеством ограничений типа равенств, число которых существенно меньше, чем число переменных в исходной задаче ЛП.
Результаты решений случайным образом сгенерированных 16 задач ЛП по программе EGM1 приведены в табл. 1. В ней указаны размерности т, п и р - плотность ненулевых элементов матрицы А, Т - время решения задачи ЛП в секундах, I - количество шагов, сделанных методом Ньютона при решении задачи (12) (при к — О). Везде полагалось, что /3=1. Вычислялись чебышевские нормы векторов невязок'
Ai = ||Ab-6|U Д2 = ||(Лти - с)+||оо, Дз = \стх — Ьти|.
Оказалось, что во всех примерах выполнялось условие /3 > /?*. Таким образом, нормальное решение прямой задачи (Р) х, = х\ было получено за одну итерацию. Приведенные в табл. 1 результаты показывают высокую эффективность предложенного метода. Например, задача ЛП с пятьюдесятью миллионами переменных и с m = 1000 решалась за 73.2 мин. (см. тринадцатую строку таблицы).
В табл. 2 даны результаты расчетов тестовых задач по программе EGM1 и по другим зарубежным коммерческим и исследовательским пакетам. Все задачи решались на компьютере Celeron 2.02 GHz с оперативной памятью 1.0 Gb. Для сравнения использовались пакеты BPMPD v.2.3 (метод внутренней точки), MOSEK v.2 0 (метод внутренней точки) и CPLEX v.6.0.1 (метод внутренней точки и симплекс-метод).
Таблица 1. Результаты численных расчетов по программе EGM1 на компьютере P-IV,2.& Ghz., 1 Gb., х0 = 0n , р0 — lm, 5 = 10~4, toll =
ю-12, 0 = 1
№ m x n x p T, с шаг Ai д2 Дз
1 100 x 106 x 0.01 29.3 17 1.7 x Ю-11 2.0 x lO"13 9.7 x lO"11
2 300 x 106 x 0.01 42.0 13 1.0 x 10~10 7.0 x lO"13 2.6 x 10~10
3 600 x 106 x 0.01 68.4 12 3.1 x Ю"10 1.7 x 10"12 2.8 x lO"10
4 1000 x (5 • 105) x 0.01 52.3 14 6.3 x Ю-9 2.7 x 10"12 9.1 x lO"8
5 1000 x 106 x 0.01 95.8 10 9.4 x Ю-10 3.5 x lO"12 6.9 x Ю-10
6 3000 x 10" x 0.01 81.5 7 2.0 x 10-9 9.1 x 10-12 3.7 x Ю-9
7 4000 x 104 x 0.01 196.2 8 2.9 x lO'9 1.2 x 10"u 2.6 x 10"8
8 500 x (3 • 106) x 0.01 179.1 12 3.2 x Ю"10 1.4 x lO"12 1.9 x 10"n
9 1000 x (3 • 106) x 0.01 309.1 11 1.2 x 10~9 4.1 x lO"12 4.9 x lO"9
10 500 x • 106) x 0.01 300.8 12 3.8 x lO"10 1.6 x lO"12 8.4 x lO"11
11 1000 x (5 • 106) x 0.01 412.8 8 7.3 x lO"9 7.4 x lO"12 7.0 x lO"8
12 500 x 107 x 0.01 387.8 8 7.6 x 10"9 3.6 x 10"12 1.1 x 10~7
13 1000 x (5 • 107) x 0.01 4392.5 6 4.4 x lO"7 2.1 x 10"13 1.8 x 10~5
14 1000 x 104 x 1 117.2 7 1.3 x ПГ7 1.0 x Ю-10 2.9 x 10"7
15 1000 x 105 x 1 1496.5 5 5.2 x lO"7 1.9 x ИГ10 8.2 x lO"7
16 100 x 106 x 1 376.5 9 4.2 x 10~8 1.2 x lO"11 3.0 x lO"7
Таблица 2. Результаты расчетов по различным программам на компьютере Celeron Р - IV, 2.02 Ghz., 1 Gb
m х пх р Solver T, с I, шаг ai a2 Дз
500 х 104 х 1 EGM1 55.0 12 1.5 x 10~8 1.8 x 10-12 1.2 x Ю-7
BPMPD (Interior point) 37.4 23 2.3 x ÎO'10 1.8 x Ю-11 1.1 x 10-10
MOSEK (Interior point) 87.2 6 9.7 x 10~8 3.8 x 10"9 1.6 x 10~6
CPLEX (Interior point) 80.3 11 1.8 x 10"8 1.1 x 10"7 0.0
CPLEX (Simplex) 61.8 8308 8.6 x 10~4 1.9 x 10-10 7.2 x 10"3
3000 х 104 х 0.01 EGMl 155.4 11 6.1 x Ю'10 3.4 x Ю-13 3.6 x 10~8
BPMPD (Interior point) 223.5 14 4.6 x 10~9 2.9 x 10-10 3.9 x Ю-9
MOSEK (Interior point) 42.6 4 3.1 x 10~8 1.2 x HT8 3.7 x Ю-8
CPLEX (Interior point) 69.9 5 1.1 x 10~6 1.3 x 10~7 0.0
CPLEX (Simplex) 1764.9 6904 3.0 x 10~3 8.1 x 10"9 9.3 x 10-2
1000 X (5 10е) х 0 01 EGMl 1007.5 10 3.9 x 10"8 1.4 x 10-13 6.1 x 10~7
1000 х 105 х 1 EGMl 2660.8 8 2.1 x 10-7 1.4 x Ю-12 7.1 x 10-7
В третьей строке табл. 2 даны результаты расчетов задач ЛП с пятью миллионами неотрицательных переменных, тысячей ограничений, однопроцентной заполненностью матрицы А ненулевыми элементами. Время расчетов по программе ЕСМ1 составило 16 мин. В четвертой строке приведены результаты в случае, когда задача имела 1000 ограничений, матрица А была полностью заполнена и п = 105. Время расчетов было 44 мин Обе задачи были решены с высокой точностью (нормы невязок не превосходили 7.1 х Ю-7 ) Обе эти задачи не удалось решить другими пакетами.
Для одной из тестовых задач на рисунке выше показано время расчетов в зависимости от /? Из результатов расчетов этой задачи следовало, что 0.01 < Д, < 0.1 При всех /3 > 0.1 время меняется слабо от 68 1 с до 84.5 с и задача (1) решается за одну итерацию На рисунке показано время решения при разных /3 одной и той же задачи ЛП с т = 700, п = 105, р = 0.1 яо = 0„, ро = 1т.
В §3.4 и §3.5 приведена программа ЕСМ2 для системы МАЛАВ -реализация итерационного метода из главы 2 Даны результаты численных экспериментов со случайным образом сгенерированными двойственными задачами ЛП.
В §3.6 представлены результаты численных экспериментов с помощью программы нахождения нормального решения систем линейных уравнений с неотрицательными переменными Сопоставлялись результаты работы метода из §1 5 и метода, основанного на теоремах об альтернативах.
В приложении даны описание практической задачи определения оптимального состава машинно-тракторного парка и результаты счета с помощью программы EGM1.
Основное содержание диссертационной работы изложено в следующих публикациях:
1 Моллаверди Н., Тюленев A.B. О программной реализации нового метода решенья задан линейного программирования.// Тез. докл. конф "Математическое программирование и приложения", Екатеринбург: УрО РАН, 2003. С.185.
2 Моллаверди Н Решение систем линейных равенств и неравенств большой размерности.// Тез. докл. конф. "Алгоритмический анализ неустойчивых задач", Екатеринбург: УрО РАН, 2004. С.287.
3. Голиков А.И., Евтушенко Ю.Г., Моллаверди Н. Применение метода Ньютона к решению задач линейного программирования большой размерности // Ж. вычисл. матем. и матем. физ. 2004. Т. 44. №9. С. 1564-1573.
4 Evtushenko Yu.G., Golikov A.!., Ketabchi S., Mollaverdi N. Augmented Lagrangin method for linear programming // Dynamics of non-homogeneous systems. M.- Russian Academy of Sciences Institute for System Analysis. 2004. V 7. Pp. 101-106.
Моллаверди Насер
Методы решения задач линейной оптимизации большой размерности Подписано в печать 14.03.2005 Формат бумаги 60x84 1/16 Уч.-изд.л. 1. Усл.-печ. л. 1 Тираж 100 экз. Заказ 6 Отпечатано на ротапринтах в Вычислительном центре им. A.A. Дородницына РАН 119991, Москва, ул. Вавилова, 40
РНБ Русский фонд
2005-4 42001
^ ta
9 ^ а j? it
Р 2005
ВВЕДЕНИЕ
1. МЕТОД РЕШЕНИЯ ПРЯМОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С БОЛЬШИМ ЧИСЛОМ НЕОТРИЦАТЕЛЬНЫХ ПЕРЕМЕННЫХ
1.1. Нахождение проекции точки на множество решений прямой задачи линейного программирования
1.2. Итерационный метод нахождения решений прямой и двойственной задач (метод ПД).
1.3. Конечная сходимость итерационного метода
1.4. Обобщенный метод Ньютона.
1.5. Нахождение проекции точки на множество решений систем линейных уравнений
2. МЕТОД РЕШЕНИЯ ДВОЙСТВЕННОЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С БОЛЬШИМ ЧИСЛОМ ПЕРЕМЕННЫХ
2.1. Нахождение проекции точки на множество решений двойственной задачи линейного программирования.
2.2. Итерационный метод нахождения решений двойственной и прямой задач (метод ДП)
3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ
3.1. Генераторы тестовых задач.
3.2. Программная реализация метода ПД в системе MATLAB.
3.3. Результаты численных экспериментов с программой EGM1.
3.4. Программная реализация метода ДП в системе MATLAB.
3.5. Результаты численных экспериментов с программой EGM2.
3.6. Результаты численных экспериментов с помощью программ нахождения нормальных решений линейных систем
ВЫВОДЫ
Теории и методам решения задач линейного программирования (ЛП) и систем линейных неравенств посвящено огромное количество исследований. "Укажем лишь несколько опубликованных на русском языке монографий [2], [4], [5], [13], [18] - [22], [26], [29], [30], [33], [36], [42], [43]. Огромный интерес к задачам ЛП определяется прежде всего их экономической содержательностью, многочисленными практическими приложениями и применением в качестве вспомогательных процедур во многих численных методах нелинейной оптимизации. Несмотря на продолжающееся повышение производительности вычислительной техники, всегда актуальным остается возможность решения задач линейного программирования очень большой размерности.
Первоначально исследования в области численных методов ЛП концентрировались в основном на симплекс-методе. Далее разрабатывались разнообразные итерационные методы, а после опубликования статей [24], [14], [15], [16], [52] внимание многих исследователей переключилось на методы внутренних точек. При этом возникли новые формулировки задач ЛП и появились новые формы задания необходимых и достаточных условий оптимальности (см. например, [60], [17], [49]). Укажем на специальный выпуск журнала Optimization Methods & Software [61], целиком посвященный методу внутренней точки, а также обзор [50].
В работах советских математиков в 70-х годах активно разрабатывался подход к задачам ЛП, основанный на использовании метода внешних штрафных функций (квадратичная функция штрафа). Хорошо известны работы в этом направлении, которые проводились А.С. Антипиным, Ф.П. Васильевым, Е.Г. Голыптейном, И.И. Ереминым, Б.Т. Поляком, Б.С. Разумихиным, Н.В. Третьяковым и другими исследователями из МГУ, ИПУ, ЦЭМИ, ИММ УрО РАН, ВЦ РАН [3], [13], [51], [32]-[35], [42], [44]. Примерно в это же время в США близкие исследования проводились О.Мангасарьяном и его сотрудниками. В их работах [53]-[55] основное внимание уделялось нахождению нормальных решений в задачах ЛП, т.е. решений, обладающих минимальной евклидовой нормой. Широкое распространение этот подход в то время не получил. Только в последнее время появились свидетельства о его перспективности с вычислительной точки зрения [57], [58]. Связано это с использованием быстро сходящегося обобщенного метода Ньютона для минимизации выпуклой кусочно квадратичной непрерывно дифференцируемой штрафной функции. У нее не существует матрица Гессе. Однако для такой штрафной функции можно построить обобщенный метод Ньютона, введя обобщенную матрицу Гессе. В работах [57], [58], [51] доказана конечная глобальная сходимость обобщенного метода Ньютона для минимизации выпуклой кусочно квадратичной функции. Минимизация этой штрафной функции, примененной к двойственной задаче ЛП, дает возможность получить точное нормальное (с минимальной евклидовой нормой) решение прямой задачи, начиная с некоторого конечного значения коэффициента штрафа.
Заметим, что, как правило, большие задачи ЛП имеют не единственное решение. Указанные методы представляют ценность тем, что дают различные решения в случае неединственности. Так, симплекс-метод дает решение, которое принадлежит вершине многогранного множества. Методы внутренней точки сходятся к решению, в котором выполнено условие строгой дополняющей нежесткости. Метод квадратичной штрафной функции, будучи примененным к двойственной задаче, дает возможность получить нормальное решение прямой задачи при конечном значении коэффициента штрафа.
Весьма актуальным является обобщение метода квадратичной штрафной функции для получения проекщга произвольной точки на множество решений прямой или двойственной задач ЛП. Задача нахождения проекции заданной точки на множество решений часто может иметь важный содержательный смысл для приложений. Так, пусть известен некоторый оптимальный план, который из-за изменившихся условий уже не только не оптимальный, но может даже оказаться и недопустимым. Желательно найти такой новый оптимальный план, который был бы ближайшим к первоначальному плану.
Работа посвящена созданию методов нахождения проекции заданной точки на множество решений задачи ЛП с большим числом переменных, программной реализации, проведению вычислительных экспериментов (в том числе и на практической задаче).
В главе 1 предлагается метод решения прямой задачи ЛП с большим числом (до нескольких десятков миллионов) неотрицательных переменных и средним числом ограничений-равенств (несколько тысяч). В §1.1 рассматривается задача нахождения проекции заданной точки на множество решений прямой задачи. Вместо обычно применяемой кусочно квадратичной штрафной функции предлагается использовать вспомогательную функцию, сходную с модифицированной функцией Лагранжа (см., например [31], [1]), зависящую от некоторого параметра (5. Этот подход характеризуется следующим: начиная с некоторого фиксированного значения параметра Д* после однократной безусловной максимизации вспомогательной функции при всех Р > /3* по простой формуле вычисляется точная проекция заданной точки на множество решений прямой задачи ЛП (теорема 1.1). В этой теореме при определенных предположе-нях получена формула для порогового значения . Эта величина может быть отрицательна. В этом случае расстояние от заданной проектируемой точки до множества решений прямой задачи совпадает с расстоянием от этой точки до допустимого множества прямой задачи. Показана связь предложенной вспомогательной функции с методами регуляризации и квадратичным штрафом, примененным к двойственной задаче. Подставляя найденную проекцию во вспомогательную функцию и, максимизируя ее, находим некоторое точное решение двойственной задачи ЛП (теорема 1.2).
В §1.2 приводится итерационный метод нахождения решений прямой и двойственной задач Л П. Этот метод является прямым-двойственным методом (ПД-метод). В процессе итераций метод дает допустимые прямые точки и недопустимые двойственные. Формально в нем не требуется знания порогового значения параметра /?*. Но, если выбранное значение /3 меньше порогового значения, то метод решает задачу ЛП более, чем за две итерации. Метод за конечное число шагов находит некоторое решение прямой задачи, но не проекцию начальной точки на множество решений прямой задачи.
При некоторых дополнительных предположениях доказана сходимость метода и в §1.3. Доказана конечная сходимость.
В §1.4 приводятся сведения об обобщенном методе Ньютона ([57], [58], [51]), который рекомендуется применять для безусловной максимизации вспомогательной функции, если прямая задача ЛП имеет среднее число ограничений (до 4 тыс.). Обобщенный метод Ньютона для данной задачи глобально сходится за конечное число шагов.
В §1.5 предложенный метод переносится на задачу нахождения проекции заданной точки на множество решений систем линейных уравнений с неотрицательными переменными.
Во второй главе рассматривается аналогичный подход для решения двойственных задач ЛП с большим числом переменных (до нескольких десятков миллионов) и средним числом ограничений-неравенств (до 4 тыс.). Здесь модифицированная функция Лагранжа зависит от параметра а. В §2.1 приводится оценка для порогового значения параметра а начиная с которого, в результате однократной максимизации вспомогательной функции на положительном ортанте, находится точная проекция заданной точки на множество решений двойственной задачи. В §2.2 приводится итерационный метод решения двойственной и прямой задач (метод ДП). В процессе итераций получаются допустимые двойственные точки и недопустимые прямые. Как и в первой главе, этот метод может быть использован со значением параметра а, меньшим, чем пороговое значение. Однако расчеты при этом не дают проекцию начальной точки на множество решений двойственной задачи. В этом методе максимизация производится на положительном ортанте. Для снятия ограничений на знак переменных применялась квадратичная штрафная функция. Это позволило здесь так же применить обобщенный метод Ньютона.
Глава 3 посвящена программной реализации и вычислительным экспериментам. В §3.1 приведено описание генераторов задач линейного программирования Code 1, Code 2 и генератора систем линейных уравнений с неотрицательными переменными Code 3. Для систем, генерируемых случайным образом, известны нормальные решения. Приводятся программы генераторов задач, написанных для системы MATLAB.
В §3.2 содержится описание программы EGM1 - итерационного метода ПД из первой главы, реализованного в системе MATLAB. В §3.3 в таблицах 3.1 - 3.8 даны результаты численных экспериментов с программой EGM1.
Расчеты проведены, в основном, на компьютере PENTIUM-IV с 1Гб оперативной памяти со случайно сгенерированными задачами ЛП и показали высокую эффективность метода при решении задач с большим числом неотрицательных переменных (решались задачи до 50 миллионов переменных) и средним числом ограничений-равенств (до 4 тысяч). Время решения таких задач составляло от нескольких десятков секунд до нескольких часов. Такие впечатляющие результаты объясняются тем, что основная вычислительная трудность предлагаемого метода приходилась на решение вспомогательных задач безусловной максимизации. Их размерность определялась количеством ограничений типа равенств, число которых существенно меньше, чем число переменных в исходной задаче ЛП и поэтому они сравнительно просто решались обобщенным методом Ньютона.
Приведено сравнение программы EGM1 с некоторыми известными зарубежными исследовательскими и коммерческими пакетами. Результаты свидетельствуют о конкурентноспособности программы EGM1 на небольших задачах, сгенерированных программой Code 2 и явном преимуществе программы EGM1 в случае задач большой размерности, которые не удалось решить другими пакетами.
В §3.4 и §3.5 приведена программа EGM2, реализующая итерационный метод ДП, и даны результаты численных экспериментов со случайным образом сгенерированными задачами ЛП. В §3.6 представлены результаты численных экспериментов с программами нахождения нормального решения систем линейных уравнений с неотрицательными переменными. Сопоставлялись результаты работы метода из §1.5 и метода, основанного на теоремах об альтернативах [7]-[9].
На рисунках 3.1 - 3.6 даны зависимости времени счета, числа итераций и количества шагов, суммарной невязки от параметра /3, полученные по программе EGM1.
На рисунках 3.7 - 3.9 приведены аналогичные графики для метода ДП, полученные по программе EGM2.
В приложении дано описание практической задачи определения оптимального состава машинно-тракторного парка и результаты счета с помощью программы EGM1.
Выводы
1. Предложены новые методы нахождения проекции точки на множество решений прямой задачи и проекции на множество решений двойственной задачи ЛП.
2. Получены формулы для определения пороговых величин параметров, начиная с которых проекция заданной точки на множество решений задачи ЛП получается в результате однократной максимизации вспомогательной функции. Если положительный параметр меньше пороговой величины, то предлагаемые итерационные процессы сходятся за конечное число шагов к некоторым решениям прямой и двойственной задач ЛП.
3. Методы реализованы в системе МАТЛАБ. Приведены тексты основных программ, реализующих предложенные методы, и тексты генераторов тестовых задач. Для решения вспомогательных задач безусловной максимизации использовался обобщенный метод Ньютона.
4. Методы апробированы на многочисленных тестовых задачах большой размерности (до пятидесяти миллионов переменных) и с умеренным количеством ограничений (до четырех тысяч).
5. Сравнительный анализ предложенных методов решения задач ЛП с доступными коммерческими и исследовательскими пакетами показал, что для задач невысокой размерности предложенные методы дают примерно такие же результаты и превосходят эти пакеты иа задачах очень большой размерности.
6. В виде примера решено несколько вариантов практической задачи определения оптимального машинно-тракторного парка для модельного сельскохозяйственного предприятия.
1. Антипин А.С. Методы нелинейного программирования, основанные на прямой и двойственной модификации функции Лагранжа. М.: ВНИИСИ. 1979.
2. Булавский В.А., Звягина Р.А., Яковлева М.А. Численные методы линейного программирования. М.: Наука, 1977.
3. Вильчевский Н. О. О выборе коэффициента штрафа в задачах линейного программирования // Автомат, и телемехан. 1970. N 4. С. 121126.
4. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 2003.
5. Гейл Д. Теория линейных экономических моделей. М.: Изд-во иностр. лит., 1963.
6. Голиков А.И., Евтушенко Ю.Г. Отыскание нормальных решений в задачах линейного программирования // Ж. вычисл. матем. и матем. физ. 2000. Т. 40. № 12. С. 1766-1786.
7. Голиков А.И., Евтушенко Ю.Г. Новый метод решения систем линейных равенств и неравенств // Докл. РАН. 2001. Т. 381. №4. С. 1-4.
8. Голиков А.И., Евтушенко Ю.Г. Теоремы об альтернативах и их применение в численных методах // Ж. вычисл. матем. и матем. физ. 2003. Т. 43. № 3. С. 354-375.
9. Голиков А.И., Евтушенко Ю.Г. Применение теорем об альтернативах к нахождению нормальных решений линейных систем // Изв. вузов. Математика. 2001. №12 (475). С. 21-31.
10. Голиков А.И., Евтушенко Ю.Г., Кетабчи С. О семействах гиперплоскостей, разделяющих полиэдры // Ж. вычисл. матем. и матем. физ. 2005. Т. 45. № 2. С. 238-253.
11. Голиков А.И., Евтушенко Ю.Г, Моллаверди Н. Применение метода Ньютона к решению задач линейного программирования большой размерности // Ж. вычисл. матем. и матем. физ. 2004. Т. 44. № 9. С. 1564-1573.
12. Голынтейн Е.Г., Третьяков Н.В. Модифицированные функции Лагранжа, теория и методы оптимизации. М.: Наука, 1989.
13. Голынтейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании. М.: Сов.радио, 1966.
14. Евтушенко Ю. Г., Жадан В. Г. Численные методы решения некоторых задач исследования операций // Ж. вычисл. матем. и матем. физ. 1973. Т. 13. N. 3. С. 583-597.
15. Евтушенко Ю. Г. Два численных метода решения задач нелинейного программирования // Докл. АН СССР. 1974. Т. 215. N. 1. С. 38-40.
16. Евтушенко Ю. Г., Жадан В. Г. Релаксационный метод решения задач нелинейного программирования // Ж. вычисл. матем. и матем. физ. 1977. Т. 17. N. 4. С. 890-904.
17. Евтушенко Ю. Г., Жадан В. Г. Барьерно-проективные и баръерно-ньтоновские численные методы оптимизации (случай линейного программирования) . М.: ВЦ РАН, 1992.
18. Еремин И.И. Теория линейной оптимизации. Екатеринбург: УрО РАН, 1998.
19. Еремин И. И., Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976.
20. Еремин И.И., Мазуров В.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983.
21. Еремин И.И. Противоречивые модели оптимального планирования. М.: Наука, 1983.
22. Еремин И.И. Двойственность в линейной оптимизации. Екатеринбург: УрО РАН, 2001.
23. Еремин И.И. О квадратичных задачах и полноквадратичных задачах выпуклого программирования // Известия вузов. Матем. 1998. № 12. С. 22-28.
24. Дикин И. И. Итеративное решегьие задач линейного и квадратичного программирования // Докл. АН СССР. 1967. Т. 174. N. 4. С. 745-747.
25. Кутанов А. Т. Об уточнении решения задачи линейного программирования в методе штрафных функций // Автомат, и телемехан. 1970. N 4. С. 127-132.
26. Линейные неравенства и смео/сные вопросы. // Сб. работ под ред. Куна Г. и Таккера А. М.: ИЛ. 1959.
27. Моллаверди Н. Решение систем линейных равенств и неравенств большой размерности. Тезисы докладов конференции "Алгоритмический анализ неустойчивых задач", Екатеринбург, 2004, с.287
28. Моллаверди Н., Тюленев А.В. О программной реализации нового метода решения задач линейного программирования. Тезисы докладов конференции "Математическое программирование и приложения", Екатеринбург, 2003, с.185.
29. Муртаф Б. Современное линейное программирование. М.: Мир, 1984.
30. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
31. Поляк Б.Т., Третьяков Н.В. Об одном итерационном методе линейного программирования и его экономической интерпретации // Эконом, и матем. методы. 1972. Т. VIII. Вып. 5.
32. Пропой А. И., Ядыкин А. Б. Параметрическое квадратичное программирование и линейное программирование II j j Автомат, и телемехан. 1978. N 2. С. 102-112, N 4. С. 135-143.
33. Разумихин Б.С. Физические модели и методы теории равновесия в программировании и экономике. М.: Наука, 1975.
34. Разумихин Б. С. О двух методах условной оптимизации II. Метод годографа для задач линейного программирования// Модели и методы оптимизации. Тр. ВНИИСИ. N 3. М.: ВНИИСИ, 1980. С. 37-53.
35. Рапопорт JI. Б. Модифицированый метод годографа для задач линейного программирования // Модели и методы оптимизации. Тр. ВНИИСИ. N 3. М.: ВНИИСИ, 1980. С. 82-93.
36. Схрейвер А. Теория линейного и целочисленного программирования. М.: Мир, 1991.
37. Тихонов А.Н.Избранные труды. М.: МАКС Пресс, 2001.
38. Тихонов А. Н., Арсеиин В. Я. Методы решения некорректных задач. М.: Наука, 1979.
39. Удзава X. Итерационные методы вогнутого программирования // К. Дж. Эрроу, J1. Гурвиц, X. Удзава. Исследования по линейному и нелинейному программированию. М.: Изд-во иностр. лит., 1962. С. 228-245.
40. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. М.: Мир, 1972.
41. Чеботарев С. П. Об изменении коэффициента штрафа в задачах линейного программирования // Автомат, и телемехан. 1974. N 3. С. 102-107.
42. Черников С.Н. Линейные неравенства. М.: Наука, 1968.
43. Юдин Д.Б., Голыптейн Е.Г. Линейное программирование: теория, методы и приложения. М.: Наука, 1969.
44. Ядыкип А. Б. О параметризации в вырожденных задачах квадратичного программирования // Ж. вычисл. матем. и матем. физ. 1977. N 3. С. 634-648.
45. Evtushenko Yu. Computational of exact gradients in disributed dynamic systems // Optimiz. Meth. and Software. 1998. V. 9. № 1-3. Pp. 45-75.
46. Evtushenko Yu.G., Golikov A.I. New perspective on the theorems of alternative // High Performance Algorithms and Software for Nonlinear Optimization. Kluwer, 2003. Pp. 227-241.
47. Evtushenko Yu.G., Golikov A.I., Ketabchi S., Mollaverdi N. Augmented Lagrangin method for linear programming // Dynamics of non-homogeneous systems. M.: Russian Academy of Sciences Institute for System Analysis. 2004. V. 7. Pp. 101-106.
48. Evtushenko Yu. G., Moretti A., Zhadan V. G. Newton's steepest descent for linear programming // Dynamics of non-homogeneous systems. Proceedings of ISA RAS. V. 2. M.: Editorial URSS. 1999. P. 86-108.
49. Evtushenko Yu. G., Zhadan V. G. Space-transformation technique: the state of the art. // Nonlinear Optimization and Applications (Edited by G. DI Pillo, F. Giannessi). Kluwer Acad. Publis. 1996. P. 101-123.
50. Kanzow C., Qi H., Qi L. On the Minimum Norm Solution of Linear Programs // Journal of Optimization Theory and Applications. 2003. V. 116. Pp. 333-345.
51. Karmarcar N. A new polinomial-time algorithm for linear programming // Combinatorica. 1984. N 4. P. 373-395.
52. Mangasarian O. L., Meyer R. R. Nonlinear perturbation of linear programs// SIAM J. Control and Optimizat. 1979. V. 17. N 6. P. 745-752.
53. Mangasarian О. L. Normal solutions of linear programs // Math. Program. Study. 1984. V. 22. P. 206-216.
54. Mangasarian O. L. Least-norm linear programming solution as an unconstrained minimization problem // J. Math. Analysis and Applic. 1983. V. 92. P. 240-251.
55. Mangasarian O.L. Nonlinear programming. Philadelphia: SIAM, 1994.
56. Mangasarian O.L. A Finite Newton Method for Classification // Optimizat. Meth. and Software. 2002. V. 17. Pp. 913-930.
57. Mangasarian O.L. A Newton Method for Linear Programming // Journal of Optimization Theory and Applications. 2004 121. pp. 1-18.
58. Meszaros Cs.( The BPMPD interior point solver for convex quadratic programming problems. // Optimizat. Meth. and Software. 1999.11&12,
59. Roos C., Terlaky Т., Vial J.-Ph. Theory and algorithms for linear optimization. An interior point approach. Chichester: John Wiley & Sons,
60. Special issue on interior point methods // Optimizat. Methods &431.449.1997.
61. Software. 1999. V. 11. N 1-4. P. 1-690.
