Задача квадратичного программирования с параметром в правых частях ограничений и ее применение
Категория реферата: Рефераты по экономико-математическому моделированию
Теги реферата: семейные реферат, ответы по тетради
Добавил(а) на сайт: Аюшиев.
1
Содержание
1. ВВЕДЕНИЕ
2.АНАЛИТИЧЕСКИЙ ОБЗОР
3. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
3. ЗАДАЧА КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ (НЕПАРАМЕТРИЧЕСКИЙ СЛУЧАЙ).
3.1 Постановка задачи:
3.2 Условия оптимальности в задаче (3.2)
3.3. Базис задачи квадратичного программирования. Оптимальный и невырожденный базисы.
3.4. Метод субоптимизации на многообразиях. Выпуклый случай.
3.5 Метод субоптимизации на многообразиях. Задача квадратичного программирования.
3.6. Метод субоптимизации на многообразиях в задаче квадратичного программирования. Теоретическое обоснование.
3.7. Вычислительная схема алгоритма субоптимизации для задачи квадратичного программирования.
3.8. Некоторые особенности вычислительной схемы метода субоптимизации на многообразиях для задачи квадратичного программирования.
4. ЗАДАЧА КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ С ПАРАМЕТРОМ В ПРАВЫХ ЧАСТЯХ ОГРАНИЧЕНИЙ.
4.1 ПОСТАНОВКА ЗАДАЧИ
4.2 Некоторые свойства решения параметрической задачи квадратичного программирования.
4.3 Применение метода субоптимизации на многообразиях к решению параметрической задачи квадратичного программирования.
5.ЭКОНОМИЧЕСКАЯ ЧАСТЬ
6.БИБЛИОГРАФИЯ
7.ПРИЛОЖЕНИЕ 1..................................................................................................................65
8.ПРИЛОЖЕНИЕ 2..................................................................................................................67
9.РИСУНОК 1...........................................................................................................................78
1. Введение
В настоящей работе рассматривается применение метода субоптимизации на многообразиях к решению задачи квадратичного программирования с параметром в правых частях ограничений.
Метод субоптимизации на многообразиях, предложенный У.Зангвиллом в 1968 году для решения задач выпуклого программирования представляет собой простую процедуру поиска оптимальной точки в задаче выпуклого программирования с ограничениями типа равенств. Метод использует подход, названный автором "выделением активных ограничений", сводящий исходную задачу выпуклого программирования к определенным образом строящейся последовательности вспомогательных задач выпуклого программирования.
В тех случаях, когда решение вспомогательных задач оказывается существенно проще решения исходной, или вообще очевидным, метод субоптимизации на многообразиях позволяет существенно снизить вычислительную трудоемкость процедуры решения исходной задачи, а также исследовать свойства решения общей задачи на основании общих свойств вспомогательных задач.
В работе показано, что, в случае задачи квадратичного программирования, решение вспомогательных задач сводится к разложению определенным образом выбираемого вектора по некоторому базису, что в свою очередь эквивалентно решению системы линейных уравнений. Таким образом решение исходной задачи оказывается эквивалентным решению конечного числа систем линейных уравнений.
Показано также, что в случае задачи выпуклого программирования решение общей задачи сводится к последовательному решению вспомогательных задач, при переходе между которыми в базисном множестве происходит замена только одного вектора.
В силу этого становится возможным создание рекуррентных формул, связывающих матрицы системы линейных уравнений соседних вспомогательных задач.
Таким образом вместо решения системы линейных уравнений на каждом шаге метода можно вычислять новое решение с помощью соответствующих рекуррентных соотношений, прибегая к непосредственному решению системы линейных уравнений только с целью коррекции накопившейся ошибки вычисления после значительного количества итераций.
В результате вычислительная трудоемкость процедуры оказывается в лучшем случае эквивалентной решению системы линейных уравнений с последующим конечным числом матричных преобразований типа умножения матрицы на вектор. В худшем случае задача оказывается эквивалентной решению конечного числа систем линейных уравнений.
Доказаны теоремы, составляющие теоретический фундамент алгоритма, приведено доказательство сходимости предложенной вычислительной процедуры.
Рассматривается применение указанного метода к решению параметрической задачи квадратичного программирования с параметром в правых частях ограничений, путем сведения указанной задачи к конечному числу задач квадратичного программирования без параметра.
В силу того, что решение параметрической задачи квадратичного программирования с параметром в правых частях ограничений оказывается кусочно-линейной функцией, исходная задача сводится к покрытию области допустимых значений параметра отрезками, на которых функция решения линейна по параметру с постоянными коэффициентами, зависящими только от значения функции в левой точке отрезка.
Показано, что такое разбиение состоит из конечного числа отрезков, и конечного числа точек переключения траектории решения.
Построение такого покрытия в худшем случае эквивалентно решению конечного числа задач квадратичного программирования без параметра в точках переключения траектории. Показаны подходы к построению процедуры перестройки решения в точках переключения траектории без необходимости полного решения задачи квадратичного программирования путем сведения ее к одной или нескольким итерациям метода субоптимизации на многообразиях.
Поставлена задача поиска оптимального вложения в задаче о портфеле ценных бумаг, являющаяся экономической интерпретацией параметрической задачи квадратичного программирования.
Составлена и отлажена программа на языке С++, функционирующая в среде операционных систем UNIX (AIX, Solaris) а также Microsoft Windows, реализующая описанные алгоритмы. Указанная программа применена к решению задачи о поиске оптимальных инвестиций в задаче о портфеле ценных бумаг, данные решения и текст программы приведен в приложениях.
Указаны возможные пути упрощения процедуры поиска решения задачи квадратичного программирования с параметром в правых частях ограничений путем отказа от решения задачи квадратичного программирования в точках переключения траектории.
2.Аналитический обзор
Для решения задач выпуклого программирования с линейными ограничениями могут применяться различные методы решения. Для построения таких методов используется как правило подход, предполагающий задачу квадратичного программирования в известном смысле расширением задачи линейного программирования.
Результатом применения такого подхода является группа методов основанных на простроении аппроксимации исходной квадратичной задачи последовательностью задач линейного программирования, а также различные обобщения линейного симплекс-метода на случай выпуклой функции-критерия.
Рассматриваемый в данной работе метод субоптимизации на многообразиях представляет собой результат совсем иного подхода к решению задачи квадратичного программирования. Процедура метода субоптимизации строится для более общего класса задач выпуклого программирования, причем указывается класс задач, для которых этот метод оказывается достаточно эффективным.
При этом задача квадратичного программирования оказывается частным случаем задачи выпуклого программирования, для которой метод субоптимизации позволяет свести решение исходной задачи к решению конечного числа систем линейных уравнений.
3. Теоретическая часть
3. Задача квадратичного программирования (непараметрический случай).
3.1 Постановка задачи:
Задачей квадратичного программирования будем называть задачу следующего вида:
(3.1.1)
здесь x-вектор столбец размера n, C- вектор-строка размера 1?n, D - матрица размера n?n, симметричная и неотрицательно определенная (D ? 0). b - столбец длины m. A - матрица размера m?n, ранг ее равен m (R(A) = m).
Имеет место также условие неотрицательности компонентов вектора x:
x ? 0.
Поскольку наличие компонента Cx не оказывает существенного влияния на результаты, изложенные в настоящей работе, будем без ограничения общности предполагать вектор C нулевым. В такой постановке задача принимает вид:
(3.1.2)
В данной постановке задача квадратичного программирования всегда имеет оптимальный вектор, и является задачей выпуклого программирования с линейными ограничениями типа равенств.
3.2 Условия оптимальности в задаче (3.2)
Условия оптимальности в задаче (3.2) представляют собой формулировку условий Куна-Таккера для этой задачи. Будем рассматривать следующую форму записи условий Куна-Таккера для задачи выпуклого программирования:
(3.2.1)
В нашем случае получим:
(3.2.2)
Здесь Ai- столбцы матрицы A длины m, Di столбцы матрицы D длины n, Lk - строки матрицы A длины n, ej - n-мерные столбцы единичной матрицы. Здесь и далее xi - компоненты оптимального вектора задачи x, ?k и ?k - множители Лагранжа условий Куна-Таккера. Запишем систему 3.2.2 в более обобщенной форме:
(3.2.3)
где составные столбцы P0, ... Pm+2n каждый длиной m+n являются столбцами блочной матрицы P, имеющей следующий вид:
(3.2.4)
В таком виде условия Куна-Таккера (3.2.3) можно записать в еще более простом виде:
(3.2.5)
Поскольку рассматриваемая нами задача является задачей выпуклого программирования, указанные условия существования минимума являются одновременно необходимыми и достаточными. Доказательство указанных условий можно найти в [1,2].
3.3. Базис задачи квадратичного программирования. Оптимальный и невырожденный базисы.
Поскольку ранг матрицы A равен m (см 3.1), система векторов
являются линейно независимой системой векторов. В то же время, легко видно, что линейная оболочка, натянутая на систему векторов P совпадает с пространством Em+n, т.е L(P)=En+m.
Следовательно из системы векторов 3.2.4 можно образовать конечное число базисов N евклидова пространства En+m, содержащих в себе векторы P1, .. Pm. Такие базисы пространства En+m будем называть базисами задачи квадратичного программирования, и обозначать следующим образом:
(3.3.1)
Для упрощения схемы алгоритма, запишем базис (3.3.1) в следующем виде:
(3.3.2)
Здесь ?1 и ?2 - наборы индексов. В случае, если ?1=?2 будем считать базис U?1,?2 порожденным одним множеством индексов ?=?1.
(3.3.3)
Коэффициенты разложения вектора b по базису U?1,?2 будем называть базисными переменными, остальные коэффициенты - небазисными переменными.
Базис U?1,?2 назовем оптимальным, если его базисные переменные удовлетворяют условиям Куна-Таккера (3.2.3).
Базис называется невырожденным, если все его базисные переменные, соответствующие компонентам вектора x отличны от нуля, т.е.
(3.3.4)
Задачу (3.1.2) будем называть невырожденной, если все ее базисы невырождены. В противном случае назовем задачу вырожденной.
3.4. Метод субоптимизации на многообразиях. Выпуклый случай.
Для решения задачи (3.1.2) предлагается использовать метод
субоптимизации на многообразиях. Вначале рассмотрим основные идеи, приводящие к методу субоптимизации в случае задачи выпуклого программирования общего вида.
Рассмотрим задачу выпуклого программирования с линейными ограничениями, состоящую в минимизации выпуклой функции f(x) на множестве L, задаваемом ограничениями типа равенств.
(3.4.1)
Предположим, что задача имеет единственное решение, т.е минимум целевой функции достигается в единственной оптимальной точке x*. В этом случае задаче (3.4.1) эквивалентна задача:
(3.4.2)
Эквивалентность этих двух задач является следствием единственности решения. Переход к задаче (3.4.2) называется выделением активных ограничений, т.е. вместо условия неотрицательности всех переменных, мы переходим к условию равенства нулю всех компонент, решения, индексы которых не принадлежат множеству ?(x*).
Предположим, что для задачи (3.4.2) нахождение оптимального решения существенно проще, чем для исходной задачи (3.4.1). В этом случае, перебирая каким-либо образом всевозможные множества индексов ?k, являющиеся подмножествами полного набора индексов {1,..n}, и решая для каждого из них задачу (3.4.2), используя ?k вместо ?*, определить искомое множество индексов ?*.
Предположим также, что задача (3.4.2) обладает свойством
единственности, т.е система векторов {L1, .. Lm, ej (j? ?(x*)}- линейно независима. В случае нарушения свойства единственности задача поиска оптимального вектора задачи (3.4.2) усложняется, и в дальнейшем этот случай рассматриваться не будет.
Алгоритм перебора множеств индексов ?k основан на следующей лемме.
Основная лемма:
Пусть x* является оптимальной точкой задачи:
(3.4.3)
где X? - линейное многообразие, определяемое следующим образом:
(3.4.4)
Предположим, что задача (3.4.3) с условием (3.4.4) обладает свойством единственности, и среди ?j, удовлетворяющих условиям Куна-Таккера существует отрицательное ?j0, т.е.
(3.4.5)
Пусть ? ' - множество индексов, полученное из ? вычитанием индекса j0:
(3.4.6)
Тогда, если x*' - оптимальный вектор задачи
(3.4.7)
то справедливо неравенство:
f(x*')
(3.4.8)
Доказательство.
Так как в силу выполнения соотношения (3.4.6) и определения множеств X? и X?' вытекает, что X?' ? X? то имеет место неравенство f(x*') ? f(x*). Следовательно для доказательства соотношения (3.4.8) достаточно показать, что f(x*') ? f(x*).
Предположим, что это не так. Тогда точка x* является оптимальной для задач (3.4.3) и (3.4.7), и удовлетворяет условиям Куна-Таккера в обоих задачах:
(3.4.9)
(3.4.10)
Добавим в правую часть равенства (3.4.10) член 0ej0. Поскольку, по предположению (3.4.5) леммы коэффициент ?j0 отличен от нуля, получаем разложение вектора градиента функции f по системе векторов {L1, .. Lm, ej (j? ?(x*)}. Получаем противоречие с условием единственности, а стало быть, и с условием основной леммы.
Доказанная лемма указывает направление перебора множеств индексов ?k (а стало быть и многообразий), уменьшающее значение целевой функции f(x).
Из доказанной леммы вытекает
Алгоритм поиска оптимального вектора
Общий вид алгоритма метода субоптимизации для задачи выпуклого программирования приведен на рис. 1. Ниже приводятся описания блоков алгоритма, изображенных на этом рисунке.
Блок 1. Определяется допустимая начальная точка x1 для исходной задачи. Это может быть точка, получаемая с помощью алгоритма построения начального базиса линейного симплекс-метода, или же решение в некотором смысле близкой линейной задачи. Предполагается ?1=?(x1), k=1.
Блок 2. Находится оптимальный вектор x*k для задачи
Если x*k оказывается допустимой для исходной задачи (3.4.1), совершается переход к блоку 3, в противном случае осуществляется переход к блоку 4.
Блок 3. Вычисляется значение
Если
то в силу выполнения условий Куна-Таккера для исходной задачи (3.4.1) точка x*k является оптимальной точкой задачи (3.4.1) и работа алгоритма заканчивается.
Если
то предполагаем
и происходит переход к блоку 2.
Блок 4. Поскольку оптимальная точка вспомогательной задачи оказалась недопустимой для исходной, выбираем в качестве новой начальной точки ближайшую к ней точку, допустимую для исходной задачи (3.4.1), и лежащую на прямой, соединяющей оптимальные точки вспомогательной задачи, т.е.
Далее полагаем ?k+1=?(xk+1), заменяем k на k+1, и переходим к блоку 2.
Таким образом построен итерационный процесс, позволяющий осуществить направленный перебор множеств индексов ? k, позволяющий найти оптимальный вектор исходной задачи. Сходимость процедуры будет рассмотрена позже.
3.5 Метод субоптимизации на многообразиях. Задача квадратичного программирования.
Рассмотрим применение метода субоптимизации, рассмотренного в (3.4) к задаче квадратичного программирования (3.1.2). Как было ранее отмечено, условием успешного применения метода субоптимизации на многообразиях в задаче выпуклого программирования является существенная простота решения задачи (3.4.2) по сравнению с исходной задачей (3.4.1).
Рассмотрим эквивалентную (3.1.2) задачу:
(3.5.1)
Запишем условия Куна-Таккера для задачи (3.5.1) с произвольным набором индексов ? :
(3.5.2)
Используя ранее введенные обозначения (3.2.3-3.2.4), систему условий Куна-Таккера (3.5.2) можно записать следующим образом:
(3.5.3)
Если множество U? порождает базис, вследствие (3.5.3) поиск минимума на многообразии X? представляет собой разложение вектора P0 по этому базису, т.е. эквивалентен решению системы линейных уравнений. Таким образом, метод субоптимизации на многообразиях в случае задачи квадратичного программирования оказывается эффективным в том случае, если в цепочке итерационного процесса встречаются только множества индексов, порождающие базисы.
Процедура метода строится на двух основных операциях, аналогичных блокам общего алгоритма субоптимизации на многообразиях для задачи выпуклого программирования.
Операция А. Пусть для некоторого набора индексов ?0 определена оптимальная точка x* и множители Лагранжа ?*k и ?*j удовлетворяющие условиям Куна-Таккера совместно с оптимальным вектором x. Рассмотрим вспомогательное многообразие
(3.5.4)
Операция А состоит в нахождении оптимального вектора x*(?), а также множителей Лагранжа, удовлетворяющих условиям Куна-Таккера задачи минимизации квадратичного функционала на многообразии (3.5.4).
Запишем условия Куна-Таккера для этой вспомогательной задачи:
Если набор индексов ?0 порождает базис, то существует разложение вектора Pm+j0 по этому базису, имеющее следующий вид:
(3.5.6)
Подставляя это разложение в (3.5.5), и учитывая оптимальность набора x*,?*,?*, получаем следующие выражения для компонент оптимальной точки на многообразии (3.5.4):
(3.5.7)
Таким образом, в случае, если набор индексов ?0 порождает базис, операция А осуществляется тривиально, и определяется выражениями (3.5.7).
Суть операции А состоит в нахождении оптимальной точки на новом многообразии (3.5.4) по известной оптимальной точке на многообразии (3.4.4).
Операция Б. Пусть некоторое вспомогательное многообразие X?0(?1) таково, что одна из базисных компонент вектора x обратилась в ноль:
(3.5.8)
Суть операции Б состоит в переходе от многообразия X?0(?1) к другому многообразию X?1 , соответствующему набору индексов ?1 , определяемому следующим образом:
(3.5.9)
т.е. индекс j0 из (3.5.4) заменяется на индекс r из (3.5.8).
Учитывая (3.5.8), разложение (3.5.5) на многообразии X?0 можно представить следующим образом:
(3.5.10)
Аналогично случаю, рассмотренному в операции А, что, если имеет место разложение:
(3.5.11)
причем выполнено соотношение
(3.5.12)
то условиям Куна-Таккера для задачи (3.5.1) соответствующей набору индексов ?1 , удовлетворяют переменные, получаемые с помощью следующих формул:
(3.5.13)
где
(3.5.14)
Учитывая вышеописанные условия, операция Б оказывается осуществимой в том случае, когда наборам индексов ?0 и ?1 соответствует базис U?1,?0 . Операция Б является аналогом блока 4 общей схемы метода субоптимизации на многообразиях для задачи выпуклого программирования.
Для большей наглядности можно определить множество L?1,?0 представляющее собой прямую, порождаемую базисом U?1,?0 следующего вида:
(3.5.15)
Здесь - коэффициенты разложения вектора P0, а xir - вектора Pm+n+r по базису U?1,?0. Заметим, что L?1,?0(0) есть оптимальный вектор многообразия (3.5.4) при ?= . Переход от этой точки к новому многообразию с помощью операции Б представляет собой движение по указанной прямой от дельта равного нулю в положительную (как будет показано позже) сторону.
3.6. Метод субоптимизации на многообразиях в задаче квадратичного программирования. Теоретическое обоснование.
Заметим, что если множество индексов ? порождает базис U? , то задача (3.5.1), соответствующая этому множеству индексов имеет единственный оптимальный вектор x* , обладая при этом свойством единственности, введенным ранее для задачи выпуклого программирования.
Выше были описаны вспомогательные задачи метода субоптимизации на многообразиях, однако не были сформулированы правила применения этих операций. Ниже будут доказаны две теоремы, дающие способ определения неизвестных шагов ? и ?. Для их доказательства потребуется несколько вспомогательных утверждений.
Лемма 1. Пусть вектора x0, x1 удовлетворяют системе уравнений условий Куна-Таккера и пусть f(x) - неотрицательно определенный квадратичный функционал вида xTDx, а ?1 вектор ограниценных по знаку множителей Лагранжа, удовлетворяющих условиям Куна-Таккера совместно с вектором x1 . Тогда имеет место следующее неравенство:
(3.6.1)
Доказательство:
Преобразуем левую часть следующим образом:
Здесь можно воспользоваться условием выполнения теоремы Куна-Таккера:
Требуемое неравенство непосредственно вытекает из последнего соотношения.
Следствие. Пусть x0, x0(?) - оптимальные точки задачи (3.5.1) с некоторым множеством индексов ? и вспомогательной задачи поиска минимума на многообразии (3.5.4). Тогда имеет место неравенство:
Доказательство. Так как x0, x0(?) удовлетворяют условиям Куна-Таккера, то выполняется неравенство Леммы 1:
В силу особенностей решений x0, x0(?) правую часть неравенства можно записать в виде
что и доказывает справедливость следствия.
Лемма 2. Пусть x0, x1 - оптимальные точки многообразий X?0 и X?1 соответственно, удовлетворяющие условиям Куна-Таккера совместно с множителями Лагранжа ?0 и ?1. Тогда справедливо соотношение:
Доказательство: Аналогично доказательству Леммы 1, получаем, что:
Складывая эти два равенства, получаем:
Из выполнения условий Куна-Таккера следует, что:
Раскрывая скобки в левой части неравенства получаем искомое неравенство.
Ниже будет доказана теорема, дающая направление движения и условия применения операции А.
Теорема 1. Пусть оптимальная точка x0 - оптимальная точка многообразия X?0 , причем совокупность индексов ?0 порождает базис U?0 . Тогда, если среди множителей Лагранжа, соответствующих x0 , существует отрицательный (предположим, что он имеет индекс j0)
то новый набор индексов
также порождает базис и в единственной оптимальной точке на многообразии выполнено условие
Доказательство. Если для набора индексов существует оптимальный вектор , то в силу утверждения леммы 2 и определения нового набора индексов имеем
с другой стороны, в силу условия единственности,
Итак, если оптимальная точка на новом многообразии существует, то доказываемое неравенство верно. Существование же оптимальной точки вытекает из того факта, что новый набор индексов порождает базис. Это так, если коэффициент ?j0j0 в разложении (3.5.6) не равен нулю.
Предположим, что этот коэффициент равен нулю. В этом случае, в силу следствия из леммы и условия отрицательности ?j0 квадратичный функционал f(x) оказывается отрицательно определенным. Теорема доказана.
Теорема 1 указывает направление движения по многообразиям с помощью операции А. Переход от многообразия X?0 к многообразию осуществляется с помощью движения по многообразиям X?0 (?) при возрастании ? от нуля до некоторой величины
В силу вида нового множества индексов величина ?0 определяется из условия обращения в ноль соответствующего множителя Лагранжа:
Сформулируем и докажем аналогичную теорему для операции Б:
Теорема 2. Пусть ?0 и ?1 наборы индексов, порождающие базис U?1,?0 , такие, что:
причем в разложении
(3.6.2)
коэффициент . Пусть также для множества индексов
существует оптимальный вектор для задачи (3.5.1), причем такой, что он не является допустимым для исходной задачи (3.1.2), т.е.
Тогда, если x1 - оптимальная точка задачи (3.5.1) на многообразии X?1 , то ?1 порождает базис U?1 , а оптимальная точка x1 принадлежит прямой (3.5.15):
(3.6.3)
Доказательство. Разложим вектор P0 по базису U?1 , а вектор Pm+n+r по базису U?1,?0 :
подставляя второе выражение в первое, и учитывая определение прямой (3.5.15) получаем очевидное следствие:
Кроме того, учитывая разложение (3.6.2), получаем, что
(3.6.4)
А согласно лемме 2, имеем:
Отсюда и из условия теоремы следует, что
Отсюда и из (3.6.4) вытекает доказываемое неравенство. Кроме того, из (3.6.4) также следует отличие от нуля коэффициента , что приводит к выводу о линейной независимости системы векторов U?1 . Это доказывает второе утверждение теоремы.
Теорема 2 указывает направление перехода от одного многообразия к другому с помощью операции Б, утверждая положительность величины шага ?1 .
3.7. Вычислительная схема алгоритма субоптимизации для задачи квадратичного программирования.
Ранее (см 3.4) была приведена общая схема алгоритма субоптимизации на многообразиях для случая задачи выпуклого программирования и получена блочная структура алгоритма. Конкретизируем теперь структуру блоков для случая задачи квадратичного программирования.
Блок1.
Определяется начальный набор индексов ?1 , порождающий базис U?1 , для которого оптимальная точка задачи (3.5.1) является одновременно допустимой для исходной задачи (3.1.2). Такая точка в [2] называется дополняющей.
В кочестве начального множества индексов можно взять начальный базис, получаемый в ходе решения первой фазы двухфазного симплекс-метода, или же решение задачи линейного программирования, близкой к решаемой квадратичной:
Блок 3. Блок полностью идентичен приведенному ранее в описании алгоритма субоптимизации на многообразиях для задачи выпуклого программирования.
Блок 2. В данном блоке определяется решение вспомогательной задачи (3.5.1). Способ определения решения зависит от предыдущего блока алгоритма:
Блок 2(А). Эта часть блока вступает в действие после блока 3. Оптимальный вектор задачи (3.5.1) находится с помощью операции А. Если полученный оптимальный вектор допустим для исходной задачи (3.1.2), осуществляется переход в блок 3. В противном случае осуществляется переход в блок 4.
Критерием выбора следующего шага является сравнение двух величин:
Первая величина задает момент обращения в ноль выбранной минимальной величины ?j0 , вторая величина задает момент обращения в ноль первой из базисных компонент вектора x . Если вторая величина оказывается меньше первой, это означает, что новое решение задачи (3.5.1), полученное в результате операции А, не является допустимым для исходной задачи (3.1.2), и необходим переход в блок 4.
Блок 2(Б). Эта часть блока вступает в действие после блока 4. В этом блоке минимум в задаче (3.5.1) находится с помощью операции Б. Если получаемое решение оказывается допустимым для исходной задачи (3.1.2), то осуществляется переход в блок 3. В противном случае осуществляется переход в блок 4.
Критерием выбора следующего шага в этой части блока является сравнение двух величин:
Блок 4. Этот блок полностью соответствует соответствующему блоку в общем алгоритме субоптимизации на многообразиях для задачи выпуклого программирования.
3.8. Некоторые особенности вычислительной схемы метода субоптимизации на многообразиях для задачи квадратичного программирования.
В этой части будет рассмотрен вычислительный аспект процедуры субоптимизации и показаны некоторые ее замечательные свойства.
Выше было показано, что решение каждой вспомогательной задачи метода субоптимизации сводится к поиску разложения некоторого вектора R размерности (m+n) по базису U?1,?2 ; при этом на соседних итерациях базисы отличаются лишь каким-то одним из векторов.
Как было показано выше, существуют четыре возможных альтернативы при переходе от одного базиса к другому, задающие четыре типа операций:
1. От U?1 к U?2 (?2=?1 j0 ) при помощи замены в базисе вектора Pm+n+j0 на Pm+j0 .
2. От U?1 к U?2,?1 (?2=?1 j0 U r) при помощи замены в базисе вектора Pm+r на Pm+j0 .
3. От U?2,?1 (?2=?1 j0 U r) к U?2 при помощи замены в базисе вектора Pm+n+j0 на Pm+n+r .
4. От U?2,?1 (?2=?1 j0 U r) к U?2',?2' (?'2=?2 U r', ?'1=?1 U r' ) при помощи замены в базисе вектора Pm+r на Pm+n+r' .
Процедура разложения вектора R по базису эквивалентна решению системы линейных уравнений вида
где B - базисная часть матрицы P (то есть матрица, составленная из столбцов матрицы P , соответствующих векторам данного базиса). Решение уравнения есть процедура, эквивалентная обращению матрицы B.
Из общего вида матрицы P (3.2.4) можно получить общий вид матрицы B, которая также имеет блочную структуру следующего вида:
Можно показать, что
Видно, что зная матрицу S1-1 можно легко получить значение матрицы B-1 . Используя общий вид переходов, а также их общее свойство, сводящееся к замене одного вектора на другой, можно применить для нахождения S1-1 известную формулу Фробениуса, и получить рекуррентные формулы, связывающие матрицы S1-1 на соседних итерациях. Это позволяет избежать непосредственного обращения матрицы на каждом шаге алгоритма, прибегая к нему через определенный промежуток времени с целью коррекции накопившейся ошибки вычисления.
4. Задача квадратичного программирования с параметром в правых частях ограничений.
4.1 Постановка задачи
Задачей параметрического квадратичного программирования с параметром в правых частях ограничений будем называть следующую задачу выпуклого программирования:
(4.1.1)
Требуется найти вектор-функцию x*(?) , минимизирующую целевую функцию при каждом ? . Интервал изменения параметра может быть и неограниченным.
4.2 Некоторые свойства решения параметрической задачи квадратичного программирования.
Пусть получено решение задачи (4.1.1) при некотором значении параметра, равном ?0 . Это означает, что получен вектор x*(?0) , а также набор индексов ?(?0) , и порожденный им оптимальный базис. Рассмотрим множество таких ? , для которых это решение остается оптимальным и допустимым. Для этого запишем условия Куна-Таккера:
(4.1.2)
Как следует из постановки задачи, правую часть выражения (4.1.2) можно представить в следующем виде:
(4.1.3)
Разложив вектор R по указанному базису, и подставив это разложение в (4.1.3), получим следующие выражения для коэффициентов разложения (4.1.2):
(4.1.4)
Здесь - коэффициенты разложения вектора R по базису. Условием нарушения оптимальности решения является факт обращения в ноль одного из неотрицательных коэффициентов (4.1.4). Отсюда следует, что интервал, на котором исходное решение является оптимальным, является отрезком следующего вида:
(4.1.5)
где
(4.1.6)
а
(4.1.7)
Из выражений (4.1.4) вытекает также тот факт, что на интервалах (4.1.5) вектор-функция x*(?) представляет собой отрезок прямой в пространстве En , и является линейной. Стало быть, значения целевой функции на интервале представляют собой параболу.
4.3 Применение метода субоптимизации на многообразиях к решению параметрической задачи квадратичного программирования.
Непосредственно из вышеизложенного следует алгоритм решения задачи квадратичного программирования с параметром в правых частях ограничений:
1. В начальной точке интервала допустимых значений параметра строится решение задачи квадратичного программирования с помощью метода субоптимизации, описанного выше.
2. С помощью формул (4.1.6-4.1.7) определяется интервал на котором полученное решение остается оптимальным.
3. В правой точке полученного интервала строится решение задачи квадратичного программирования методом субоптимизации на многообразиях. Поскольку в этой точке существуют два оптимальных базиса, с целью предотвращения зацикливания в качестве начального базиса для решения задачи предлагается использовать предыдущий оптимальный базис (если решение потеряло оптимальность) или предыдущий оптимальный базис с исключенными векторами, чьи базисные переменные обратились в ноль.
5.Экономическая часть
Рассмотрим применение описанной теории к задаче определения оптимального портфеля ценных бумаг. Сформулируем задачу:
Имеется n видов ценных бумаг, имеющих доходности выражающиеся случайными величинами , распределенными по нормальному закону с параметрами . Помимо этого, имеется один вид ценных бумаг, дающий гарантированную доходность . Некий финансист ищет такой способ вложения единицы капитала в эти ценные бумаги, который обеспечил бы максимальный уровень дохода с заданной вероятностью ?.
Покажем, что указанную задачу можно свести к задаче математического программирования:
Предположим, что вектор задает вложения финансиста в ценные бумаги соответствующего типа, а величина вложения в ценные бумаги с гарантированной доходностью. Тогда доход финансиста представляет собой случайную величину:
Очевидно, что характеристики этой случайной величины зависят от решения финансиста, и что эта величина распределена по нормальному закону:
Чтобы перейти от задачи максимизации к задаче минимизации, запишем необходимую нам функцию распределения следующим образом:
Запишем функцию квантили уровня ? для этой функции распределения:
При заданном уровне ? нам требуется минимизировать эту функцию, тем самым, максимизируя искомый доход R .
Для этого заметим, что случайная величина (-R) распределена также по нормальному закону с параметрами . Тогда можно записать функцию распределения этой величины, используя функцию Лапласа:
Следовательно, можно заключить, что:
Обозначим квантиль уровня ? , т.е. решение уравнения
Учитывая монотонность функции Лапласа, неравенство можно записать в следующем виде:
Отсюда можно легко получить выражение, дающее ключ к виду функции квантили:
Учитывая определение функции квантили:
получаем
Характеристики распределения случайной величины R выглядят следующим образом:
Таким образом, исходная задача сводится к следующей задаче математического программирования:
Покажем, как указанная задача математического программирования может быть сведена к задаче квадратичного программирования с параметром в правых частях ограничений:
Введем в рассмотрение параметр
Тогда задачу можно записать в следующем эквивалентном виде:
При каждом фиксированном значении параметра данная задача может быть сформулирована следующим образом:
Это задача квадратичного программирования с параметром в правой части ограничений. Решая эту задачу для каждого значения параметра получаем значения функции , а, следовательно, и значения искомой минимизируемой функции
Таким образом исходная задача сводится к последовательному решению двух задач - задачи квадратичного программирования с параметром в правой части ограничений и задаче одномерной оптимизации.
6.Библиография
1. Бахшиян Б.Ц., Назиров Р.Р, Эльясберг П.Е. Определение и коррекция движения (гарантирующий подход) - М.: Наука, 1980.
2. Зангвилл У.И. Нелинейное программирование. Единый подход. - М.: Советское Радио, 1973.
3. Муртаф Б. Современное линейное программирование. - М.:Мир, 1984.
4. Пропой А.И., Ядыкин А.Б. Параметрическое квадратичное и линейное программирование. - Автоматика и телемеханика, 1978, т.12, NN 2,4.
5. Хедли Дж. Нелинейное и динамическое программирование. - М.: Мир, 1967.
6. Ядыкин А.Б. Параметрический метод в задачах квадратичного программирования с вырожденной квадратичной формой. - Журнал вычислительной математики и математической физики, 1975, т.8, N4.
7. Boot J. Quadratic Programming. - Amsterdam: North-Holland Publ. Co., 1964.
8. Van de Pann C. Methods for Linear and Quadratic Programming. - Amsterdam: North-Holland Publ. Co., 1975.
Скачали данный реферат: Evstigneev, Кутепов, Панин, Остап, Ibragimov, Ягунов, Dubolazov.
Последние просмотренные рефераты на тему: культурология, база рефератов, егэ ответы, курсовая работа на тему право.
1
1. ВВЕДЕНИЕ
2.АНАЛИТИЧЕСКИЙ ОБЗОР
3. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
3. ЗАДАЧА КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ (НЕПАРАМЕТРИЧЕСКИЙ СЛУЧАЙ).
3.1 Постановка задачи:
3.2 Условия оптимальности в задаче (3.2)
3.3. Базис задачи квадратичного программирования. Оптимальный и невырожденный базисы.
3.4. Метод субоптимизации на многообразиях. Выпуклый случай.
3.5 Метод субоптимизации на многообразиях. Задача квадратичного программирования.
3.6. Метод субоптимизации на многообразиях в задаче квадратичного программирования. Теоретическое обоснование.
3.7. Вычислительная схема алгоритма субоптимизации для задачи квадратичного программирования.
3.8. Некоторые особенности вычислительной схемы метода субоптимизации на многообразиях для задачи квадратичного программирования.
4. ЗАДАЧА КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ С ПАРАМЕТРОМ В ПРАВЫХ ЧАСТЯХ ОГРАНИЧЕНИЙ.
4.1 ПОСТАНОВКА ЗАДАЧИ
4.2 Некоторые свойства решения параметрической задачи квадратичного программирования.
4.3 Применение метода субоптимизации на многообразиях к решению параметрической задачи квадратичного программирования.
5.ЭКОНОМИЧЕСКАЯ ЧАСТЬ
6.БИБЛИОГРАФИЯ
7.ПРИЛОЖЕНИЕ 1..................................................................................................................65
8.ПРИЛОЖЕНИЕ 2..................................................................................................................67
9.РИСУНОК 1...........................................................................................................................78
1. Введение
В настоящей работе рассматривается применение метода субоптимизации на многообразиях к решению задачи квадратичного программирования с параметром в правых частях ограничений.
Метод субоптимизации на многообразиях, предложенный У.Зангвиллом в 1968 году для решения задач выпуклого программирования представляет собой простую процедуру поиска оптимальной точки в задаче выпуклого программирования с ограничениями типа равенств. Метод использует подход, названный автором "выделением активных ограничений", сводящий исходную задачу выпуклого программирования к определенным образом строящейся последовательности вспомогательных задач выпуклого программирования.
В тех случаях, когда решение вспомогательных задач оказывается существенно проще решения исходной, или вообще очевидным, метод субоптимизации на многообразиях позволяет существенно снизить вычислительную трудоемкость процедуры решения исходной задачи, а также исследовать свойства решения общей задачи на основании общих свойств вспомогательных задач.
В работе показано, что, в случае задачи квадратичного программирования, решение вспомогательных задач сводится к разложению определенным образом выбираемого вектора по некоторому базису, что в свою очередь эквивалентно решению системы линейных уравнений. Таким образом решение исходной задачи оказывается эквивалентным решению конечного числа систем линейных уравнений.
Показано также, что в случае задачи выпуклого программирования решение общей задачи сводится к последовательному решению вспомогательных задач, при переходе между которыми в базисном множестве происходит замена только одного вектора.
В силу этого становится возможным создание рекуррентных формул, связывающих матрицы системы линейных уравнений соседних вспомогательных задач.
Таким образом вместо решения системы линейных уравнений на каждом шаге метода можно вычислять новое решение с помощью соответствующих рекуррентных соотношений, прибегая к непосредственному решению системы линейных уравнений только с целью коррекции накопившейся ошибки вычисления после значительного количества итераций.
В результате вычислительная трудоемкость процедуры оказывается в лучшем случае эквивалентной решению системы линейных уравнений с последующим конечным числом матричных преобразований типа умножения матрицы на вектор. В худшем случае задача оказывается эквивалентной решению конечного числа систем линейных уравнений.
Доказаны теоремы, составляющие теоретический фундамент алгоритма, приведено доказательство сходимости предложенной вычислительной процедуры.
Рассматривается применение указанного метода к решению параметрической задачи квадратичного программирования с параметром в правых частях ограничений, путем сведения указанной задачи к конечному числу задач квадратичного программирования без параметра.
В силу того, что решение параметрической задачи квадратичного программирования с параметром в правых частях ограничений оказывается кусочно-линейной функцией, исходная задача сводится к покрытию области допустимых значений параметра отрезками, на которых функция решения линейна по параметру с постоянными коэффициентами, зависящими только от значения функции в левой точке отрезка.
Показано, что такое разбиение состоит из конечного числа отрезков, и конечного числа точек переключения траектории решения.
Построение такого покрытия в худшем случае эквивалентно решению конечного числа задач квадратичного программирования без параметра в точках переключения траектории. Показаны подходы к построению процедуры перестройки решения в точках переключения траектории без необходимости полного решения задачи квадратичного программирования путем сведения ее к одной или нескольким итерациям метода субоптимизации на многообразиях.
Поставлена задача поиска оптимального вложения в задаче о портфеле ценных бумаг, являющаяся экономической интерпретацией параметрической задачи квадратичного программирования.
Составлена и отлажена программа на языке С++, функционирующая в среде операционных систем UNIX (AIX, Solaris) а также Microsoft Windows, реализующая описанные алгоритмы. Указанная программа применена к решению задачи о поиске оптимальных инвестиций в задаче о портфеле ценных бумаг, данные решения и текст программы приведен в приложениях.
Указаны возможные пути упрощения процедуры поиска решения задачи квадратичного программирования с параметром в правых частях ограничений путем отказа от решения задачи квадратичного программирования в точках переключения траектории.
2.Аналитический обзор
Для решения задач выпуклого программирования с линейными ограничениями могут применяться различные методы решения. Для построения таких методов используется как правило подход, предполагающий задачу квадратичного программирования в известном смысле расширением задачи линейного программирования.
Результатом применения такого подхода является группа методов основанных на простроении аппроксимации исходной квадратичной задачи последовательностью задач линейного программирования, а также различные обобщения линейного симплекс-метода на случай выпуклой функции-критерия.
Рассматриваемый в данной работе метод субоптимизации на многообразиях представляет собой результат совсем иного подхода к решению задачи квадратичного программирования. Процедура метода субоптимизации строится для более общего класса задач выпуклого программирования, причем указывается класс задач, для которых этот метод оказывается достаточно эффективным.
При этом задача квадратичного программирования оказывается частным случаем задачи выпуклого программирования, для которой метод субоптимизации позволяет свести решение исходной задачи к решению конечного числа систем линейных уравнений.
3. Теоретическая часть
3. Задача квадратичного программирования (непараметрический случай).
3.1 Постановка задачи:
Задачей квадратичного программирования будем называть задачу следующего вида:
(3.1.1)
здесь x-вектор столбец размера n, C- вектор-строка размера 1?n, D - матрица размера n?n, симметричная и неотрицательно определенная (D ? 0). b - столбец длины m. A - матрица размера m?n, ранг ее равен m (R(A) = m).
Имеет место также условие неотрицательности компонентов вектора x:
x ? 0.
Поскольку наличие компонента Cx не оказывает существенного влияния на результаты, изложенные в настоящей работе, будем без ограничения общности предполагать вектор C нулевым. В такой постановке задача принимает вид:
(3.1.2)
В данной постановке задача квадратичного программирования всегда имеет оптимальный вектор, и является задачей выпуклого программирования с линейными ограничениями типа равенств.
3.2 Условия оптимальности в задаче (3.2)
Условия оптимальности в задаче (3.2) представляют собой формулировку условий Куна-Таккера для этой задачи. Будем рассматривать следующую форму записи условий Куна-Таккера для задачи выпуклого программирования:
(3.2.1)
В нашем случае получим:
(3.2.2)
Здесь Ai- столбцы матрицы A длины m, Di столбцы матрицы D длины n, Lk - строки матрицы A длины n, ej - n-мерные столбцы единичной матрицы. Здесь и далее xi - компоненты оптимального вектора задачи x, ?k и ?k - множители Лагранжа условий Куна-Таккера. Запишем систему 3.2.2 в более обобщенной форме:
(3.2.3)
где составные столбцы P0, ... Pm+2n каждый длиной m+n являются столбцами блочной матрицы P, имеющей следующий вид:
(3.2.4)
В таком виде условия Куна-Таккера (3.2.3) можно записать в еще более простом виде:
(3.2.5)
Поскольку рассматриваемая нами задача является задачей выпуклого программирования, указанные условия существования минимума являются одновременно необходимыми и достаточными. Доказательство указанных условий можно найти в [1,2].
3.3. Базис задачи квадратичного программирования. Оптимальный и невырожденный базисы.
Поскольку ранг матрицы A равен m (см 3.1), система векторов
являются линейно независимой системой векторов. В то же время, легко видно, что линейная оболочка, натянутая на систему векторов P совпадает с пространством Em+n, т.е L(P)=En+m.
Следовательно из системы векторов 3.2.4 можно образовать конечное число базисов N евклидова пространства En+m, содержащих в себе векторы P1, .. Pm. Такие базисы пространства En+m будем называть базисами задачи квадратичного программирования, и обозначать следующим образом:
(3.3.1)
Для упрощения схемы алгоритма, запишем базис (3.3.1) в следующем виде:
(3.3.2)
Здесь ?1 и ?2 - наборы индексов. В случае, если ?1=?2 будем считать базис U?1,?2 порожденным одним множеством индексов ?=?1.
(3.3.3)
Коэффициенты разложения вектора b по базису U?1,?2 будем называть базисными переменными, остальные коэффициенты - небазисными переменными.
Базис U?1,?2 назовем оптимальным, если его базисные переменные удовлетворяют условиям Куна-Таккера (3.2.3).
Базис называется невырожденным, если все его базисные переменные, соответствующие компонентам вектора x отличны от нуля, т.е.
(3.3.4)
Задачу (3.1.2) будем называть невырожденной, если все ее базисы невырождены. В противном случае назовем задачу вырожденной.
3.4. Метод субоптимизации на многообразиях. Выпуклый случай.
Для решения задачи (3.1.2) предлагается использовать метод
субоптимизации на многообразиях. Вначале рассмотрим основные идеи, приводящие к методу субоптимизации в случае задачи выпуклого программирования общего вида.
Рассмотрим задачу выпуклого программирования с линейными ограничениями, состоящую в минимизации выпуклой функции f(x) на множестве L, задаваемом ограничениями типа равенств.
(3.4.1)
Предположим, что задача имеет единственное решение, т.е минимум целевой функции достигается в единственной оптимальной точке x*. В этом случае задаче (3.4.1) эквивалентна задача:
(3.4.2)
Эквивалентность этих двух задач является следствием единственности решения. Переход к задаче (3.4.2) называется выделением активных ограничений, т.е. вместо условия неотрицательности всех переменных, мы переходим к условию равенства нулю всех компонент, решения, индексы которых не принадлежат множеству ?(x*).
Предположим, что для задачи (3.4.2) нахождение оптимального решения существенно проще, чем для исходной задачи (3.4.1). В этом случае, перебирая каким-либо образом всевозможные множества индексов ?k, являющиеся подмножествами полного набора индексов {1,..n}, и решая для каждого из них задачу (3.4.2), используя ?k вместо ?*, определить искомое множество индексов ?*.
Предположим также, что задача (3.4.2) обладает свойством
единственности, т.е система векторов {L1, .. Lm, ej (j? ?(x*)}- линейно независима. В случае нарушения свойства единственности задача поиска оптимального вектора задачи (3.4.2) усложняется, и в дальнейшем этот случай рассматриваться не будет.
Алгоритм перебора множеств индексов ?k основан на следующей лемме.
Основная лемма:
Пусть x* является оптимальной точкой задачи:
(3.4.3)
где X? - линейное многообразие, определяемое следующим образом:
(3.4.4)
Предположим, что задача (3.4.3) с условием (3.4.4) обладает свойством единственности, и среди ?j, удовлетворяющих условиям Куна-Таккера существует отрицательное ?j0, т.е.
(3.4.5)
Пусть ? ' - множество индексов, полученное из ? вычитанием индекса j0:
(3.4.6)
Тогда, если x*' - оптимальный вектор задачи
(3.4.7)
то справедливо неравенство:
f(x*')
(3.4.8)
Доказательство.
Так как в силу выполнения соотношения (3.4.6) и определения множеств X? и X?' вытекает, что X?' ? X? то имеет место неравенство f(x*') ? f(x*). Следовательно для доказательства соотношения (3.4.8) достаточно показать, что f(x*') ? f(x*).
Предположим, что это не так. Тогда точка x* является оптимальной для задач (3.4.3) и (3.4.7), и удовлетворяет условиям Куна-Таккера в обоих задачах:
(3.4.9)
(3.4.10)
Добавим в правую часть равенства (3.4.10) член 0ej0. Поскольку, по предположению (3.4.5) леммы коэффициент ?j0 отличен от нуля, получаем разложение вектора градиента функции f по системе векторов {L1, .. Lm, ej (j? ?(x*)}. Получаем противоречие с условием единственности, а стало быть, и с условием основной леммы.
Доказанная лемма указывает направление перебора множеств индексов ?k (а стало быть и многообразий), уменьшающее значение целевой функции f(x).
Из доказанной леммы вытекает
Алгоритм поиска оптимального вектора
Общий вид алгоритма метода субоптимизации для задачи выпуклого программирования приведен на рис. 1. Ниже приводятся описания блоков алгоритма, изображенных на этом рисунке.
Блок 1. Определяется допустимая начальная точка x1 для исходной задачи. Это может быть точка, получаемая с помощью алгоритма построения начального базиса линейного симплекс-метода, или же решение в некотором смысле близкой линейной задачи. Предполагается ?1=?(x1), k=1.
Блок 2. Находится оптимальный вектор x*k для задачи
Если x*k оказывается допустимой для исходной задачи (3.4.1), совершается переход к блоку 3, в противном случае осуществляется переход к блоку 4.
Блок 3. Вычисляется значение
Если
то в силу выполнения условий Куна-Таккера для исходной задачи (3.4.1) точка x*k является оптимальной точкой задачи (3.4.1) и работа алгоритма заканчивается.
Если
то предполагаем
и происходит переход к блоку 2.
Блок 4. Поскольку оптимальная точка вспомогательной задачи оказалась недопустимой для исходной, выбираем в качестве новой начальной точки ближайшую к ней точку, допустимую для исходной задачи (3.4.1), и лежащую на прямой, соединяющей оптимальные точки вспомогательной задачи, т.е.
Далее полагаем ?k+1=?(xk+1), заменяем k на k+1, и переходим к блоку 2.
Таким образом построен итерационный процесс, позволяющий осуществить направленный перебор множеств индексов ? k, позволяющий найти оптимальный вектор исходной задачи. Сходимость процедуры будет рассмотрена позже.
3.5 Метод субоптимизации на многообразиях. Задача квадратичного программирования.
Рассмотрим применение метода субоптимизации, рассмотренного в (3.4) к задаче квадратичного программирования (3.1.2). Как было ранее отмечено, условием успешного применения метода субоптимизации на многообразиях в задаче выпуклого программирования является существенная простота решения задачи (3.4.2) по сравнению с исходной задачей (3.4.1).
Рассмотрим эквивалентную (3.1.2) задачу:
(3.5.1)
Запишем условия Куна-Таккера для задачи (3.5.1) с произвольным набором индексов ? :
(3.5.2)
Используя ранее введенные обозначения (3.2.3-3.2.4), систему условий Куна-Таккера (3.5.2) можно записать следующим образом:
(3.5.3)
Если множество U? порождает базис, вследствие (3.5.3) поиск минимума на многообразии X? представляет собой разложение вектора P0 по этому базису, т.е. эквивалентен решению системы линейных уравнений. Таким образом, метод субоптимизации на многообразиях в случае задачи квадратичного программирования оказывается эффективным в том случае, если в цепочке итерационного процесса встречаются только множества индексов, порождающие базисы.
Процедура метода строится на двух основных операциях, аналогичных блокам общего алгоритма субоптимизации на многообразиях для задачи выпуклого программирования.
Операция А. Пусть для некоторого набора индексов ?0 определена оптимальная точка x* и множители Лагранжа ?*k и ?*j удовлетворяющие условиям Куна-Таккера совместно с оптимальным вектором x. Рассмотрим вспомогательное многообразие
(3.5.4)
Операция А состоит в нахождении оптимального вектора x*(?), а также множителей Лагранжа, удовлетворяющих условиям Куна-Таккера задачи минимизации квадратичного функционала на многообразии (3.5.4).
Запишем условия Куна-Таккера для этой вспомогательной задачи:
Если набор индексов ?0 порождает базис, то существует разложение вектора Pm+j0 по этому базису, имеющее следующий вид:
(3.5.6)
Подставляя это разложение в (3.5.5), и учитывая оптимальность набора x*,?*,?*, получаем следующие выражения для компонент оптимальной точки на многообразии (3.5.4):
(3.5.7)
Таким образом, в случае, если набор индексов ?0 порождает базис, операция А осуществляется тривиально, и определяется выражениями (3.5.7).
Суть операции А состоит в нахождении оптимальной точки на новом многообразии (3.5.4) по известной оптимальной точке на многообразии (3.4.4).
Операция Б. Пусть некоторое вспомогательное многообразие X?0(?1) таково, что одна из базисных компонент вектора x обратилась в ноль:
(3.5.8)
Суть операции Б состоит в переходе от многообразия X?0(?1) к другому многообразию X?1 , соответствующему набору индексов ?1 , определяемому следующим образом:
(3.5.9)
т.е. индекс j0 из (3.5.4) заменяется на индекс r из (3.5.8).
Учитывая (3.5.8), разложение (3.5.5) на многообразии X?0 можно представить следующим образом:
(3.5.10)
Аналогично случаю, рассмотренному в операции А, что, если имеет место разложение:
(3.5.11)
причем выполнено соотношение
(3.5.12)
то условиям Куна-Таккера для задачи (3.5.1) соответствующей набору индексов ?1 , удовлетворяют переменные, получаемые с помощью следующих формул:
(3.5.13)
где
(3.5.14)
Учитывая вышеописанные условия, операция Б оказывается осуществимой в том случае, когда наборам индексов ?0 и ?1 соответствует базис U?1,?0 . Операция Б является аналогом блока 4 общей схемы метода субоптимизации на многообразиях для задачи выпуклого программирования.
Для большей наглядности можно определить множество L?1,?0 представляющее собой прямую, порождаемую базисом U?1,?0 следующего вида:
(3.5.15)
Здесь - коэффициенты разложения вектора P0, а xir - вектора Pm+n+r по базису U?1,?0. Заметим, что L?1,?0(0) есть оптимальный вектор многообразия (3.5.4) при ?= . Переход от этой точки к новому многообразию с помощью операции Б представляет собой движение по указанной прямой от дельта равного нулю в положительную (как будет показано позже) сторону.
3.6. Метод субоптимизации на многообразиях в задаче квадратичного программирования. Теоретическое обоснование.
Заметим, что если множество индексов ? порождает базис U? , то задача (3.5.1), соответствующая этому множеству индексов имеет единственный оптимальный вектор x* , обладая при этом свойством единственности, введенным ранее для задачи выпуклого программирования.
Выше были описаны вспомогательные задачи метода субоптимизации на многообразиях, однако не были сформулированы правила применения этих операций. Ниже будут доказаны две теоремы, дающие способ определения неизвестных шагов ? и ?. Для их доказательства потребуется несколько вспомогательных утверждений.
Лемма 1. Пусть вектора x0, x1 удовлетворяют системе уравнений условий Куна-Таккера и пусть f(x) - неотрицательно определенный квадратичный функционал вида xTDx, а ?1 вектор ограниценных по знаку множителей Лагранжа, удовлетворяющих условиям Куна-Таккера совместно с вектором x1 . Тогда имеет место следующее неравенство:
(3.6.1)
Доказательство:
Преобразуем левую часть следующим образом:
Здесь можно воспользоваться условием выполнения теоремы Куна-Таккера:
Требуемое неравенство непосредственно вытекает из последнего соотношения.
Следствие. Пусть x0, x0(?) - оптимальные точки задачи (3.5.1) с некоторым множеством индексов ? и вспомогательной задачи поиска минимума на многообразии (3.5.4). Тогда имеет место неравенство:
Доказательство. Так как x0, x0(?) удовлетворяют условиям Куна-Таккера, то выполняется неравенство Леммы 1:
В силу особенностей решений x0, x0(?) правую часть неравенства можно записать в виде
что и доказывает справедливость следствия.
Лемма 2. Пусть x0, x1 - оптимальные точки многообразий X?0 и X?1 соответственно, удовлетворяющие условиям Куна-Таккера совместно с множителями Лагранжа ?0 и ?1. Тогда справедливо соотношение:
Доказательство: Аналогично доказательству Леммы 1, получаем, что:
Складывая эти два равенства, получаем:
Из выполнения условий Куна-Таккера следует, что:
Раскрывая скобки в левой части неравенства получаем искомое неравенство.
Ниже будет доказана теорема, дающая направление движения и условия применения операции А.
Теорема 1. Пусть оптимальная точка x0 - оптимальная точка многообразия X?0 , причем совокупность индексов ?0 порождает базис U?0 . Тогда, если среди множителей Лагранжа, соответствующих x0 , существует отрицательный (предположим, что он имеет индекс j0)
то новый набор индексов
также порождает базис и в единственной оптимальной точке на многообразии выполнено условие
Доказательство. Если для набора индексов существует оптимальный вектор , то в силу утверждения леммы 2 и определения нового набора индексов имеем
с другой стороны, в силу условия единственности,
Итак, если оптимальная точка на новом многообразии существует, то доказываемое неравенство верно. Существование же оптимальной точки вытекает из того факта, что новый набор индексов порождает базис. Это так, если коэффициент ?j0j0 в разложении (3.5.6) не равен нулю.
Предположим, что этот коэффициент равен нулю. В этом случае, в силу следствия из леммы и условия отрицательности ?j0 квадратичный функционал f(x) оказывается отрицательно определенным. Теорема доказана.
Теорема 1 указывает направление движения по многообразиям с помощью операции А. Переход от многообразия X?0 к многообразию осуществляется с помощью движения по многообразиям X?0 (?) при возрастании ? от нуля до некоторой величины
В силу вида нового множества индексов величина ?0 определяется из условия обращения в ноль соответствующего множителя Лагранжа:
Сформулируем и докажем аналогичную теорему для операции Б:
Теорема 2. Пусть ?0 и ?1 наборы индексов, порождающие базис U?1,?0 , такие, что:
причем в разложении
(3.6.2)
коэффициент . Пусть также для множества индексов
существует оптимальный вектор для задачи (3.5.1), причем такой, что он не является допустимым для исходной задачи (3.1.2), т.е.
Тогда, если x1 - оптимальная точка задачи (3.5.1) на многообразии X?1 , то ?1 порождает базис U?1 , а оптимальная точка x1 принадлежит прямой (3.5.15):
(3.6.3)
Доказательство. Разложим вектор P0 по базису U?1 , а вектор Pm+n+r по базису U?1,?0 :
подставляя второе выражение в первое, и учитывая определение прямой (3.5.15) получаем очевидное следствие:
Кроме того, учитывая разложение (3.6.2), получаем, что
(3.6.4)
А согласно лемме 2, имеем:
Отсюда и из условия теоремы следует, что
Отсюда и из (3.6.4) вытекает доказываемое неравенство. Кроме того, из (3.6.4) также следует отличие от нуля коэффициента , что приводит к выводу о линейной независимости системы векторов U?1 . Это доказывает второе утверждение теоремы.
Теорема 2 указывает направление перехода от одного многообразия к другому с помощью операции Б, утверждая положительность величины шага ?1 .
3.7. Вычислительная схема алгоритма субоптимизации для задачи квадратичного программирования.
Ранее (см 3.4) была приведена общая схема алгоритма субоптимизации на многообразиях для случая задачи выпуклого программирования и получена блочная структура алгоритма. Конкретизируем теперь структуру блоков для случая задачи квадратичного программирования.
Блок1.
Определяется начальный набор индексов ?1 , порождающий базис U?1 , для которого оптимальная точка задачи (3.5.1) является одновременно допустимой для исходной задачи (3.1.2). Такая точка в [2] называется дополняющей.
В кочестве начального множества индексов можно взять начальный базис, получаемый в ходе решения первой фазы двухфазного симплекс-метода, или же решение задачи линейного программирования, близкой к решаемой квадратичной:
Блок 3. Блок полностью идентичен приведенному ранее в описании алгоритма субоптимизации на многообразиях для задачи выпуклого программирования.
Блок 2. В данном блоке определяется решение вспомогательной задачи (3.5.1). Способ определения решения зависит от предыдущего блока алгоритма:
Блок 2(А). Эта часть блока вступает в действие после блока 3. Оптимальный вектор задачи (3.5.1) находится с помощью операции А. Если полученный оптимальный вектор допустим для исходной задачи (3.1.2), осуществляется переход в блок 3. В противном случае осуществляется переход в блок 4.
Критерием выбора следующего шага является сравнение двух величин:
Первая величина задает момент обращения в ноль выбранной минимальной величины ?j0 , вторая величина задает момент обращения в ноль первой из базисных компонент вектора x . Если вторая величина оказывается меньше первой, это означает, что новое решение задачи (3.5.1), полученное в результате операции А, не является допустимым для исходной задачи (3.1.2), и необходим переход в блок 4.
Блок 2(Б). Эта часть блока вступает в действие после блока 4. В этом блоке минимум в задаче (3.5.1) находится с помощью операции Б. Если получаемое решение оказывается допустимым для исходной задачи (3.1.2), то осуществляется переход в блок 3. В противном случае осуществляется переход в блок 4.
Критерием выбора следующего шага в этой части блока является сравнение двух величин:
Блок 4. Этот блок полностью соответствует соответствующему блоку в общем алгоритме субоптимизации на многообразиях для задачи выпуклого программирования.
3.8. Некоторые особенности вычислительной схемы метода субоптимизации на многообразиях для задачи квадратичного программирования.
В этой части будет рассмотрен вычислительный аспект процедуры субоптимизации и показаны некоторые ее замечательные свойства.
Выше было показано, что решение каждой вспомогательной задачи метода субоптимизации сводится к поиску разложения некоторого вектора R размерности (m+n) по базису U?1,?2 ; при этом на соседних итерациях базисы отличаются лишь каким-то одним из векторов.
Как было показано выше, существуют четыре возможных альтернативы при переходе от одного базиса к другому, задающие четыре типа операций:
1. От U?1 к U?2 (?2=?1 j0 ) при помощи замены в базисе вектора Pm+n+j0 на Pm+j0 .
2. От U?1 к U?2,?1 (?2=?1 j0 U r) при помощи замены в базисе вектора Pm+r на Pm+j0 .
3. От U?2,?1 (?2=?1 j0 U r) к U?2 при помощи замены в базисе вектора Pm+n+j0 на Pm+n+r .
4. От U?2,?1 (?2=?1 j0 U r) к U?2',?2' (?'2=?2 U r', ?'1=?1 U r' ) при помощи замены в базисе вектора Pm+r на Pm+n+r' .
Процедура разложения вектора R по базису эквивалентна решению системы линейных уравнений вида
где B - базисная часть матрицы P (то есть матрица, составленная из столбцов матрицы P , соответствующих векторам данного базиса). Решение уравнения есть процедура, эквивалентная обращению матрицы B.
Из общего вида матрицы P (3.2.4) можно получить общий вид матрицы B, которая также имеет блочную структуру следующего вида:
Можно показать, что
Видно, что зная матрицу S1-1 можно легко получить значение матрицы B-1 . Используя общий вид переходов, а также их общее свойство, сводящееся к замене одного вектора на другой, можно применить для нахождения S1-1 известную формулу Фробениуса, и получить рекуррентные формулы, связывающие матрицы S1-1 на соседних итерациях. Это позволяет избежать непосредственного обращения матрицы на каждом шаге алгоритма, прибегая к нему через определенный промежуток времени с целью коррекции накопившейся ошибки вычисления.
4. Задача квадратичного программирования с параметром в правых частях ограничений.
4.1 Постановка задачи
Задачей параметрического квадратичного программирования с параметром в правых частях ограничений будем называть следующую задачу выпуклого программирования:
(4.1.1)
Требуется найти вектор-функцию x*(?) , минимизирующую целевую функцию при каждом ? . Интервал изменения параметра может быть и неограниченным.
4.2 Некоторые свойства решения параметрической задачи квадратичного программирования.
Пусть получено решение задачи (4.1.1) при некотором значении параметра, равном ?0 . Это означает, что получен вектор x*(?0) , а также набор индексов ?(?0) , и порожденный им оптимальный базис. Рассмотрим множество таких ? , для которых это решение остается оптимальным и допустимым. Для этого запишем условия Куна-Таккера:
(4.1.2)
Как следует из постановки задачи, правую часть выражения (4.1.2) можно представить в следующем виде:
(4.1.3)
Разложив вектор R по указанному базису, и подставив это разложение в (4.1.3), получим следующие выражения для коэффициентов разложения (4.1.2):
(4.1.4)
Здесь - коэффициенты разложения вектора R по базису. Условием нарушения оптимальности решения является факт обращения в ноль одного из неотрицательных коэффициентов (4.1.4). Отсюда следует, что интервал, на котором исходное решение является оптимальным, является отрезком следующего вида:
(4.1.5)
где
(4.1.6)
а
(4.1.7)
Из выражений (4.1.4) вытекает также тот факт, что на интервалах (4.1.5) вектор-функция x*(?) представляет собой отрезок прямой в пространстве En , и является линейной. Стало быть, значения целевой функции на интервале представляют собой параболу.
4.3 Применение метода субоптимизации на многообразиях к решению параметрической задачи квадратичного программирования.
Непосредственно из вышеизложенного следует алгоритм решения задачи квадратичного программирования с параметром в правых частях ограничений:
1. В начальной точке интервала допустимых значений параметра строится решение задачи квадратичного программирования с помощью метода субоптимизации, описанного выше.
2. С помощью формул (4.1.6-4.1.7) определяется интервал на котором полученное решение остается оптимальным.
3. В правой точке полученного интервала строится решение задачи квадратичного программирования методом субоптимизации на многообразиях. Поскольку в этой точке существуют два оптимальных базиса, с целью предотвращения зацикливания в качестве начального базиса для решения задачи предлагается использовать предыдущий оптимальный базис (если решение потеряло оптимальность) или предыдущий оптимальный базис с исключенными векторами, чьи базисные переменные обратились в ноль.
5.Экономическая часть
Рассмотрим применение описанной теории к задаче определения оптимального портфеля ценных бумаг. Сформулируем задачу:
Имеется n видов ценных бумаг, имеющих доходности выражающиеся случайными величинами , распределенными по нормальному закону с параметрами . Помимо этого, имеется один вид ценных бумаг, дающий гарантированную доходность . Некий финансист ищет такой способ вложения единицы капитала в эти ценные бумаги, который обеспечил бы максимальный уровень дохода с заданной вероятностью ?.
Покажем, что указанную задачу можно свести к задаче математического программирования:
Предположим, что вектор задает вложения финансиста в ценные бумаги соответствующего типа, а величина вложения в ценные бумаги с гарантированной доходностью. Тогда доход финансиста представляет собой случайную величину:
Очевидно, что характеристики этой случайной величины зависят от решения финансиста, и что эта величина распределена по нормальному закону:
Чтобы перейти от задачи максимизации к задаче минимизации, запишем необходимую нам функцию распределения следующим образом:
Запишем функцию квантили уровня ? для этой функции распределения:
При заданном уровне ? нам требуется минимизировать эту функцию, тем самым, максимизируя искомый доход R .
Для этого заметим, что случайная величина (-R) распределена также по нормальному закону с параметрами . Тогда можно записать функцию распределения этой величины, используя функцию Лапласа:
Следовательно, можно заключить, что:
Обозначим квантиль уровня ? , т.е. решение уравнения
Учитывая монотонность функции Лапласа, неравенство можно записать в следующем виде:
Отсюда можно легко получить выражение, дающее ключ к виду функции квантили:
Учитывая определение функции квантили:
получаем
Характеристики распределения случайной величины R выглядят следующим образом:
Таким образом, исходная задача сводится к следующей задаче математического программирования:
Покажем, как указанная задача математического программирования может быть сведена к задаче квадратичного программирования с параметром в правых частях ограничений:
Введем в рассмотрение параметр
Тогда задачу можно записать в следующем эквивалентном виде:
При каждом фиксированном значении параметра данная задача может быть сформулирована следующим образом:
Это задача квадратичного программирования с параметром в правой части ограничений. Решая эту задачу для каждого значения параметра получаем значения функции , а, следовательно, и значения искомой минимизируемой функции
Таким образом исходная задача сводится к последовательному решению двух задач - задачи квадратичного программирования с параметром в правой части ограничений и задаче одномерной оптимизации.
6.Библиография
1. Бахшиян Б.Ц., Назиров Р.Р, Эльясберг П.Е. Определение и коррекция движения (гарантирующий подход) - М.: Наука, 1980.
2. Зангвилл У.И. Нелинейное программирование. Единый подход. - М.: Советское Радио, 1973.
3. Муртаф Б. Современное линейное программирование. - М.:Мир, 1984.
4. Пропой А.И., Ядыкин А.Б. Параметрическое квадратичное и линейное программирование. - Автоматика и телемеханика, 1978, т.12, NN 2,4.
5. Хедли Дж. Нелинейное и динамическое программирование. - М.: Мир, 1967.
6. Ядыкин А.Б. Параметрический метод в задачах квадратичного программирования с вырожденной квадратичной формой. - Журнал вычислительной математики и математической физики, 1975, т.8, N4.
7. Boot J. Quadratic Programming. - Amsterdam: North-Holland Publ. Co., 1964.
8. Van de Pann C. Methods for Linear and Quadratic Programming. - Amsterdam: North-Holland Publ. Co., 1975.
Скачали данный реферат: Evstigneev, Кутепов, Панин, Остап, Ibragimov, Ягунов, Dubolazov.
Последние просмотренные рефераты на тему: культурология, база рефератов, егэ ответы, курсовая работа на тему право.
1