Квадратичное программирование

Федеральное агентство по образованию РФ

Государственное образовательное учреждение высшего  профессионального образования

«Владимирский государственный гуманитарный университет» 
 
 
 
 

КУРСОВАЯ  РАБОТА

на тему: 

«Квадратичное программирование» 
 
 
 

Выполнила:

студентка группы ММ-31

очной формы обучения ТЭФ

Коротеева А. А. 

Научный руководитель:

                    доцент кафедры

алгебры и теории чисел

Евсеева Ю. Ю. 
 

Владимир, 2010 г.

О Г Л А В Л  Е Н И Е 
 

 

 

     Введение

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

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

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

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

    Для того, чтобы достичь данной цели необходимо решить следующие задачи:

1. определить задачу квадратичного программирования;
2. проанализировать конечный алгоритм решения задачи квадратичного программирования;
3. применить конечный алгоритм на практике.

    Объектом  исследования является метод квадратичного программирования.

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

    Курсовая  работа состоит из введения, трех глав, заключения и списка литературы.

 

1. Постановка задачи квадратичного программирования

 
 

    Пусть задана квадратичная функция

                                                       (1*)

или в  векторно-матричной форме

                                                                                        (1)

и линейные неравенства

       ,                          (2*)

которые в векторно-матричной форме запишем  так:

,                                                                                                     (2)

и пусть  неравенства  (2) определяют некоторую  область Ω, содержащую внутренние точки.

    Будем предполагать, что матрица  симметричная и положительно определенная, так что - выпуклая функция.

    Задача  квадратичного программирования формулируется так:  отыскать точку , для которой достигается минимум функции (1) при ограничениях (2):

    

                                                                                   (3)

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

    

 при  ,

где - -мерный вектор, - симметричная матрица , - -мерный вектор и - матрица . 

    Из  всех задач нелинейного программирования задача квадратичного программирования является самой легкой для решения и лишь немного сложнее, чем задача линейного программирования. Рассмотрим на примере.

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

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

    Подход  к решению задачи с позиций линейного  программирования:

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

    

 при .

    Формулировка  квадратичного программирования:

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

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

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

    

 при  ,

    Таким образом, мы видим, что задача квадратичного  программирования достаточно проста в  решении и лишь немного сложнее, чем задача линейного программирования.  
 
 
 

 

2. Конечный  алгоритм решения задачи квадратичного программирования

 
 

    Приведем  теперь изложение одного конечного алгоритма для решения задачи (1) – (3) квадратичного программирования.

    1) Составим таблицу из ограничений  (2*)  и частных производных минимизируемой функции (1*):

    

    Найдем  единственную точку  , в которой достигает минимума. Если , то , и задача решена. Если же , то выберем произвольную точку (исходная точка) и вектор , вдоль которого будем двигаться к точке до встречи с границей многогранника в некоторой точке , которую будем считать первым приближением, т.е. будем увеличивать в формуле

    

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

    Пусть для удобства значение достигается при т.е.

    

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

    Действительно, если мы меняем местами  и (разрешающий элемент ), то , следовательно,

а)

,

где - новая строка и - также новая строка;

б)

      .

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

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

    2) Определим единственную точку  , в которой функция достигает относительного минимума при условии . Для этого решаем систему линейных уравнений  

    

    

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

    

 

    Если  , то и . Такую точку будем называть стационарной.

    Если  , то стационарная точка является решением.

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

    Если  же , то стационарная точка может не являться решением.

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

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