Читать практическое задание по математике: "Градієнтні методи" Страница 1

(Назад) (Cкачать работу)

Міністерство освіти і науки України

НТУУ КПІ

Кафедра АПЕПС Лабораторна робота

по темі "Градієнтні методи" Виконала

ст. 3-го курсу

ТЕФ, гр. ТМ-81

Кошева А.С. Київ 2010

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

Задача багатомірної безумовної оптимізації формулюється у вигляді: де x={x (1), x (2), …, x (n) } - точка в n-мірному просторі X=IRn, тобто цільова функція f (x) =f (x (1),…,f (x (n)) - функція n аргументів.

Так само як і в першій лабораторній роботі ми розглядаємо задачу мінімізації. Чисельні методи відшукання мінімуму, як правило, складаються в побудові послідовності точок {xk}, що задовольняють умові f (x0) >f (x1) >…>f (xn) >…. Методи побудови таких послідовностей називаються методами спуску. У цих методах точки послідовності {xk} обчислюються за формулою: хk+1 = xk + kpk, k=0,1,2,…, де pk - напрямок спуску, k - довжина кроку в цьому напрямку.

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

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

xk+1 = xk - k f’ (xk), k>0, k=0, 1, 2, … У координатній формі цей процес записується в такий спосіб:

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

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

Реалізація методу

Похожие работы