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

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

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

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

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

(10) ; (11) .(12)

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

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

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

D + C× X^*-A^T× L + V = 0, (13)B - A× X^* - W = 0, (14)V^T× X^* = 0, (15) W^T× L = 0.(16)

Решение задачи КП нужно только среди опорных планов этой системы. Такие решения находятся методами линейного программирования. Опорный план системы (13), (14), удовлетво­ряющий условиям (15), (16), будет оптимальным решением задачи КП.

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

(17)

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

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

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

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

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

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

Для задач КП экстремум может находиться в любой точке.

Сепарабельное программирование (СП)

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

f(x₁, x₂,..., x_n) = (18)

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