Смекни!
smekni.com

Формирование инвестиционного портфеля (стр. 2 из 6)

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) эквивалентна задача:

(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 основан на следующей лемме.

Основная лемма:

Пусть x*является оптимальной точкой задачи:

(3.4.3)

где XÁ - линейное многообразие, определяемое следующим образом:

(3.4.4)

Предположим, что задача (3.4.3) с условием (3.4.4) обладает свойствомединственности, и среди Dj, удовлетворяющих условиям Куна-Таккера существуетотрицательное Dj0, т.е.

(3.4.5)

Пусть Á ' - множество индексов, полученное из Á вычитанием индекса j0:

(3.4.6)

Тогда, если x*' - оптимальный вектор задачи

(3.4.7)

то справедливо неравенство:

f(x*')<f(x*) (3.4.8)

Доказательство.

Так как в силу выполнения соотношения (3.4.6) и определения множеств XÁ и XÁ'вытекает, что XÁ'É XÁ то имеет место неравенство f(x*') £ f(x*). Следовательно длядоказательства соотношения (3.4.8) достаточно показать, что f(x*') ¹ f(x*).

Предположим, что это не так. Тогда точка x* являетсяоптимальной длязадач (3.4.3) и (3.4.7), и удовлетворяет условиям Куна-Таккера в обоих задачах:

(3.4.9)
(3.4.10)

Добавим в правую часть равенства (3.4.10) член 0ej0. Поскольку, по предположению (3.4.5) леммы коэффициент Dj0 отличен от нуля, получаем разложение вектора градиента функции f по системе векторов {L1, .. Lm, ej (jÎÁ(x*)}. Получаем противоречие с условием единственности, а стало быть, и с условием основной леммы.