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

Министерство  образования и науки Российской Федерации

Государственное образовательное учреждение

высшего профессионального образования

Дальневосточный Федеральный Университет  
 
 
 
 

РЕФЕРАТ

на тему: 

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

Выполнил:

студент группы Г-5216а

Иванов П. С. 
 
 
 
 
 
 
 

Владивосток, 2011 г.

    Введение

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

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

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

 

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

 

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

                                                       (1*)

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

                                                                                        (1)

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

       ,                          (2*)

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

,                                                                                                     (2)

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

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

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

    

                                                                                   (3)

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

    

 при  ,

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

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

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

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

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

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

    

 при .

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

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

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

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

    

 при  ,

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

 

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

 
 

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

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

    

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

    

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

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

    

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

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

а)

,

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

б)

      .

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

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

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

    

    

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

    

 

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

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

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

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

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

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

    3) Определим направление движения  из стационарной точки. Пусть  стационарная точка  принадлежит плоскостям (в соответствии с таблицей (*)) . Тогда, если , то точка - решение задачи.

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

    Для получения направления наискорейшего  спуска решаем следующую задачу линейного  программирования: минимизировать функцию 

    

при ограничениях

                                                  

                                                                                          

    Но  - независимые переменные, поэтому (в соответствии с таблицей (*))

    

    

    ……………………………….

    

 

    Далее, точка  стационарная, т.е.  , поэтому

    

.

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

    

при ограничениях

                                                                                           ,

                                                          

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

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

    

где - значение , минимизирующее функцию .