автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Развитие алгоритмов внутренних точек и их приложение к системам неравенств

Введение.

Глава 1. Краткий обзор алгоритмов внутренних точек в линейном программировании

1.1. Теоретические основы линейной оптимизации.

1.2. Аффинно-масштабирующие алгоритмы.

1.3. Полиномиальные алгоритмы.

Глава 2. Алгоритмы оптимизации в конусе скошенного пути для решения пары взаимно-двойственных задач линейного программирования.

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

2.2. Описание и теоретическое исследование алгоритмов оптимизации в конусе скошенного пути.

2.3. Экспериментальное исследование алгоритмов.

Глава 3. Решение систем уравнений и неравенств алгоритмами внутренних точек.

3.1. Задача определения допустимых режимов электроэнергетических систем.

3.2. Аффинно-масштабирующие алгоритмы применительно к решению линеаризованной подзадачи.;.

3.3. Алгоритмы центрального и скошенного пути применительно к решению линеаризованной подзадачи.

Актуальность темы

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

Важно отметить российский приоритет в теории оптимизации в целом и в теории линейной оптимизации в частности. Зарождение линейного программирования связано с именем Л.В.Канторовича, а фундаментальные работы по линейным неравенствам были выполнены С.Н.Черниковым. Среди других лидеров теории оптимизации в России отметим Н.Н.Моисеева и Б.Т. Поляка (Москва), И.И.Еремина (Екатеринбург), В.А.Булавского и В.Т.Дементьева (Новосибирск), О.В.Васильева и В.П.Булатова (Иркутск). Крупный вклад в развитие методов оптимизации был внесен представителями украинской и белорусской школ Б.Н.Пшеничным, Н.З.Шором, Р.Габасовым, Ф.М.Кирилловой и другими. Среди зарубежных исследователей, заложивших фундамент современной теории оптимизации, следует выделить Дж.фон Неймана, Дж.Данцига, Г.Куна и А.Таккера.

Существует большое количество методов решения задач линейного программирования. Одним из активно развивающихся их направлений являются алгоритмы внутренних точек, первый из которых был опубликован в 1967 году И.И.Дикиным. До середины 80-х годов развитие алгоритмов внутренних точек осуществлялось исключительно в работах российских ученых, среди которых выделим Ю.Г. Евтушенко, В.И.Зоркальцева и В.Г.Жадана.

Повышенный интерес к данному направлению (результатом которого стали более 2000 опубликованных статей) в мировой науке возник вслед за созданием в 1984 году Н.Кармаркаром первого алгоритма внутренних точек, обладающего полиномиальными оценками максимального объема вычислений, необходимых для решения задачи. При этом основная масса работ была посвящена изложению новых модификаций алгоритмов и теоретических результатов по их обоснованию. В связи с огромным числом разработанных алгоритмов особенно важную роль начинают играть экспериментальные исследования. Они позволяют провести сопоставление алгоритмов и выбрать их наиболее перспективные, с учетом специфики конкретных типов задач, варианты.

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

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

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

Цели работы

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

2. Развитие теоретических исследований алгоритмов внутренних точек на задачах линейного программирования. Разработка и теоретическое обоснование новых алгоритмов, обладающих расширенными возможностями, в частности, не предъявляющих жестких требований к стартовому приближению.

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

Методы исследований

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

Основные результаты, составляющие научную новизну работы и выносимые на защиту

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

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

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

Практическая ценность

Разработанные алгоритмы могут быть использованы при реализации многих технических, экономических, экологических и других моделей, где возникает необходимость решения задач линейного программирования и систем линейных неравенств. Сюда относится и широкий класс существенно нелинейных моделей, при реализации которых применяется итеративная линеаризация. К настоящему времени предложенные в диссертации алгоритмы нашли непосредственное практическое применение на задаче определения допустимых режимов ЭЭС и внедрены в разработанный в ИСЭМ СО РАН программно-вычислительный комплекс "СДО" управления режимами ЭЭС.

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

Исследования выполнялись в рамках грантов РФФИ №97-01-00859 ("Разработка и теоретические исследования проективных алгоритмов оптимизации с приложением в задачах энергетики") и №00-01-00530 ("Развитие алгоритмов внутренних точек и их применение в задачах энергетики"). Основные результаты опубликованы в 23 научных работах, в том числе, в 14 статьях, а также докладывались и обсуждались на конференциях научной молодежи ИСЭМ СО РАН (1997-2000), XI и XII международных Байкальских школах-семинарах "Методы оптимизации и их приложения" (Иркутск, 1998, 2001), международных конференциях "Дискретный анализ и исследование операций" (Новосибирск, 1998, 2000), международной конференции "Математическое программирование и приложения" (Екатеринбург, 1999), международной конференции "Распределенные системы: оптимизация и приложения" (Екатеринбург, 2000), на семинарах ИСЭМ СО РАН и ИДСТУ СО РАН.

1. Краткий обзор алгоритмов внутренних точек в линейном программировании

Заключение

Сформулируем кратко основные результаты диссертационной работы:

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

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

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

4. Продемонстрировано, что, хотя наилучшие оценки достигаются при значении квадрата радиуса конуса скошенного пути 9=0.5, на практике наиболее эффективны алгоритмы со значением близким к 0.9. Также перспективным оказывается использование более высоких степеней р в процессе решения вспомогательной задачи определения величины Лк. Данные два вывода объединяет идея целесообразности расширения конуса скошенного пути, реализуемая двумя различными способами.

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

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

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

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

9. Предложенные алгоритмы апробируются на практической задаче определения допустимых режимов ЭЭС и внедряются в разрабатываемый в ИСЭМ СО РАН программно-вычислительный комплекс "СДО" управления режимами ЭЭС.

1. Анциферов Е.Г., Булатов В.П. К полиномиальным методам в выпуклом программировании // Оптимизация: модели, методы, решения. Новосибирск: Наука, 1992, 359с.

2. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 1998.

3. Войтов О.Н., Зоркальцев В.И., Филатов А.Ю. Исследование систем неравенств алгоритмами внутренних точек на задачах поиска допустимых режимов электроэнергетических систем. Иркутск: препринт СЭИ СО РАН, 1997, №10, 30с.

4. Голиков А.И., Евтушенко Ю.Г. Двойственный подход к решению систем линейных равенств и неравенств // Труды XII Байкальской международной конференции "Методы оптимизации и их приложения", Пленарные доклады, Иркутск, 2001, с.91-99.

5. Грумбков Ю.О. Повышение эффективности расчетов установившихся режимов электроэнергетических систем // Известия АН СССР. Энергетика и транспорт, 1984, №3, с.30-38.

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

7. Демидович Б.П., Марон И.А. Основы вычислительной математики. М.: Наука, 1966, 664с.

8. Дикин И.И. Итеративное решение задач линейного и квадратичного программирования // Доклады АН СССР, 1967, том 174, с.747-748.

9. Дикин И.И. О сходимости одного итерационного процесса. В кн.: Управляемые системы. Вып. 12. Новосибирск, ИМ СО АН СССР, 1974, с.54-60.

10. Дикин И.И., Зоркальцев В.И. Итеративное решение задач математического программирования (алгоритмы метода внутренних точек). Новосибирск: Наука, 1980, 144с.

11. П.Евтушенко Ю.Г., Жадан В.Г. Барьерно-проективные и барьерно-ньютоновские численные методы оптимизации (случай линейного программирования). М.: ВЦ РАН, 1992.

12. Евтушенко Ю.Г., Жадан В.Г. Релаксационный метод решения задач нелинейного программирования // Журнал вычислительной математики и математической физики, 1977, том 17, №4, с.890-904.

13. Евтушенко Ю.Г., Жадан В.Г. Численные методы решения некоторых задач исследования операций // Журнал вычислительной математики и математической физики, 1973, том 13, №3, с.583-597.

14. Еремин И.И. Теория линейной оптимизации. Екатеринбург: Екатеринбург, 1999, 312с.

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

16. Зоркальцев В.И. Итеративный алгоритм решения задачи линейного программирования. В кн. Алгоритмы и программы решения задач линейной алгебры и математического программирования. Иркутск, СЭИ СО АН СССР, 1978, с.77-89.

17. Зоркальцев В.И. Метод относительно внутренних точек. Сыктывкар. Коми филиал АН СССР, 1986,18с.

18. Зоркальцев В.И. Методы прогнозирования и анализа эффективности функционирования системы топливоснабжения. М.: Наука, 1988, 144с.

19. Зоркальцев В.И. Самосопряженный алгоритм решения задач линейного программирования // Известия высших учебных заведений. Математика, 1994, том 391, №12, с.42-49.

20. Зоркальцев В.И., Нечаева М.С. Оптимизация в конусе центрального пути. Иркутск: препринт СЭИ СО РАН, 1995, №2, 24с.

21. Зоркальцев В.И., Филатов А.Ю. Исследование алгоритмов оптимизации в конусе центрального пути. Иркутск: препринт СЭИ СО РАН, 1997, №7, 50с.

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

23. Каганович Б.М., Филиппов С.П. Равновесная термодинамика и математическое программирование. Новосибирск: Наука, 1995, 236с.

24. Канторович. JI.B. Математические методы организации и планирования производства. Д.: ЛГУ, 1939, 68с.

25. Крумм Л.А. Метод приведенного градиента при управлении энергетическими системами. Новосибирск: Наука, 1977, 368с.

26. Мурашко H.A., Охорзин Ю.А., Крумм Л.А. и др. Анализ и управление установившимися состояниями электроэнергетических систем. Новосибирск: Наука, 1987, 240с.

27. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.

28. Пшеничный Б.Н. Метод линеаризации. М.: Наука, 1983.

29. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973, 470с.

30. Стецюк П.И. Об ускорении сходимости методов эллипсоидов // Труды XII Байкальской международной конференции "Методы оптимизации и их приложения", том 1: "Математическое программирование", Иркутск, 2001, с.61-66.

31. Тришечкин A.M. Метод расчета допустимых режимов электроэнергетических систем // Известия АН СССР. Энергетика и транспорт, 1984, №2, с. 18-26.

32. Трошина Г.М. Об одном подходе к решению задачи минимизациидефицита мощности в электроэнергетических системах (ЭЭС). В сб.: "Методические вопросы исследования надежности больших систем энергетики", вып. 15, Иркутск, 1978, с.34-43.

33. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной оптимизации. М.: Мир, 1972, 240с.

34. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании // Доклады АН СССР, 1979, том 244, с.1093-1096.

35. Черников С.Н. Линейные неравенства. М.: Наука, 1968, 488с.

36. Шор Н.З. Методы отсечения с растяжением пространства для решения задач выпуклого программирования // Кибернетика, 1977, №1, с.94-95.

37. Adler I., Resende М., Veiga G., Karmarkar N. An implementation of Karmarkar's algorithm for linear programming problems // Mathematical programming, 1989, №44, pp.297-335.

38. Anstreicher K. A combined phase I phase II scaled potential algorithm for linear programming // Mathematical programming, 1991, №52, pp.429-439.

39. Anstreicher K. Potential reduction algorithms. In Terlaky Т., editor, Interior point methods of mathematical programming, pp. 125-158, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1996.

40. Barnes E. A variation on Karmarkar's algorithm for solving linear programming problems // Mathematical programming, 1986, №36, pp. 174-182.

41. Farkas J. Theorie der einfachen Ungleichungen // J. Reine und Angewandte Methematik, 1902, №124, pp. 1-27.

42. Freund R. A potential-function reduction algorithm for solving a linear program directly from an infeasible "warm start" // Mathematical programming, 1991, №52, pp.441-466.

43. Freund R. A potential reduction algorithm with user-specified phase I -phase II balance for solving a linear program from an infeasible warm start // SIAM journal on optimization, 1995, №5, pp.247-268.

44. Freund R., Jarre F., Mizuno S. Convergence of a class of inexact interior-point algorithms for linear programs // Mathematics of operation research, 1999, №1, pp.50-71.

45. Frisch K. The logarithmic potential method for solving linear programming problems. Memorandum, University Institute of Economics, Oslo, 1955.

46. Gill P., Murray W., Saunders M., Tomlin J., Wright M. On projected Newton barrier methods for linear programming and an equivalence to Karmarkar' s projective method // Mathematical programming, 1986, №36, pp. 183-209.

47. Goldman A., Tucker A. Theory of linear programming // Annals of mathematical studies, 1956, №38, pp.53-97.

48. Gonzaga C. Polynomial affine algorithms for linear programming // Mathematical programming, 1991, №49, pp.7-21.

49. Huard P. Resolution of mathematical programming with nonlinear constraints by the method of centers. In Abadie J., editor, Nonlinear programming, Amsterdam, 1967, pp.207-219.

50. Jansen B., Roos C., Terlaky T., Vial J.-Ph. Primal-dual target-following algorithms for linear programming // Annals of operations research, 1996, №62, pp. 197-231.

51. Karmarkar N. A new polynomial-time algorithm for linear programming // Combinatories 1984, №4, pp.373-395.

52. Kojima M., Megiddo N., Mizuno S. A primal-dual infeasible-interior-point algorithm for linear programming // Mathematical programming, 1993, №61, pp.263-280.

53. Kojima M., Mizuno S., Yoshise A. A polynomial-time algorithm for a class of linear complementarity problems // Mathematical programming, 1989, №44, pp.27-49.

54. Kojima M., Mizuno S., Yoshise A. A primal-dual interior point algorithm for linear programming. In Megiddo N., editor, Progress in mathematicalprogramming: interior point and related methods. Springer Verlag, New York, 1989, pp.29-47.

55. Lustig I. A practical approach to Karmarkar's algorithm. System optimization laboratory technical report, 1985, №5.

56. Mascarenhas W. The affine scaling algorithm fails for stepsize 0.999. SIAM journal on optimization, 1997, №1, pp.34-46.

57. Megiddo N. Pathways to the optimal set in linear programming. In Megiddo N., editor, Progress in mathematical programming: interior point and related methods, Springer Verlag, New York, 1989, pp.131-158.

58. Monma C. Recent breakthroughs in linear programming method. Morristown, NJ: Bell communications research, 1989.

59. Monma C., Morton A. Computational experience with a dual affine variant of Karmarkar's method for linear programming // Operations research letters, 1987, №6, pp.261-267.

60. Monteiro R., Adler I. Interior path-following primal-dual algorithms. Part 1: Linear programming // Mathematical programming, 1989, №44, pp.27-49.

61. Paradimitriou C., Steiglitz K. Combinatorial optimization. Algorithms and complexity. Prentice-Hall, Inc, Englewood Cliffs, New Jersey, 1982.

62. Portugal L., Resende G., Veiga G., Judice J. A truncated primal-infeasibleodual-feasible interior point network flow method. Technical report, AT&T Bell laboratories, Murray Hill, NJ, 1994.

63. Renegar J. A polynomial-time algorithm, based on Newton's method, for linear programming // Mathematical programming, 1988, №40, pp.59-93.

64. Resende M., Veiga G. An efficient implementation of a network interior point method. Manuscript, AT&T Bell laboratories, Murray Hill, NJ, 1992.

65. Roos K., Terlaky T., Vial J.-Ph. Theory and algorithms for linear optimization: an interior point approach. John Wiley & Sons, New Jersey, 1997, 480p.

66. Shanno D. Computing Karmarkar's projection quickly // Mathematical programming, 1988, №41, pp.61 -71.

67. Terlaky T. Tsuchiya T. A note on Mascarenhas' counterexample about global convergence of the affine scaling algorithm // Applied mathematics and optimization, 1999, №40, pp.287-314.

68. Todd M. Combined phase I and phase II in a potential reduction algorithm for linear programming // Mathematical programming, 1993, №59, pp.133-150.

69. Todd M. Potential reduction algorithms in mathematical programming. Technical report 1112, School of operation research and industrial engineering, Cornell University, Ithaca, 1995.

70. Tomlin J. Experimental result with an implementation of the projective method. ORSA computer science technical section newsletter, 1985.

71. Tsuchiya T. Global convergence of the affine scaling methods for degenerate linear programming problems // Mathematical programming, 1991, №52, pp.377-404.

72. Vanderbei R., Meketon M., Freedman B. A modification of Karmarkar's linear programming algorithm // Algorithmica, 1986, №1, pp.395-407.

73. Von Neumann J. On a maximization problem. Manuscript, Institute for Advanced Studies, Princeton University, Princeton, NJ 08544, USA, 1947.

74. Ye Y. An O(n3) potential reduction algorithm for linear programming // Mathematical programming, 1991, №50, pp.239-258.

75. Ye Y., Todd M., Mizuno S. An 0(V«) -iteration homogeneous and self-dual linear programming algorithm // Mathematics of operation research, 1994, №19, pp.53-67.