Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Тема: Поняття про чисельні методи оптимізації




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

(1)

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

Наприклад: для розв’язання задачі мінімізації диференціальної функції ƒ можна використати будь – який чисельний метод рішення системи рівнянь у перших похідних ƒ´(x) = 0. Однак, як правило, найбільш ефективними є методи розроблені спеціально для рішення задачі оптимізації, так як вони дозволяють найбільш точно врахувати її специфіку.

Розрізняють наступні типи задач, які розв’язуються за допомогою чисельних методів:

· одно – та багатовимірні

· безумовні та умовні

· дискретні

· задачі оптимального управління

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

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

Інколи, якщо тільки це і потрібно, будується наближене до мінімуму значення цільової функції ƒ˟ = minƒ(x), де х ϵ Х, для кожної конкретної задачі питання про те які характеристики необхідно вибрати для обчислення, вирішується в залежності від властивостей мінімізованої функції, обмежень та значень обробки та збереження інформації.

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

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

Робота алгоритмів складається з двох частин:

1. етап: обчислюються передбачені алгоритмом характеристики задачі;

2. етап: за отриманою методикою будується її наближене рішення.

Для вирішення більшості задач точки для обчислення обирають в порядку черги, тобто точка хk+1 обирається лише тоді,коли вже обрані точки з попередніх обчислень: х1,…,хk, і в кожній з них відбулися передбачені алгоритмом обчислення. Такі алгоритми називаються послідовними.

Далі для запису методів оптимізації будемо використовувати відношення виду: xᵏ+¹=xᵏ+αk· hk де αk ϵ R, k=0,1,2,… (2).

В даному випадку конкретний алгоритм визначається наступним:

1. Точкою хₒ;

2. Правилами вибору вектора ͞ hk та чисел αk на підставі отриманої в результаті обчислень інформації;

3. Умовами для зупинки

Вектор hk визначає напрямок k+1 - кроку методу оптимізації, а αk - довжину цього кроку.

Зазвичай назва методу мінімізації визначається способом вибору hk, а його різноманітні варіанти пов’язані з різними способами вибору вектора.

Складність рішення задачі оптимізації визначається наступним:

· Числом її змінних

· Видом цільової функції

· Видом та числом її обмежень

Серед методів мінімізації можна умовно виділити:

а) кінцевокрокові(кінцеві) – ці методи гарантують знайдення рішень задачі за кінцеву кількість кроків. Їх можна побудувати лише для деяких спеціальних типів задач оптимізації(задач лінійного або квадратичного програмування).

б) безкінечно крокові – для цих методів рішення можливе лише в граничному значенні(lim).

 

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

- рішення задачі (1)

Якщо:

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

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

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

Кажуть, що сходиться до сверхлінійно, якщо (4)

Говорять про квадратичну збіжність, якщо існують такі константи:

и , що (5)

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

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

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

«Умови зупинки»
- Може визначатися наявні ресурси, а також зупинка може проводиться з досягнення заданої точності умов завдання

ТЕМА: ГРАДІЄНТНІ МЕТОДИ

Методи, які будуть розглянуті нижче (градієнтні та метод Ньютона) мають важливе значення в ідейному відношенні:

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

- в градієнтному методі беруть лінійну частину розкладу;

- в методі Ньютона беруть квадратичну частину розкладу.

Градієнтний метод – це метод першого порядку (використовує похідні першого порядку), а метод Ньютона – метод другого порядку (використовує похідні другого порядку). Тобто ці методи засновані також на ідеї апроксимації функції.

П 1.Сутність та схема градієнтного методу

Для мінімізації функції (2) використовується обчислювальна схема (1):

(2)

, (1)

- параметр, що регулює довжину кроку вздовж .

; (3)

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

В градієнтному методі використовуються різноманітні підходи при виборі довжини кроку:

1. довжина кроку вибирається з умови мінімізації функції вздовж напрямку;

2. метод дроблення кроку;

3. метод з адитивним шляхом пошуку

Перший метод означає, що значення функції в точці виходячи з умови (3) матиме вигляд:

(4)

Для вирішення задачі одномірної оптимізації (4) необхідно застосувати методи одномірної оптимізації (методи дихотомії, «Золотого перерізу», метод Фібоначі).

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

 

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

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

Теорема 1.

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

, ; (5)

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

(6)

;

 

П 3. Обговорення градієнтного методу

 

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

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

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

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

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

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

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

Градієнтний метод слугую для основою для створення інших корисних евристичних методів.

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

Приклад: Метод градієнтного спуску

;

Щоб знайти необхідно вирішити задачу мінімізації:

Далі вирішується методом Фібоначі/ «Золотого перерізу» /дихотомії відносно .




Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 1587; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.