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

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

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

(1.2).

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

(1.3).

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

(1.4).

и пусть неравенства (1.4) определяют некоторую область ?, содержащую внутренние точки. Будем предполагать, что матрица симметричная и положительно определенная, так что — выпуклая функция. Задача квадратичного программирования формулируется так: отыскать точку, для которой достигается минимум функции (1.1) при ограничениях (1.4):

(1.5).

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

.

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

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

Пример

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

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

.

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

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

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

.

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