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

З адачи квадратичного программирования (КП) - целевая функция – сумма линейной и квадратичной форм, а все условия линейные. В задаче с двумя переменными целевая квадратичная функция:

В векторной форме она принимает вид:

. Обобщая на случай многих переменных, получаем:

Матрица С – квадратная, диагонально-симметричная (C_ij=C_ji). Задача КП ставится в виде:

;

Чтобы она являлась задачей выпуклого программирования, целевая функция дб вогнутой. Свойства функции определяются матрицей С. Для вогнутости функции необходимо, чтобы матрица С была отрицательно определенной (строгая вогнутость) или отрицательно полуопределенной. Матрица С отрицательно определенная, если для всех ненулевых X справедливо Х^TСХ< 0, и отрицательно полуопределенная, если Х^TСХ  0. В случае минимизации целевая функция должна быть выпуклой - положительно определенная или положительно полуопределенная матрица С. Определить свойство квадратичной функции можно с помощью достаточных условий экстремума: если функция в стационарной точке имеет максимум, она вогнутая, а если минимум, то выпуклая. Будем полагать, что условия вогнутости функции выполняются. Тогда решение задачи КП можно найти на основе теоремы (из условий Куна-Таккера).

Теорема Для того чтобы вектор Х* являлся решением задачи, необходимо и достаточно существования таких неотрицательных m-мерных векторов W и  и неотрицательного n-мерного вектора V, которые удовлетворяют следующей системе уравнений:

D + CX^*-A^T + V = 0, B - AX^* - W = 0 (1) , V^TX^* = 0, W^T = 0. (2)

Функция Лагранжа для рассматриваемой задачи: .

Система уравнений (1),(2) – нелинейная. Она содержит (m + n + 2) уравнений и 2(m + n) неизвестных X*, , V и W. Так как и векторы V и X неотрицательны, следует, что по крайней мере n переменных из v_j и x_j равны 0. Аналогично вытекает, что равны нулю не менее m переменных из w_i и _i. Таким образом, в решении системы (1) положительными могут быть не более (m + n) переменных. Это свойство системы дает ключ к решению.

Действительно, линейная система (1) содержит n+m уравнений и 2(n + m) неизвестных. Но известно, что в искомом решении число положительных переменных не превышает (m + n). Следовательно, это допустимое базисное решение (опорный план) системы (1). Поэтому искать решение задачи КП нужно только среди опорных планов этой системы. Такие решения находятся методами ЛП. Опорный план системы (1), удовлетво­ряющий условиям (2), будет оптимальным решением задачи КП.

Перепишем уравнения (1) в обычном виде:

Если вектор D – неположительный, а вектор B – неотрицательный, то начальное базисное решение V=-D, W=B удовлетворяет условиям (2) и, значит, является оптимальным решением задачи КП. Однако, как правило, вектор D имеет положительные компоненты и такое начальное решение оказывается недопустимым. В этом случае, ориентируясь на использование прямого симплекс-метода, строится искусственное начальное решение: в уравнения с отрицательной правой частью вводятся искусственные переменные y_k и они вместе с неотрицательными v_j и w_i образуют базисное решение. Критерий - сумма искусственных переменных: L_иск = y_k  min. Для выполнения условий дополняющей нежесткости (2) алгоритм симплекс-метода дополняется правилом ограниченного ввода:

в базисном решении не могут находиться одновременно переменные v, x (w, ) с одинаковыми индексами. Если по оценкам претендентом на ввод является переменная, которую согласно правилу нельзя вводить, в базисное решение вводится другая переменная с положительной оценкой. Признак выполнения условий теоремы (1)-(2) и оптимальности решения задачи КП - равенство 0 всех искусств. переменных или L_иск=0.

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

Пример: Найти решение следующей задачи КП:

f = 10x₁ + 20 x₂ + x₁x₂ – 2x₁² – 2x₂²  max, 8 – x₂  0, 9 – x₁ – x₂  0, x₁, x₂  0.

Перепишем целевую функцию в векторной форме:

По матрице С (гессиану) проверяем достаточные условия: ₁=-4<0, ₁=16-2>0. Значит, f имеет максимум и строго вогнутая. Записываем первую систему уравнений:

или

Добавляем вторую: Для образования начального базисного решения вводим в первую систему искусственные переменные y₁ и y₂:

Критерий линейной задачи: L_иск = у₁ + у₂  min.

		0	0	0	0	0	0	0	0	0	1	1
	Баз.
1		10	4	-1	0	1	-1	0	0	0	1	0	5/2
1		20	-1	4	1	1	0	-1	0	0	0	1	-
0		8	0	1	0	0	0	0	1	0	0	0	-
0		9	1	1	0	0	0	0	0	1	0	0	9
		30	3	3	1	2	-1	-1	0	0	0	0
		30	3	3	1	2	-1	-1	0	0	0	0

Базисные переменные в начальном решении: y₁, y₂, w₁ и w_2. Заполняем начальную симплекс-таблицу.

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

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