Чисельна оптимізація в Matlab

1. Загальні відомості
2. Пошук екстремумів в Matlab
3. Стандартні методи Matlab
4. Метод Ньютона Matlab
5. висновок

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

Загальні відомості

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

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

Якщо не зрозуміло - ось простий приклад з усіма відомої параболою:

У цій функції є один мінімум, і він знаходиться в точці x = 0. Ця точка називається точкою мінімуму, а саме значення цієї функції є мінімум (він теж дорівнює 0). Максимумів у цій функції немає, але якби функцію перевернули догори ногами, то він би з'явився.

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

Пошук екстремумів в Matlab

І тепер, коли ви хоч якось познайомилися з поняттями оптимізації і знаходження екстремумів функції, можемо перейти до знаходження максимумів і мінімумів в Matlab. Далі, як зазвичай ми будемо розбирати приклади різної складності. Частина прикладів буде містити в собі стандартні команди Matlab для знаходження мінімуму і максимуму функції, а інша частина - це реалізація методу з нуля.

Стандартні методи Matlab

Розберемо 2 завдання знаходження мінімуму в Matlab:

1 приклад. Обчислити мінімум функції f (x) = - x1 / x, визначивши графічно інтервал його локалізації. Обчислення провести з мінімальним кроком по аргументу 1 * 10-5

Для початку створимо скрипт, який відобразить цю функцію. Ось код для цього:

x = 0.00001: 0.00001: 10; y = - x. ^ (X. ^ (- 1)); plot (x, y); hold on; grid on;

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

Тепер створимо ще один скрипт, дамо йому назву first.m і пропишемо в нього функцію:

function fun = first (x) fun = - x. ^ (X. ^ (- 1)); end

Таким чином в цьому m-файлі ми визначили функцію. Тепер в командному вікні ми пропишемо наступний код:

>> [X, y] = fminbnd (@first, 2.5, 3)

І отримуємо такі значення:
x = 2.7183 - координата точки мінімуму
y = -1.4447 - значення мінімуму

У цій частині коду ми використовували стандартний метод Matlab для знаходження мінімуму функції - fminbnd. ми передаємо 3 параметра - саму функцію і інтервали для пошуку мінімуму. Варто зазначити, що цей метод підходить тільки для функцій, що залежать від однієї змінної.

Отже, для цього завдання ми створили 2 скрипт-файлу, які ви можете завантажити в кінці статті.

2 приклад. Обчислити мінімум функції двох змінних x4 + y4-2x2 + 4xy-2y2 + 1 з точність 1 * 10-5.
Координати початкової точки пошуку [1.0, -1.0].

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

[Xy] = meshgrid (- 2: 0.1: 2, - 2: 0.1: 2); z = x. ^ 4 + y. ^ 4 - 2 * x. ^ 2 + 4 * x. * Y - 2 * y. ^ 2 + 1; surf (x, y, z);

Функція surf дозволяє будувати тривимірні графіки і відображати глибину значень функції для кращого розуміння. Запускаємо скрипт - в результаті вийшов такий графік:
Як видно з графіка, є дві ділянки, де присутня локальний мінімум (темно-сині ділянки), і наше завдання знайти координати і значення двох цих точок. Скористаємося стандартними інструментами Matlab і створимо новий скрипт з ім'ям second.m, в якому і пропишемо код:

function fun = second (x) fun = x (1) ^ 4 + x (2) ^ 4 - 2 * x (1) ^ 2 + 4 * x (1) * x (2) - 2 * x (2) ^ 2 + 1; end

Після цього, в командному рядку, як і для першого завдання, прописуємо стандартну функцію Matlab:

>> [Z, f, exitflag, output] = fminsearch (@second, [1.0, - 1.0], optimset ( 'TolX', 1e-5))

Отримуємо такий висновок:

z = 1.4142 -1.4142 f = -7.0000 exitflag = 1 output = iterations: 40 funcCount: 74 algorithm: 'Nelder-Mead simplex direct search' message: [1x196 char]

Для знаходження мінімумів в Matlab на цей раз ми використовували функцію fminsearch. Ця функція реалізує симплекс - метод Нелдера-Міда. У висновку ми отримали кілька змінних: в z записалися значення координат точок мінімуму, в f саме значення цього мінімуму. А в змінних exitflag і output поміщені умови переривання процесу пошуку та інформація про оптимізацію відповідно.

В результаті у нас знову вийшло 2 m-файлу.

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

А тепер спробуємо самі реалізувати метод Ньютона для оптимізації функції.

3 приклад. Методом Ньютона знайти точку мінімуму x * і мінімальне значення f * функції f (x) = (x-2) 4-lnx на відрізку xє [2; 3] c точністю 10-7

Почнемо з того, що створимо новий скрипт і назвемо його Newton.m. Потім пропишемо в ньому код:

function [Xk, Yk] = Newton (f, diap) a = diap (1); % Кордони b = diap (2); df = char (diff (sym (f))); % Символьно шукаємо першу ddf = char (diff (sym (df))); % І другу похідні F = inline (f); % Перетворимо в функції F1 = inline (df); F2 = inline (ddf); eps = 0.0000001; % Задаємо точність if F (a) * F2 (a)> 0% перевірка з якої межі починати шукати Xk = b; else Xk = a; end while abs (F1 (Xk))> eps X0 = Xk; % X0 - значення попереднього кроку Xk = X0 - (F1 (X0) / (F2 (X0))); % Розрахунок нового значення Yk = F (Xk); end end

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

>> Fun = '(x-2) ^ 4 - log (x)'; >> Diap = [2, 3]; >> [Xk, Yk] = Newton (fun, diap);

У підсумку вийшло:
Xk = 2.4663
Yk = -0.8554

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

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

висновок

Ну що ж, в цій статті ми розглянули деякі методи для знаходження екстремумів в Matlab. Ми використовували як стандартні методи, так і реалізували метод Ньютона в середовищі Matlab. Їх вихідні трохи нижче.
завантажити вихідні

На цьому сьогодні все, залишайте ваші коментарі і задавайте питання.

схоже