Категорія: Пошук екстремумів функцій

Мінімізація функції однієї змінної методом рівномірного пошуку

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

Читати далі

Мінімізація функції методами других порядків (метод Ньютона)

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

Метод Ньютона

де Метод Ньютона – квадратна матриця (матриця Гессе), елементами якої є частинні похідні другого порядку функції optumizacija_metodom_njytona4 в точці Метод Ньютона і які можна обчислити за наступною формулою:

Метод Ньютона

Далі, для визначення напрямку пошуку точки мінімуму за методом Ньютона, замінимо в виразі (1) Метод Ньютона на Метод Ньютона і Метод Ньютона на Метод Ньютона. В результаті отримаємо:

Читати далі

Мініиізація функції декількох змінних використовуючи метод градієнтного спуску

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

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

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

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

Читати далі

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

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

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

Читати далі

Мінімізація функції однієї змінної методом дихотомії

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

Метод дихотомії

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

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

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

Читати далі