4.3 Применение метода субоптимизации на многообразиях к решению параметрической задачи квадратичного программирования.

К оглавлению1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
17 18 

                Непосредственно из вышеизложенного следует алгоритм решения задачи квадратичного программирования с параметром в правых частях ограничений:

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

                2. С помощью формул (4.1.6-4.1.7) определяется интервал на котором полученное решение остается оптимальным.

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

 

 

5.Экономическая часть

                Рассмотрим применение описанной теории к задаче определения оптимального портфеля ценных бумаг. Сформулируем задачу:

                Имеется n видов ценных бумаг, имеющих доходности выражающиеся случайными величинами , распределенными по нормальному закону с параметрами . Помимо этого, имеется один вид ценных бумаг, дающий гарантированную доходность . Некий финансист ищет такой способ вложения единицы капитала в эти ценные бумаги, который обеспечил бы максимальный уровень дохода с заданной вероятностью a.

                Покажем, что указанную задачу можно свести к задаче математического программирования:

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

                Очевидно, что характеристики этой случайной величины зависят от решения финансиста, и что эта величина распределена по нормальному закону:

                Чтобы перейти от задачи максимизации к задаче минимизации, запишем необходимую нам функцию распределения следующим образом:

                Запишем функцию квантили уровня a для этой функции распределения:

                При заданном уровне a нам требуется минимизировать эту функцию, тем самым, максимизируя искомый доход R .

 

                Для этого заметим, что случайная величина (-R) распределена также по нормальному закону с параметрами . Тогда можно записать функцию распределения этой величины, используя функцию Лапласа:

   

                Следовательно, можно заключить, что:

                Обозначим квантиль уровня a , т.е. решение уравнения

                Учитывая монотонность функции Лапласа, неравенство можно записать в следующем виде:

                Отсюда можно легко получить выражение, дающее ключ к виду функции квантили:

                Учитывая определение функции квантили:

                получаем

                Характеристики распределения случайной величины R выглядят следующим образом:

 

                Таким образом, исходная задача сводится к следующей задаче математического программирования:

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

                Введем в рассмотрение параметр

                Тогда задачу можно записать в следующем эквивалентном виде:

                При каждом фиксированном значении параметра данная задача может быть сформулирована следующим образом:

                Это задача квадратичного программирования с параметром в правой части ограничений. Решая эту задачу для каждого значения параметра получаем значения функции , а, следовательно, и значения искомой минимизируемой функции

                Таким образом исходная задача сводится к последовательному решению двух задач - задачи квадратичного программирования с параметром в правой части ограничений и задаче одномерной оптимизации.

 

6.Библиография

1. Бахшиян Б.Ц., Назиров Р.Р, Эльясберг П.Е. Определение и коррекция движения (гарантирующий подход) - М.: Наука, 1980.

2. Зангвилл У.И. Нелинейное программирование. Единый подход. - М.: Советское Радио, 1973.

3. Муртаф Б. Современное линейное программирование. - М.:Мир, 1984.

4. Пропой А.И., Ядыкин А.Б. Параметрическое квадратичное и линейное программирование. - Автоматика и телемеханика, 1978, т.12, NN 2,4.

5. Хедли Дж. Нелинейное и динамическое программирование. - М.: Мир, 1967.

6. Ядыкин А.Б. Параметрический метод в задачах квадратичного программирования с вырожденной квадратичной формой. - Журнал вычислительной математики и математической физики, 1975, т.8, N4.

7. Boot J. Quadratic Programming. - Amsterdam: North-Holland Publ. Co., 1964.

8. Van de Pann C. Methods for Linear and Quadratic Programming. - Amsterdam: North-Holland Publ. Co., 1975.

                Непосредственно из вышеизложенного следует алгоритм решения задачи квадратичного программирования с параметром в правых частях ограничений:

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

                2. С помощью формул (4.1.6-4.1.7) определяется интервал на котором полученное решение остается оптимальным.

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

 

 

5.Экономическая часть

                Рассмотрим применение описанной теории к задаче определения оптимального портфеля ценных бумаг. Сформулируем задачу:

                Имеется n видов ценных бумаг, имеющих доходности выражающиеся случайными величинами , распределенными по нормальному закону с параметрами . Помимо этого, имеется один вид ценных бумаг, дающий гарантированную доходность . Некий финансист ищет такой способ вложения единицы капитала в эти ценные бумаги, который обеспечил бы максимальный уровень дохода с заданной вероятностью a.

                Покажем, что указанную задачу можно свести к задаче математического программирования:

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

                Очевидно, что характеристики этой случайной величины зависят от решения финансиста, и что эта величина распределена по нормальному закону:

                Чтобы перейти от задачи максимизации к задаче минимизации, запишем необходимую нам функцию распределения следующим образом:

                Запишем функцию квантили уровня a для этой функции распределения:

                При заданном уровне a нам требуется минимизировать эту функцию, тем самым, максимизируя искомый доход R .

 

                Для этого заметим, что случайная величина (-R) распределена также по нормальному закону с параметрами . Тогда можно записать функцию распределения этой величины, используя функцию Лапласа:

   

                Следовательно, можно заключить, что:

                Обозначим квантиль уровня a , т.е. решение уравнения

                Учитывая монотонность функции Лапласа, неравенство можно записать в следующем виде:

                Отсюда можно легко получить выражение, дающее ключ к виду функции квантили:

                Учитывая определение функции квантили:

                получаем

                Характеристики распределения случайной величины R выглядят следующим образом:

 

                Таким образом, исходная задача сводится к следующей задаче математического программирования:

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

                Введем в рассмотрение параметр

                Тогда задачу можно записать в следующем эквивалентном виде:

                При каждом фиксированном значении параметра данная задача может быть сформулирована следующим образом:

                Это задача квадратичного программирования с параметром в правой части ограничений. Решая эту задачу для каждого значения параметра получаем значения функции , а, следовательно, и значения искомой минимизируемой функции

                Таким образом исходная задача сводится к последовательному решению двух задач - задачи квадратичного программирования с параметром в правой части ограничений и задаче одномерной оптимизации.

 

6.Библиография

1. Бахшиян Б.Ц., Назиров Р.Р, Эльясберг П.Е. Определение и коррекция движения (гарантирующий подход) - М.: Наука, 1980.

2. Зангвилл У.И. Нелинейное программирование. Единый подход. - М.: Советское Радио, 1973.

3. Муртаф Б. Современное линейное программирование. - М.:Мир, 1984.

4. Пропой А.И., Ядыкин А.Б. Параметрическое квадратичное и линейное программирование. - Автоматика и телемеханика, 1978, т.12, NN 2,4.

5. Хедли Дж. Нелинейное и динамическое программирование. - М.: Мир, 1967.

6. Ядыкин А.Б. Параметрический метод в задачах квадратичного программирования с вырожденной квадратичной формой. - Журнал вычислительной математики и математической физики, 1975, т.8, N4.

7. Boot J. Quadratic Programming. - Amsterdam: North-Holland Publ. Co., 1964.

8. Van de Pann C. Methods for Linear and Quadratic Programming. - Amsterdam: North-Holland Publ. Co., 1975.