Методы решения задач линейной оптимизации большой размерности

Теории и методам решения задач линейного программирования (ЛП) и систем линейных неравенств посвящено огромное количество исследований. «Укажем лишь несколько опубликованных на русском языке монографий [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. В виде примера решено несколько вариантов практической задачи определения оптимального машинно-тракторного парка для модельного сельскохозяйственного предприятия.