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

005020416

На правах рукописи

Марковцев Денис Анатольевич

МЕТОД ГЛАДКИХ ШТРАФНЫХ ФУНКЦИЙ В ЗАДАЧАХ ПАРАМЕТРИЧЕСКОГО ПРОГРАММИРОВАНИЯ

01.01.09 - дискретная математика и математическая кибернетика

2 з ма р тг

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2012

005020416

Работа выполнена на кафедре высшей математики Московского физико-тсхнического института (государственного университета)

Научный руководитель:

доктор технических наук, профессор Умнов Александр Евгеньевич

Официальные оппоненты: Дикусар Василий Васильевич,

д.ф.-м.н., профессор, Вычислительный центр им. A.A. Дородницына РАН, ведущий научный сотрудник,

Бирюков Александр Гаврилович, к.ф.-м.н., доцент,

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

Ведущая организация:

Защита состоится

Институт проблем управления им. В.А.Трапезникова РАН

2012 г. в часов на заседании

диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета).

Автореферат разослан

- 2012 г.

Ученый секретарь диссертационного совета

Федько Ольга Сергеевна

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации. По теме диссертации опубликовано 8 печатных работ, из них 5 [1, 2, 3, 6, 8] - из списка, рекомендованного ВАК РФ.

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

Содержание работы

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

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

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

(2012).

найти min/(x, и)

(1)

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

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

х

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

а на втором

найти шт/(х'(и),и) (3)

и

при условиях де(х*(и),и) > 0, й = [1,т],

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

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

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

II Нг I 11т

£1 £2 ••• ?п и || гл || = I 1/1 и2 •■■ Ц . Предполагается, что функции /(ж,и),де{х,и),8 = [1,т имеют непрерывные частные производные до второго порядка включительно.

В первой главе «Задачи параметрического программирования: проблемы и методы их решения» описаны факторы, осложняющие решение двухуровневой системы задач (2)-(3) и проведен тематический обзор возможных методов преодоления отмеченных затруднений.

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

Действительно, зависимость х*{и) обладает рядом «неудобных» для вычислений свойств:

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

- существование не для всех значений параметра и;

- неоднозначность зависимости х*[и) для тех и, при которых задача (2) не имеет локально изолированных решений;

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

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

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

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

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

- методы недифференцируемой оптимизации, использующие субднффс-ренциальное исчисление;

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

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

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

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

Идея метода сглаживания заключается в замене зависимости х*(и) достаточно гладкой и определенной для всех и € Г2 С Е1 и любых положительных

г функцией х+{г, и), такой что lim х+(г, и) = х*(и). При этом в качестве ап-

1—>+о

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

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

х+(г, и) = argmine(r, х, и) (4)

X

где вспомогательная функция метода гладких штрафных функций выбирается следующего вида:

m

e{r,x,u) = f(x, и) + ^2P(r,gs(x,u)). (5)

3=1

Если помимо стандартного свойства

limP(.,a) = (+00' а<° (6)

>'->+о { 0, а > 0,

достаточно гладкая штрафная функция Р(г, а) удовлетворяет также и неравенствам

дР д2Р

" ГС

то х+(г, и) - точка минимума вспомогательной функции е, находимая из условия стационарности

grade(r, х+, и) = о, (8)

или

grad f{x, и) + jr dP^9sM) , gT&dgs{XjU) = 0< (9)

x S=1 !

удовлетворяет условиям сглаживания зависимости ж* (и).

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

1. Решение уравнений (8), являющихся условиями стационарности функции (5), х+(г, и) существует и локально единственно для любых и £ О. С. Е1 и г > 0, и потому зависимость х+{г,и) является функциональной.

2. Для зависимости х+(г,и) верно равенство lim х+(г,и) = х*{и).

г->+О

3. Функция х+(г, и) является непрерывно дифференцируемой по всем своим аргументам.

Как известно, основное свойство метода штрафных функций состоит в том, что

lirn^r, х+(г, и), и) = f(x*(u), и), (10)

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

Е(г, и) = е(г, х+(г, и), и). (11)

Введем обозначение

ü(r) = arg min E(r, и). (12)

Пусть пара векторов х* и и* есть решение задачи (1), тогда справедливы равенства:

lim ü(r) = и*. lim x+(r, и) = ж*(м) и (13)

lim E(r,ü(r)) = lim e(r,x+(r,ü(r)),wir)) = f(x*,u*),

r-»+0 Г-++0

следующие из теорем 2, 3 и 4.

Теорема 2. Точка {х,й} является стационарной точкой функционала е{г, х, и) тогда и только тогда, когда й - стационарная точка функционала Е(г,и).

Теорема 3. Точка {х, й} является локальным изолированным минимумом функционала е(г, х, и) тогда и только тогда, когда точки х и и являются локальными изолированными минимумами функционалов e(r, х, й) и Е(г, и) соответственно.

Теорема 4. Точка {а;*, и*} £ Еп@Е1 является локальным изолированным решением задачи (1) тогда и только тогда, когда х* и и* - соответственно локальные изолированные решения задач (2) для и* и (3) соответственно.

С другой стороны, из теорем 1 и 6 следует, что Vs = [1, m]

lim dP(r,gs{x+{r,ü{r)),ü(r))) = r_>+° dgs s'

hm -—--gs(x (r,u(r)),u(r)) = 0.

r->+o ögs

Что, в сочетании с условиями (9), позволяет убедиться в выполнении необходимых условий оптимальности решения задачи (3):

Vs = [l,m] ЗА* > 0 такие, что (15)

K9s{x*, и*) = 0, и

m

grad/(z*,u*) + • grades (а;*, и*) = о.

1

Следует отмстить, числа Л* существуют всегда и совпадают со стандартными множителями Лагранжа, когда последние имеют конечное единственное значение.

Теорема 1. (Сходимость к двойственному решению) Пусть задача математического программирования

найти вектор переменных х* £ Еп, (16)

доставляющий минимум функционалу /(х) при условиях gs{x) > 0, s = [1, т],

решается методом штрафных функций. В качестве функции штрафа используется Р(г,а), удовлетворяющая условиям (6) и (7), г - коэффициент штрафа. Функции }{х), — gs(x) Vs = [1, m] выпуклы, множество оптимальных точек задачи (16) компактно. Если к тому же {rk} - строго убывающая и стремящаяся к нулю последовательность положительных чисел, то в процессе решения получаются точки

ИЫ,А(Г*)]. (17)

где

=--—-, s = [1,т], (18)

допустимые для двойственной задачи

найти maxL{x,\) (19)

при условиях (20)

VxL(x, Л) = 0, (21)

As>0, s = [1, mj, (22)

и также выполняются

lim L{x{rk),\{rk)) = min/(ж) = f (23)

k-юо К

и

lim \,(rk)gs(x(rk)) =0, a = [1, m], (24)

где

R = {x\gs{x) > 0, s = [l,m]} (25)

и

m

L{x, А) = f(x) — ^ Xsgs(x) (26)

- функция Лагранжа.

Теорема 6. Пусть и* есть решение задачи верхнего уровня, х* - решение задачи нижнего уровня для и = и*, функции /(х), —д3(х), в = [1,т] -локально выпуклы. Тогда существуют числа Л* > 0, в = [1,т] такие, что

т

gvadf(x*,u*) + V Л^ • егас138(а;*,и*) = о, (27)

*=1

\*ед$(х,,и,)=0. (28)

Условия существования решения задачи верхнего уровня дает следующая теорема.

Теорема 5. Пусть допустимое множество Я = {(я, и) £ Епх.Е1\ д3(х, и) > О, э = [1, т]} исходной задачи (1) - компакт, тогда решение задачи верхнего уровня (3) существует.

Так как аналитическое представление вектор-функции х+(г,и) получить невозможно, то для практического решения задачи верхнего уровня естественно использовать стандартную итеративную процедуру построения последовательных приближений к искомому решению и* в пространстве Е\ к-й шаг которой состоит из следующего набора операторов:

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

2. затем оцениваются как величина <т> , так и направление шага

3. выполняется переход к точке по формуле

Щ+1 = Щ + (29)

4. если в 1 условие окончания итерационного процесса не выполнено, то ик присваивается значение и^+1 и делается переход к пункту 1.

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

Главным преимуществом описанной схемы является возможность использования классических численных методов, не требующих явного аналитического представления для Е(г,и).

Условия сходимости определены теоремой 7 и заключаются в дифференцируемое™ и ограниченности снизу функционала Е(г,и), градиент которого кроме того должен удовлетворять условию Липшица.

Теорема 7. Пусть функции f(x,u),gs(x,u),s — [1, m] и Р(г,а) дважды непрерывно дифференцируемы на компакте M С Е1. Тогда градиент функционала (11) удовлетворяет условию Липшица на множестве М.

В свою очередь, поиск wк и гарантирующих сходимость процедуры (29), может потребовать нахождения локальных численных характеристик функционала Е(г, и), таких как: его значение, значения компонент градиента н матрицы Гесса, то есть, частных производных первого и второго порядка для некоторого фиксированного и. Эти характеристики могут быть найдены по формулам

= = M (30)

и

Необходимые для использования (31) значения

Vt = [l,n], Vj = [U] (32)

можно найти, решив систему линейных уравнений:

^ dÇidÇj dvt dijdvt

которая получается при дифференцировании (8) по всем компонентам и G Е1.

На практике использование предельных соотношений (13) ограничено ухудшением обусловленности уравнения (9) при уменьшении абсолютной величины г - ^врожденном» недостатке метода гладких штрафных функций. Уменьшение вначале вызывает рост затрат вычислительных ресурсов на реализацию процесса (29), а затем и вовсе приводит к нарушению его сходимости. В случае, когда процедура (29) далека от завершения, различие между х+{г,и) и х*{и) не играет существенной роли, н вычисления можно выполнять при достаточно большом г, отложив его уменьшение до завершающей стадии этой процедуры.

Если требуемая точность решения уравнения (8) при этом все же не будет достигнута, то погрешность можно понизить при помощи тейлоровской аппроксимации:

дх+

х+{г + Дг,и) = х+(т,и) + + о(Аг), (34)

из которой следует оценка при А г —» —г сверху:

дх+

х*(и) = х+(г, и) —-—г + о(г). (35)

Компоненты вектор-функции дх могут быть найдены по теореме о неявной функции из системы линейных уравнений:

¿а^-тр;-*™ (36)

получаемой при дифференцировании уравнения (8) по параметру г.

В третьей главе «Реализация метода сглаживающих штрафных функций» исследуются проблемы решения задач вида (1), допускающих параметрическую линеаризацию. То есть таких, что задача нижнего уровня (2) оказывается при фиксации параметров задачей линейного программирования с

п

= (37)

¿=1

п

д3(х, и) = а3г(и)& - Ьц(и). ¿=1

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

В качестве штрафной функции выберем

Р(г,а)={\> ^ (38)

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

gгad£'(r, и) и \iess Е(г, и),

и и

значения компонент которых вычислены в точке х+(г, и).

В рассматриваемом случае вспомогательный функционал задачи (2) выпуклый, что позволяет получить связь процедуры сглаживания с двойственной задачей. Обозначим

ЛПг,и) = УР{г>9^2Г'и)'и)), « = [1.Ч (39)

тогда условие стационарности примет вид, совпадающий по форме с условием стационарности функции Лаграижа для задачи нижнего уровня

гп

grad/{х+(г,и),и) - ^Л+(г,ы) • gгadffs(z+(r, и), и) = о, (40)

X . X

в=1

или, с учетом линейности задачи (2),

т

сАи) - Аз{г> = о, г = [1, п]. (41)

«=1

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

ДтЛ+(г,и) = Л;(и)>0, в = [1,т]. (42)

Следовательно, будет справедливо равенство

т

grad¡{х*{и),и) - У]Л*(м) ■ grad <?8(а;*(и), и) = о, (43)

I . X

й—1

и числа Л*(м),й = [1,ттг] совпадают со значениями множителей Лаграижа задачи нижнего уровня в случае, когда последние существуют и единственны. В общем же случае, числа Л*(и),я = [1 , т] являются одним из решений системы уравнений

grad/(x*(u),гí) - ^ А*(и) • gradgs(a;*(гí),гí) = о, (44)

Х т/ ч Х

seJ( и)

где J{u) - множество индексов активных ограничений задачи нижнего уровня, то есть ограничений, для которых д3(х*(и),и) = 0. Система уравнений (44) не всегда однозначно разрешима относительно неотрицательных А*(и). Это может иметь место, например, в случае, когда число активных ограничений больше, чем п. Равенство (43) позволяет из множества активных ограничений выделить особое подмножество ./+(ы) С J(u), такое что

^(и) = {в=[1,тЦА;(и)>0}. (45)

Из свойств квадратичной штрафной функции Р(г, а) при г —> +0 следует д3(х+(г, и), и) < 0, (46)

д3(х+(г, и), и) > 0, в £ У+(ы).

Таким образом для ограничений с индексами в 6 метод штрафных

функций генерирует точки х+(г,и) вне допустимой области, в то время как для ограничений с индексами 5 ^ ^(и) получаются точки внутри допустимой области. Поэтому ограничения, индексы которых принадлежат множеству «7+ (и), логично назвать ре-активными. Если ограничение не является реактивным, то значение и дифференциальные характеристики функционала Е(г,и) от него не зависят, и эти ограничения можно исключить из рассмотрения в точке и.

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

Рассмотрим теперь алгоритм решения двухуровневой задачи (2)-(3) при условиях (37).

Алгоритм решения задачи нижнего уровня. Входными данными для алгоритма является точка щ 6 Е1. На начальном этапе решается исходная линейная задача нижнего уровня:

найти х*(щ) = а^ттДа^иП (47)

X

при условиях дя(х, щ) > 0, я = [1 , т].

Если задача совместна, то сформируем множество У(и^), включающее индексы ограничений, активных в точке х*(щ)- Если же задача несовместна, то включим во множество J{u]г) индексы всех ограничений задачи (47).

Теперь сформируем вспомогательную функцию:

е{г,х,щ)= ¡{х,ик) + ^ ^ ®*(-9в{х,У-к))д2з{х,ик) (48)

«еЛ«/.-)

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

Если размер множества 3{ик) не превышает п, и градиенты ограничений из J{uk) - линейно независимы, то в силу теоремы 1 можно выделить множество 3+{ик), решив двойственную к (47) задачу. В этом случае х+(г,ик) является решением системы линейных уравнений:

д/(х,ик) ,1 ^ ( ,дд(х,ик) .

~-^ 9з{х,ик)—--=0, г = [1,п]. (49)

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

Решением задачи нижнего уровня для заданного ик является пара: х+(г, ик),

Алгоритм решения задачи верхнего уровня. Перейдем к решению задачи верхнего уровня. Сформируем вспомогательную функцию:

Е(г,и) = /(х+(и),и) + ~ £ д23(х+(и),и). (50)

(ик)

В зависимости от выбранного метода безусловной минимизации может потребоваться вычисление производных функции Е(г, и). Производные находятся по формулам (30) - (33). Вычислив производные функции Е(г,и) в точке щ находим направление спуска ак и величину шага шк. Новая точка в пространство параметров определяется по формуле:

Щ+1 =Щ + сгкшк. 17

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

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

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

- Для задачи оптимизации формы множества Парето в многокритериальных моделях, основанных на схеме минимизации рассогласования критериев (методов класса reference point). Следует отметить, что в том случае задача (2)-(3) является трехуровневой, поскольку постановка задачи (2) содержит в своем описании оптимальные значения целевых функций, решаемых независимо друг от друга, однокритериальных задач.

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

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

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

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

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

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

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

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

Формальное описание анробациоппой модели выполнено при помощи величин: N (количество периодов), к = [1, -/V] (номер периода), х„(к), ха{к), Хе(к), Ус1(к), уе(к), ус(к), ур(к). Эти величины при любом к = [1, N — 1] связываются следующими динамическими соотношениями:

ха(к + 1) - ха(к) = -ус{к)х<1{к) + ур(к)хс{к) + уй{к) - уе{к). (54)

Хй(к + 1) - хл(к) = уа(к), хе(к + 1) - хе{к) =уе{к),

(52)

(53)

В данной системе разностных уравнений фазовыми переменными являются ха(к),ха(к), хе(к), линейно входящими управлениями уа{к) и уе(к), а нелинейно входящими управлениями ус{к),ур(к). Фазовые переменные и управления должны удовлетворять следующим ограничениям:

ха{к)> 0;

xd(k)> 0; Vke[l,N], хе{к)> 0; Vfce[l,7V], 9d < Vd(k) < до, 9е<Уе{к)<9Е, Vfc € [l,N],

(55)

(56)

(57)

(58)

(59)

где дл, до, де, 9е ~ константы. Начальные условия:

®„(1) = ^(1) = 1е(1) = 0. (60)

Конечные условия:

хл{Ы) = хе(Щ = 0. (61)

Наконец, целевой функцией модели является ха(Ы) —> тах.

К управлениям модели, нелинейно входящим в динамические соотношения и подлежащим оптимизации на верхнем уровне, относятся

Ус(к),ур(к), \/к=[1,Ы].

Для рассматриваемой модели требовалось найти оптимальные у*с{к) и у*р(к) в классе кусочно-постоянных функций вида:

9с

Ус(к)

9с

9с

к <п\, 5р. к < mi;

П\<к< П 2\ 9P + v ь mi < к < гиг;

п2<к < п3; ур{к) = < 9р, т,2 < к < т3;

п3< к < щ; 9р + тп3< к < Ш4;

П4 < к; 9р, ГП4 < к.

(62)

Причем в качестве варьируемых параметров были выбраны и v^, в то время как остальные параметры имели постоянные значения.

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

N = 60, 150, 300. Для каждого варианта задачи указаны: значения фиксированных параметров; зависимость управлений ус(к),ур(к) от варьируемых параметров; график зависимости вспомогательной функции верхнего уровня от значения варьируемых параметров при различных коэффициентах штрафа; таблицы решения задачи верхнего уровня при различных коэффициентах штрафа. Характерные графики, иллюстрирующие процесс решения задачи верхнего уровня, изображены на рисунках 1 и 2.

Рис. 1. Траектории движения в пространстве параметров при решении задачи об инвестициях, один параметр, 150 периодов.

Рис. 2. Траектории движения в пространство параметров при решении задачи об инвестициях, два параметра, 60 периодов.

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

Основные результаты работы

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

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

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

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

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

Публикации автора по теме диссертации

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

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

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

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

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

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

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

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

Марковцев Денис Анатольевич

МЕТОД ГЛАДКИХ ШТРАФНЫХ ФУНКЦИЙ В ЗАДАЧАХ ПАРАМЕТРИЧЕСКОГО ПРОГРАММИРОВАНИЯ

АВТОРЕФЕРАТ

Подписано в печать 27.02.2012 Формат 60 ' 84 1/16. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 624. Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Московский физико-технический ипститу (государственный университет)" Отдел оперативной полиграфии "Физтех-полиграф" 141700, Московская обл., г. Долгопрудный, Институтский пер., 9

61 12-1/742

Московский физико-технический институт (государственный универститет) Кафедра высшей математики

На правах рукописи УДК 519.8

Марковцев Денис Анатольевич

МЕТОД ГЛАДКИХ ШТРАФНЫХ ФУНКЦИЙ В ЗАДАЧАХ ПАРАМЕТРИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Специальность 01.01.09 «Дискретная математика и математическая кибернетика»

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель доктор технических наук, профессор Умнов А.Е.

Москва 2012

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3.4 Модели ....................................................62

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ 99

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

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

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

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

ВВЕДЕНИЕ

Актуальность темы. Одним из возможных способов расширения состава задач математического программирования, поддающихся решению численными методами, является параметризация их постановки [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. ЗАДАЧИ ПАРАМЕТРИЧЕСКОГО ПРОГРАММИРОВАНИЯ: ПРОБЛЕМЫ И МЕТОДЫ

ИХ РЕШЕНИЯ

Рассмотрим возможные подходы к решению задачи параметрического программирования (А) по двухуровневой схеме (В)-(С).

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

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

Действительно, зависимость х*(и) обладает рядом неудобных для вычислений свойств:

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

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

- неоднозначность зависимости х*(и) для тех и. при которых задача (В) не имеет локально изолированных решений;

- недифференцируемость зависимости х*(и) даже в случае, когда у функций /(х,и) и д8(х.и),з = [1, га] существуют непрерывные производные достаточно высокого порядка.

Последнее свойство является следствием того, что условия задачи (В) содержат ограничения типа неравенство. Более того, как показано в [6], не гарантируется не только желательная гладкость, но даже и непрерывность зависимости х*(и).

Модель 1.1

Проиллюстрируем вышеуказанные особенности зависимости х* (и) на простом примере:

х*(и) — а^гшп(ж — 1) * (и — 1) (1.1)

X

и-2

X < 2, и > 0.

График зависимости х* (и) (сплошная жирная линия) приведен на рисунке 1.1. Нетрудно видеть, что зависимость х*(и) является недифференцируе-мой, неоднозначной и определена не для всех и Е Е1. Также зависимость х*{и) не является непрерывной.

Модель 1.2

В качестве иллюстрации зависимости /(ж*(к),«) рассмотрим следующую двухуровневую задачу. Задача нижнего уровня:

найти тах(2^х + 3£г) (1-2)

X

при условиях £1 > 0, £2 >0,

Ы1 + Ы2 < 6,

26 +6 <6. (1.3)

Рис. 1.1. График зависимости х*(и) для задачи (1.1).

Это задача линейного программирования с нелинейно входящими в ее условие параметрами, решение которой представляется зависимостями

^2), £2К^)-

Задача верхнего уровня:

найти тах(2££{щ, и2) + З^^ъ щ)) (1.4)

и

при условиях 0.1 < VI < 15.9,

0.1 < щ < 14.9. (1.5)

На рисунке 1.2 приведена графическая форма зависимости функционала 2^(1/1,1/2) + 3^2(^1,^2) от [г/1, г/2] - компонент вектора и Е Яи (множество Яи в данном случае целиком определяется ограничениями задачи верхнего уровня), которая позволяет заключить, что данная зависимость непрерывная, нелинейная, невыпуклая и не дифференцируемая для всех и Е а задача верхнего уровня имеет неединственное решение.

Если в условии задачи верхнего уровня в качестве целевого взять функционал, отличающийся по структуре от (1.2), то свойства этой зави-

17-18

Рис. 1.2. График зависимости //2) + З^О-'ъ 1/2) для задачи (1.2).

симорти могут измениться. Например, если (1.4) имеет вид З^Ки-у. щ) + , ио). то эта зависимость уже не будет являться непрерывной (см. рисунок 1.3). А, если множество Яи сузить условием щ + ~ 36 и заменить целевой функционал па т.т.(ДЗ^(;д, гл) + 2^2(^:1-^2)), Т(:) задача верхнего уровня будет иметь единственное решение. Следует отметить, что в в последнем случае в оптимальной точке и* 6 Ни функционал 3£Г(П, у->) + 2^2(^1, т) не является дифференцируемым (см. рисунок 1.4).

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

Рассмотрим возможные подходы к преодолению затруднений, вызываемых особенностями зависимости х*(и).

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

Рис. "1.3. График; зависимости (, ио) + (и, Ш) для задачи (1.2).

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

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

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

14 12 10 8 6 4 2 0

Рис. 1.4. График зависимости щ) + 2^2(^1, щ) от щ для задачи (1.2)

с дополнительным условием щ + 6^2 = 36.

вать как частный случай задачи двухуровневого программирования. А другим частным случаем является хорошо известная минимаксная задача [29, 21]. Методы решения задач двухуровневого программирования в настоящий момент находятся в стадии активной разработки и еще не доказали свою эффективность.

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

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