Xreferat.com » Рефераты по экономико-математическому моделированию » Задача квадратичного программирования с параметром в правых частях ограничений и ее применение при формировании портфеля ценных бумаг

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

В данном блоке определяется решение вспомогательной задачи (3.5.1). Способ определения решения зависит от предыдущего блока алгоритма:


Блок 2(А). Эта часть блока вступает в действие после блока 3. Оптимальный вектор задачи (3.5.1) находится с помощью операции А. Если полученный оптимальный вектор допустим для исходной задачи (3.1.2), осуществляется переход в блок 3. В противном случае осуществляется переход в блок 4.

Критерием выбора следующего шага является сравнение двух величин:



Первая величина задает момент обращения в ноль выбранной минимальной величины Dj0 , вторая величина задает момент обращения в ноль первой из базисных компонент вектора 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*(m) , минимизирующую целевую функцию при каждом m . Интервал изменения параметра может быть и неограниченным.

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

Пусть получено решение задачи (4.1.1) при некотором значении параметра, равном m0 . Это означает, что получен вектор x*(m0) , а также набор индексов Б(m0) , и порожденный им оптимальный базис. Рассмотрим множество таких m , для которых это решение остается оптимальным и допустимым. Для этого запишем условия Куна-Таккера:



(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*(m) представляет собой отрезок прямой в пространстве En , и является линейной. Стало быть, значения целевой функции на интервале представляют собой параболу.


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

Непосредственно из вышеизложенного следует алгоритм решения задачи квадратичного программирования с параметром в правых частях ограничений:

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

2. С помощью формул (4.1.6-4.1.7) определяется интервал на котором полученное решение остается оптимальным.

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


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


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


Имеется n видов ценных бумаг, имеющих доходности выражающиеся случайными величинами , распределенными по нормальному закону с параметрами . Помимо этого, имеется один вид ценных бумаг, дающий гарантированную доходность . Некий финансист ищет такой способ вложения единицы капитала в эти ценные бумаги, который обеспечил бы максимальный уровень дохода с заданной вероятностью a.

Покажем, что указанную задачу можно свести к задаче математического программирования:


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



Очевидно, что характеристики этой случайной величины зависят от решения финансиста, и что эта величина распределена по нормальному закону:



Чтобы перейти от задачи максимизации к задаче минимизации, запишем необходимую нам функцию распределения следующим образом:



Запишем функцию квантили уровня a для этой функции распределения:



При заданном уровне a нам требуется минимизировать эту функцию, тем самым, максимизируя искомый доход R .



Для этого заметим, что случайная величина (-R) распределена также по нормальному закону с параметрами . Тогда можно записать функцию распределения этой величины, используя функцию Лапласа:



Следовательно, можно заключить, что:



Обозначим квантиль уровня a , т.е. решение уравнения



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



Отсюда можно легко получить выражение, дающее ключ к виду функции квантили:



Учитывая определение функции квантили:



получаем



Характеристики распределения случайной величины 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.

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: