Методы релаксации

Метод релаксации  
 

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

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

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

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

(1)

Условие (1) может быть использовано в том случае, когда оптимум лежит внутри допустимой области изменения независимых переменных. Если же оптимум попадает на границу области допустимого изменения переменных V, то критерий (1) не пригоден и вместо него следует применять условие положительности всех производных по допустимым осевым направлениям. При этом допустимым осевым будет направление внутри области V .

Алгоритм  спуска для выбранного осевого направления  может быть записан  в виде : 

Причем :

U^k_j - значение изменяемой переменной на к-ом шаге спуска *

h^k - величина к-го шага , которая может изменять свое значение в зависимости от номера шага*

sign - функция знака ("сигнум ")

U^P - вектор точки, в которой последний раз производилось вычисление производных целевой функции.  
Графическое изображение движения от исходного состояния к оптимальному показано на Рис.1.  
Очевидно, что скорость движения к минимуму зависит от того, насколько удачно выбран шаг h^k изменения независимых переменных.  

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

R(U^k+1)<R(U^k)

При нарушении  условия на каком-либо шаге направление  спуска по оси изменяется на обратное , и спуск продолжается из последней  рассчитанной точки с уменьшением  вдвое величиной шага . Этот алгоритм может быть записан следующим  образом:

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

Существенной  особенностью метода релаксации является зависимость времени поиска от ориентации системы координат (Рис.2 и 3).  

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

 

Рис.4.  Поиск оптимума при наличии ограничений  

Рис.5.  Поиск оптимума при наличии "оврагов" 

При использовании  метода релаксации иногда возникают значительные трудности: