Реферат: Задача квадратичного программирования с параметром в правых частях ограничений и ее применение при формировании портфеля ценных бумаг

Реферат

Дипломнаяработа содержит 78 страниц, 2 приложения, 1 рисунок.

Списокключевых слов: программирование, квадратичное, параметрическое.

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

Содержание

TOC o «1-3» 1. Введение

… GOTOBUTTON _Toc379719392 PAGEREF _Toc379719392 4

2.

Аналитическийобзор… GOTOBUTTON _Toc379719393 PAGEREF _Toc379719393 9

3.

Теоретическаячасть… GOTOBUTTON _Toc379719394 PAGEREF _Toc379719394 11

3

.Задача квадратичного программирования (непараметрический случай).… GOTOBUTTON _Toc379719395 PAGEREF _Toc379719395 11

3

.1Постановка задачи:… GOTOBUTTON _Toc379719396 PAGEREF _Toc379719396 11

3.2 Условия оптимальности в задаче (

3

.3.Базис задачи квадратичного программирования. Оптимальный и невырожденный базисы. GOTOBUTTON _Toc379719398 PAGEREF _Toc379719398 15

3.4. Метод субоптимизации на многообразиях. Выпуклый случай.

… GOTOBUTTON _Toc379719399 PAGEREF _Toc379719399 18

3.5

Методсубоптимизации на многообразиях. Задача квадратичного программирования. GOTOBUTTON _Toc379719400 PAGEREF _Toc379719400 26

3

.6.Метод субоптимизации на многообразиях в задаче квадратичного программирования. Теоретическое обоснование.… GOTOBUTTON _Toc379719401 PAGEREF _Toc379719401 34

3

.7.Вычислительная схема алгоритма субоптимизации для задачи квадратичногопрограммирования. GOTOBUTTON _Toc379719402 PAGEREF _Toc379719402 44

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

… GOTOBUTTON _Toc379719409 PAGEREF _Toc379719409 47

4

.Задача квадратичного программирования с параметром в правых частях ограничений. GOTOBUTTON _Toc379719411 PAGEREF _Toc379719411 51

4.1 Постановка задачи

… GOTOBUTTON _Toc379719412 PAGEREF _Toc379719412 51

4.2 Некоторые свойства решения параметрической задачиквадратичного программирования.

GOTOBUTTON _Toc379719413 PAGEREF _Toc379719413 51

4.3 Применение метода субоптимизации на многообразиях крешению параметрической задачи квадратичного программирования.

… GOTOBUTTON _Toc379719414 PAGEREF _Toc379719414 54

5.Экономическая часть

… GOTOBUTTON _Toc379719415 PAGEREF _Toc379719415 56

6.

Библиография… GOTOBUTTON _Toc379719416 PAGEREF _Toc379719416 63

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 ³

Поскольку наличие компонента 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, l

kи Dk — множителиЛагранжаусловий Куна-Таккера. Запишем систему 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)обладает свойствомединственности, и среди D

j, удовлетворяющих условиямКуна-Таккера существуетотрицательноеDj0, т.е.

(3.4.5)

Пусть Á

' — множество индексов, полученное из Á вычитаниеминдекса j0:

(3.4.6)

Тогда, если x*' — оптимальный векторзадачи

(3.4.7)

то справедливо неравенство:

f(x*')<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) леммы коэффициент D

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, позволяющий найти оптимальный вектор исходной задачи.Сходимость процедур

еще рефераты

Еще работы по ценным бумагам

Реферат по ценным бумагам

Некоторые вопросы практики вексельного обращения

29 Августа 2013

Реферат по ценным бумагам

Рынок ГКО-ОФЗ в России

29 Августа 2013