2.5. Задача квадратичного программирования

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

Ax ≤ b

x ≥ 0

где Н – матрица размерности (пхп), А – матрица размерности (mxn), x и d - (nx1)- векторы, b - (mx1) – вектор. Целевая функция этой задачи имеет квадратичную форму, а ограничения, как и в задаче линейного программирования, линейны. Обычно предполагается, что при минимизации целевой функции матрица Н является положительно определенной, то есть имеет место х^ТНх  ,  х  Е^п, х  0, а в случае максимизации – отрицательно определенной, то есть х^ТНх  ,  х  Е^п, х  0. В первом случае целевая функция выпукла, а во втором случае она вогнута. Эти условия обеспечивают существование и единственность решения, если только значение целевой функции конечно на множестве допустимых решений, заданном ограничениями Ax ≤ b, x ≥ 0. Для определенности рассмотрим задачу на минимум. Функция Лагранжа для такой задачи записывается в виде

следовательно, необходимые и достаточные условия оптимальности решения х^* примут вид

Заметим, что в первой строке этого выражения величина d + Hx^* представляет собой производную целевой функции по вектору х в точке х^*.

Рассмотрим численный пример. Пусть решается задача

f(x) = 3x₁² + 4x₁x₂+5x₂² → min,

x₁+x₂ ≥ 4

x₁, x₂ ≥ 0

в которой всего одно ограничение q₁ (x) = -x₁- x₂+ 4 ≤ 0, а линейная часть целевой функции отсутствует, т.е. вектор d равен нулю. Поэтому функция Лагранжа будет равна L(x, ) = f(x) + ^T(Ax + b) = 3x₁² +4x₁x₂+5x₂² + (-x₁ – x₂ +4), а условия оптимальности примут вид

L(x^*, )/х₁ = 6х₁ + 4х₂ -   0;

х₁^*L(x^*, )/х₁ = 0;

L(x^*, )/х₂ = 4х₁ + 10х₂ -   0;

х₂^*L(x^*, )/х₂ = 0;

L(x^*, )/ = - х₁ – х₂ + 4 ≤ 0;

(- х₁ – х₂ + 4) = 0;

  0;

Легко проверить, что решение этой задачи есть x* = (3, 1)^T, f* = f(x*) = 44,

Это же решение можно получить, если в исходной задаче условие неотрицательности переменных, т.е. x₁, x₂  0, заменить ограничениями q₂ (x) = -x₁ ≤ 0, q₃ (x) = -x₂ ≤ 0. Тогда функция Лагранжа примет вид

а условия теоремы Куна – Таккера будут равны

;

Рекомендуем студентам самостоятельно проверить, что решение этой системы совпадает с полученным выше решением x* = (3, 1)^T; f* = f(x*) = 44, .

Ниже, на рисунке представлена геометрическая интерпретация решения задачи. Как видно, область допустимых решений задачи представляет собой выпуклое многогранное множество (выпуклый многогранник), а линии уровня целевой функции представляют собой эллипсы, стягивающиеся в начало координат. Линия минимального уровня целевой функции касается отрезка прямой, заданной уравнением x₁+ x₂ = 4, в точке с координатами (3, 1), что и совпадает с решением данной задачи.