Формирование инвестиционного портфеля
Критерием выбора следующего шага в этой части блока является сравнение двух величин:


Блок 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) при некотором значении параметра, равном m 0 . Это означает, что получен вектор x*(m 0) , а также набор индексов Á (m 0) , и порожденный им оптимальный базис. Рассмотрим множество таких 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.





