Курсовая работа: Формирование инвестиционного портфеля
(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) эквивалентна задача:
 |
(3.4.2) |
Эквивалентность этих двух задач является следствием единственности решения. Переход к задаче (3.4.2) называется выделением активных ограничений, т.е. вместо условия неотрицательности всех переменных, мы переходим к условию равенства нулю всех компонент, решения, индексы которых не принадлежат множеству Á (x*).
Предположим, что для задачи (3.4.2) нахождение оптимального решения существенно проще, чем для исходной задачи (3.4.1). В этом случае, перебирая каким-либо образом всевозможные множества индексов Á k , являющиеся подмножествами полного набора индексов {1,..n} , и решая для каждого из них задачу (3.4.2), используя Á k вместо Á * , определить искомое множество индексов Á * .
Предположим также, что задача (3.4.2) обладает свойством
единственности, т.е система векторов { L1 , .. Lm , ej (j Î Á (x*) } - линейно независима. В случае нарушения свойства единственности задача поиска оптимального вектора задачи (3.4.2) усложняется, и в дальнейшем этот случай рассматриваться не будет.
Алгоритм перебора множеств индексов Á k основан на следующей лемме.
Основная лемма :