Метод наискорейшего спуска

Представим трехмерную поверхность функции в виде контур­ной диаграммы на плоскости x₁, x₂. Каждой точке плоскости соответствует определенная величина.

Линии F = const представлены замкнутыми кривыми, окружающими точку М^*, в которой F имеет наименьшее значение. Пусть в начальный момент значения x₁ и x₂ соответствуют точке М₀.

Операция поиска начинается серией пробных шагов. Полагая значе­ния х₂ - неизменным, величине х₁ дают малое приращение δ х₁ > 0 и определяют приращение δ F₁, которое можно счи­тать (если δ х₁ всегда одно и тоже) пропорциональным частной производной

≈ = const. ∂ F₁.

Рис. 3.1. Метод наискорейшего спуска

Затем при х₁ = const дают приращение δ х₂ величине x₂. Получаемое приращение δ F₂ является мерой другой частной про­изводной

≈ = const ∂ F₂.

Определение частных производных означает нахождение вектора гра­диента функции F,

grad F =

направление которого совпадает с направлением наиболее крутого возрастания величины F. Противоположное направление называют " наискорейшим спуском" величины F.

После нахождения составляющих градиента пробные движения
прекращаются и производятся, рабочие шаги в направлении наискорейшего спуска, причем величина шага выбирается в соответствии с величиной вектора grad F. Эти условия соблюдаются, если рабо­чие шаги ∆ X₁ и ∆ Х₂ пропорциональны полученным ранее производным

где λ - положительная постоянная величина. После каждого шага оценивается приращение ∆ F. Если оно отрицательное, то направление движения M₀M выбрано правильно. За­тем определяется grad F в другой точке М и движение про­изводится по новому найденному направлению M₁M₂ и т.д.

Когда рассмотренная система находится вблизи минимума, по­казателем чего является малое значение величины

Ε = ,

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

ЛЕКЦИЯ 4