2.3.5 Поиск при наличии "оврагов" целевой функции

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

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

2) Выбирается начальная точка u0 , из которой производится поиск, будем считать для определенности, минимума любым методом локального поиска. Этот поиск закончится на дне "оврага", в результате чего будет найдена некоторая критическая точкаu1…. (рис. 2.13).

Рисунок 2.13 –Метод "оврагов"

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

4) Из состояния производится поиск минимума, в результате которого определяется еще одна критическая точкаu2, расположенная на дне "оврага" (рис. 2.13).

5) Две найденные критические точки u1 иu2 соединяются прямой и выполняется "шаг по оврагу" в направлении убывания целевой функции. Это дает новое исходное состояние .

6) Из состояния производится спуск на "дно оврага" и находится критическая точкаu3. Далее определяется состояние и т.д. (рис. 2.13).

Процесс поиска продолжается до тех пор, пока значение целевой функции во вновь найденной критической точке не окажется больше, чем в предыдущей точке. Минимум в этом случае находится между точкамиuk–1 иuk+1. Далее процесс поиска можно повторить, но уже с меньшими "шагами по оврагу", пока не будет достигнута требуемая точность.

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