Оптимізація функції багатьох змінних методом покоординатного спуску

Нехай дано деяку функцію Метод покоординатного спуску для якої потрібно визначити мінімальне значення. Для цього, в якості початкового наближення, виберемо деяку точку Метод покоординатного спуску. Далі, підставимо в функцію Метод покоординатного спуску всі точки початкового наближення крім першої. Тоді отримаємо функцію однієї змінної Метод покоординатного спуску. Знайшовши для даної функції точку мінімуму, переходимо від точки Метод покоординатного спуску до точки Метод покоординатного спуску в якій функція Метод покоординатного спуску приймає мінімальне значення по координаті Метод покоординатного спуску. У цьому полягає перший крок процесу оптимізації, що складається в спуску по координаті Метод покоординатного спуску (для знаходження точки мінімуму функції однієї змінної можна використовувати наступні методи: методом дихотомії, методом Фібоначі, методом золотого перетину,...).

Підставимо тепер в функцію Метод покоординатного спуску всі координати точки Метод покоординатного спуску крім Метод покоординатного спуску, і розглянемо функцію виду Метод покоординатного спуску. Знову вирішуючи одновимірну задачу оптимізації, знаходимо нову точку Метод покоординатного спуску, в якій функція Метод покоординатного спуску приймає мінімальне значення по координаті Метод покоординатного спуску. Аналогічним чином проводиться спуск по координатах Метод покоординатного спуску після чого процедура знову повторюється від Метод покоординатного спуску до Метод покоординатного спуску. В результаті даного процесу отримуємо послідовність точок Метод покоординатного спуску в яких значення цільової функції складають монотонно спадну послідовність Метод покоординатного спуску. Відмітимо, що на будь-якому Метод покоординатного спуску-му кроці данний процес можна призупинити, і в якості мінімального значення функції приймається  Метод покоординатного спуску.

Таким чином, метод покоординатного спуску зводить задачу про знаходження найменшого значення функції багатьох змінних до багаторазового рішенням одновимірних задач оптимізації по кожній з цих змінних.

Давайте продемонструємо даний процес для функції, яка описує деяку поверхність в тривимірному просторі, тобто являється функцією двох змінних виду Метод покоординатного спуску. Процес оптимізації в цьому випадку проходить наступним чином: в якості початкового наближення береться точка Метод покоординатного спуску після чого проводиться спуск по координаті Метод покоординатного спуску (попадаємо в точку Метод покоординатного спуску); далі проводимо спуск по координаті Метод покоординатного спуску (попадаємо в точку Метод покоординатного спуску) і так далі продовжуємо даний процес.

Графічне представлення методу покоординатного спуску

Графічне представлення методу покоординатного спуску

Також слід зазначити, що процес збіжності методу покоординатного спуску залежить від виду самої функції та вибору початкового наближення.

Блок-схема програмної реалізації методу покоординатного спуску для функції двох змінних:

Метод покоординатного спуску

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар