Пример: Автоматизированное рабочее место
Я ищу:
На главную  |  Добавить в избранное  

Главная/

Ценные бумаги и фондовый рынок /

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

←предыдущая следующая→
1 2 3 4 5 6 7 

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

            Указаны возможные пути упрощения процедуры поиска решения задачи квадратичного программирования с параметром в правых частях ограничений путем отказа от решения задачи квадратичного программирования в точках переключения траектории.

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 - наборы индексов. В случае, если Б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) эквивалентна задача:

←предыдущая следующая→
1 2 3 4 5 6 7 


Copyright © 2005—2007 «Refoman.Ru»