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

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

Например, в задаче с двумя переменными целевая квадратичная функция записывается следующим образом:

f(x ₁, x ₂ ) = d ₁ x ₁ + d ₂ x ₂ + ½(C ₁₁ x ₁² + C ₁₂ x ₁ x ₂ + C ₂₁ x ₁ x ₂ + C ₂₂ x ₂²).

линейная форма квадратичная форма

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

.

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

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

В целом задача квадратичного программирования ставится в виде:

(8.10)

; (8.11)

. (8.12)

Чтобы она являлась задачей выпуклого программирования, целевая функция (8.10) должна быть вогнутой.

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

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

Теорема

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

D + C×X^*-A^T×L + V = 0, (8.13)

B - A×X^* - W = 0, (8.14)

V^T×X^* = 0, (8.15)

W^T×L = 0. (8.16)

Покажем, что теорема выводится из условий Куна-Таккера. Функция Лагранжа для рассматриваемой задачи имеет вид

.

Записываем условия (8.5):

.

Введя в это неравенство неотрицательный вектор дополнительных переменных V, получаем (8.13). (8.14) – это исходное условие задачи после приведения его к равенству вводом неотрицательного вектора дополнительных переменных W. Очевидно. что производная , когда дополнительная переменная V>0 и , когда V=0. Таким образом, V играет роль индикатора производной. Поэтому условие дополняющей нежесткости (8.6) принимает вид (8.15). Аналогична взаимосвязь вектора W с производной F по L, и отсюда имеем второе условие дополняющей нежесткости (8.16).

Система уравнений (8.13)-(8.16) – нелинейная, так как нелинейны (8.15) и (8.16). Она содержит (m + n + 2) уравнений и 2×(m + n) неизвестных X*, L, V и W.

Так как и векторы V и X неотрицательны, из (8.15) следует, что по крайней мере n переменных из v_j и x_j равны 0. Аналогично из (8.16) вытекает, что равны нулю не менее m переменных из w_i и l_i. Таким образом, в решении системы (8.13)-(8.14) положительными могут быть не более (m + n) переменных. Это свойство системы дает ключ к решению.

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

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

(8.17)

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

L _иск = S y_k à min.

Для выполнения условий дополняющей нежесткости (8.15)-(8.16) алгоритм симплекс-метода дополняется правилом ограниченного ввода:

если в базисном решении имеется v_j, то не может вводиться x_j (с тем жеиндексом) и наоборот;

если в базисном решении имеется w_i, то не может вводиться l_i (с тем жеиндексом) и наоборот.

Иначе говоря, в базисном решении не могут находиться одновременно переменные v, x (w, l) с одинаковыми индексами. Если по оценкам претендентом на ввод является переменная, которую согласно правилу нельзя вводить, в базисное решение вводится другая переменная с положительной оценкой.

Признаком выполнения условий теоремы (8.13)-(8.16) и, следовательно, оптимальности решения задачи КП является равенство нулю всех искусственных переменных или L _иск=0.

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

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

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 имеет максимум и строго вогнутая.

Записываем первую систему уравнений (8.17):

или

Добавляем вторую:

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

Критерий линейной задачи:

L _иск = у ₁ + у ₂ à min.

Базисные переменные в начальном решении: y ₁, y ₂, w ₁ и w _2.

Заполняем начальную симплекс-таблицу.

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

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

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

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