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

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

(1*).

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

(1).

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

(2*).

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

(2).

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

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

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

(3).

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

при ,.

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

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

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

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

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

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

при .

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

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

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

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

при ,.

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