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

Главная/

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

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

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

/referats/58/3874/Index.files/image109.gif" >

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

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

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

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

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

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

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

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

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

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

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

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

            Теорема 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 указывает направление перехода от одного многообразия к другому с помощью операции Б, утверждая положительность величины шага d1 .

     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.

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

           

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


Copyright © 2005—2007 «Refoman.Ru»