Эволюция и психика

Эволюция и психика

Міністерство освіти і науки, молоді та спорту України

Курсова робота

Прямі методи безумовної мінімізації функцій

ЗМІСТ

Вступ

І. Формулювання задачі мінімізації. Основні поняття

.1 Формулювання задачі мінімізації

.2 Мінімум функції однієї змінної

.3 Мінімум функції багатьох змінних

.4 Унімодальні функції

.5 Опуклі функції

.6 Прямі методи безумовної мінімізації

ІІ. Прямі методи одновимірної безумовної оптимізації

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

.2 Метод золотого перерізу

ІІІ. Прямі методи безумовної мінімізації функцій багатьох змінних

.1 Метод покоординатного циклічного спуску

.2 Алгоритм Хука-Дживса

.3 Метод правильного симплексу

.5 Метод деформованого симплексу

Висновки

Перелік використаної літератури

Вступ

безумовна мінімізація функція

Задача мінімізації завжди була гостро актуальною, а останнім часом, з прискореним розвитком різних областей науки і техніки, вона набула ще більш вагомішого значення. Так як поведінку будь-якого фізичного об'єкта можна описати певною функціональною залежністю (тобто створити математичну модель реального об'єкта), то питання найоптимальнішого використання даного об'єкта призводить до необхідності розв'язання відповідної задачі оптимізації. Кожну задачу оптимізації, зрештою, можна звести до розв'язання задачі мінімізації (для того, щоб знайти максимум функції f(x) достатньо знайти мінімум функції -f(x)). Саме тому методи мінімізації дозволяють вирішувати такі питання як: оптимальне управління, максимізація доходів підприємста, мінімізація похибок експериментальних вимірювань, тощо. Без використання методів мінімізації, зокрема, не можливо собі уявити обробку експериментальних даних у сучасній фізіці.

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

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

. проаналізувати прямі методи одновимірної безумовної мінімізації такі як метод дихотомії та золотого перерізу,

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

. для зазначених методів описати покроково відповідні алгоритми.

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

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

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

І. Формулювання задачі мінімізації. Основні поняття

.1 Формулювання задачі мінімізації

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

Під мінімізацією функції n змінних f (x) = f(x1,.., xn) на заданій множині U n-мірного векторного простору Еn розуміють визначення хоча б однієї з точок мінімуму цієї функції на множині U, а також, якщо це необхідно, і мінімального на U значення f(x). Записуючи математичні задачі мінімізації в загальному вигляді, зазвичай, використовують наступну символіку:

f(x) ®min, хÎ U,

де f(x) - цільова функція, U - множина допустимих значень змінних.

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

Якщо область допустимих значень вихідної функції задана, тобто є обмеження, то мінімізація називається умовною.

Якщо ж обмежень немає, тобто областю визначення є область існування функції f(x), то така мінімізація називається безумовною.

1.2 Мінімум функції однієї змінної

Нехай функція f (x) визначена на множині U дійсної осі R.

. Число х*Î U називають точкою глобального (абсолютного) мінімуму або просто точкою мінімуму функції f(x) на множині U, якщо f(x*)£ f(x) для всіх хÎ U.

Значення f* = f(x*) називають глобальним (абсолютним) мінімумом або просто мінімумом функції f(x) на множині U.

Множину усіх точок мінімуму f(x) на U надалі будемо позначати через U*.

2. Число ÎU називається точкою локального мінімуму функції f(x), якщо  для всіх xÎU достатньо близьких до , тобто якщо існує e >0 таке, що ця нерівність виконується для будь-кого .

Глобальний мінімум f(x) є і локальним мінімумом, а зворотне невірно.

1.3 Мінімум функції багатьох змінних

Будемо розглядати функції багатьох змінних f = f(x1, …, xn) як функції, задані в точках х n-вимірного евклідового простору Еn: f =f(х).

1. Точка х*ÎЕn, називається точкою глобального мінімуму функції f(х), якщо для всіх х*ÎЕn виконується нерівність f(x*) £ f(х). Значення f(x*)= називається мінімумом функції. Множину усіх точок глобального мінімуму функції f(х) будемо позначати через U*.

. Точка  називається точкою локального мінімуму функції f(х), якщо існує e-окіл точки : Un () ={x | r (x, )<e} такий, що для всіх х*ÎUn() виконується нерівність f() £ f(х).

. Якщо допустима множина U в задачі мінімізації функції n змінних збігається з усім простором En, то говорять про задачу безумовної мінімізації , x Î En.

1.4 Унімодальні функції

Якщо функція f(x) на множині U має, крім глобального, локальні мінімуми, відмінні від нього, то мінімізація f(x), як правило, сильно ускладнюється. Зокрема, багато методів пошуку точки мінімуму f(x) пристосовані тільки для функцій, у яких кожен локальний мінімум є одночасно і глобальним. Цією властивістю володіють унімодальні функції.

Функція f(x) називається унімодальною на відрізку [а; b], якщо вона неперервна на [а; b] і існують числа a та b, , такі, що:

) якщо а < a, то на відрізку [a; a] функція f(x) монотонно спадає;

) якщо b < b, то на відрізку [b; b] функція f(x) монотонно зростає;

) при х Î [a; b]: f(x) =f *= .

Множину унімодальних на відрізку [а; b] функцій ми будемо позначати через Q [а; b]. Зазначимо, що можливе виродження в точку одного або двох відрізків з [a; a], [a; b] і [b; b]. Деякі випадки розташування і виродження в точку відрізків монотонності та сталості унімодальної функції показані на малюнку 1.

Рисунок 1 - Деякі випадки розташування і виродження в точку відрізків монотонності та сталості унімодальної функції

Основні властивості унімодальних функцій:

. Будь-яка з точок локального мінімуму унімодальної функції є і точкою її глобального мінімуму на відрізку [а; b].

. Функція, унімодальна на відрізку [а; b], є унімодальною і на будь-якому меншому відрізку [с; d]  [а; b].

. Нехай f(x) Q [а; b] і , тоді:

якщо, то x*[a; x2] ;

якщо , то x* [x1; b],

де х* - одна з точок мінімуму f(x) на відрізку [a; b].

Функція f(x), задана на відрізку [a; b], називається опуклою на цьому відрізку, якщо для всіх х', х"  [а; b] і для довільного числа  [0; 1] виконується нерівність

[ax'+ (1- a) x"] £ af(x') + (1 - a) f(x"). (1)

Перерахуємо основні властивості опуклих функцій.

. Якщо функція f(x) опукла на [a; b], то на будь-якому відрізку [х'; х"] Ì [a; b] її графік розташований не вище хорди, проведеної через точки графіка з абсцисами х' і х" (рисунок 2).

Рисунок 2 - Взаємне розташування

Нехай х' і х" - довільні точки відрізка [a; b], причому х' < х". Легко перевірити, що при будь-якому a Î [0; 1] точка xa = ax' + (1 - a) x" лежить на відрізку [x'; х"] і при неперервній зміні a від 0 до 1 точка xa пробігає цей відрізок від точки х" (при a = 0) до точки x' (при a = 1).

Розглянемо хорду графіка f(x), що проходить через точки (х',f(х')) і (х",f(х")). Ордината ya точки цієї хорди, що відповідає абсциссі xa , рівна af(x') + (1 - a)f(x"). Тому нерівність (1) означає, що f(xa) £ ya , тобто при будь-якому розташуванні xa на відрізку [х'; х"] точка графіка функції f(x) лежить не вище відповідної точки хорди.

. З курсу математичного аналізу відомі наступні умови опуклості функції:

а) для того щоб дифференційовна на відрізку [а; b] функція f(x) була опуклою на цьому відрізку, необхідно і достатньо, щоб похідна f '(x) не спадала на [а; b];

б) для того щоб двічі дифференційовна на відрізку [а; b] функція f(x) була опуклою на цьому відрізку, необхідно і достатньо, щоб при всіх хÎ[а; b] виконувалася нерівність f "(x) ³ 0.

. Умова опуклості для дифференційовної на відрізку [а; b] функції f(x) означає, що на цьому відрізку будь дотична до графіка f(x) лежить не вище цього графіка (рисунок 3).

Рисунок 3 - Умова опуклості

Рівняння дотичної до графіка f(х) в точці (x0, f(x0)), x0 Î [а; b] має вигляд: у(х) =f(x0) +f '(x0) (x - x0). За формулою кінцевих приростів для будь-якого хÎ[а; b] маємо: f(х) =f(x0) +f '(x) (x - x0), де точка x лежить між x і x0. Тому

(х) - у (х) = [f '(x) - f '(x0)] (x - x0), хÎ [а; b],

звідки з урахуванням того, що похідна f '(x) опуклої функції не спадає, отримуємо:

(x) - y(x) ³ 0 (2)

для всіх хÎ [а; b].

. Якщо f(x) - опукла дифференційовна на відрізку [а; b] функція і в точці х* Î [а; b] виконується рівність'(x*) = 0 (3)

то х* є точкою глобального мінімуму f(х) на [а; b].

З урахуванням (3) рівняння дотичної у(х) =f(х0) +f '(х0) (х-х0) до графіка f(x) для точки x0 =х* приймає вигляд у(х) =f(x*). Тому з (2) випливає, що f(x)f(x*) для всіх хÎ [а; b], тобто х* - точка глобального мінімуму f(x).

Завдяки властивості 3 опуклих функцій дана властивість набуває простий геометричний зміст: оскільки дотична до графіка f(x) в точці з абсцисою х* горизонтальна, а цей графік розташований не нижче дотичної, то х* є точкою мінімуму f(x) (рисунок 3) .

. Можна показати, що будь-яка опукла неперервна на відрізку [а; b] функція є і унімодальною на цьому відрізку. Зворотне, взагалі кажучи, невірне (рисунок 4).

Рисунок 4 - Графік унімодальної, але не опуклої функції

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

.6 Прямі методи безумовної мінімізації

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

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

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

ІІ. Прямі методи одновимірної безумовної оптимізації

Нехай а<x1<х2<b. Порівнявши значення f(x) в точках x1 і х2 (пробних точках), можна скоротити відрізок пошуку точки х*, перейшовши до відрізка [а; х2], якщо  або до відрізка [x1; b] якщо  (рисунок 5). Описану процедуру можна повторити необхідну кількість разів, послідовно зменшуючи відрізок, що містить точку мінімуму. Коли довжина останнього із знайдених відрізків стане досить малою, слід покласти , де  - одна з точок цього відрізка, наприклад, його середина. Методи мінімізації, що грунтуються на цьому принципі, називаються методами виключення відрізків.

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

Рисунок 5 - Зменшення відрізка пошуку точки мінімуму методами виключення відрізків

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

Суть методу полягає в тому, що заданий відрізок [а; b] ділять навпіл: . Потім у кожній з половин відрізка [а; с] і [с; b] вибирають по одній точці x1 і х2, і в них обчислюють значення функції, проводять порівняння отриманих значень, і в результаті порівняння встановлюють відрізок, в якому мінімуму бути не може. Відкинувши його, продовжують ту ж процедуру з отриманим відрізком до тих пір, поки знову отриманий відрізок не стане менше по довжині деякої наперед заданої величини:

.

Швидкість досягнення очевидно залежить від величини відрізка, що відкидається. Тому x1 і х2 вибирають симетрично на відстані d := с-d , х2= с+d (4)

де d > 0 - мале число.

В кінці обчислень за методом дихотомії в якості наближеного значення х* приймають середину останнього із знайдених відрізків [а; b], переконавшись попередньо, що має місце нерівність .

Опишемо алгоритм методу поділу відрізка навпіл.

Крок 0. Задати  та d.

Крок 1. Визначити середину відрізка та значення x1 і х2 за формулами (4). Обчислити f(x1) і f(x2).

Крок 2. Порівняти f(x1) і f(x2). Якщо, то перейти до відрізка [а; x2], поклавши b = x2, інакше - до відрізка [x1; b], поклавши а = x1.

Крок 3. Знайти досягнуту точність . Якщо  то перейти до наступної ітерації, повернувшись до кроку 1. Якщо , то завершити пошук х*, перейшовши до кроку 4.

Крок 4. Покласти

.

Зауваження:

. Число d вибирають з інтервалу (0; 2e) з урахуванням наступних міркувань:

а) чим менше d, тим більше відносне зменшення довжини відрізка на кожній ітерації, тобто при зменшенні d досягається більш висока швидкість збіжності методу дихотомії;

б) при надмірно малому d порівняння значень f(x) в точках x1 і х2, що відрізняються на величину 2d, стає проблематичним. Тому вибір d повинен бути узгоджений з точністю визначення f(x) і з кількістю точних десяткових знаків при заданні аргументу х.

2. Нехай  - похибка обчислень. Тоді слід враховувати наступну умову:

.

2.2 Метод золотого перерізу

Розглянемо таке симетричне розташування точок x1 і х2 на відрізку [а; b], при якому одна з них стає пробною точкою і на новому відрізку, отриманому після виключення частини вихідного відрізка. Використання таких точок дозволяє на кожній ітерації методу виключення відрізків, крім першої, обмежитись визначенням лише одного значення f(x), так як інше значення вже знайдено на одній з попередніх ітерацій.

Знайдемо точки x1 і х2, що володіють зазначеним властивістю.

Розглянемо спочатку відрізок [0; 1] і для визначеності припустимо, що при його зменшенні виключається права частина цього відрізка. Нехай х2 = t, тоді симетрично розташована точка х1 = 1-t (рисунок 6).

Рисунок 6 - Визначення пробних точок у методі золотого перерізу

Пробна точка х1 відрізка [0; 1] перейде в пробну точку х2¢ =1-t нового відрізка [0; t]. Щоб точки х2 = t і х2¢ = 1-t ділили відрізки [0; 1] і [0; t] відповідно в одному і тому ж відношенні, повинна виконуватись рівність  або , звідки знаходимо додатнє значення

…

Таким чином,

х1 = 1-t = , .

Для довільного відрізка [а; b] вирази для пробних точок приймуть вигляд

; . (5)

Зауваження:

. Точки x1 і х2 з (5) мають наступну властивість: кожна з них ділить відрізок [а; b] на дві нерівні частини так, що відношення довжини всього відрізка до довжини його більшої частини дорівнює відношенню довжин більшої і меншої частин відрізка. Точки з такою властивістю називаються точками золотого перерізу відрізка [а; b]. Це і пояснює назву даного методу.

. На кожній ітерації виключення відрізків з пробними точками (5) одна з них переходить на наступний відрізок і значення f(x) в цій точці обчислювати не потрібно. Якщо новим відрізком стає [а; х2], то на нього переходить пробна точка х1 вихідного відрізка, ставши при цьому його другою пробною точкою (х2¢= х1) (рисунок 6). У разі переходу до відрізка [х1;b] пробна точка х2 вихідного відрізка стає першою пробною точкою (х1¢=х2) відрізка [х1; b].

. В кінці обчислень за методом золотого перерізу в якості наближеного значення х* можна прийняти середину останнього з отриманих відрізків

.

Опишемо алгоритм методу золотого перерізу.

Крок 0. Задати . Знайти х1 і х2 за формулами (5). Обчислити f(x1) і f(x2).

Крок 1. Визначити . Перевірка умови закінчення пошуку: якщо en>e, то перейти до кроку 2, інакше - до кроку 3.

Крок 2. Перехід до нового відрізку і нових пробних точок. Якщо f(x1)£ f(x2) то покласти b=x2, x2=x1, f(x2) = f(x1), х1=а+b-х2 і обчислити f(x1), інакше - покласти a=x1, x1= x2, f(x1) = f(x2), x2=а+b-х1 і обчислити f(x2). Перейти до кроку 1.

Крок 3. Закінчення пошуку: покласти

, .

Порівнювання методів виключення відрізків. При порівнюванні прямих методів мінімізації зазвичай враховують кількість N обчислень значень f(x), що гарантує задану точність визначення точки х* тим чи іншим методом. Чим менше N, тим ефективнішим вважається метод. При цьому допоміжні операції такі, як вибір пробних точок, порівняння значень f(x) і т.п., не враховуються. У багатьох практичних випадках визначення значень цільової функції потребує великих затрат (наприклад, часу ЕОМ) і тому допоміжними обчисленнями можна знехтувати.

Ефективність методів мінімізації можна також порівнювати на підставі гарантованої точності e (N) визначення точки х*, яку вони забезпечують в результаті визначення N значень f(x). Метод золотого перерізу в цьому сенсі вважають «більш точним», ніж метод дихотомії, хоча різниця в точності в даному випадку незначна.

ІІІ. Прямі методи безумовної мінімізації функцій багатьох змінних

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

3.1 Метод покоординатного циклічного спуску

Цей метод полягає в послідовній мінімізації цільової функції f(x) за напрямками x2 і x1.

Рисунок 7 - Циклічний покоординатний спуск.

Опишемо цей алгоритм.

Крок 0. Вибрати початкову точку х(0) = (x1(0), x2(0)) Î E2, критерій досягнення точності e і крок . Обчислити f(x1(0), x2(0)).

Крок 1. Прийняти x1(1)=x1(0)+. Визначити f(x1(1), x2(0)). Порівняти отримане значення з початковим значенням функції. Якщо f(x1(1),x2(0))<f(x1(0),x2(0)), то перейти до кроку 5, якщо ж f(x1(1),x2(0))>f(x1(0),x2(0)), то перейти до кроку 2.

Крок 2. Прийняти x1(1)=x1(0)-. Визначити f(x1(1), x2(0)). Порівняти отримане значення з початковим значенням функції. Якщо f(x1(1),x2(0))<f(x1(0),x2(0)), то перейти до кроку 5, якщо ж f(x1(1),x2(0))>f(x1(0),x2(0)), то перейти до кроку 3.

Крок 3. Прийняти x2(1)= x2(0)+. Визначити f(x1(0), x2(1)). Порівняти отримане значення з початковим значенням функції. Якщо f(x1(0),x2(1))<f(x1(0),x2(0)), то перейти до кроку 5, якщо ж f(x1(0), x2(1)) > f(x1(0), x2(0)), то перейти до кроку 4.

Крок 4. Прийняти x2(1)= x2(0)-. Визначити f(x1(0), x2(1)). Порівняти отримане значення з початковим значенням функції. Якщо f(x1(0),x2(1))<f(x1(0),x2(0)), то перейти до кроку 5, якщо ж f(x1(0), x2(1)) > f(x1(0), x2(0)), то перейти до кроку 6.

Крок 5. Перевірити умову досягнення точності . Якщо нерівність виконується, то прийняти точку х(1) Î E2 за точку мінімуму функції, інакше - покласти х(0) = х(1) і перейти до кроку 1.

Крок 6. Перевірити умову досягнення точності . Якщо нерівність виконується, то прийняти початкову точку х(0) Î E2 за точку мінімуму функції, інакше - покласти  і перейти до кроку 1.

3.2 Алгоритм Хука-Дживса

Цей алгоритм містить дві основні процедури:
а) процедуру покоординатного пошуку в околі даної точки, призначену для визначення напрямку спадання f(х);

б) процедуру переміщення в напрямку спадання f(х).

Рисунок 8 - Метод Хука-Дживса

Розглянемо один з численних варіантів цього методу.

Крок 0. Вибираємо початкову точку (x0, y0) і знаходимо в ній значення функції f(x0, y0). Вибираємо кут напрямку руху .

Крок 1. Обчислюємо координати 4-х точок в околі початкової за наступними формулами:

Знаходимо в зазначених точках значення функції

Порівнюємо отримані значення між собою. Нехай , m = 1, 2, 3, 4. Якщо , то переходимо до кроку 3, інакше - переходимо до кроку 2.

Крок 2. Зменшуємо крок  і переходимо до кроку 3.

Крок 3. Перевіряємо умову досягнення точності . Якщо ця умова не виконується, то приймаємо  і повертаємось до кроку 1, інакше - точку  приймаємо за точку мінімуму функції.

3.3 Метод правильного симплексу

Правильним симплексом в просторі En називається множина з n + 1 рівновіддалених одна від одної точок (вершин симплексу). Відрізок, що зєднує дві вершини, називається ребром симплексу.

У просторі E2 правильним симплексом є сукупність вершин рівностороннього трикутника, в E3 - правильного тетраедра.

Якщо х0 - одна з вершин правильного симплексу в En то координати інших n вершин х1,. ., хn можна знайти, наприклад, за формулами:

 (6),

де d1 , d2 , a - довжина ребра, j=1, 2, …, n (тут j - це номер виміру простору En). Вершину х0 симплексу, побудованого за формулами (6), будемо називати бaзовою. В алгоритмі симплексного методу використовується наступна важлива властивість правильного симплексу. За відомим симплексом можна побудувати новий симплекс відображенням якої-небудь вершини, наприклад, хk симметрично щодо центру ваги хc інших вершин симплексу. Нова  і стара хk вершини пов'язані співвідношенням:

, де xc.

В результаті отримується новий правильний симплекс з тим же ребром і вершинами =2xc - хk, хi, i= 0, ..., n, i¹ k. Таким чином, відбувається переміщення симплексу в просторі Еn. На рисунку 9 представлена ​​ілюстрація цієї властивості симплексу в просторі Е2.

Рисунок 9 - Побудова нового симплексу в E2 відображенням точки х: a - початковий симплекс х0, х1, х2; б - новий симплекс х0, х1, ; центр відображення - точкa xc = (х0+ х1) /2 .

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

Крок 0. Вибрати параметр точності e, базову точку х0 = , ребро .

Крок 1. Побудувати початковий симплекс за формулами:

Крок 2. Обчислити значення f(х) в вершинах симплексу х0, ..., x2. Упорядкувати вершини симплексу х0,..., х2 так, щоб f (х0)£ f (х1)£ f (х2).

Крок 3. Знайти середнє значення функції:

.

Перевірити умову  з урахуванням того, що:

Якщо ця умова виконується, то обчислення припинити, вважаючи х* » х0, f * » f(x0). В протилежному випадку перейти до кроку 4.

Крок 4. Знайти

і виконати відображення вершини х2. Так як точка xc має координати , то відображена вершина  матиме координати:

.

Якщо f() < f(x2), то покласти х2 =  (тобто побудувати новий симплекс з вершинами х0, х1, ) і перейти до кроку 2, інакше - перейти до кроку 5.

Крок 5. Перейти до нового правильного симплексу з удвічі меншим ребром, вважаючи базовою вершиною х0. Тобто покласти а=а / 2 і перейти до кроку 1.

Рисунок 10 - Пошук точки мінімуму функції  за допомогою правильних симплексів в просторі

3.5 Метод деформованого симплексу

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

 (7)

Геометрична ілюстрація цих процедур для простору E2 приведена на рисунках 11 і 12.

Рисунок 11 - Пробні точки z1,z2,z3,z4 для переходу до нового симплексу

Рисунок 12 - Симплекси, отримані в результаті процедур стиснення (а, б); відображення (в); розтягування (г).

Так як величина a Î (0;1), то вибір точок z1 і z2 відповідає стисненню симплексу; b  1, а тому вибір точки z3 відповідає відображенню, а g > 1 і тому вибір точки z4 призводить до розтягування симплексу. Чисельні експерименти показують, що цей алгоритм добре працює в просторі En для n £ 6. Зазначимо, що при деформаціях втрачається властивість правильності вихідного симплексу. Тому, не прагнучи до правильності початкового симплексу, його будують з довільної базової точки х0 Î En, за формулами

, (8)

де ei - i-й базисний вектор; а - параметр симплексу. На практиці добре зарекомендував себе наступний набір параметрів a, b і g для вибору пробних точок zi в формулах (7): a = 1/2, b = 1 і g =2.

Опишемо алгоритм методу пошуку точки мінімуму функції за допомогою деформованого симплексу.

Крок 0. Вибрати параметр точності e, параметри a, b і g, базову точку х0, параметр а і побудувати початковий симплекс. Обчислити f(х0).

Крок 1. Обчислити значення функції в вершинах симплексу х1,..., xn.

Крок 2. Упорядкувати вершини х0,..., xn так, щоб f(х0) £ … £ f(хn).

Крок 3. Перевірити досягнення заданої точності. Якщо задану точність досягнуто, то обчислення завершити, прийнявши х* » х0, f* » f(х0). Інакше - перейти до кроку 4.

Крок 4. Знайти  і пробні точки zk, k=1, …, 4 за формулами (7). Знайти f(z*) = min f(zk). Якщо f(z*) < f(zn), то покласти xn=z* і перейти до кроку 2. Інакше - перейти до кроку 5.

Крок 5. Зменшити симплекс, поклавши хi = (хi + х0) /2, i = 1, ..., n і перейти до кроку 1.

З теоретичної точки зору описані симплексні методи мінімізації погано досліджені, однак практика показує їх працездатність.

Висновки

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

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

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

Перелік використаної літератури

1. Турчак Л.И. Основы численных методов: Учеб. пособие. - М.: Наука, Гл. ред. физ. - мат. лит., 1978. - 320 с.

2. Колесникова Е. В., Колесникова Л. И., Русин Л. Ю. Безградиентные методы оптимизации для исследований динамики элементарных процессов / Физико-химическая кинетика в газовой динамике - 2010 / www.chemphys.edu.ru/pdf/2010-10-25-001.pdf

3. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. - М.: Мир, 1985 -509с.

4. Дегтярев Ю.И., "Исследование операций", Москва 1986.