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

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

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

а) б)

Рис. 8.12. Поведение изображения точки при движении к оптимуму

при наличии вытянутого гребня:

а) метод крутого восхождения; б) метод сопряженных градиентов

Алгоритм метода сопряженных градиентов состоит из следующих частей.

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

2. Осуществление движения в найденном направлении и определение точки частного экстремума в этом направлении (аналогично методу крутого восхождения). Для произвольного k-го цикла это дает точку — центр следующего цикла движения.

3. Постановка эксперимента, вычисление координат градиента в точке и коэффициентов , необходимых для выбора направления в (k+1)-м цикле поиска.

4. Определение направления движения в (k+1)-м цикле:

; (8.27)

.

Таким образом, движение в методе сопряженных градиентов осуществляется в компромиссном направлении, причем коэффициенты , связанные с направлением градиента на предыдущем k-м цикле, входят в формулу для направления перемещения в (k+1)-м цикле с весовым коэффициентом

. (8.28)

Реализация движения производится в соответствии с описанием п. 2. Подобный способ организации движения сохраняется до n-го цикла включительно. Конечный итог поиска после n-го цикла – точка — центр следующего (n+1)-го цикла.

5. Повторение п.п. 1- 4. В качестве начальной точки в п. 1 следует использовать полученную точку . Алгоритм начинает функционировать как бы с самого начала, то есть с обычного движения по градиенту. Подобная потеря инерционности оказывается полезной, так как во многих случаях ускоряет поиск экстремума. Кроме того, для алгоритма метода сопряженных градиентов доказано, что в случае чисто квадратичной поверхности отклика и при отсутствии помех гарантируется достижение экстремума ровно за n операций. Поэтому после реализации n циклов желательно проведение более тщательной проверки того факта, достигнута или нет точка экстремума. Показателем, свидетельствующим о близости этой точки, является примерное равенство нулю всех коэффициентов (или ); .

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