Задача квадратичного программирования с параметром в правых частях ограничений и ее применение при формировании портфеля ценных бумаг
Блок 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.





