§ 3. Алгоритмы максимизации квадратичной формы

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

Теория метода сопряженных градиентов описана во многих руководствах по поиску максимума функции (например, [12,80]).

Рассмотрим сначала метод сопряженных градиентов для максимизации квадратичной формы:

где А — положительно определенная матрица, вектор, у — вектор.

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

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

Начиная со второго шага, направление движения определяется вектором

где - градиенты функции в точках направление движения в точке Движение по направлению ведется до достижения условного максимума. Этот максимум достигается

в точке

где величина

определяет шаг движения.

Формулы (11.22), (11.23) задают, таким образом, алгоритм поиска максимума квадратичной функции

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

Вектор есть условный градиент функции на множестве .

Будем совершать восхождения к максимуму, используя формулы (11.22), (11.23), где заменено на Движение начинается из произвольной точки положительного квадранта и продолжается до момента выхода на ограничение в точке Тогда снова начинается восхождение по методу сопряженных градиентов, но из точки Поиск максимума заканчивается, когда выполнятся неравенства

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

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

Важной особенностью такого метода поиска максимума функции в положительном квадранте является то,

что он допускает последовательную процедуру поиска. Пусть пространство имеет координаты

Можно сначала найти условный максимум функции при ограничениях

а затем, используя найденную точку максимума как начальную, найти максимум в области

В нашем случае при поиске максимума функции

в положительном квадранте, условный градиент есть вектор с координатами

Обозначим составляющие вектора задающего направление движения на шаге, через

Согласно (11.22) имеют место соотношения

где

При вычислении шага по формуле (11.23) необходимо вычислить величину

В нашем случае

где обозначено

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