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

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

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

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

 

 

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

;

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

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

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

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

Система уравнений (1),(2) – нелинейная. Она содержит (m + n + 2) уравнений и 2×(m + n) неизвестных X*, L, V и W. Так как и векторы V и X неотрицательны, следует, что по крайней мере n переменных из v_j и x_j равны 0. Аналогично вытекает, что равны нулю не менее m переменных из w_i и l_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 _иск = S y_k à min. Для выполнения условий дополняющей нежесткости (2) алгоритм симплекс-метода дополняется правилом ограниченного ввода:

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

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

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

f = 10 x ₁ + 20 x ₂ + x ₁× x ₂ – 2 x ₁² – 2 x ₂² à max, 8 – x ₂ ³ 0, 9 – x ₁ – x ₂ ³ 0, x ₁, x ₂ ³ 0.

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

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

или

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

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

	Баз.
				-1			-1						5/2
			-1					-1					-
													-
							-1	-1
						-1	-1

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

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

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