Определение минимального значения многопараметрической функции Q (х), заданной в n-мерном евклидовом пространстве связано с решением задачи безусловной оптимизации:

min Q(x₁, х₂,…, x_n). (5.1)

Здесь каждая переменная x_i, i= 1, 2, …, n, может принимать значения от -∞ до +∞. Предположим, что функция Q (х) является унимодальной функцией, для которой в каждой точке х может быть получено с помощью градиента ∇Q(х)= {∂Q/∂x₁, …, ∂Q/∂x_n), а при необходимости и гессиана (матрицы вторых производных)

G(х) = {∂₂Q/∂x_i∂x_j}.

Рассмотрим класс алгоритмов, осуществляющих последовательный поиск точки минимума х* функции Q (х) из заданного начального приближения х° по итерационной формуле

x^r+1 = x^r + Δ^r = x^r + λ_rS^r, r = 0,1,… (5.2)

где x^r — приближенное решение задачи (5.1), полученное на r-й итерации; Δ^r= (х^r+1 — х^r) — приращение варьируемых параметров на r-й итерации; S^r — единичное направление, ведущее к уменьшению функции Q (х); λ_r — длина шага вдоль направления S^r. Последовательность точек испытаний {х^r}, полученная по формуле (5,2) и удовлетворяющая цепочке неравенств

Q(х⁰) > Q(x¹) > … > Q (x^k). (5.3)

называется релаксационной последовательностью.

Разложим функцию Q (х) относительно точки х^r в ряд Тейлора, ограничиваясь членами первого порядка

Q(x^r+1) ≈ Q(x^r) + (∇Q^T(x^r), Δ^r). (5.4)

Из условия (5.3) следует, что на каждой итерации приращение А’ должно выбираться таким образом, чтобы выполнялось неравенство: Q (х^r+1) — Q (х^r) < 0. Учитывая соотношение (5.4), получаем, что

(∇Q^T(x^r), Δ^r) = λ_r(∇Q^T(x^r), S^r) < 0. (5.5)

Для обеспечения наибольшей скорости уменьшения функции Q (х) вдоль единичного направления последнее должно совпадать с нормализованным значением антиградиента:

S^r = -∇Q(x^r)/||∇Q(x^r||. (5.6)

Из (5.4) с учетом неравенства (5.5) следует, что единичное направление S^r, обеспечивающее наибольшую скорость уменьшения функции Q (х), является решением экстремальной задачи

min (∇Q^T(x^r), S) при условии что (S^T‘, S)= 1.

Методы построения релаксационной последовательности (5.3) с помощью итерационной формулы (5.2), в которой направление поиска S^r зависит от значения антиградиента, называются градиентными методами спуска. При заданном направлении поиска S^r выбор точки очередного испытания согласно (5.2) сводится к определению положительного значения шага λ_r вдоль этого направления. Реализация градиентного метода спуска, в которой оптимальная длина шага λ_r вдоль направления антиградиента (5.6) является решением одномерной задачи минимизации:

Q{x^r + λ_rS^r) = min Q(x^r + λS_r), (6.10)

называется методом наискорейшего спуска.

Алгоритмы, реализующие метод наискорейшего спуска, отличаются друг от друга способом. решения экстремальной задачи (5.10). Если функция Q (х) является дважды дифференцируемой (Q(х)∈С²), то ее можно аппроксимировать в точке (r + 1)-го приближения полиномом второй степени

Q(x^r+1) ≈ Q (х^r) + λ_r(∇Q^T(х^r), S^r) + λ_r²(S^r)^TG(х^r)S^r.

Отсюда получаем, что оптимальным решением задачи (5.10) является выражение

λ_r = —(∇Q^T(х^r), S^r)/(S^r)^TG(х^r)S^r. (5.13)

Достоинством метода наискорейшего спуска является его простота. Однако он имеет ряд существенных недостатков, среди которых необходимо отметить следующие. Во-первых, это — одношаговый метод, в котором при выборе точки очередного испытания х^r+1 не используется информация о предыдущих испытаниях, кроме испытания в точке x^r. Во-вторых, если гессиан G (х) минимизируемой функции Q (х) является плохо обусловленной матрицей, наименьшее и наибольшее собственные значения которой сильно отличаются друг от друга, то процесс поиска замедляется в связи с зигзагообразностью траектории проводимых испытаний х⁰, х¹,…,х^k (рис. 5.1).

Рис. 5.1. Зигзагообразная траектория приближения к точке минимума x* квадратичной функции с помощью метода наискорейшего спуска

При этом может потребоваться недопустимо большое число итераций, прежде чем будет получена требуемая точность локализации точки локального минимума х*.
Q(x) = x^TAx+b^Tx + a

Рассмотренное свойство метода привод к тому, что он позволяет получить оптимальное решение х* задачи безусловной минимизаций (5.1) за конечное число итераций и в качестве условия окончания поиска обычно используется неравенство

||∇Q(x^r)|| ≤ ε.

Для устранения недостатка метода F²², связанного с игнорированием информации о предыдущих испытаниях, рассмотрим алгоритм, реализующий градиентный метод с памятью, в котором при выборе очередного приращения Δ^r учитывается информация о приращении Δ^r-1 на предыдущем шаге. Для этого потребуем, чтобы на каждой итерации приращение Δ^r выбиралось таким образом, чтобы обеспечивалась наибольшая скорость уменьшения функции Q (х) при условии, что квадрат модуля разности приращения Δ^r и взвешенного приращения βΔ^r-1 оставался равным постоянной величине К:

min (∇Q^T(x^r), Δ). (5.17)

Оптимальным решением задачи (5.17) является линейная комбинация антиградиента функции Q (х), вычисленного в точке х^r и приращения, полученного на предыдущей итерации:

Δ^r = — λ_r∇Q(x^r) + β_rΔ^r-1. (5.18)

Значения коэффициентов λ_r и β_r в формуле (5.18), полученной для построения очередного приращения Δ^r, могут быть выбраны из условия обеспечения минимального значения функции Q (х) вдоль направления Δ^r:

Q(x^r — λ_r∇Q(x^r) + β_rΔ^r-1) = min Q (^r — λ_r∇Q(x^r) + β_rΔ^r-1). (5.21)

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

О градиентных методах спуска, которые позволяют найти точку минимума x* = (х₁, …, x₁) квадратичной функции (5.14) не больше, чем за n итераций, говорят, что они обладают квадратичной скоростью сходимости. Более подробно методы локальной оптимизации, обладающие квадратичной скоростью сходимости, будут рассмотрены в следующем посте.

Комментарии запрещены.