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

Заказать работу

Реферат


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

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


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


Содержание

1. Введение 3

2.Аналитический обзор 9

3. Теоретическая часть 11

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

3.1 Постановка задачи: 11

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

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

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

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

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

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

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

4. Задача квадратичного программирования с параметром в правых частях ограничений. 52

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

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

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

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

6.Библиография 65


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, lk и 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 - наборы индексов. В случае, если Б12 будем считать базис 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) обладает свойством единственности, и среди Dj, удовлетворяющих условиям Куна-Таккера существует отрицательное Dj0, т.е.


(3.4.5)


Пусть Б ' - множество индексов, полученное из Б вычитанием индекса j0:


(3.4.6)


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


(3.4.7)


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


f(x*')

Другие материалы

  • Формирование инвестиционного портфеля
  • ... Solaris) а также Microsoft Windows, реализующая описанные алгоритмы. Указанная программа применена к решению задачи о поиске оптимальных инвестиций в задаче о портфеле ценных бумаг, данные решения и текст программы приведен в приложениях. Указаны возможные пути упрощения процедуры поиска решения ...

  • Теория эффективных фондовых инвестиций и ее применение (раздел дипломной работы)
  • ... измерителя риска фондового актива показала свою эффективность в большинстве практических задач, а простота и интегральность этого показателя выгодно отличают его от альтернативных измерителей риска. Эти обстоятельства и обусловили преимущественное его применение. 2.2. Модель Г. Марковица   ...

  • Теория портфеля Г.Марковица и модель оценки доходности финансовых активов
  • ... адекватность количественных характеристик активов и портфеля, которые являются исходными данными в теории Г. Марковица. Возможно, поэтому Дж. Тобин получил Нобелевскую премию на 9 лет раньше, чем Г. Марковиц. 2. Модель оценки доходности финансовых активов. С 1964 г. появляются новые работы, ...

  • Оперативное управление портфелем финансовых инвестиций
  • ... с недостаточным развитием рынка производных ценных бумаг.2.2. Стратегия управления инвестиционным портфелем Алгоритм реализации современной портфельной теории позволяющей оптимизировать формируемый пор­тфель финансовых инвестиций состо­ит из следующих этапов: 1. Оценка инвестиционных качеств ...

  • Разработка автоматизированной информационной системы для управления портфелем реальных инвестиций
  • ... трудом с высвобождением персонала. Конкретно будет разрабатываться автоматизированная информационная система для управления портфелем реальных инвестиций предприятия СФ ОАО «ВолгаТелеком». Разработка данной системы приведет к экономии затрат, связанных с проведением анализа и оценки инвестиционных ...

  • Управление портфелем ценных бумаг. Портфельные стратегии
  • ... будут гасить друг друга. 4. Особенности практики управления портфелями ценных бумаг в России Российскому рынку по-прежнему характерны негативные особенности, препятствующие применению принципов портфельного инвестирования, что в определенной степени сдерживает интерес субъектов рынка к этим ...

  • Управление процентным риском портфеля ГКО-ОФЗ в посткризисный период
  • ... параметров в случае резкого перехода к новой рыночной ситуации. Глава 2. Обоснование методов поддержки принятия решений по управлению процентным риском портфеля ГКО–ОФЗ в посткризисный период. §2.1. Иммунизация процентного риска портфеля ГКО–ОФЗ от непараллельных перемещений временной структуры ...

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

  • Формирование инвестиционного портфеля предприятия (на примере ОАО "МХК ЕвроХим")
  • ... » и поиску путей формирования оптимальной структуры портфеля ценных бумаг организации на текущую дату. Рис. 4. Доходность еврооблигаций ОАО «МХК «ЕвроХим» на 02.03.2009 г. 3. Управление инвестиционным портфелем предприятия 3.1 Направления совершенствования структуры ...

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

  • Прикладная математика
  • ... объяснить при защите курсовой работы!) и найдите по ней худшую и лучшую операции. 18.   Произвести математико-статистический анализ за T лет Xt, Kt, Lt (t = 1, …, T) о выпуске продукции (в стоимостном виде), ОПФ и числе занятых исследуемого производственного экономического ...

Каталог учебных материалов

Свежие работы в разделе

Наша кнопка

Разместить ссылку на наш сайт можно воспользовавшись следующим кодом:

Контакты

Если у вас возникли какие либо вопросы, обращайтесь на email администратора: admin@kazreferat.info