§ 3. Метод параллельных касательных (партан)

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

или, иначе,

  .

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

На рис. 28 изображены линии уровня функции , представляющие собой подобные концентрические эллипсы.

Рис. 28.

Пусть  – произвольная точка,  – линия уровня (эллипс), проходящая через ,  – касательная к эллипсу в точке ,  – градиент функции  в точке . Очевидно, что градиент  нормален к линии уровня, т. е. перпендикулярен касательной .

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

1) из произвольной точки  провести прямую  в направлении градиента функции  в точке ;

2) на этой прямой найти точку условного максимума ;

3) через  провести прямую в направлении градиента и на этой прямой найти точку , доставляющую условный максимум;

4) соединить точки  и  прямой и найти точку максимума на этой прямой. Найденная точка есть точка, доставляющая максимум функции на всей плоскости.

Вернемся теперь к задаче о нахождении максимума  в -мерном пространстве . В соответствии со сказанным выше, процесс, описанный в § 1, может быть приведен к следующему виду.

А. Начальный шаг.

1) В произвольной точке  пространства  находится градиент  функции ;

2) на прямой  ищется точка , доставляющая максимум функции .

Б. Общий шаг. Пусть уже найдены точки

1) В точке  находится градиент  функции ;

2) на плоскости, проходящей через точки  и параллельной направлению , т. е. на плоскости

,

ищется точка , доставляющая условный максимум функции .

В. Останов алгоритма. Процесс прекращается, когда на очередном шаге окажется, что . Тогда  – точка максимума  во всем пространстве .

Для осуществления пункта 2) общего шага применим метод параллельных касательных. Обозначим  двумерную плоскость вида

( и  – параметры) и, начиная с точки , будем действовать по методу «партан». Прежде всего необходимо найти в точке  условный градиент функции  на плоскости . Известно, что условный градиент на гиперпространстве  есть проекция полного градиента на это гиперпространство. Таким образом, нам нужно спроектировать вектор  на плоскость . Но в соответствии с (16.2) и (16.3) вектор  ортогонален , а векторы  и  ортогональны между собой. Поэтому проекция  на плоскость  коллинеарна вектору .

Прямая, проходящая через точку  в направлении условного градиента на плоскости, имеет, таким образом вид

,

а точка максимума на этой прямой есть , так как эта прямая принадлежит пространству  и  доставляет максимум  на всем .

Итак, оказывается, что первый шаг двумерного «партана» фактически уже выполнен и точка  этого алгоритма совпадает с .

Далее, нужно взять условный градиент  в точке . Но направление полного градиента  в точке  принадлежит гиперплоскости . Поэтому условный градиент совпадает с полным. Теперь через точку  нужно провести прямую

и найти на этой прямой точку , доставляющую условный максимум . Наконец, точку  необходимо соединить с  прямой и на этой прямой найти точку, в которой достигается условный максимум . Эта точка и есть .

Таким образом, общий шаг алгоритма приобретает следующий вид:

1) в точке  находится градиент ,

2) на прямой  определяется точка , в которой функция  достигает условного экстремума по формуле

,

где

;

3) на прямой  ищется точка , доставляющая условный экстремум , по формуле

,

где

.

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

Метод параллельных касательных может быть применен и в случае неквадратичной функции, при этом поиск условного экстремума на прямой должен производиться одним из известных методов одномерного поиска. Однако при этом нет никаких гарантий, что процесс закончится через  шагов. Экспериментально же установлено, что этот метод поиска сходится значительно лучше, чем методы наискорейшего спуска или Гаусса-Зайделя.