Градиентные методы

05.11.2022

Градиентные методы — численные методы решения с помощью градиента задач, сводящихся к нахождению экстремумов функции.

Постановка задачи решения системы уравнений в терминах методов оптимизации

Задача решения системы уравнений:

{ f 1 ( x 1 , x 2 , … , x n ) = 0 … f n ( x 1 , x 2 , … , x n ) = 0 {displaystyle left{{egin{array}{lcr}f_{1}(x_{1},x_{2},ldots ,x_{n})&=&0ldots &&f_{n}(x_{1},x_{2},ldots ,x_{n})&=&0end{array}} ight.} (1)

с n {displaystyle n} x 1 , x 2 , … , x n {displaystyle x_{1},x_{2},ldots ,x_{n}} эквивалентна задаче минимизации функции

F ( x 1 , x 2 , … , x n ) ≡ ∑ i = 1 n | f i ( x 1 , x 2 , . . . , x n ) | 2 {displaystyle F(x_{1},x_{2},ldots ,x_{n})equiv sum _{i=1}^{n}|f_{i}(x_{1},x_{2},...,x_{n})|^{2}} (2)

или какой-либо другой возрастающей функции от абсолютных величин | f i | {displaystyle |f_{i}|} невязок (ошибок) f i = f i ( x 1 , x 2 , … , x n ) {displaystyle f_{i}=f_{i}(x_{1},x_{2},ldots ,x_{n})} , i = 1 , 2 , … , n {displaystyle i=1,2,ldots ,n} . Задача отыскания минимума (или максимума) функции n {displaystyle n} переменных и сама по себе имеет большое практическое значение.

Для решения этой задачи итерационными методами начинают с произвольных значений x i [ 0 ] ( i = 1 , 2 , . . . , n ) {displaystyle x_{i}^{[0]}(i=1,2,...,n)} и строят последовательные приближения:

x → [ j + 1 ] = x → [ j ] + λ [ j ] v → [ j ] {displaystyle {vec {x}}^{[j+1]}={vec {x}}^{[j]}+lambda ^{[j]}{vec {v}}^{[j]}}

или покоординатно:

x i [ j + 1 ] = x i [ j ] + λ [ j ] v i [ j ] , i = 1 , 2 , … , n , j = 0 , 1 , 2 , … {displaystyle x_{i}^{[j+1]}=x_{i}^{[j]}+lambda ^{[j]}v_{i}^{[j]},quad i=1,2,ldots ,n,quad j=0,1,2,ldots } (3)

которые сходятся к некоторому решению x → [ k ] {displaystyle {vec {x}}^{[k]}} при j → ∞ {displaystyle {j o infty }} .

Различные методы отличаются выбором «направления» для очередного шага, то есть выбором отношений

v 1 [ j ] : v 2 [ j ] : … : v n [ j ] {displaystyle v_{1}^{[j]}:v_{2}^{[j]}:ldots :v_{n}^{[j]}} .

Величина шага (расстояние, на которое надо передвинуться в заданном направлении в поисках экстремума) определяется значением параметра λ [ j ] {displaystyle lambda ^{[j]}} , минимизирующим величину F ( x 1 [ j + 1 ] , x 2 [ j + 1 ] , … , x n [ j + 1 ] ) {displaystyle F(x_{1}^{[j+1]},x_{2}^{[j+1]},ldots ,x_{n}^{[j+1]})} как функцию от λ [ j ] {displaystyle lambda ^{[j]}} . Эту функцию обычно аппроксимируют её тейлоровским разложением или интерполяционным многочленом по трем-пяти выбранным значениям λ [ j ] {displaystyle lambda ^{[j]}} . Последний метод применим для отыскания max и min таблично заданной функции F ( x 1 , x 2 , . . . , x n ) {displaystyle F(x_{1},x_{2},...,x_{n})} .

Градиентные методы

Основная идея методов заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом − ∇ F {displaystyle - abla F} :

x → [ j + 1 ] = x → [ j ] − λ [ j ] ∇ F ( x → [ j ] ) {displaystyle {overrightarrow {x}}^{[j+1]}={overrightarrow {x}}^{[j]}-lambda ^{[j]} abla F({overrightarrow {x}}^{[j]})}

где λ [ j ] {displaystyle lambda ^{[j]}} выбирается:

  • постоянной, в этом случае метод может расходиться;
  • дробным шагом, то есть длина шага в процессе спуска делится на некое число;
  • наискорейшим спуском: λ [ j ] = a r g m i n λ F ( x → [ j ] − λ [ j ] ∇ F ( x → [ j ] ) ) {displaystyle lambda ^{[j]}=mathrm {argmin} _{lambda },F({vec {x}}^{[j]}-lambda ^{[j]} abla F({vec {x}}^{[j]}))}

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

Выбирают v i [ j ] = − ∂ F ∂ x i {displaystyle v_{i}^{[j]}=-{frac {partial F}{partial x_{i}}}} , где все производные вычисляются при x i = x i [ j ] {displaystyle x_{i}=x_{i}^{[j]}} , и уменьшают длину шага λ [ j ] {displaystyle lambda ^{[j]}} по мере приближения к минимуму функции F {displaystyle F} .

Для аналитических функций F {displaystyle F} и малых значений f i {displaystyle f_{i}} тейлоровское разложение F ( λ [ j ] ) {displaystyle F(lambda ^{[j]})} позволяет выбрать оптимальную величину шага

λ [ j ] = ∑ k = 1 n ( ∂ F ∂ x k ) 2 ∑ k = 1 n ∑ h = 1 n ∂ 2 F ∂ x k d x h ∂ F ∂ x k ∂ F ∂ x h {displaystyle lambda ^{[j]}={frac {sum _{k=1}^{n}({frac {partial F}{partial x_{k}}})^{2}}{sum _{k=1}^{n}sum _{h=1}^{n}{frac {partial ^{2}F}{partial x_{k}dx_{h}}}{frac {partial F}{partial x_{k}}}{frac {partial F}{partial x_{h}}}}}} (5)

где все производные вычисляются при x i = x i [ j ] {displaystyle x_{i}=x_{i}^{[j]}} . Параболическая интерполяция функции F ( λ [ j ] ) {displaystyle F(lambda ^{[j]})} может оказаться более удобной.

Алгоритм

  • Задаются начальное приближение и точность расчёта x → 0 , ϵ {displaystyle {vec {x}}^{0}!,,epsilon }
  • Рассчитывают x → [ j + 1 ] = x → [ j ] − λ [ j ] ∇ F ( x → [ j ] ) {displaystyle {vec {x}}^{[j+1]}={vec {x}}^{[j]}-lambda ^{[j]} abla Fleft({vec {x}}^{[j]} ight)} , где λ [ j ] = a r g m i n λ F ( x → [ j ] − λ [ j ] ∇ F ( x → [ j ] ) ) {displaystyle lambda ^{[j]}=mathrm {argmin} _{lambda },Fleft({vec {x}}^{[j]}-lambda ^{[j]} abla Fleft({vec {x}}^{[j]} ight) ight)}
  • Проверяют условие останова:
    • Если | x → [ j + 1 ] − x → [ j ] | > ϵ {displaystyle left|{vec {x}}^{[j+1]}-{vec {x}}^{[j]} ight|>epsilon } , то j = j + 1 {displaystyle j=j+1} и переход к шагу 2.
    • Иначе x → = x → [ j + 1 ] {displaystyle {vec {x}}={vec {x}}^{[j+1]}} и останов.

    • Метод покоординатного спуска Гаусса — Зейделя

    Этот метод назван по аналогии с методом Гаусса — Зейделя для решения системы линейных уравнений. Улучшает предыдущий метод за счёт того, что на очередной итерации спуск осуществляется постепенно вдоль каждой из координат, однако теперь необходимо вычислять новые λ n {displaystyle lambda quad n} раз за один шаг.

    Алгоритм

  • Задаются начальное приближение и точность расчёта x → 0 0 , ε {displaystyle {vec {x}}_{0}^{0},quad varepsilon }
  • Рассчитывают { x → 1 [ j ] = x → 0 [ j ] − λ 1 [ j ] ∂ F ( x → 0 [ j ] ) ∂ x 1 e → 1 … x → n [ j ] = x → n − 1 [ j ] − λ n [ j ] ∂ F ( x → n − 1 [ j ] ) ∂ x n e → n {displaystyle left{{egin{array}{lcr}{vec {x}}_{1}^{[j]}&=&{vec {x}}_{0}^{[j]}-lambda _{1}^{[j]}{frac {partial F({vec {x}}_{0}^{[j]})}{partial x_{1}}}{vec {e}}_{1}ldots &&{vec {x}}_{n}^{[j]}&=&{vec {x}}_{n-1}^{[j]}-lambda _{n}^{[j]}{frac {partial F({vec {x}}_{n-1}^{[j]})}{partial x_{n}}}{vec {e}}_{n}end{array}} ight.} , где λ i [ j ] = a r g m i n λ F ( x → i − 1 [ j ] − λ [ j ] ∂ F ( x → i − 1 [ j ] ) ∂ x i e → i ) {displaystyle lambda _{i}^{[j]}=mathrm {argmin} _{lambda },Fleft({vec {x}}_{i-1}^{[j]}-lambda ^{[j]}{frac {partial F({vec {x}}_{i-1}^{[j]})}{partial x_{i}}}{vec {e}}_{i} ight)}
  • Проверяют условие остановки:
    • Если | x → n [ j ] − x → 0 [ j ] | > ε {displaystyle |{vec {x}}_{n}^{[j]}-{vec {x}}_{0}^{[j]}|>varepsilon } , то x → 0 [ j + 1 ] = x → n [ j ] , j = j + 1 {displaystyle {vec {x}}_{0}^{[j+1]}={vec {x}}_{n}^{[j]},quad j=j+1} и переход к шагу 2.
    • Иначе x → = x → n [ j ] {displaystyle {vec {x}}={vec {x}}_{n}^{[j]}} и останов.

    • Метод сопряжённых градиентов

    Метод сопряженных градиентов основывается на понятиях прямого метода многомерной оптимизации — метода сопряжённых направлений.

    Применение метода к квадратичным функциям в R n {displaystyle mathbb {R} ^{n}} определяет минимум за n {displaystyle n} шагов.

    Алгоритм

  • Задаются начальным приближением и погрешностью: x → 0 , ε , k = 0 {displaystyle {vec {x}}_{0},quad varepsilon ,quad k=0}
  • Рассчитывают начальное направление: j = 0 , S → k j = − ∇ f ( x → k ) , x → k j = x → k {displaystyle j=0,quad {vec {S}}_{k}^{j}=- abla f({vec {x}}_{k}),quad {vec {x}}_{k}^{j}={vec {x}}_{k}}
  • x → k j + 1 = x → k j + λ S → k j , λ = arg ⁡ min λ f ( x → k j + λ S → k j ) , S → k j + 1 = − ∇ f ( x → k j + 1 ) + ω S → k j , ω = | | ∇ f ( x → k j + 1 ) | | 2 | | ∇ f ( x → k j ) | | 2 {displaystyle {vec {x}}_{k}^{j+1}={vec {x}}_{k}^{j}+lambda {vec {S}}_{k}^{j},quad lambda =arg min _{lambda }f({vec {x}}_{k}^{j}+lambda {vec {S}}_{k}^{j}),quad {vec {S}}_{k}^{j+1}=- abla f({vec {x}}_{k}^{j+1})+omega {vec {S}}_{k}^{j},quad omega ={frac {|| abla f({vec {x}}_{k}^{j+1})||^{2}}{|| abla f({vec {x}}_{k}^{j})||^{2}}}}
    • Если | | S → k j + 1 | | < ε {displaystyle ||{vec {S}}_{k}^{j+1}||<varepsilon } или | | x → k j + 1 − x → k j | | < ε {displaystyle ||{vec {x}}_{k}^{j+1}-{vec {x}}_{k}^{j}||<varepsilon } , то x → = x → k j + 1 {displaystyle {vec {x}}={vec {x}}_{k}^{j+1}} и останов.
    • Иначе
      • если ( j + 1 ) < n {displaystyle (j+1)<n} , то j = j + 1 {displaystyle j=j+1} и переход к 3;
      • иначе x → k + 1 = x → k j + 1 , k = k + 1 {displaystyle {vec {x}}_{k+1}={vec {x}}_{k}^{j+1},quad k=k+1} и переход к 2.


    • Имя:*
    E-Mail:
    Комментарий: