Xreferat.com » Рефераты по информатике и программированию » Формирование инвестиционного портфеля

Формирование инвестиционного портфеля

height="38" />

то предполагаем

Формирование инвестиционного портфеля

и происходит переход к блоку 2.

Блок 4. Поскольку оптимальная точка вспомогательной задачи оказалась недопустимой для исходной, выбираем в качестве новой начальной точки ближайшую к ней точку, допустимую для исходной задачи (3.4.1), и лежащую на прямой, соединяющей оптимальные точки вспомогательной задачи, т.е.

Формирование инвестиционного портфеля

Далее полагаем Á k+1=Á (xk+1), заменяем k на k+1, и переходим к блоку 2.

Таким образом построен итерационный процесс, позволяющий осуществить направленный перебор множеств индексов Á k, позволяющий найти оптимальный вектор исходной задачи. Сходимость процедуры будет рассмотрена позже.

 

3.5 Метод субоптимизации на многообразиях. Задача квадратичного программирования.

Рассмотрим применение метода субоптимизации, рассмотренного в (3.4) к задаче квадратичного программирования (3.1.2). Как было ранее отмечено, условием успешного применения метода субоптимизации на многообразиях в задаче выпуклого программирования является существенная простота решения задачи (3.4.2) по сравнению с исходной задачей (3.4.1).

Рассмотрим эквивалентную (3.1.2) задачу:

Формирование инвестиционного портфеля

 

(3.5.1)

Запишем условия Куна-Таккера для задачи (3.5.1) с произвольным набором индексов Á :

Формирование инвестиционного портфеля

 

(3.5.2)

Используя ранее введенные обозначения (3.2.3-3.2.4), систему условий Куна-Таккера (3.5.2) можно записать следующим образом:

Формирование инвестиционного портфеля

 

(3.5.3)

Если множество UÁ порождает базис, вследствие (3.5.3) поиск минимума на многообразии XÁ представляет собой разложение вектора P0 по этому базису, т.е. эквивалентен решению системы линейных уравнений. Таким образом, метод субоптимизации на многообразиях в случае задачи квадратичного программирования оказывается эффективным в том случае, если в цепочке итерационного процесса встречаются только множества индексов, порождающие базисы.

Процедура метода строится на двух основных операциях, аналогичных блокам общего алгоритма субоптимизации на многообразиях для задачи выпуклого программирования.

Операция А. Пусть для некоторого набора индексов Á 0 определена оптимальная точка x* и множители Лагранжа l *k и D *j удовлетворяющие условиям Куна-Таккера совместно с оптимальным вектором x. Рассмотрим вспомогательное многообразие

Формирование инвестиционного портфеля

(3.5.4)

Операция А состоит в нахождении оптимального вектора x*(q ), а также множителей Лагранжа, удовлетворяющих условиям Куна-Таккера задачи минимизации квадратичного функционала на многообразии (3.5.4).

Запишем условия Куна-Таккера для этой вспомогательной задачи:

Формирование инвестиционного портфеля

Если набор индексов Á 0 порождает базис, то существует разложение вектора Pm+j0 по этому базису, имеющее следующий вид:

Формирование инвестиционного портфеля

(3.5.6)

Подставляя это разложение в (3.5.5), и учитывая оптимальность набора x*,l *,D *, получаем следующие выражения для компонент оптимальной точки на многообразии (3.5.4):

Формирование инвестиционного портфеля

 

(3.5.7)

Таким образом, в случае, если набор индексов Á 0 порождает базис, операция А осуществляется тривиально, и определяется выражениями (3.5.7).

Суть операции А состоит в нахождении оптимальной точки на новом многообразии (3.5.4) по известной оптимальной точке на многообразии (3.4.4).

Операция Б. Пусть некоторое вспомогательное многообразие XÁ 0(q 1) таково, что одна из базисных компонент вектора x обратилась в ноль:

Формирование инвестиционного портфеля

(3.5.8)

Суть операции Б состоит в переходе от многообразия XÁ 0(q 1) к другому многообразию XÁ 1 , соответствующему набору индексов Á 1 , определяемому следующим образом:

Формирование инвестиционного портфеля

(3.5.9)

т.е. индекс j0 из (3.5.4) заменяется на индекс r из (3.5.8).

Учитывая (3.5.8), разложение (3.5.5) на многообразии XÁ 0 можно представить следующим образом:

Формирование инвестиционного портфеля

(3.5.10)

Аналогично случаю, рассмотренному в операции А, что, если имеет место разложение:

Формирование инвестиционного портфеля

(3.5.11)

причем выполнено соотношение

Формирование инвестиционного портфеля

(3.5.12)

то условиям Куна-Таккера для задачи (3.5.1) соответствующей набору индексов Á 1 , удовлетворяют переменные, получаемые с помощью следующих формул:

Формирование инвестиционного портфеля

 

 

(3.5.13)

где

Формирование инвестиционного портфеля

(3.5.14)

Учитывая вышеописанные условия, операция Б оказывается осуществимой в том случае, когда наборам индексов Á 0 и Á 1 соответствует базис UÁ 1,Á 0 . Операция Б является аналогом блока 4 общей схемы метода субоптимизации на многообразиях для задачи выпуклого программирования.

Для большей наглядности можно определить множество LÁ 1,Á 0 представляющее собой прямую, порождаемую базисом UÁ 1,Á 0 следующего вида:

Формирование инвестиционного портфеля

(3.5.15)

Здесь Формирование инвестиционного портфеля - коэффициенты разложения вектора P0, а xir - вектора Pm+n+r по базису UÁ 1,Á 0. Заметим, что LÁ 1,Á 0(0) есть оптимальный вектор многообразия (3.5.4) при q = Формирование инвестиционного портфеля. Переход от этой точки к новому многообразию с помощью операции Б представляет собой движение по указанной прямой от дельта равного нулю в положительную (как будет показано позже) сторону.

 

3.6. Метод субоптимизации на многообразиях в задаче квадратичного программирования. Теоретическое обоснование.

Заметим, что если множество индексов Á порождает базис UÁ , то задача (3.5.1), соответствующая этому множеству индексов имеет единственный оптимальный вектор x* , обладая при этом свойством единственности, введенным ранее для задачи выпуклого программирования.

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

Лемма 1. Пусть вектора x0, x1 удовлетворяют системе уравнений условий Куна-Таккера и пусть f(x) - неотрицательно определенный квадратичный функционал вида xTDx, а D 1 вектор ограниценных по знаку множителей Лагранжа, удовлетворяющих условиям Куна-Таккера совместно с вектором x1 . Тогда имеет место следующее неравенство:

Формирование инвестиционного портфеля

(3.6.1)

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

Преобразуем левую часть следующим образом:

Формирование инвестиционного портфеля

Здесь можно воспользоваться условием выполнения теоремы Куна-Таккера:

Формирование инвестиционного портфеля

Требуемое неравенство непосредственно вытекает из последнего соотношения.

Следствие. Пусть x0, x0(q ) - оптимальные точки задачи (3.5.1) с некоторым множеством индексов Á и вспомогательной задачи поиска минимума на многообразии (3.5.4). Тогда имеет место неравенство:

Формирование инвестиционного портфеля

Доказательство. Так как x0, x0(q ) удовлетворяют условиям Куна-Таккера, то выполняется неравенство Леммы 1:

Формирование инвестиционного портфеля

В силу особенностей решений x0, x0(q ) правую часть неравенства можно записать в виде

Формирование инвестиционного портфеля

что и доказывает справедливость следствия.

Лемма 2. Пусть x0, x1 - оптимальные точки многообразий XÁ 0 и XÁ 1 соответственно, удовлетворяющие условиям Куна-Таккера совместно с множителями Лагранжа D 0 и D 1. Тогда справедливо соотношение:

Формирование инвестиционного портфеля

Доказательство: Аналогично доказательству Леммы 1, получаем, что:

Формирование инвестиционного портфеля

Складывая эти два равенства, получаем:

Формирование инвестиционного портфеля

Из выполнения условий Куна-Таккера следует, что:

Формирование инвестиционного портфеля

Раскрывая скобки в левой части неравенства получаем искомое неравенство.

Ниже будет доказана теорема, дающая направление движения и условия применения операции А.

Теорема 1. Пусть оптимальная точка x0 - оптимальная точка многообразия XÁ 0 , причем совокупность индексов Á 0 порождает базис UÁ 0 . Тогда, если среди множителей Лагранжа, соответствующих x0 , существует отрицательный (предположим, что он имеет индекс j0)

Формирование инвестиционного портфеля

то новый набор индексов

Формирование инвестиционного портфеля

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

Формирование инвестиционного портфеля

Доказательство. Если для набора индексов Формирование инвестиционного портфеля существует оптимальный вектор Формирование инвестиционного портфеля, то в силу утверждения леммы 2 и определения нового набора индексов имеем

Формирование инвестиционного портфеля

с другой стороны, в силу условия единственности,

Формирование инвестиционного портфеля

Итак, если оптимальная точка на новом многообразии существует, то доказываемое неравенство верно. Существование же оптимальной точки вытекает из того факта, что новый набор индексов порождает базис. Это так, если коэффициент D j0j0 в разложении (3.5.6) не равен нулю.

Предположим, что этот коэффициент равен нулю. В этом случае, в силу следствия из леммы и условия отрицательности D j0 квадратичный функционал f(x) оказывается отрицательно определенным. Теорема доказана.

Теорема 1 указывает направление движения по многообразиям с помощью операции А. Переход от многообразия XÁ 0 к многообразию Формирование инвестиционного портфеля осуществляется с помощью движения по многообразиям XÁ 0 (q ) при возрастании q от нуля до некоторой величины

Формирование инвестиционного портфеля

В силу вида нового множества индексов Формирование инвестиционного портфеля величина q 0 определяется из условия обращения в ноль соответствующего множителя Лагранжа:

Формирование инвестиционного портфеля

Сформулируем и докажем аналогичную теорему для операции Б:

Теорема 2. Пусть Á 0 и Á 1 наборы индексов, порождающие базис UÁ 1,Á 0 , такие, что:

Формирование инвестиционного портфеля

причем в разложении

Формирование инвестиционного портфеля

(3.6.2)

коэффициент Формирование инвестиционного портфеля. Пусть также для множества индексов

Формирование инвестиционного портфеля

существует оптимальный вектор Формирование инвестиционного портфелядля задачи (3.5.1), причем такой, что он не является допустимым для исходной задачи (3.1.2), т.е.

Формирование инвестиционного портфеля

Тогда, если x1 - оптимальная точка задачи (3.5.1) на многообразии XÁ 1 , то Á 1 порождает базис UÁ 1 , а оптимальная точка x1 принадлежит прямой (3.5.15):

Формирование инвестиционного портфеля

(3.6.3)

Доказательство. Разложим вектор P0 по базису UÁ 1 , а вектор Pm+n+r по базису UÁ 1,Á 0 :

Формирование инвестиционного портфеля

Формирование инвестиционного портфеля

подставляя второе выражение в первое, и учитывая определение прямой (3.5.15) получаем очевидное следствие:

Формирование инвестиционного портфеля

Кроме того, учитывая разложение (3.6.2), получаем, что

Формирование инвестиционного портфеля

(3.6.4)

 

А согласно лемме 2, имеем:

Формирование инвестиционного портфеля

Отсюда и из условия теоремы следует, что

Формирование инвестиционного портфеля

Отсюда и из (3.6.4) вытекает доказываемое неравенство. Кроме того, из (3.6.4) также следует отличие от нуля коэффициента Формирование инвестиционного портфеля, что приводит к выводу о линейной независимости системы векторов UÁ 1 . Это доказывает второе утверждение теоремы.

Теорема 2 указывает направление перехода от одного многообразия к другому с помощью операции Б, утверждая положительность величины шага d 1 .

 

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

Ранее (см 3.4) была приведена общая схема алгоритма субоптимизации на многообразиях для случая задачи выпуклого программирования и получена блочная структура алгоритма. Конкретизируем теперь структуру блоков для случая задачи квадратичного программирования.

Блок1.

Определяется начальный набор индексов Á 1 , порождающий базис UÁ 1 , для которого оптимальная точка задачи (3.5.1) является одновременно допустимой для исходной задачи (3.1.2). Такая точка в [2] называется дополняющей.

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

Формирование инвестиционного портфеля

Блок 3. Блок полностью идентичен приведенному ранее в описании алгоритма субоптимизации на многообразиях для задачи выпуклого программирования.

Блок 2. В данном блоке определяется решение вспомогательной задачи (3.5.1). Способ определения решения зависит от предыдущего блока алгоритма:

Блок 2(А). Эта часть блока вступает в действие после блока 3. Оптимальный вектор задачи (3.5.1) находится с помощью операции А. Если полученный оптимальный вектор допустим для исходной задачи (3.1.2), осуществляется переход в блок 3. В противном случае осуществляется переход в блок 4.

Критерием выбора следующего шага является сравнение двух величин:

Формирование инвестиционного портфеля

Формирование инвестиционного портфеля

Первая величина задает момент обращения в ноль выбранной минимальной величины D j0 , вторая величина задает момент обращения в ноль первой из базисных компонент вектора x . Если вторая величина оказывается меньше первой, это означает, что новое решение задачи (3.5.1), полученное в результате операции А, не является допустимым для исходной задачи (3.1.2), и необходим переход в блок 4.

Блок 2(Б). Эта часть блока

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: