Оптимізація функції двох змінних використовуючи метод градієнтного спуску на Delphi
Метод градієнтного спуску, для знаходження мінімального значення функції використовує її градієнт і таким чином мінімізація функції на кожній ітерації відбувається у напрямку найшвидшого спадання, що значно прискорює процес пошуку оптимуму. Оптимізація функції при використанні методу градієнта проводиться в два етапа. На першому знаходяться значення частинних похідних по всіх незалежних змінних, які визначають напрям градієнта в розглядуваній точці. На другому етапі здійснюється крок у напрямку, зворотному напрямку градієнта, тобто в напрямку найшвидшого спадання цільової функції. І таким чином, на кожній ітерації, одночасно змінюються значення всіх незалежних змінних. Кожна з яких одержує приріст, пропорційний відповідній складовій градієнта по даній осі.
Алгоритм градієнтного методу розглядати не будемо, його можна знайти перейшовши за посиланням мінімізація функції декількох змінних використовуючи метод градієнтного спуску. Розглянимо лише delphi-проект, який реалізує даний алгоритм.
Мініиізація функції декількох змінних використовуючи метод градієнтного спуску
З курсу математики відомо, що напрямок найбільшого зростання будь-якої функції, в нашому випадку характеризується її градієнтом:
де — одиничні вектори у напрямку координатних осей. Отже, напрям, протилежний градієнтному, вкаже напрямок найбільшого спадання функції а методи, засновані на виборі шляху оптимізації за допомогою градієнта, називаються градієнтними.
Процес відшукання точки мінімуму функції за методом градієнтного спуску полягає в наступному: на початку вибираємо деяку початкову точку
і обчислюємо в ній градієнт функції
. Далі, робимо крок у антиградієнтному напрямку
(де
). У результаті отримуємо нову точку
, значення функції в якій зазвичай менше за значення функції в точці
. Якщо ця умова не виконується, тобто значення функції не змінилося або навіть зросла, то потрібно зменшити крок
(
), після чого, у новій точці обчислюємо градієнт і знову робимо крок у зворотному до нього напрямку
.
Мінімізація функції двох змінних методом покоординатного спуску засобами Delphi
Програма призначена для знаходження точки мінімуму функції двох змінних з заданою точністю. У програмі реалізовано метод покоординатного спуску, який для знаходження розв'язку вимагає вибір точки початкового наближення. Зауважимо, що від вибору даної точки залежить процес збіжності методу. Результатом роботи програми є вивід точки мінімуму та значення функції в даній точці.

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