z(X(h)) = min (Xk – h grad z(Xk)) (4.29)
h ³ 0
где Xk и grad z(Xk) – известные векторы.
Найденную таким образом длину шага часто называют оптимальной. Говорят также, что при использовании такого шага выполняется (рабочий) шаг оптимальной длины.
После нахождения оптимального значения hопт рассчитывается точка Xk+1 , в которой осуществляется повторный расчет антиградиента и снова решается задача одномерной оптимизации длины следующего шага.
Идея нахождения оптимальной длины шага в рассматриваемом методе аналогична идее, использующейся в методе Гаусса-Зейделя (см. п 4.2.3.5 и рис. 4.9). Отличие заключается в том, что плоскость, в которой рассматривается зависимость ЦФ от параметра h, проходит не в направлении одной из координатных осей, а в направлении антиградиента.
Метод наискорейшего спуска имеет две разновидности.
Первая разновидность метода предусматривает на каждом шаге аналитическое решение вспомогательной задачи оптимизации (4.24). При этом предполагается, что известно аналитическое выражение ЦФ и определенные его основе аналитические выражения компонент градиента. В этом случае оптимальная длина шага определяется как наименьший положительный корень уравнения dz(X(h))/dh = 0.
Вторая разновидность метода предполагает на каждом шаге решение вспомогательной задачи оптимизации одним из численных методов одномерной оптимизации.
При этом, как и в методе Гаусса-Зейделя, нахождение точки минимума может производиться как с относительно высокой, так и с относительно низкой точностью.
В последнем случае движение в направлении антиградиента осуществляется с некоторым постоянным вспомогательным шагом до момента нарушения условия убывания ЦФ. Последняя достигнутая точка на луче (а иногда предпоследняя или средняя [24]) принимается за точку окончания спуска в этом направлении, после чего в ней снова вычисляется градиент и процесс поиска продолжается по тому же алгоритму.
З а м е ч а н и е 4.24. Значение градиента в обоих разновидностях метода может быть вычислено как на основе аналитических выражений, так и с помощью численных методов (см. формулу (4.17)).
Рис 4.13
Можно сказать, что особенностью метода является максимальное “использование” направления, находимого с помощью антитрадиента.
З а м е ч а н и е 4.25. Формально метод наискорейшего спуска может считаться разновидностью метода градиента, описывающейся соотношением (4.20). Его особенность состоит в специфике задания длины шага hk.
Сравнение логики методов наискорейшего спуска и метода градиента позволяет ожидать большую эффективность первого из них (в первую очередь в связи с уменьшением числа вычислений производных ЦФ). Однако в общем случае метод наискорейшего спуска не обладает какими-либо оптимальными свойствами (например, способностью отыскивать оптимальную точку за минимальное число шагов) [18]. Возможный выигрыш в его использовании во многом определяется особенностями конкретной ЦФ и выбором начальной точки. Такой выигрыш достигается вдали от точки экстремума, а при приближении к ней эффективность рассматриваемых методов выравнивается.
Общим достоинством методов первого порядка по отношению к методам нулевого порядка является выбор более эффективных направлений поиска. Однако такой выигрыш достигается ценой достаточно громоздких и частых вычислений значений первых производных.
Общим недостатком рассмотренных градиентных методов является их низкая эффективность в овражных функциях.
Таким образом, использование градиентных методов целесообразно для решения задач оптимизации гладких и выпуклых ЦФ, допускающих относительно несложную процедуру вычисления их производных. В практике автоматизированного проектирования градиентные методы используются в комбинации с другими методами, более эффективными на начальной стадии решения задачи оптимизации.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.