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, далее поиск продолжается по описанному выше алгоритму.

2.4 Методы поиска условного экстремума

При рассмотрении реальных задач оптимизации на переменные состояния накладываются условия типа равенств или неравенств, которые задают область изменения независимых переменных.

Задача нелинейного программирования в этом случае формулируется следующим образом: требуется найти оптимум (минимум) функции Q() при и условия, что .

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