4.3 Применение метода субоптимизации на многообразиях к решению параметрической задачи квадратичного программирования.
К оглавлению1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1617 18
Непосредственно из вышеизложенного следует алгоритм решения задачи квадратичного программирования с параметром в правых частях ограничений:
1. В начальной точке интервала допустимых значений параметра строится решение задачи квадратичного программирования с помощью метода субоптимизации, описанного выше.
2. С помощью формул (4.1.6-4.1.7) определяется интервал на котором полученное решение остается оптимальным.
3. В правой точке полученного интервала строится решение задачи квадратичного программирования методом субоптимизации на многообразиях. Поскольку в этой точке существуют два оптимальных базиса, с целью предотвращения зацикливания в качестве начального базиса для решения задачи предлагается использовать предыдущий оптимальный базис (если решение потеряло оптимальность) или предыдущий оптимальный базис с исключенными векторами, чьи базисные переменные обратились в ноль.
Рассмотрим применение описанной теории к задаче определения оптимального портфеля ценных бумаг. Сформулируем задачу:
Имеется n видов ценных бумаг, имеющих доходности выражающиеся случайными величинами , распределенными по нормальному закону с параметрами . Помимо этого, имеется один вид ценных бумаг, дающий гарантированную доходность . Некий финансист ищет такой способ вложения единицы капитала в эти ценные бумаги, который обеспечил бы максимальный уровень дохода с заданной вероятностью a.
Покажем, что указанную задачу можно свести к задаче математического программирования:
Предположим, что вектор задает вложения финансиста в ценные бумаги соответствующего типа, а величина вложения в ценные бумаги с гарантированной доходностью. Тогда доход финансиста представляет собой случайную величину:
Очевидно, что характеристики этой случайной величины зависят от решения финансиста, и что эта величина распределена по нормальному закону:
Чтобы перейти от задачи максимизации к задаче минимизации, запишем необходимую нам функцию распределения следующим образом:
Запишем функцию квантили уровня a для этой функции распределения:
При заданном уровне a нам требуется минимизировать эту функцию, тем самым, максимизируя искомый доход R .
Для этого заметим, что случайная величина (-R) распределена также по нормальному закону с параметрами . Тогда можно записать функцию распределения этой величины, используя функцию Лапласа:
Следовательно, можно заключить, что:
Обозначим квантиль уровня a , т.е. решение уравнения
Учитывая монотонность функции Лапласа, неравенство можно записать в следующем виде:
Отсюда можно легко получить выражение, дающее ключ к виду функции квантили:
Учитывая определение функции квантили:
получаем
Характеристики распределения случайной величины R выглядят следующим образом:
Таким образом, исходная задача сводится к следующей задаче математического программирования:
Покажем, как указанная задача математического программирования может быть сведена к задаче квадратичного программирования с параметром в правых частях ограничений:
Введем в рассмотрение параметр
Тогда задачу можно записать в следующем эквивалентном виде:
При каждом фиксированном значении параметра данная задача может быть сформулирована следующим образом:
Это задача квадратичного программирования с параметром в правой части ограничений. Решая эту задачу для каждого значения параметра получаем значения функции , а, следовательно, и значения искомой минимизируемой функции
Таким образом исходная задача сводится к последовательному решению двух задач - задачи квадратичного программирования с параметром в правой части ограничений и задаче одномерной оптимизации.
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. В правой точке полученного интервала строится решение задачи квадратичного программирования методом субоптимизации на многообразиях. Поскольку в этой точке существуют два оптимальных базиса, с целью предотвращения зацикливания в качестве начального базиса для решения задачи предлагается использовать предыдущий оптимальный базис (если решение потеряло оптимальность) или предыдущий оптимальный базис с исключенными векторами, чьи базисные переменные обратились в ноль.
Рассмотрим применение описанной теории к задаче определения оптимального портфеля ценных бумаг. Сформулируем задачу:
Имеется n видов ценных бумаг, имеющих доходности выражающиеся случайными величинами , распределенными по нормальному закону с параметрами . Помимо этого, имеется один вид ценных бумаг, дающий гарантированную доходность . Некий финансист ищет такой способ вложения единицы капитала в эти ценные бумаги, который обеспечил бы максимальный уровень дохода с заданной вероятностью a.
Покажем, что указанную задачу можно свести к задаче математического программирования:
Предположим, что вектор задает вложения финансиста в ценные бумаги соответствующего типа, а величина вложения в ценные бумаги с гарантированной доходностью. Тогда доход финансиста представляет собой случайную величину:
Очевидно, что характеристики этой случайной величины зависят от решения финансиста, и что эта величина распределена по нормальному закону:
Чтобы перейти от задачи максимизации к задаче минимизации, запишем необходимую нам функцию распределения следующим образом:
Запишем функцию квантили уровня a для этой функции распределения:
При заданном уровне a нам требуется минимизировать эту функцию, тем самым, максимизируя искомый доход R .
Для этого заметим, что случайная величина (-R) распределена также по нормальному закону с параметрами . Тогда можно записать функцию распределения этой величины, используя функцию Лапласа:
Следовательно, можно заключить, что:
Обозначим квантиль уровня a , т.е. решение уравнения
Учитывая монотонность функции Лапласа, неравенство можно записать в следующем виде:
Отсюда можно легко получить выражение, дающее ключ к виду функции квантили:
Учитывая определение функции квантили:
получаем
Характеристики распределения случайной величины R выглядят следующим образом:
Таким образом, исходная задача сводится к следующей задаче математического программирования:
Покажем, как указанная задача математического программирования может быть сведена к задаче квадратичного программирования с параметром в правых частях ограничений:
Введем в рассмотрение параметр
Тогда задачу можно записать в следующем эквивалентном виде:
При каждом фиксированном значении параметра данная задача может быть сформулирована следующим образом:
Это задача квадратичного программирования с параметром в правой части ограничений. Решая эту задачу для каждого значения параметра получаем значения функции , а, следовательно, и значения искомой минимизируемой функции
Таким образом исходная задача сводится к последовательному решению двух задач - задачи квадратичного программирования с параметром в правой части ограничений и задаче одномерной оптимизации.
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.