wiki

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

Метод сопряженных градиентов — метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в Rn{displaystyle mathbb {R} ^{n}}минимум находится за n{displaystyle n} шагов.

Содержание

Основные понятия

Определим терминологию:

Пусть S1→,…,Sn→∈X⊂Rn{displaystyle {vec {S_{1}}},ldots ,{vec {S_{n}}}in mathbb {X} subset mathbb {R} ^{n}!}

 .

Введём на X{displaystyle mathbb {X} !}

  целевую функцию f(x→)∈C2(X){displaystyle f({vec {x}})in mathrm {C^{2}} (mathbb {X} )!} .

Вектора S1→,…,Sn→{displaystyle {vec {S_{1}}},ldots ,{vec {S_{n}}}!}

  называются сопряжёнными, если:

  • Si→THSj→=0,i≠j,i,j=1,…,n{displaystyle {vec {S_{i}}}^{T}H{vec {S_{j}}}=0,quad ineq j,quad i,j=1,ldots ,n!} 
  • Si→THSi→⩾0,i=1,…,n{displaystyle {vec {S_{i}}}^{T}H{vec {S_{i}}}geqslant 0,quad i=1,ldots ,n!} 

где H{displaystyle H!}

  — матрица Гессе f(x→){displaystyle f({vec {x}})!} .

Logo arte.jpg  Теорема (о существовании).
Существует хотя бы одна система n{displaystyle n!}  сопряжённых направлений для матрицы H{displaystyle H!} , т.к. сама матрица H{displaystyle H!}  (её собственные вектора) представляет собой такую систему.

Обоснование метода

Нулевая итерация

  Иллюстрация последовательных приближений метода наискорейшего спуска (зелёная ломаная) и метода сопряжённых градиентов (красная ломаная) к точке экстремума.

Пусть S0→=−∇f(x0→)(1){displaystyle {vec {S_{0}}}=-nabla f({vec {x_{0}}})qquad (1)!}

 

Тогда x1→=x0→+λ1S0→(2){displaystyle {vec {x_{1}}}={vec {x_{0}}}+lambda _{1}{vec {S_{0}}}qquad (2)!}

 .

Определим направление S1→=−∇f(x1→)+ω1S0→{displaystyle {vec {S_{1}}}=-nabla f({vec {x_{1}}})+omega _{1}{vec {S_{0}}}!}

  так, чтобы оно было сопряжено с S0→{displaystyle {vec {S_{0}}}!} :

S0→THS1→=0(3){displaystyle {vec {S_{0}}}^{T}H{vec {S_{1}}}=0qquad (3)!} 

Разложим ∇f(x→){displaystyle nabla f({vec {x}})!}

  в окрестности x0→{displaystyle {vec {x_{0}}}!}  и подставим x→=x1→{displaystyle {vec {x}}={vec {x_{1}}}!} :

∇f(x1→)−∇f(x0→)=H(x1→−x0→)=λ1HS0→{displaystyle nabla f({vec {x_{1}}})-nabla f({vec {x_{0}}})=H,({vec {x_{1}}}-{vec {x_{0}}})=lambda _{1}H{vec {S_{0}}}!} 

Транспонируем полученное выражение и домножаем на H−1{displaystyle H^{-1}!}

  справа:

(∇f(x1→)−∇f(x0→))TH−1=λ1S0→THTH−1{displaystyle (nabla f({vec {x_{1}}})-nabla f({vec {x_{0}}}))^{T}H^{-1}=lambda _{1}{vec {S_{0}}}^{T}H^{T}H^{-1}!} 

В силу непрерывности вторых частных производных HT=H{displaystyle H^{T}=H!}

 . Тогда:

S0→T=(∇f(x1→)−∇f(x0→))TH−1λ1{displaystyle {vec {S_{0}}}^{T}={frac {(nabla f({vec {x_{1}}})-nabla f({vec {x_{0}}}))^{T}H^{-1}}{lambda _{1}}}!} 

Подставим полученное выражение в (3):

(∇f(x1→)−∇f(x0→))TH−1HS1→λ1=0{displaystyle {frac {(nabla f({vec {x_{1}}})-nabla f({vec {x_{0}}}))^{T}H^{-1}H{vec {S_{1}}}}{lambda _{1}}}=0!} 

Тогда, воспользовавшись (1) и (2):

(∇f(x1→)−∇f(x0→))T(−∇f(x1→)−ω1∇f(x0→)))=0(4){displaystyle (nabla f({vec {x_{1}}})-nabla f({vec {x_{0}}}))^{T}(-nabla f({vec {x_{1}}})-omega _{1}nabla f({vec {x_{0}}})))=0qquad (4)!} 

Если λ=arg⁡minλf(x0→+λS0→){displaystyle lambda =arg min _{lambda }f({vec {x_{0}}}+lambda {vec {S_{0}}})!}

 , то градиент в точке x1→=x0→+λS0→{displaystyle {vec {x_{1}}}={vec {x_{0}}}+lambda {vec {S_{0}}}!}  перпендикулярен градиенту в точке x0→{displaystyle {vec {x_{0}}}!} , тогда по правилам скалярного произведения векторов:

(∇f(x0→),∇f(x1→))=0{displaystyle (nabla f({vec {x_{0}}}),nabla f({vec {x_{1}}}))=0!} 

Приняв во внимание последнее, получим из выражения (4) окончательную формулу для вычисления ω{displaystyle omega !}

 :

ω1=||∇f(x1→)||2||∇f(x0→)||2{displaystyle omega _{1}={frac {||nabla f({vec {x_{1}}})||^{2}}{||nabla f({vec {x_{0}}})||^{2}}}!} 

К-я итерация

На k-й итерации имеем наборS0→,…,Sk−1→{displaystyle {vec {S_{0}}},ldots ,{vec {S_{k-1}}}!}

 .

Тогда следующее направление вычисляется по формуле:

Sk→=−∇f(x0→)+ω1S0→+…+ωkS→k−1,ωi=||∇f(xi→)||2||∇f(x→i−1)||2,{displaystyle {vec {S_{k}}}=-nabla f({vec {x_{0}}})+omega _{1}{vec {S_{0}}}+ldots +omega _{k}{vec {S}}_{k-1},quad omega _{i}={frac {||nabla f({vec {x_{i}}})||^{2}}{||nabla f({vec {x}}_{i-1})||^{2}}},!} 

где ωk{displaystyle omega _{k}!}

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

Это выражение может быть переписано в более удобном итеративном виде:

Sk→=−∇f(xk→)+ωkS→k−1{displaystyle {vec {S_{k}}}=-nabla f({vec {x_{k}}})+omega _{k}{vec {S}}_{k-1}!} 

Алгоритм

  • Пусть x→0{displaystyle {vec {x}}_{0}!}  — начальная точка, r→0{displaystyle {vec {r}}_{0}!}  — направление антиградиента и мы пытаемся найти минимум функции f(x→){displaystyle f({vec {x}})!} . Положим S→0=r→0{displaystyle {vec {S}}_{0}={vec {r}}_{0}!}  и найдем минимум вдоль направления S→0{displaystyle {vec {S}}_{0}!} . Обозначим точку минимума x→1{displaystyle {vec {x}}_{1}!} .
  • Пусть на некотором шаге мы находимся в точке x→k{displaystyle {vec {x}}_{k}!} , и r→k{displaystyle {vec {r}}_{k}!}  — направление антиградиента. Положим S→k=r→k+ωkS→k−1{displaystyle {vec {S}}_{k}={vec {r}}_{k}+omega _{k}{vec {S}}_{k-1}!} , где ωk{displaystyle omega _{k}!}  выбирают либо (r→k,r→k)(r→k−1,r→k−1){displaystyle {frac {({vec {r}}_{k},{vec {r}}_{k})}{({vec {r}}_{k-1},{vec {r}}_{k-1})}}!}  (стандартный алгоритм), либо max(0,(r→k,r→k−r→k−1)(r→k−1,r→k−1)){displaystyle max(0,{frac {({vec {r}}_{k},{vec {r}}_{k}-{vec {r}}_{k-1})}{({vec {r}}_{k-1},{vec {r}}_{k-1})}})!}  (алгоритм Полака–Райбера). После чего найдем минимум в направлении Sk→{displaystyle {vec {S_{k}}}!}  и обозначим точку минимума x→k+1{displaystyle {vec {x}}_{k+1}!} . Если в вычисленном направлении функция не уменьшается, то нужно забыть предыдущее направление, положив ωk=0{displaystyle omega _{k}=0!}  и повторив шаг.

Формализация

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

Случай квадратичной функции

Logo arte.jpg  Теорема.
Если сопряжённые направления используются для поиска минимума квадратичной функции, то эта функция может быть минимизирована за n{displaystyle n}  шагов, по одному в каждом направлении, причём порядок несущественен.

Литература

  1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
  2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
  3. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
  4. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
  5. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
  6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.

Ссылки

Читайте также