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

| Категория реферата: Рефераты по экономико-математическому моделированию
| Теги реферата: реферат легкая атлетика, баллов
| Добавил(а) на сайт: Smetanin.

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

Показано, что такое разбиение состоит из конечного числа отрезков, и конечного числа точек переключения траектории решения.

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

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

Составлена и отлажена программа на языке С++, функционирующая в среде операционных систем UNIX (AIX, Solaris) а также Microsoft Windows, реализующая описанные алгоритмы. Указанная программа применена к решению задачи о поиске оптимальных инвестиций в задаче о портфеле ценных бумаг, данные решения и текст программы приведен в приложениях.

Указаны возможные пути упрощения процедуры поиска решения задачи квадратичного программирования с параметром в правых частях ограничений путем отказа от решения задачи квадратичного программирования в точках переключения траектории.

2.Аналитический обзор

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

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

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

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

3. Теоретическая часть

3. Задача квадратичного программирования (непараметрический случай).

3.1 Постановка задачи:

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

|[pic] | |
| |(3.1.1) |

здесь x-вектор столбец размера n, C- вектор-строка размера 1(n, D - матрица размера n(n, симметричная и неотрицательно определенная (D ( 0). b - столбец длины m. A - матрица размера m(n, ранг ее равен m (R(A) = m).

Имеет место также условие неотрицательности компонентов вектора x:

x ( 0.

Поскольку наличие компонента Cx не оказывает существенного влияния на результаты, изложенные в настоящей работе, будем без ограничения общности предполагать вектор C нулевым. В такой постановке задача принимает вид:

|[pic] | |
| |(3.1.2) |

В данной постановке задача квадратичного программирования всегда имеет оптимальный вектор, и является задачей выпуклого программирования с линейными ограничениями типа равенств.

3.2 Условия оптимальности в задаче (3.2)

Условия оптимальности в задаче (3.2) представляют собой формулировку условий Куна-Таккера для этой задачи. Будем рассматривать следующую форму записи условий Куна-Таккера для задачи выпуклого программирования:

|[pic] | |
| | |
| | |
| | |
| |(3.2.1) |