2020-04-12
142
Градиентные методы
... нет такой воды, которая не стремилась бы [течь] вниз.
Мэн-цзы
Здесь изучается класс так называемых градиентных методов приближенного решения задач оптимизации. Доказываются теоремы сходимости, описываются простейшие модификации.
Общие соображения и определения.
Наиболее распространенные и эффективные методы приближенного решения задачи безусловной оптимизации
| f (x) → min, | (1) |
где f: R m → R, укладываются в следующую грубую схему. Начиная с некоторого x 0 ∈ R m, строится последовательность { xn } ⊂ R m такая, что
| f (xn +1) < f (xn) | (2) |
при всех n ∈ N. Такие последовательности иногда называют релаксационными, а методы построения релаксационных последовательностей – итерационными методами или методами спуска. Последовательность, удовлетворяющую (2), строят в надежде, что уменьшая на каждом шаге (переходе от xn к xn +1) значение функции, мы приближаемся к минимуму (по крайней мере, локальному).
Мы будем говорить, что метод, начиная с данного x 0 ∈ R m,
|
|
|
а) условно сходится, если последовательность { xn } релаксационна и
| f ′(xn) → Θ при n → ∞; |
б) сходится, если
| xn → x * = argmin f (x) при n → ∞; |
в) линейно сходится (или сходится со скоростью геометрической прогрессии, или имеет первый порядок сходимости), если при некоторых C > 0 и q ∈ [0, 1)
| || xn – x *|| ≤ Cqn; | (3) |
г) сверхлинейно сходится, если для любого q ∈ (0, 1) и некоторого (зависящего от q) C выполнено неравенство (3);
д) квадратично сходится (или имеет второй порядок сходимости), если при некоторых C > 0 и q ∈ [0, 1) и всех n ∈ N
| || xn – x *|| ≤ Cq 2 n . |
Если эти свойства выполняются только для x 0 достаточно близких к x *, то как всегда добавляется эпитет "локально".
З а д а ч а 1*. Пусть при некотором q ∈ [0, 1)
| || xn +1 – x *|| ≤ q || xn – x *||, n ∈ N. |
Докажите, что метод линейно сходится.
З а д а ч а 2*. Пусть при некотором C 1 > 0
| || xn +1 – x *|| ≤ C 1|| xn – x *||2, n ∈ N |
и || x 0 – x *|| достаточно мала. Докажите, что метод квадратично сходится.
Будем говорить, что на данной последовательности метод сходится с порядком p (или имеет p-ый порядок сходимости), если при некотором C
| || xn +1 – x *|| ≤ C || xn – x *|| p. |
Эвристические соображения, приводящие к градиентным методам.
Выше уже отмечалось, что если x не является точкой локального минимума функции f, то двигаясь из x в направлении, противоположном градиенту (еще говорят, в направлении антиградиента), мы можем локально уменьшить значение функции. Этот факт позволяет надеяться, что последовательность { xn }, рекуррентно определяемая формулой
| xn +1 = xn – α f ′(xn), | (4) |
где α - некоторое положительное число, будет релаксационной.
|
|
|
К этой же формуле приводит и следующее рассуждение. Пусть у нас есть некоторое приближение xn. Заменим в шаре B (xn, ε) с центром в точке xn функцию f ее линейным (вернее, афинным) приближением:
| f (x) ≈ φ(x) ≝ f (xn) + (f ′(xn), x – xn) (4*) |
(функция φ аппроксимирует f в окрестности точки xn с точностью o (x – xn)). Разумеется, (линейная) безусловная задача φ(x) → min неразрешима, если f ′(xn) ≠ Θ. В окрестности же B (xn, ε) функция φ имеет точку минимума. Эту точку естественно взять за следующее приближение xn +1.
Градиентный метод с постоянным шагом.
В общем случае число α в формуле (4) может на каждом шаге (т. е. для каждого n) выбираться заново:
| xn +1 = xn – α nf ′(xn). | (5) |
Именно методы, задаваемые формулой (5), называются градентными. Если α n = α при всех n, то получающийся метод называется градиентным методом с постоянным шагом (с шагом α.)
Поясним геометрическую суть градиентного метода. Для этого мы выберем способ изображения функции с помощью линий уровня. Линией уровня функции f (изолинией) называется любое множество вида { x ∈ R m: f (x) = c }. Каждому значению c отвечает своя линия уровня (см. рис. 1).
Рис. 1.
З а д а ч а 3. Докажите, что касательная к линии уровня функции f: R 2 → R ортогональна к градиенту. Как обобщить это утверждение на многомерный случай?
Геометрическая интерпретация градиентного метода с постоянным шагом изображена на рис. 2. На каждом шаге мы сдвигаемся по вектору антиградиента, "уменьшенному в α раз".
Рис. 2.
