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

• Моллаверди Насер
• кандидат физико-математических наук
• 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. В виде примера решено несколько вариантов практической задачи определения оптимального машинно-тракторного парка для модельного сельскохозяйственного предприятия.

Список литературы диссертационного исследования кандидат физико-математических наук Моллаверди Насер, 2005 год

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.