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

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

Одним из возможных способов расширения состава задач математического программирования, поддающихся решению численными методами, является параметризация их постановки [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) Предлагаемые алгоритмы апробированы на ряде моделей анализа эффективности управления инвестициями на рынке ценных бумаг.

ЗАКЛЮЧЕНИЕ

.