WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

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

УДК 519.8 Марковцев

Денис Анатольевич МЕТОД ГЛАДКИХ ШТРАФНЫХ ФУНКЦИЙ В ЗАДАЧАХ ПАРАМЕТРИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

АВТОРЕФЕРАТ

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

Москва – 2012

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

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

Официальные оппоненты: Дикусар Василий Васильевич, д.ф.-м.н., профессор, Вычислительный центр им. А.А. Дородницына РАН, ведущий научный сотрудник, Бирюков Александр Гаврилович, к.ф.-м.н., доцент, кафедра математических основ управления Московского физико-технического института (государственного университета), доцент

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

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




© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.
д. 9, ауд. 903 КПМ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Одним из возможных способов расширения множества задач математического программирования, поддающихся решению численными методами, является параметризация их постановки. Параметризация заключается в разделении множества переменных исходной задачи найти min f(x, u) (1) x,u при условиях gs(x, u) 0, s = [1, m], на два подмножества: собственно переменных x и параметров u, значения которых при необходимости могут быть зафиксированы. Такое разделение позволяет свести решение исходной задачи (1) к двухуровневой схеме. На первом уровне решается задача математического программирования найти min f(x, u) (2) x при условиях gs(x, u) 0, s = [1, m], u = fix, a на втором найти min f(x(u), u) (3) u при условиях gs(x(u), u) 0, s = [1, m], где x(u) есть решение задачи (2) при фиксированном векторе параметров u.

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

Условимся в дальнейшем задачу (3) называть задачей верхнего уровня, а задачу (2) будем называть задачей нижнего уровня. Пару задач верхнего и нижнего уровня будем называть двухуровневой системой задач или задачей параметрического программирования. В рассматриваемых задачах x En - вектор переменных и u El - вектор параметров являются элементами конечномерных евклидовых пространств, координаты которых x = T T и u =. Предполагается, что функ 1 2 · · · n 1 2 · · · l ции f(x, u), gs(x, u), s = [1, m] имеют непрерывные частные производные до второго порядка включительно.

В первой главе Задачи параметрического программирования:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как известно, решением задачи нижнего уровня (2) при использовании метода штрафных функций является x+(r, u) = arg min (r, x, u) (4) x где вспомогательная функция метода гладких штрафных функций выбирается следующего вида:

m (r, x, u) = f(x, u) + P (r, gs(x, u)). (5) s=Если помимо стандартного свойства { +, < lim P (r, ) = (6) r+0, 0, достаточно гладкая штрафная функция P (r, ) удовлетворяет также и неравенствам P 2P 0 и 0, , (7) то x+(r, u) - точка минимума вспомогательной функции , находимая из условия стационарности grad (r, x+, u) = o, (8) x или m P (r, gs(x, u)) grad f(x, u) + · grad gs(x, u) = o, (9) gs x x s=удовлетворяет условиям сглаживания зависимости x(u).

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

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

1. Решение уравнений (8), являющихся условиями стационарности функции (5), x+(r, u) существует и локально единственно для любых u El и r > 0, и потому зависимость x+(r, u) является функциональной.

2. Для зависимости x+(r, u) верно равенство lim x+(r, u) = x(u).

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

Как известно, основное свойство метода штрафных функций состоит в том, что lim (r, x+(r, u), u) = f(x(u), u), (10) r+где x(u) – решение задачи (2). Поэтому в качестве целевого функционала, оптимизация которого позволяет получить оценку решения задачи верхнего уровня, можно принять E(r, u) = (r, x+(r, u), u). (11) Введем обозначение (r) = arg min E(r, u). (12) u Пусть пара векторов x и u есть решение задачи (1), тогда справедливы равенства:

lim (r) = u, lim x+(r, u) = x(u) и (13) r+0 r+lim E(r, (r)) = lim (r, x+(r, (r)), (r)) = f(x, u), r+0 r+следующие из теорем 2, 3 и 4.

Теорема 2. Точка {x, } является стационарной точкой функционала (r, x, u) тогда и только тогда, когда – стационарная точка функционала E(r, u).

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

Теорема 4. Точка {x, u} En El является локальным изолированным решением задачи (1) тогда и только тогда, когда x и u – соответственно локальные изолированные решения задач (2) для u и (3) соответственно.

С другой стороны, из теорем 1 и 6 следует, что s = [1, m] P (r, gs(x+(r, (r)), (r))) lim = -, (14) s r+gs P (r, gs(x+(r, (r)), (r))) lim gs(x+(r, (r)), (r)) = 0.

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

s = [1, m] 0 такие, что (15) s gs(x, u) = 0, и s m grad f(x, u) + · grad gs(x, u) = o.

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

Теорема 1. (Сходимость к двойственному решению) Пусть задача математического программирования найти вектор переменных x En, (16) доставляющий минимум функционалу f(x) при условиях gs(x) 0, s = [1, m], решается методом штрафных функций. В качестве функции штрафа используется P (r, ), удовлетворяющая условиям (6) и (7), r – коэффициент штрафа. Функции f(x), -gs(x) s = [1, m] выпуклы, множество оптимальных точек задачи (16) компактно. Если к тому же {rk} – строго убывающая и стремящаяся к нулю последовательность положительных чисел, то в процессе решения получаются точки [x(rk), (rk)], (17) где P (rk, gs(x(rk)) s(rk) = -, s = [1, m], (18) gs допустимые для двойственной задачи найти max L(x, ) (19) при условиях (20) xL(x, ) = 0, (21) s 0, s = [1, m], (22) и также выполняются lim L(x(rk), (rk)) = min f(x) = f (23) k R и lim s(rk)gs(x(rk)) = 0, s = [1, m], (24) k где R = {x|gs(x) 0, s = [1, m]} (25) и m L(x, ) = f(x) - sgs(x) (26) s=– функция Лагранжа.

Теорема 6. Пусть u есть решение задачи верхнего уровня, x – решение задачи нижнего уровня для u = u, функции f(x), -gs(x), s = [1, m] – локально выпуклы. Тогда существуют числа 0, s = [1, m] такие, что s m grad f(x, u) + · grad gs(x, u) = o, (27) s u u s=gs(x, u) = 0. (28) s Условия существования решения задачи верхнего уровня дает следующая теорема.

Теорема 5. Пусть допустимое множество R = {(x, u) EnEl| gs(x, u) 0, s = [1, m]} исходной задачи (1) - компакт, тогда решение задачи верхнего уровня (3) существует.

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

1. для некоторого исходного приближения uk решается задача нижнего уровня, 2. затем оцениваются как величина k, так и направление шага wk, 3. выполняется переход к точке uk+1 по формуле uk+1 = uk + kwk, (29) 4. если в uk+1 условие окончания итерационного процесса не выполнено, то uk присваивается значение uk+1 и делается переход к пункту 1.

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

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

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

Узнайте, что такое Саентология...

Ваша жизнь поменяется...

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

В свою очередь, поиск wk и k, гарантирующих сходимость процедуры (29), может потребовать нахождения локальных численных характеристик функционала E(r, u), таких как: его значение, значения компонент градиента и матрицы Гесса, то есть, частных производных первого и второго порядка для некоторого фиксированного u. Эти характеристики могут быть найдены по формулам E =, j = [1, l] (30) j j и n + 2 2 i E t = +, j, t = [1, l]. (31) j jt i=1 ij t Необходимые для использования (31) значения + i, i = [1, n], j = [1, l] (32) t можно найти, решив систему линейных уравнений:

n + 2 i 2 = -, j, t = [1, l], (33) ij t jt i=которая получается при дифференцировании (8) по всем компонентам u El.

На практике использование предельных соотношений (13) ограничено ухудшением обусловленности уравнения (9) при уменьшении абсолютной величины r – врожденном недостатке метода гладких штрафных функций.

Уменьшение вначале вызывает рост затрат вычислительных ресурсов на реализацию процесса (29), а затем и вовсе приводит к нарушению его сходимости. В случае, когда процедура (29) далека от завершения, различие между x+(r, u) и x(u) не играет существенной роли, и вычисления можно выполнять при достаточно большом r, отложив его уменьшение до завершающей стадии этой процедуры.

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

x+ x+(r + r, u) = x+(r, u) + r + o(r), (34) r из которой следует оценка при r -r сверху:

x+ x(u) = x+(r, u) - r + o(r). (35) r x+(r,u) Компоненты вектор-функции могут быть найдены по теореме о неявr ной функции из системы линейных уравнений:

n + 2 i 2 = -, j = [1, n], (36) ij r j r i=получаемой при дифференцировании уравнения (8) по параметру r.

В третьей главе Реализация метода сглаживающих штрафных функций исследуются проблемы решения задач вида (1), допускающих параметрическую линеаризацию. То есть таких, что задача нижнего уровня (2) оказывается при фиксации параметров задачей линейного программирования с n f(x, u) = ci(u)i, (37) i=n gs(x, u) = asi(u)i - bs(u).

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

В качестве штрафной функции выберем { , < 2r P (r, ) = (38) 0, 0, Сходимость итерационной процедуры (29) при использовании штрафной функции такого типа обосновывается утверждениями теоремы 11. Процедура сглаживания, как и в общем случае, сводится к нахождению вектора x+(r, u), а также grad E(r, u) и hess E(r, u), u u значения компонент которых вычислены в точке x+(r, u).

В рассматриваемом случае вспомогательный функционал задачи (2) выпуклый, что позволяет получить связь процедуры сглаживания с двойственной задачей. Обозначим P (r, gs(x+(r, u), u)) +(r, u) = -, s = [1, m], (39) gs тогда условие стационарности примет вид, совпадающий по форме с условием стационарности функции Лагранжа для задачи нижнего уровня m grad f(x+(r, u), u) - +(r, u) · grad gs(x+(r, u), u) = o, (40) x x s=или, с учетом линейности задачи (2), m ci(u) - +(r, u)asi(u) = o, i = [1, n]. (41) s s=При этом уравнение (40) имеет в силу свойств метода штрафных функций локально единственное решение x+(r, u). Из теоремы 1 вытекает, что существуют lim +(r, u) = (u) 0, s = [1, m]. (42) s s r+Следовательно, будет справедливо равенство m grad f(x(u), u) - (u) · grad gs(x(u), u) = o, (43) x x s=и числа (u), s = [1, m] совпадают со значениями множителей Лагранжа s задачи нижнего уровня в случае, когда последние существуют и единственны. В общем же случае, числа (u), s = [1, m] являются одним из решений s системы уравнений grad f(x(u), u) - (u) · grad gs(x(u), u) = o, (44) s x x sJ(u) где J(u) – множество индексов активных ограничений задачи нижнего уровня, то есть ограничений, для которых gs(x(u), u) = 0. Система уравнений (44) не всегда однозначно разрешима относительно неотрицательных (u).

s Это может иметь место, например, в случае, когда число активных ограничений больше, чем n. Равенство (43) позволяет из множества активных ограничений выделить особое подмножество J+(u) J(u), такое что J+(u) = {s = [1, m]|(u) > 0}. (45) s Из свойств квадратичной штрафной функции P (r, ) при r +0 следует gs(x+(r, u), u) < 0, s J+(u), (46) gs(x+(r, u), u) 0, s J+(u).

Таким образом для ограничений с индексами s J+(u) метод штрафных функций генерирует точки x+(r, u) вне допустимой области, в то время как для ограничений с индексами s J+(u) получаются точки внутри допустимой области. Поэтому ограничения, индексы которых принадлежат множеству J+(u), логично назвать ре-активными. Если ограничение не является реактивным, то значение и дифференциальные характеристики функционала E(r, u) от него не зависят, и эти ограничения можно исключить из рассмотрения в точке u.

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

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

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

найти x(uk) = arg min f(x, uk) (47) x при условиях gs(x, uk) 0, s = [1, m].

Если задача совместна, то сформируем множество J(uk), включающее индексы ограничений, активных в точке x(uk). Если же задача несовместна, то включим во множество J(uk) индексы всех ограничений задачи (47).

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

(r, x, uk) = f(x, uk) + s(-gs(x, uk))gs(x, uk) (48) 2r sJ(uk) Эта функция является выпуклой в En в силу линейности целевого функционала и выбранной функции штрафа, поэтому множество точек минимума вспомогательной функции не пусто. Чтобы выбрать единственную точку x+(r, uk) может понадобиться выполнить регуляризацию вспомогательной функции.

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

f(x, uk) 1 g(x, uk) + gs(x, uk) = 0, i = [1, n]. (49) i r i sJ+(uk) Если же размер множества J(uk) больше n, то необходимо найти x+(r, uk) как минимум вспомогательной функции (48). Это можно сделать, например, с помощью метода Ньютона. При решении вспомогательной задачи необходимо следить, чтобы в процессе решения не изменилось множество активных ограничений. Вычислив x+(r, uk), можно выделить множество индексов J+(uk).

Решением задачи нижнего уровня для заданного uk является пара: x+(r, uk), J+(uk).

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

E(r, u) = f(x+(u), u) + gs(x+(u), u). (50) 2r sJ+(uk) В зависимости от выбранного метода безусловной минимизации может потребоваться вычисление производных функции E(r, u). Производные находятся по формулам (30) - (33). Вычислив производные функции E(r, u) в точке uk находим направление спуска k и величину шага k. Новая точка в пространстве параметров определяется по формуле:

uk+1 = uk + kk. (51) Если условие окончания процесса выполнено, то найдено оптимальное решение. В противном случае выполняется переход к следующей итерации.

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

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

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

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

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

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

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

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

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

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

Формальное описание апробационной модели выполнено при помощи величин: N (количество периодов), k = [1, N] (номер периода), xa(k), xd(k), xe(k), yd(k), ye(k), yc(k), yp(k). Эти величины при любом k = [1, N - 1] связываются следующими динамическими соотношениями:

xd(k + 1) - xd(k) = yd(k), (52) xe(k + 1) - xe(k) = ye(k), (53) xa(k + 1) - xa(k) = -yc(k)xd(k) + yp(k)xe(k) + yd(k) - ye(k). (54) В данной системе разностных уравнений фазовыми переменными являются xa(k), xd(k), xe(k), линейно входящими управлениями yd(k) и ye(k), а нелинейно входящими управлениями yc(k), yp(k). Фазовые переменные и управления должны удовлетворять следующим ограничениям:

xa(k) 0; k [1, N], (55) xd(k) 0; k [1, N], (56) xe(k) 0; k [1, N], (57) gd yd(k) gD, (58) ge ye(k) gE, k [1, N], (59) где gd, gD, ge, gE – константы.

Начальные условия:

xa(1) = xd(1) = xe(1) = 0. (60) Конечные условия:

xd(N) = xe(N) = 0. (61) Наконец, целевой функцией модели является xa(N) max.

К управлениям модели, нелинейно входящим в динамические соотношения и подлежащим оптимизации на верхнем уровне, относятся yc(k), yp(k), k = [1, N].

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

gc, k < n1; gp, k < m1;

gc + 1, n1 k < n2; gp + 1, m1 k < m2;

yc(k) = yp(k) = (62) gc, n2 k < n3; gp, m2 k < m3;

gc + 2, n3 k < n4; gp + 2, m3 k < m4;

gc, n4 k; gp, m4 k.

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

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

53r=0.r=0.0r=0.0 53 53E(r,u) 53 53 53 53 0 0.002 0.004 0.006 0.008 0.u Рис. 1. Траектории движения в пространстве параметров при решении задачи об инвестициях, один параметр, 150 периодов.

69 68E(r,u) 67 66 650.0.0.0.0.0.1 0.03 0.0.0.Рис. 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, с.

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, Московская обл., г. Долгопрудный, Институтский пер.,

Авторефераты по всем темам  >>  Авторефераты по разным специальностям



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.