Рис. 4.12
При использовании геометрических представлений учитывается, что градиентное направление является ортогональным к линиям равного уровня (или что направление вектора градиента в некоторой точке X нормально линии уровня, проходящей через эту точку).
Отметим далее, что выбор длины шага является очень важным для рассматриваемого метода.
При этом, в частности, приходится принимать во внимание, что модуль вектора- градиента уменьшается по мере продвижения к точке экстремума. Поэтому в стратегии спуска (4.23) модуль вектора шага D(Xk) при постоянном значении h будет также уменьшаться. Такое изменение, в принципе, благоприятно для реализации метода. Тем не менее, как указано в [15,24,33], такое уменьшение в ряде случаев может оказаться недостаточным. В частности, значение целевой функции во вновь рассчитанной точке может оказаться большим, чем ее значение в предыдущей точке (то есть нарушится условие z(Xk+1) < z(Xk) ). (Можно сказать, что в этом случае шаг D(Xk) изменяется слишком медленно).
Для предотвращения подобных случаев на практике применяются различные стратегии изменения длины шага hk, описываемые в общем виде формулой (4.24).
Так, может быть использован один из алгоритмов поиска с возвратом [22]. В соответствии с одним из них, после нарушения условия убывания ЦФ, поиск производится путем возврата в предыдущую точку Xk и повторного перемещения в том же направлении с шагом hk /2 . (При этом процедура дробления шага производится до тех пор, пока его значение не станет меньше некоторого малого положительного числа Dзад). Аналогичный алгоритм, предусматривающий уменьшение длины шага в два раза, приводится и в [26].
В [17] описан способ удвоения, в соответствии к которым в зависимости от выполнения или не выполнения на определенном шаге условия убывания ЦФ шаг либо уменьшается, либо увеличивается в два раза.
Разработаны и более гибкие тактики увеличения или уменьшения длины шага (названные в [4] тактиками «разгона и торможения»), учитывающие, например, угол поворота градиента на k +1-м шаге по отношению к градиенту на k-м шаге [26], а также сумму абсолютных значений компонент вектора градиента на k-ом шаге [33].
Использование нормированного вектора градиента gz(X) позволяет более эффективно реализовывать различные стратегии изменения hk для изменения длины D(Xk), поскольку в этом случае этом отпадает необходимость учета изменения модуля градиента.
В качестве критериев окончания поиска в рассматриваемом методе помимо критериев вида (4.11) при переменном шаге может использоваться “шаговые” критерии
hk £ Dзад или ïXk-Xk+1ï £ Dзад . (4.27)
Кроме того, может использоваться специальный “градиентный” критерий, основывающийся на том, что модуль вектора-градиента в окрестности точки оптимума при увеличении k стремится к нулю:
| grad z(Xk) | £ Dзад . (4.28)
Метод наискорейшего спуска.
(Другое название - метод скорейшего спуска).
Рассматриваемый метод считается развитием предыдущего метода. В основе его лежит идея того, что для повышения быстродействия целесообразно каждую итерацию выполнять с максимально возможным шагом.
В методе наискорейшего спуска движение вдоль направления, задаваемого градиентом, осуществляется до тех пор, пока ЦФ уменьшается (или, более точно, до точки, где ЦФ принимает минимальное значение в направлении антиградиента).
Таким образом, очередная точка Xk+1 определяется как точка минимума ЦФ z(X) на луче, задаваемом соотношением X(h) = Xk – h grad z(Xk), h³0, направленном от точки Xk по антиградиенту.
Длина шага, обеспечивающая такое движение на каждой итерации, может быть определена в результате решения вспомогательной одномерной задачи оптимизации по неотрицательной переменной h:
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.