Градієнтні методи — Вікіпедія

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

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

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

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

Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її.

Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки. Матеріал без джерел може бути піддано сумніву та вилучено. (жовтень 2017)