Лекція №6-7 оптимізація функцій кількох змінних ідентифікація оптимуму icon

Лекція №6-7 оптимізація функцій кількох змінних ідентифікація оптимуму




Скачати 114.56 Kb.
НазваЛекція №6-7 оптимізація функцій кількох змінних ідентифікація оптимуму
Дата14.09.2012
Розмір114.56 Kb.
ТипЛекція
1. /Lekc/MO_lections.doc
2. /Lekc/lekciya_10_new(opt).doc
3. /Lekc/lekciya_1_new(tpr).doc
4. /Lekc/lekciya_2_MAI_new(tpr).doc
5. /Lekc/lekciya_2_new(tpr).doc
6. /Lekc/lekciya_3_new(opt).doc
7. /Lekc/lekciya_4-5_new(opt).doc
8. /Lekc/lekciya_6-7_new(opt).doc
9. /Lekc/lekciya_8_new(opt).doc
10. /Lekc/lekciya_9_new(opt).doc
3 Чисельні методи пошуку умовного екстремуму
Лекция №1 Вступ. Особливості та елементи задач прийняття рішень
Метод аналізу ієрархій (анр)
Лекція №2 Прийняття рішень в умовах невизначеності природи. Однокритеріальні задачі
Лекція № постановка І класифікація задач оптимізації
Методи безумовної оптимізації (мбо) оптимізація функцій однієї змінної
Лекція №6-7 оптимізація функцій кількох змінних ідентифікація оптимуму
Лекція №8 Методи першого І другого порядку Метод градієнтного спуску
Лінійне програмування


Лекція №6-7

ОПТИМІЗАЦІЯ ФУНКЦІЙ КІЛЬКОХ ЗМІННИХ


1. Ідентифікація оптимуму

Функцію називають функцією кількох змінних (багатопараметричною), якщо – вектор, тобто .


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


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



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

Нормою градієнта функції в точці називають величину .


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



Матриця Гессе має розмір і є симетричною відносно головної діагоналі.


Приклад

Для функції обчислити градієнт, норму градієнта і матрицю Гессе в точках , , , .


Обчислення градієнта:

; ; .

; ; ; .

; ;

; .


Обчислення матриці Гессе:

; ; ; ;


; .


Квадратична форма , а також відповідна матриця Гессе називається:

додатньо визначеною (), якщо для будь-якого ненульового виконується строга нерівність ;

додатньо напіввизначеною (), якщо для будь-якого ненульового виконується нестрога нерівність ;

від’ємно визначеною (), якщо для будь-якого ненульового виконується строга нерівність ;

від’ємно напіввизначеною (), якщо для будь-якого ненульового виконується нестрога нерівність ;

невизначеною (), якщо існують такі вектори і , що виконуються нерівності , ;

рівною нулю (), якщо для будь-якого виконується рівність .

Приклад


Класифікувати квадратичну форму і матрицю Гессе функції для точки .

Обчислюємо градієнт

Знаходимо матрицю Гессе .

Записуємо квадратичну форму

Очевидно, що квадратична форма для будь-якого ненульового і для і будь-яких , значить вона додатньо напіввизначена.


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

1) матриця Гессе додатньо визначена тоді, коли всі її визначники

, , ...,

додатні;

2) матриця Гессе від’ємно визначена тоді, коли всі непарні визначники від’ємні, а парні – додатні.

3) при будь-якій іншій комбінації визначників квадратична форма буде невизначеною.


Необхідна умова існування точки локального мінімуму (максимуму) функції : якщо функція двічі диференційовна в точці , то для наявності в цій точці локального мінімуму (максимуму) необхідним є виконання умови:

і ()

Стаціонарна (сідлова) точка – точка, в якій градієнт дорівнює нулю.

Достатня умова існування точки локального мінімуму (максимуму) функції : якщо функція двічі диференційовна в точці , а її градієнт в цій точці дорівнює нулю, то для наявності в цій точці локального мінімуму (максимуму) достатнім є виконання умови:

().

Приклад

Дослідити стаціонарні точки функції .


1. Обчислюємо градієнт функції:; ;



2. Прирівнюємо градієнт до нуля і розв’язуємо отриману систему рівнянь:

Маємо одну стаціонарну точку .


3. Визначимо характер цієї стаціонарної точки. Для цього обчислюємо матрицю Гессе в точці :

; ; ;

; ;

.

Визначаємо характер отриманої матриці Гессе за критерієм Сільвестра, для чого обчислюємо визначники: ; ; .

За критерієм Сільвестра від’ємно визначена, тоді точка – локальний максимум.


2. Методи оптимізації функцій кількох змінних

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

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

,

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

,

де – наступна точка; – поточна точка; – довжина кроку; – напрямок переходу з точки в точку ; – номер ітерації.

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

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

2) методи першого порядку, які використовують інформацію про перші похідні функції;

3) методи другого порядку, які використовують також інформацію про другі похідні функції


2.1. Методи нульового порядку

Методи прямого пошуку.

Поділяються на три групи:

1.методи координатного підйому(спуску)


2.методи пошуку по симплексу

3.методи випадкового пошуку

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

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

Алгоритм методу включає такі кроки:

1) задають початкову точку , величину кроку , коефіцієнт зменшення кроку , необхідну точність ;

2) приймають , ;

3) визначають напрямок зменшення функції вздовж -ої осі; якщо пошук невдалий, переходять на крок 6; інакше на крок 4;

4) обчислюють наступну точку послідовності:

,

;

5) якщо , приймають і переходять на крок 4; інакше переходять на крок 6;

6) якщо , приймають і переходять на крок 3;

інакше якщо і пошук був вдалим хоча б для однієї координати, приймають і переходять на крок 3; інакше переходять на крок 7;

7) якщо , то , інакше приймають , і переходять на крок 3.

2.1.2.Методи пошуку за симплексом


Регулярний симплекс – це багатогранник, який будується в просторі N параметрів і має (N+1) вершин, рівновіддалених одна від одної.

Якщо N=2, N+1=3, отримаємо рівносторонній трикутник

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

а)б)

Рис 1 - Побудова нового симплекса. а- початк. симплекс; х(1)(2)(3); б-новий сим.; х(2) , х(3), х(4)

Правило 1. «Накрив» точки мінімуму

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

Правило 2. Циклічний рух

Якщо деяка вершина симплекса не виключається на протязі більш ніж M ітерацій, то необхідно зменшити розміри симплекса за допомогою коефіцієнта і побудувати новий симплекс, вибравши за базову точку, якій відповідає мінімальне значення цільової функції. M=1,65N+0,05N2,

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

Правило 3. Критерії закінчення пошуку

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

Початкові умови


1) область допустимих значень, в яких існує цільова

функція унімодальна.

2) існує початкова точка Д.

Для того, щоб побудувати новний комплекс:

  1. Обирається масштабний множник . При =1 ребра регулярного симплексу мають одиничну довжину.

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



  1. координати інших N вершин симплекса в N-мірному просторі обчислюються за формулою

, для i = j=1,2,3,...,N.

  1. знаходимо центр тяжіння;



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

х(j)нов.=2хс(j)поперед


Існує випадок, коли симплекс покриває мінімум, тоді для побудови нового симплексу вибирається середня вершина.



Умови закінчення ітераційного процесу

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

Метод деформованого багатогранника Нелдера-Міда

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

(представити графічну інтерпретацію [Пантелеев, стр. 138])

Алгоритм методу включає такі кроки:

1) задають координати вершин багатогранника , , ..., ; параметри відображення , стиснення , розтягу ; необхідну точність .

2) приймають ;

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

4) знаходять центр ваги всіх вершин, за виключенням точки :



5) обчислюють величину



6) якщо , то , інакше перейти на крок 7;

7) виконати операцію відображення найгіршої вершини через центр ваги

;

8) виконують перевірку умов:

а) якщо , виконують операцію розтягу:

і знаходять вершини нового багатогранника:

– якщо , то вершину замінюють вершиною , приймають і переходять на крок 2;

– якщо , то вершину замінюють вершиною , приймають і переходять на крок 2;

б) якщо , виконати операцію стиснення:

і знаходять вершини нового багатогранника:

вершину замінюють вершиною , приймають і переходять на крок 2;

в) якщо , то вершину замінюють вершиною , приймають і переходять на крок 2;

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

, ,

приймають і переходять на крок 2.

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

Нелдер і Мід , , Павіані , ,

Паркінсон і Хатчінсон , , .

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

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

(представити графічну інтерпретацію [Химмельблау, стр. 162])

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

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

.

де – поточна базова точка;

– попередня базова точка;

– точка побудована за зразком;

Функція Хіммєльблау:

f
(x)=[x12+x2-11]2+[x1+x22-7]2 . (4.3)


Рисунок 4.1 - Лінії рівняня мультімодальної функції Хіммєльблау


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

Алгоритм методу включає такі кроки:

1) задають початкову точку , величину приросту , коефіцієнт зменшення кроку , необхідну точність ;

2) проводять етап дослідження;

3) якщо етап дослідження був вдалим (була знайдена точка з меншим значенням цільової функції), то перейти на крок 5; інакше на крок 4;

4) якщо , то , інакше , і перейти на крок 2;

5) обчислюють точку зразка

;

6) проводять етап дослідження, використовуючи в якості базової точки, в результаті якого визначають найкращу точку ;

7) якщо значення функції в точці менше, ніж в точці , то , , і перейти на крок 5; інакше на крок 4.



Схожі:

Лекція №6-7 оптимізація функцій кількох змінних ідентифікація оптимуму iconХарактеристика навчальних дисциплін кафедри (складова Інформаційного пакету)
«Диференціальне числення функції однієї змінної», «Інтегральне числення функції однієї змінної», «Ряди», «Диференціальне числення...
Лекція №6-7 оптимізація функцій кількох змінних ідентифікація оптимуму iconНазва модуля: Оптимізація прийняття рішень
Змістовна та формалізована постановки задачі прийняття рішень. Етапи прийняття рішень. Структура множини альтернатив. Методи та алгоритми...
Лекція №6-7 оптимізація функцій кількох змінних ідентифікація оптимуму iconНазва модуля: Програмування для систем реального часу
Програмування таймера. Сторожовий таймер. Послідовні інтерфейси. Паралельні інтерфейси. Оптимізація програмного забезпечення систем...
Лекція №6-7 оптимізація функцій кількох змінних ідентифікація оптимуму iconДо аспірантури математичний аналіз
Формула Тейлора та її застосування. Дослідження на екстремум І умовний екстремум функцій багатьох змінних. Диференційовні відображення...
Лекція №6-7 оптимізація функцій кількох змінних ідентифікація оптимуму iconБібліотека нові надходження
Текст] : навч посібн. Кн. 1 : Лінійна й векторна алгебра. Аналітична геометрія. Вступ до математичного аналізу. Диференціальне числення...
Лекція №6-7 оптимізація функцій кількох змінних ідентифікація оптимуму iconЛекція Ідентифікація та автентифікація Основні поняття І класифікація Застосування при міжмережевій взаємодії
Звичайно для вирішення даної проблеми застосовуються спеціальні прийоми, що дають можливість перевірити коректність повідомлень про...
Лекція №6-7 оптимізація функцій кількох змінних ідентифікація оптимуму icon3. Метод поділення змінних. (Метод Фур’є)
Для найпростішого рівняння з частинними похідними поділення змінних – це пошук розв’язку у вигляді
Лекція №6-7 оптимізація функцій кількох змінних ідентифікація оптимуму iconТип модуля: обов’язковий Семестр: 8 Обсяг модуля
Нелінійне програмування. Опукле та неопукле програмування. Метод Ньютона. Методи прямого пошуку Методи пошуку екстремумів функції...
Лекція №6-7 оптимізація функцій кількох змінних ідентифікація оптимуму iconНазва модуля: Вища математика Ч. 2 Код модуля
Невизначений та визначений інтеграл. Застосування визначеного інтегралу до задач геометрії та фізики. Границя, неперервність та диференційованість...
Лекція №6-7 оптимізація функцій кількох змінних ідентифікація оптимуму iconДиференційованість елементарних функцій
У попередньому параграфі розглянуто правила обчислення похідних для функцій однієї змінної. Вони дозволяють знаходити похідні будь-яких...
Лекція №6-7 оптимізація функцій кількох змінних ідентифікація оптимуму iconДиференційованість елементарних функцій
У попередньому параграфі розглянуто правила обчислення похідних для функцій однієї змінної. Вони дозволяють знаходити похідні будь-яких...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи