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

| Категория реферата: Рефераты по экономико-математическому моделированию
| Теги реферата: реферат легкая атлетика, баллов
| Добавил(а) на сайт: Smetanin.

В нашем случае получим:

|[pic] | |
| | |
| | |
| | |
| |(3.2.2) |

Здесь Ai- столбцы матрицы A длины m, Di столбцы матрицы D длины n, Lk
- строки матрицы A длины n, ej - n-мерные столбцы единичной матрицы. Здесь и далее xi - компоненты оптимального вектора задачи x, (k и (k - множители
Лагранжа условий Куна-Таккера. Запишем систему 3.2.2 в более обобщенной форме:

|[pic] | |
| | |
| |(3.2.3) |

где составные столбцы P0, ... Pm+2n каждый длиной m+n являются столбцами блочной матрицы P, имеющей следующий вид:

|[pic] | |
| |(3.2.4) |

В таком виде условия Куна-Таккера (3.2.3) можно записать в еще более простом виде:

|[pic] | |
| | |
| |(3.2.5) |

Поскольку рассматриваемая нами задача является задачей выпуклого программирования, указанные условия существования минимума являются одновременно необходимыми и достаточными. Доказательство указанных условий можно найти в [1,2].

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

Поскольку ранг матрицы A равен m (см 3.1), система векторов

[pic]

являются линейно независимой системой векторов. В то же время, легко видно, что линейная оболочка, натянутая на систему векторов P совпадает с пространством Em+n, т.е L(P)=En+m.

Следовательно из системы векторов 3.2.4 можно образовать конечное число базисов N евклидова пространства En+m, содержащих в себе векторы P1,
.. Pm. Такие базисы пространства En+m будем называть базисами задачи квадратичного программирования, и обозначать следующим образом:

|[pic] |(3.3.1) |

Для упрощения схемы алгоритма, запишем базис (3.3.1) в следующем виде:

|[pic] |(3.3.2) |

Здесь (1 и (2 - наборы индексов. В случае, если (1=(2 будем считать базис U(1,(2 порожденным одним множеством индексов (=(1.

|[pic] |(3.3.3) |

Коэффициенты разложения вектора b по базису U(1,(2 будем называть базисными переменными, остальные коэффициенты - небазисными переменными.

Базис U(1,(2 назовем оптимальным, если его базисные переменные удовлетворяют условиям Куна-Таккера (3.2.3).

Базис называется невырожденным, если все его базисные переменные, соответствующие компонентам вектора x отличны от нуля, т.е.

|[pic] | |
| | |
| |(3.3.4) |

Задачу (3.1.2) будем называть невырожденной, если все ее базисы невырождены. В противном случае назовем задачу вырожденной.

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