Метод наискорейшего спуска (крутого восхождения)

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

Путь (рис.1.4.17) поиска экстремума методом наискорейшего спуска

Рис.1.4.17. Метод наискорейшего спуска.

Направление, противоположное нормированному (единичному) градиенту

     , т.е. направление наискорейшего спуска, определяется в точке  

– единичный вектор в направлении градиента

 

 

На k -м этапе переход из точки     в точку

описывается следующим соотношением:

 

Подстановка в последнее выражение

 предыдущего дает следующее

соотношение для метода наискорейшего спуска:

 

 

Поскольку выражение                    – скалярная величина, то оно может быть заменено некоторым числом λ*(k)

 

Тогда

Поиск в соответствии с этим выражением осуществляется многократно.

Для каждого направления градиента осуществляется минимизация

функции

Это может осуществляться формально

путем вычисления λ из уравнения:

Но чаще используют тот или иной метод одномерного поиска для определения величины λ *(k), минимизирующей на k -м шаге поиска целевую функцию.

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

 

Метод релаксаций

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

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

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

Алгоритм поиска при методе релаксаций

 имеет вид:

– значение переменной, по которой происходит оптимизация на данном шаге

 

hj– фактор шага, величина которого изменяется в процессе поиска

 

Обычно шаг выбирается так: вначале он принимается равным числу h1 = δ, затем делается еще один шаг в этом направлении h2 = h1, если шаг оказался успешным, то он удваивается h3 = 2h2.

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

Метод релаксаций можно рассматривать как комбинацию методов, использующих производные.