III. Нахождение минимума функции или функционала методом наискорейшего спуска

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

функции от каждого аргумента по трем точкам далеко не достаточно, то станет ясно, что нахождение минимума функции путем численного исследования ее зависимости от всех аргументов в интересующей нас области их изменения представляет собой в сколько-нибудь сложных случаях практически невыполнимую задачу. Еще сложнее задача численного нахождения минимума функционала. Поэтому естественно возникает вопрос: как избежать большого объема ненужных непосредственно для отыскания минимума вычислений, выбирая комбинации значений аргументов для расчета таким образом, чтобы обеспечить насколько возможно более быстрое приближение к искомому минимуму? Такая организация вычислений достигается применением метода наискорейшего спуска. В этом методе каждая последующая расчетная точка (комбинация значений аргументов при отыскании минимума функции и функция при отыскании минимума функционала) выбирается таким образом, чтобы обеспечить максимальное возможное убывание функции или функционала, чем и объясняется название метода. идею можно наглядно проиллюстрировать на примере минимума функции двух переменных, которую можно изобразить поверхностью в трехмерном пространстве. При применении метода наискорейшего спуска переход от каждой расчетной точки поверхности к следующей осуществляется в направлении линии наибольшего ската, т. е. в направлении стекания воды, вылитой в этой точке. Интуитивно ясно, что метод наискорейшего спуска является наиболее эффективным из всех возможных численных методов отыскания минимума функции или функционала, основанных на непосредственном вычислении значений функции или функционала в ряде точек.

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

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

или, в векторной форме,

Выразим приращение функции при переходе от вектора к вектору по формуле Тейлора:

где нуликом внизу отмечены значения производных функции в точке

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

Тогда, обозначая для краткости значение вектора градиента функции в точке через

можем переписать равенство (III. 4) в векторной форме:

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

где через и обозначены нормы (модули) векторов т. е. положительные квадратные корни из сумм квадратов их составляющих (см. Дополнение, I). Знак равенства в (III. 9) имеет

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

где некоторое положительное число, пропорциональное норме вектора Очевидно, что вместо того, чтобы задавать норму вектора можно непосредственно задавать число Подставляя выражение (III. 10) в формулу (III. 3), получим:

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

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

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

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

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

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

Тогда формула (III. 13) при примет вид:

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

Для доказательства введем новые параметры

Тогда, рассматривая функционал как сложную функцию а, получим:

Но согласно определению (III. 14)

Подставляя эти выражения в (III. 18), мы и получим формулу (III. 16).

Так как равенство (III. 16) справедливо для любых сумм, то оно справедливо и для интегралов, т. е. при любых функциях и области изменения параметра X имеет место равенство

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

то, пользуясь равенством (III. 21), находим:

Величина

которая является функцией параметра X и функционалом относительно функции у, не зависит от функции и. Пользуясь обозначением (III. 24), можно переписать формулу (III. 23) в виде:

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

Полагая в формуле (III. 15) приведем ее при помощи формул (III. 3) и (III. 25) к виду (III. 8). Так как определение скалярного произведения двух функций в виде интеграла (III. 25) удовлетворяет всем условиям сноски на стр. 854, то для интеграла (III. 25) справедливо неравенство Следовательно, все рассуждения и выкладки, в результате которых мы пришли к формулам ( справедливы для случая, когда являются функциями, функционалом. При этом функции определяются формулой

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

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

Формулы ( справедливы и для случая, когда у и и являются векторными функциями. Представив произвольную векторную функцию в виде суммы векторных функций и пользуясь формулой (III. 16), а затем применяя к каждой составляющей

формулы выразим функционал от векторных функций в виде:

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

где

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

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

Метод наискорейшего спуска, по-видимому, впервые применялся для определения оптимальных значений числовых параметров систем автоматического управления Н. М. Сотским и Н. И. Андреевым. Ю. П. Леонов предложил применять метод наискорейшего спуска для определения весовых функций оптимальных линейных систем по критерию минимума средней квадратической ошибки.