Локальний і глобальний екстремуми функцій

Розглянемо два завдання, що виникають при проектуванні мереж зв'язку.

Завдання 1. Проектується канал передачі даних з вирішальним зворотним зв'язком. Вузол А відправляє інформаційні пакети вузлу В. Вузол В перевіряє правильність кожного отриманого пакету і при правильному чи неправильному прийомі відправляє вузлу А. відповідно, позитивні чи негативні квитанції. При отриманні позитивної квитанції вузол А відправляє наступний пакет, при отриманні негативної - повторює передачу попереднього пакету. Кожен пакет складається з інформаційної частини довжиною k символів і перевірочної частини довжиною r символів. Ефективність роботи каналу передачі даних (КПД) оцінюється по відносній швидкості передачі R - еквіваленту коефіцієнта корисного використання пропускної здатності каналу передачі даних, R = f (k). Справді, якщо k = 0, тобто інформації в пакеті немає і він містить тільки перевірочну частину, то R = 0. При збільшенні k буде рости і R. Однак, якщо k надмірно велике, то пакети мають велику довжину і, при ймовірності спотворення повідомлень в ККД відмінною від нуля, будуть частіше дивуватися помилками, а, отже, і частіше повторюватися. Таким чином, при зміні k від 0 до ¥ залежність R = f (k) буде мати вигляд показаний на малюнку 1.

Природним є бажання знайти таке значення k. при якому R (k) досягає максимуму.

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

Нехай довжина пакета становить n = k + r = const. Очевидно, що k і r можуть змінюватися від 0 до n. При цьому загальна довжина пакета не повинна бути відмінною від n. Достовірність визначається ймовірністю не виявлення помилки Pош. Залежність Pош від відносини r / k має вигляд

Потрібно знайти таке співвідношення між r і k. при якому ймовірність спотворення пакету в каналі передачі даних мінімальна P * ош = min P (r / k).

Видно, що завдання 1 і 2 - завдання пошуку екстремуму деякої функції в заданій області зміни її аргументу (області дослідження).

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

Локальним екстремумів будемо називати точку простору дослідження, в якій цільова функція має найбільше (найменше) значення в порівнянні з її значеннями у всіх інших точках найближчій околиці. На рис.4.1 показана одномірна функція, що має п'ять локальних екстремумів. Частина простору дослідження може містити багато локальних екстремумів і слід зберігати обережність, щоб не прийняти перший з них за рішення задачі.

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

Завдання одновимірної оптимізації можна поставити в такий спосіб. Нехай значення змінної x укладені в інтервалі [a; b]. Інтервал значень змінної x. в якому проводиться пошук оптимуму цільової функції, будемо називати інтервалом невизначеності. На початку процесу оптимізації цей інтервал має довжину b-a. Необхідно визначити значення оптимуму функції з похибкою e, тобто знайти в інтервалі [a; b] точку x. таку що

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

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

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

Проводячи N вимірювань отримаємо (N +1) частин інтервалу невизначеності і тоді:

де 2 - залишилося частин інтервалу невизначеності; N +1 - було частин інтервалу невизначеності.

Фактично ми перейшли від однокрокового алгоритму до багатокроковому алгоритму.