Градієнтні методи

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

Постановка задачі розв'язання системи рівнянь в термінах методів оптимізації

Завдання рішення системи рівнянь:

${\displaystyle \left\{{\begin{array}{lcr}f_{1}(x_{1},x_{2},\ldots ,x_{n})&=&0\\\ldots &&\\f_{n}(x_{1},x_{2},\ldots ,x_{n})&=&0\end{array}}\right.}$(1)

з ${\displaystyle n}$ ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ еквівалентна задачі мінімізації функції

${\displaystyle F(x_{1},x_{2},\ldots ,x_{n})\equiv \sum _{i=1}^{n}|f_{i}(x_{1},x_{2},...,x_{n})|^{2}}$ (2)

або якій-небудь іншій зростаючій функції від абсолютних величин ${\displaystyle |f_{i}|}$ нев'язок (помилок) ${\displaystyle f_{i}=f_{i}(x_{1},x_{2},\ldots ,x_{n})}$, ${\displaystyle i=1,2,\ldots ,n}$. Завдання знаходження мінімуму (або максимуму) функції ${\displaystyle n}$ змінних і сама по собі має велике практичне значення.

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

${\displaystyle {\vec {x}}^{[j+1]}={\vec {x}}^{[j]}+\lambda ^{[j]}{\vec {v}}^{[j]}}$

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

${\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)

які зводяться до деякого рішенням ${\displaystyle {\vec {x}}^{[k]}}$ при ${\displaystyle {j\to \infty }}$.

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

${\displaystyle v_{1}^{[j]}:v_{2}^{[j]}:\ldots :v_{n}^{[j]}}$.

Величина кроку (відстань, на яку треба піднятися в заданому напрямку в пошуках екстремуму) визначається значенням параметра ${\displaystyle \lambda ^{[j]}}$, який мінімізує величину ${\displaystyle F(x_{1}^{[j+1]},x_{2}^{[j+1]},\ldots ,x_{n}^{[j+1]})}$ як функцію від ${\displaystyle \lambda ^{[j]}}$. Цю функцію зазвичай апроксимують її розкладанням у ряд Тейлора або інтерполяційним многочленом з трьох-п'яти вибраних значень ${\displaystyle \lambda ^{[j]}}$. Останній метод застосуємо для знаходження max і min таблично заданої функції ${\displaystyle F(x_{1},x_{2},...,x_{n}).}$

Градієнтні методи

Основна ідея методів полягає в тому, щоб йти в напрямку найшвидшого спуску, а це напрямок задається антиградієнтом ${\displaystyle -\nabla F}$:

${\displaystyle {\overrightarrow {x}}^{[j+1]}={\overrightarrow {x}}^{[j]}-\lambda ^{[j]}\nabla F({\overrightarrow {x}}^{[j]})}$

де ${\displaystyle \lambda ^{[j]}}$ вибирається:

• сталою, в цьому випадку метод може розходитися;
• дробовим кроком, тобто довжина кроку в процесі спуску ділиться на деяке число;
• якнайскорішим спуском: ${\displaystyle \lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F({\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F({\vec {x}}^{[j]}))}$

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

Вибирають ${\displaystyle v_{i}^{[j]}=-{\frac {\partial F}{\partial x_{i}}}}$, де всі похідні обчислюються при ${\displaystyle x_{i}=x_{i}^{[j]}}$, і зменшують довжину кроку ${\displaystyle \lambda ^{[j]}}$ по мірі наближення до мінімуму функції ${\displaystyle F}$.

Для аналітичних функцій ${\displaystyle F}$ і малих значень ${\displaystyle f_{i}}$ тейлорівський розклад ${\displaystyle F(\lambda ^{[j]})}$ дозволяє вибрати оптимальну величину кроку

${\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)

де всі похідні обчислюються при ${\displaystyle x_{i}=x_{i}^{[j]}}$. Параболічна інтерполяція функції ${\displaystyle F(\lambda ^{[j]})}$ може виявитися більш зручною.

Алгоритм

1. Задаються початкове наближення і точність розрахунку ${\displaystyle {\vec {x}}^{0},\quad \epsilon }$
2. Розраховують ${\displaystyle {\overrightarrow {x}}^{[j+1]}={\overrightarrow {x}}^{[j]}-\lambda ^{[j]}\nabla F({\overrightarrow {x}}^{[j]})}$, де ${\displaystyle \lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F({\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F({\vec {x}}^{[j]}))}$
3. Перевіряють умову зупинки:
   • Якщо ${\displaystyle |{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}|>\epsilon }$, то ${\displaystyle j=j+1}$ і перехід до кроку 2.
   • Інакше ${\displaystyle {\vec {x}}={\vec {x}}^{[j+1]}}$ і зупинка.

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

Цей метод названий за аналогією з методом Гауса — Зейделя для розв'язання системи лінійних рівнянь. Покращує попередній метод за рахунок того, що на черговій ітерації спуск здійснюється поступово уздовж кожної з координат, однак тепер необхідно обчислювати нові ${\displaystyle \lambda n}$ раз за один крок.

Алгоритм

1. Задаються початкове наближення і точність розрахунку ${\displaystyle {\vec {x}}_{0}^{0},\quad \varepsilon }$
2. Розраховують${\displaystyle \left\{{\begin{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}}\right.}$, де ${\displaystyle \lambda _{i}^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}_{i-1}^{[j]}-\lambda ^{[j]}{\frac {\partial F({\vec {x}}_{i-1}^{[j]})}{\partial x_{i}}}{\vec {e}}_{i}\right)}$
3. Перевірють умову зупинки:
   • Якщо ${\displaystyle |{\vec {x}}_{n}^{[j]}-{\vec {x}}_{0}^{[j]}|>\varepsilon }$, то ${\displaystyle {\vec {x}}_{0}^{[j+1]}={\vec {x}}_{n}^{[j]},\quad j=j+1}$ і перехід до кроку 2.
   • Інакше ${\displaystyle {\vec {x}}={\vec {x}}_{n}^{[j]}}$ і зупинка.

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

Докладніше: Метод спряженого градієнта

Метод спряжених градієнтів ґрунтується на поняттях прямого методу багатовимірної оптимізації — методу спряжених напрямів.

Застосування методу до квадратичних функцій ${\displaystyle \mathbb {R} ^{n}}$ визначає мінімум за ${\displaystyle n}$ кроків.

Алгоритм

1. Задаються початковим наближенням і похибкою: ${\displaystyle {\vec {x}}_{0},\quad \varepsilon ,\quad k=0}$
2. Розраховують початковий напрямок: ${\displaystyle j=0,\quad {\vec {S}}_{k}^{j}=-\nabla f({\vec {x}}_{k}),\quad {\vec {x}}_{k}^{j}={\vec {x}}_{k}}$
3. ${\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}}}}$
   • Якщо ${\displaystyle ||{\vec {S}}_{k}^{j+1}||<\varepsilon }$ або ${\displaystyle ||{\vec {x}}_{k}^{j+1}-{\vec {x}}_{k}^{j}||<\varepsilon }$, то ${\displaystyle {\vec {x}}={\vec {x}}_{k}^{j+1}}$ і зупинка.
   • Інакше
     
     • якщо ${\displaystyle (j+1)<n}$, то ${\displaystyle j=j+1}$ і перехід до 3;
     • ${\displaystyle {\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1}$ і перехід до 2.

Див. також

• Інтерполяційні формули
• Математичне програмування
  • Метод градієнта
  • Метод спряжених градієнтів
  • Прямі методи
• Формула Тейлора
• Чисельні методи
  • (Чисельні методи розв'язання рівнянь)
  • Метод Нелдера — Міда

Література

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