2.6. Квадратичное программирование. Свойства решений задачи

Задачи квадратичного программирования, как отмечалось в гл. 1, имеют (следующие особенности: целевая функция) представляет собой сумму вида

функции входящие в ограничения, линейны относительно т. е.

обычно присутствует требование не отрицательности переменных.

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

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

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

для всех x_j, х_k, удовлетворяющих принятым ограничениям.

Учитывая сказанное, обратимся к задаче: найти

при

(2.11)

Положив

будем говорить в дальнейшем только о глобальном экстремуме z.

Рассмотрим необходимые условия существования X^*, z^*. Здесь

и

Обозначим для удобства через - производную dΦ/dx_j, а через q_i - производную dΦ/dλ_i. Тогда искомые условия можно трактовать так: значения x^*_j(j = 1,....,n) определяются теми решениями системы

(2.12)

которые удовлетворяют требованиям

Переход к системе (2.12) позволяет в большинстве случаев упростить процедуру отыскания x^*_j (j = 1,...,n) за счет использования, как будет показано ниже, симплекс- алгоритма. Возвращаясь к (2.12), заметим, что рассматриваемая система содержит m+n линейных уравнений с 2 (n+m) неизвестными x^*_j, p^*_j, λ_i^*, q^*_i. Предполагая уравнения (2.12) независимыми (поскольку независимы условия, из которых они получены), можно сказать, что n+m из названных 2 (n+m) переменных являются свободными.

Если некоторое решение (2.12) удовлетворяет требованиям x^*_jp^*_j = 0 (j = 1,...,n), λ^*_iq^*_i = 0 (i = 1,...,m), то среди его компонент должно быть как минимум n+m равных нулю; таким образом, оно может иметь вид "ровно n+m компонент отличны от нуля, ровно n+m компонент "равны нулю" или "менее n+m компонент отличны от 0, более n+m компонент равны 0".

Очевидно, подобные решения являются базисными, и для отыскания X^* должен существовать метод, аналогичный симплекс-методу (см. гл. 1), оперирующему с базисными решениями. Возникает вопрос: нельзя ли сразу выбрать произвольно n+m свободных переменных среди x^*_j, p^*_j, λ_i^*, q^*_i, положить их равными нулю, а затем определить через них остальные переменные в соответствии с уравнениями( 2.12)? Ответ здесь может быть только отрицательным, потому что произвольный выбор решения может привести к нарушению условий ∀x^*_j≥0, ∀p^*_j≥0, ∀λ_i^*≥0, ∀q^*_i≥0. Приходится

обращаться к специальным методам определения x^*_j. Одним из них является так называемый метод Вольфа, предусматривающий исследование задач линейного программирования с целью получить решения задачи квадратичного программирования.