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

• Марковцев, Денис Анатольевич
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Марковцев, Денис Анатольевич

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ЗАДАЧИ ПАРАМЕТРИЧЕСКОГО ПРОГРАММИРОВАНИЯ: ПРОБЛЕМЫ И МЕТОДЫ ИХ РЕШЕНИЯ

1.1 Проблемы решения задач параметрического программирования

1.2 Возможные подходы к решению задач параметрического программирования

1.3 Тематический обзор методов решения задач параметрического программирования

1.3.1 Методы параметрического программирования

1.3.2 Методы недифференцируемой оптимизации

1.3.3 Методы двухуровневого программирования

ГЛАВА 2. МЕТОД СГЛАЖИВАЮЩИХ ШТРАФНЫХ ФУНКЦИЙ И ЕГО ОБОСНОВАНИЕ

2.1 Основная идея метода сглаживающих штрафных функций

2.2 Двухуровневая схема решения задач параметрического программирования

2.2.1 Связь метода штрафных функций с решением двойственной задачи

2.2.2 Необходимые и достаточные условия существования и единственности решения двухуровневой задачи

2.2.3 Условия сходимости итерационного процесса

2.2.4 Проблема точности

2.3 Построение дифференциальной аппроксимации решения задачи нижнего уровня

ГЛАВА 3. РЕАЛИЗАЦИЯ МЕТОДА СГЛАЖИВАЮЩИХ

ШТРАФНЫХ ФУНКЦИЙ

3.1 Проблемы решения задачи нижнего уровня

3.1.1 Построение множества реактивных ограничений

3.1.2 Схема решения задачи нижнего уровня

3.2 Проблемы решения задачи верхнего уровня

3.2.1 Применение классических методов безусловной гладкой минимизации

3.2.2 Модифицированный метод Ньютона

3.3 Использование квадратичной штрафной функции в схемах параметрической линеаризации

3.3.1 Алгоритм решения задачи нижнего уровня

3.3.2 Алгоритм решения задачи верхнего уровня

3.3.3 Условия сходимости итерационного процесса

3.3.4 Модели

ГЛАВА 4. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ МЕТОДА

СГЛАЖИВАЮЩИХ ШТРАФНЫХ ФУНКЦИЙ

4.1 Оптимизация формы множества Парето в задачах многокритериальной оптимизации

4.2 Экстремальные задачи для системы моделей

4.3 Параметрическая оптимизация для неполных математических моделей

4.4 Параметрическая линеаризация в дискретных задачах оптимального управления

4.5 Задача анализа эффективности управления инвестициями на

рынке ценных бумаг

4.5.1 Результаты численных расчетов

ЗАКЛЮЧЕНИЕ

ПРИЛОЖЕНИЕ: ЛИСТИНГ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕДУР

СПИСОК ИЛЛЮСТРАЦИЙ

СПИСОК ТАБЛИЦ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Введение диссертации (часть автореферата) на тему «Метод гладких штрафных функций в задачах параметрического программирования»

ВВЕДЕНИЕ

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

найти min /(ж, и) (А)

х,и

при условиях gs(x,u) > 0,s — [1 , га],

на два подмножества: собственно переменных х и параметров и, значения которых при необходимости могут быть зафиксированы. Такое разделение позволяет свести решение исходной задачи (А) к двухуровневой схеме. На первом уровне решается задача математического программирования

найти min f(x, и) (В)

X

при условиях gs(x, и) > 0, s = [1, т], и = fix,

а на втором

найти min fix* (и), и) (С)

и

при условиях gs(x*(u),u) > 0,s = [1,тп],

где х*(и) есть решение задачи (В) при фиксированном векторе параметров и.

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

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

Условимся в дальнейшем задачу (С) называть задачей верхнего уровня, а задачу (В) будем называть задачей нижнего уровня. Пару задач верхнего и нижнего уровня будем называть двухуровневой системой задач или задачей параметрического программирования. В рассматриваемых задачах х € Еп - вектор переменных и и Е Е1 - вектор параметров являются элементами конечномерных евклидовых пространств, координаты которых

II*

а б ••• &

т

и || и ||

Щ Ъ>2 ■•• Щ

т

Предполагается,

имеют непрерывные частные произ-

что функции /(ж, и),д8(х, и), 5 = [1, т водные до второго порядка включительно. Введем также ряд обозначений:

- допустимая область исходной задачи (А)

Я = {(ж, и) е Еп х Е1\ д8(х, и) >0,3 = [1, т]};

- допустимая область задачи нижнего уровня (В)

Ях(и) = {х е Еп\(х,и) е Щ;

- допустимая область задачи верхнего уровня (С)

яи = {и е Е11 (х,и) £ Я}.

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

- невозможностью (за исключением некоторых простых случаев) получения аналитического представления зависимости х*(и)]

- существованием зависимости х*(и) не для всех и Е Е1, поскольку задача нижнего уровня может оказаться несовместной;

- возможной неоднозначностью решения задачи (В), то есть нефункциональностью зависимости х*(и);

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

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

- методы, предполагающие возможность получения явного вида зависимости х*(и) [4];

- двухуровневые схемы (типа bilevel programming), нацеленные на решение более общей задачи с различными функционалами на верхнем и нижнем уровне [36];

- методы, использующие алгоритмы недифференцируемой (негладкой) оптимизации [5, 21];

- схемы, основанные на построении сглаженных аппроксимаций зависимости х*(и), лишенных отмеченных выше недостатков [27].

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

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

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

В соответствии со сформулированной целью исследования в диссертационной работе рассматриваются следующие задачи.

1) Анализ теоретических и практических аспектов, как обосновывающих целесообразность использования схем параметрического программирования, так и ограничивающих возможности их применения.

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

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

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

5) Практическая реализация предлагаемых подходов • и исследование ее эффективности при решении конкретных задач математического программирования.

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

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

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

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

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

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

Апробация. Основные положения диссертационной работы докладывались, обсуждались и получили одобрение специалистов на научных семинарах кафедр высшей математики и математических основ управления Московского физико-технического института (государственного университета) (2007-2012), научных семинарах в Вычислительном центре им. A.A. Дородницына РАН (2012) и в Институте проблем управления им. В.А. Трапезникова РАН (2012).

Публикации. По теме диссертации опубликовано 8 печатных работ, из них 5 [13, 15, 16, 18, 19] - из списка, рекомендованного ВАК РФ.

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Марковцев, Денис Анатольевич

Основные результаты диссертационной работы заключаются в следующем:

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

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

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

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

5) Предлагаемые алгоритмы апробированы на ряде моделей анализа эффективности управления инвестициями на рынке ценных бумаг.

ЗАКЛЮЧЕНИЕ

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Алексеев В. М., Тихомиров В. М., Фомин С. В. Оптимальное управление. - М.: Наука, 1979.- 429 с.

2. Афанасьев А. П., Дику cap В. В., Милютин А. А., Чуканов С. А. Необходимое условие в оптимальном управлении. — М.: Наука, 1990. — 320 с.

3. Ашманов С. А. Линейное программирование.— М.: Наука, 1981. — 340 с.

4. Гольштейн Е. Г., Юдин Д. Б. Новые направления в линейном программировании. — М.: Советское радио, 1966.— 524 с.

5. Демьянов В. Ф., Васильев Л. В. Недифференцируемая оптимизация. — М.: Наука, 1981.- 384 с.

6. Дику cap В. В., Умное Е. А. Анализ эффективности метода параметрической линеаризации для решения задач оптимального управления со смешанными ограничениями // Динамика неоднородных систем. — М.: ИСА РАН, 2005,- С. 125-136.

7. Евтушенко Ю. Г. Методы решения экстремальных задач и их применение в системах оптимизации. — М.: Наука, 1982. — 432 с.

8. Еремин И. И. Теория двойственности в линейной оптимизации. — Южно-Уральский государственный университет, 2005. — 194 с.

9. Иванилов Ю. П., Лотов А. В. Математические модели в экономике.— М.: Наука, 1979.- 304 с.

10. Карабегов В. И. Об одной параметрической задаче линейного программирования // Журнал вычислительной математики и математической физики. - 1963. - Т. 3. - С. 547-558.

11. Карманов В. Г. Математическое программирование: Учеб. пособие.— М.: ФИЗМАТЛИТ, 2004.- 264 с.

12. Кудрявцев Л. Д. Курс математического анализа. Том 2. — М.: ДРОФА, 2004. - 720 с.

13. Марковцев Д. А. Об использовании дискретных периодических моделей в задачах с неполной информацией // Труды Института системного анализа Российской академии наук. Динамика неоднородных систем. — М.: КомКнига, 2006. - Т. 10(2).- С. 51-56.

14. Марковцев Д. А. Об обосновании метода параметризации в задачах математического программирования // Современные проблемы фундаментальной и прикладной математики. — М.: МФТИ, 2012. — С. 8088.

15. Марковцев Д. А. Условия сходимости итерационного процесса решения задач параметрического программирования методом гладких штрафных функций // Труды Московского физико-технического института. - М.: МФТИ, 2012. - Т. 4, № 1. - С. 50-54.

16. Марковцев Д. А,, Умное А. Е., Умное Е. А. Параметрическая оптимизация для систем математических моделей // Труды Института системного анализа Российской академии наук. Динамика неоднородных систем. - М.: Издательство ЛКИ, 2007. - Т. 31(1). - С. 42-50.

17. Марковцев Д. А., Умное А. Е., Умное Е. А. Об одной квазиклассической схеме решения задач математического программирования // Современные проблемы фундаментальной и прикладной математики. — М.: МФТИ, 2008,- С. 99-112.

18. Марковцев Д. А., Умное А. Е., Умное Е. А. Параметрический анализ нелинейной модели управления инвестициями на рынке ценных бумаг // Труды Института системного анализа Российской академии наук. Динамика неоднородных систем. — М.: Книжный дом ЛИБРО-КОМ, 2009. - Т. 42(2). - С. 195-202.

19. Марковцев Д. А., Умное Е. А. Использование метода штрафных функций для решения задач параметрического программирования // Труды Института системного анализа Российской академии наук. Динамика линейных и нелинейных систем, — М.: КомКнига, 2006.— Т. 25(1). — С. 181-187.

20. Моисеев П. П. Численные методы в теории оптимальных систем. — М.: Наука, 1971.-424 с.

21. Нурминский Е. А. Численные методы решения детерминированных и стохастических минимаксных задач.— Киев: Наукова думка, 1979.— 161 с.

22. Орловский С. А. Проблемы принятия решений при нечеткой исходной информации. — М.: Наука, 1981. — 208 с.

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

24. Пропой А. И. Элементы теории оптимальных дискретных процессов. — М.: Наука, 1973.-256 с.

25. Соколов А. В., Токарев В. В. Методы оптимальных решений. Том 1,— М.: ФИЗМАТЛИТ, 2011.- 564 с.

26. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации: Учеб. пособие, - М.: ФИЗМАТЛИТ, 2005.- 368 с.

27. Умное А. Е. Метод штрафных функций в задачах большой размерности // Журнал вычислительной математики и математической физики. - 1975. - Т. 15. - С. 1399-1411.

28. Умное А. Е., Марковцев Д. А., Умное Е. А. Задача параметрического программирования: Учебно-методическое пособие. — М.: МФТИ, 2008. - 44 с.

29. Федоров В. В. Численные методы максимина. — М.: Наука, 1979. — 280 с.

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

31. Bard, J., Falk J. An explicit solution to the multi-level programming problem // Computers and Operations Research. — 1982. — V. 9. — P. 77-100.

32. Bard J. F., Moore J. T. A branch and bound algorithm for the bilevel programming problem // Journal of Scientific and Statistical Computing. — 1990.-V. 11. — P. 281-292.

33. Bialas W., Karwan M. Two-level linear programming // Management Science. - 1984. - V. 30. - P. 1004-1020.

34. Censor Y. Pareto optimality in multiobjective problems // Applied Mathematics and Optimization. — N.Y.: Springer, 1977, — V. 4,— P. 41-59.

35. Colson В., Marcotte P., Savard G. An overview of bilevel optimization // Annals of Operations Research.— US: Springer, 2007.— V. 153(1). — P. 235-256.

36. Dempe S. Foundations of bilevel programming. — Dordrecht: Kluwer Academic Publishers, 2002. - 320 p.

37. Gass S., Saaty T. The computational algorithm for the parametric objective function // Naval Research Logistics Quarterly. — 1955. — V. 2. — P. 39-45.

38. Gass S., Saaty T. Parametric objective function, part ii, generalization // Journal of the Operation Research Sosiety of America. — 1955.— V. 3.— P. 395-401.

39. Jaumard ВSavard G., Xiong J. A new algorithm for the convex bilevel programming problem // Technical report, Ecole Polytechnique de Montreal. - 2000.

40. Kolstad C. D., Lasdon L. S. Derivative estimation and computational experience with large bilevel mathematical programs // Journal of Optimization Theory and Applications. - 1990. - V. 65. - P. 485-499.

41. Sakawa M., Nishizaki I. Cooperative and Noncooperative Multi-Level Programming. — N.Y.:Springer, 2009.— 260 p.

42. Savard G., Gauvin J. The steepest descent direction for the nonlinear bilevel programming problem // Operations Research Letters. — 1994.— V. 15. - P. 265-272.

43. Umnov A. E. A nondifferentiable optimization technique for use in multi-objective regional planning // Studies of Regional Science and Urban Economics. — Amsterdam-New York-Oxford, 1082: North-Holland PC, 1982. — V. 8.- P. 205-211.

44. White D., Anandalingam G. A penalty function approach for solving bilevel linear programs // Journal of Global Optimization. — 1993. — V. 3. — P. 397-419.