Ирина Эланс

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

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

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

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

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

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

РЕФЕРАТ

на тему:

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

Выполнил:

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

Иванов П. С.

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

Введение

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

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

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

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

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

(1*)

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

(1)

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

, (2*)

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

, (2)

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

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

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

(3)

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

при ,

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

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

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

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

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

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

при .

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

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

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

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

при ,

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

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

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

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

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

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

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

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

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

а)

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

б)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Так как алгоритм монотонный, а стационарных точек – конечное число, то после конечного числа шагов получим решение .

Применение алгоритма квадратичного программирования на практике

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

Пример:

Задана функция . Необходимо минимизировать заданную функцию при ограничениях:

Решение:

Предварительный шаг. Составляем таблицу:

Первый шаг.

1) Определение точки минимума. Решив систему линейных уравнений

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

Находим какую-нибудь точку , например . Действительно,

2) Определение .

3)Определение . Двигаемся вдоль луча , т.е. В итоге для шага получим: .

4) Определение новой точки и новых уклонений.

Второй шаг.

1) Определение точки условного минимума функции. Производим шаг жорданова исключения в таблице с разрешающим элементом . Получим таблицу

Решив систему линейных уравнений

найдем условную экстремальную точку функции (при условии ) в новых координатах :

2) Определение .

3) Определение . Двигаемся вдоль луча , т.е. Для шага получим: .

4) Определение новой точки и новых отклонений.

Третий шаг.

Решив уравнение , найдем условную экстремальную точку функции (при условии ) в новых координатах :

так что - стационарная точка.

Получив стационарную точку, опускаем операции 2) и 3).

4) Определение новых уклонений.

Четвертый шаг. Опускаем операцию 1).

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

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

Для получим: .

3) Определение . Двигаемся вдоль луча , т.е. Для шага получим: где минимизирует функцию

4) Определение новой точки и новых уклонений.

причем

Пятый шаг.

1) Определение точки условного минимума функции . Решив систему линейных уравнений

найдем условную экстремальную точку функции (при условии ) в новых координатах :

так что - стационарная точка.

Так как , то и будет являться решением, т.е. функция в точке будет принимать своё минимальное значение.