Конечный алгоритм решения задачи квадратичного программирования

Приведем теперь изложение одного конечного алгоритма для решения задачи (1) — (3) квадратичного программирования.

1) Составим таблицу из ограничений (2*) и частных производных минимизируемой функции (1*):

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

до значений, равного наименьшему положительному среди значений.

Пусть для удобства значение достигается при т. е.

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

Действительно, если мы меняем местами и (разрешающий элемент), то, следовательно, а).

.

где — новая строка и — также новая строка;

б).

.

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

Пусть после последовательных шагов жордановых исключений пришли к таблице.

2) Определим единственную точку, в которой функция достигает относительного минимума при условии. Для этого решаем систему линейных уравнений.

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

Если, то и. Такую точку будем называть стационарной.

Если, то стационарная точка является решением.

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

Если же, то стационарная точка может не являться решением.

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

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

3) Определим направление движения из стационарной точки. Пусть стационарная точка принадлежит плоскостям (в соответствии с таблицей (*)). Тогда, если, то точка — решение задачи.

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

Для получения направления наискорейшего спуска решаем следующую задачу линейного программирования: минимизировать функцию.

при ограничениях.

Но — независимые переменные, поэтому (в соответствии с таблицей (*)).

Далее, точка стационарная, т. е., поэтому.

.

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

при ограничениях.

.

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

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

где — значение, минимизирующее функцию .

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

Так как алгоритм монотонный, а стационарных точек — конечное число, то после конечного числа шагов получим решение .