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

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

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

  1. У поле «Функція» — X*X+Y*Y-16.
  2. У поле «Список змінних» — X;Y.
  3. У поле «Початкове значення» — 0;0.

Після того, як всі поля заповнено, головна форма набуде наступного вигляду:

Читати повністю

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

В даному параграфі розглядається delphi-проект, який використовуючи метод Ньютона знаходить мінімум функції двох змінних. За допомогою даного методу часто вдається за невелику кількість ітерацій отримувати рішення задачі на безумовний мінімум з високою точністю. Однак, при практичному застосуванні метод Ньютона вимагає значних обчислювальних витрат. Це зумовлено тим, що на кожній ітерації доводиться обчислювати градієнт функції (вектор, елементами якого є частинні похідні першого порядку), обчислювати елементи матриці Гессе (для визначення яких необхідно знайти частинні похідні другого порядку від заданої функції) та знаходження оберненої матриці. Більш детальний опис алгоритму мінімізації функції за даним методом можна знайти за посиланням мінімізація функції багатьох змінних використовуючи методом Ньютона.

Результатом роботи програми, є побудова графіка функції використовуючи компонент Plot3D, вивід в статусний рядок (міститься в нижній частині форми) координатів точки мінімуму та обчислення значення функції в цій точці. Також відмітимо, що дана програма не є універсальною, тобто мінімізує лише  задану функцію.

Читати повністю

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

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

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

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

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

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

Читати повністю

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

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

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

Читати повністю

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

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

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

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

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

Читати повністю

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

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

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

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

Читати повністю

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

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

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

Читати повністю