Методи оптимізації Математичну оптимізацію можна коротко описати так
* William Н. Press, Brian P.
мих змінних (які позначимо fv fn). Ви хочете знайти значення (-ня) незалежної змінної (-них), що доставляє мінімум (або іноді, як у нашому випадку, максимум) цільової функції. Максимізація та мінімізація, по суті, є одним і тим самим (те, що для одного дорівнює G, для іншого буде G).
У самому примітивному випадку ви можете оптимізувати так: перебираючи всі комбінації значень змінних і підставляючи їх у цільову функцію, шукати таку комбінацію, яка дає найкращий результат. Припустимо, наприклад, що хочемо знайти оптимальне / для одночасного кидання двох монет з точністю до 0,01. Тоді ми могли б постійно проводити розрахунки для монети 1 на значенні 0,0, у той час як для монети 2 переходити від 0,0 до 0,01 до 0,02 і так далі, поки не дійдемо до 1,0. Після цього ми могли б повернутися до монети 1 і, прораховуючи її на значенні 0,01, випробувати всі можливі значення для монети 2. Діючи таким чином і надалі, ми прийдемо до того, що значення обох змінних виявляться на їх максимумах, тобто стануть дорівнюють 1,0. Оскільки в кожної змінної в даному випадку є за 101 можливим значенням (від 0 до 1,0 включно з кроком 0,01), ми повинні випробувати 101 * 101 комбінацій, тобто цільова функція повинна бути розрахована 10201 разів.
За бажанням, ми могли б вимагати більшої точності, ніж 0,01. Тоді в нас стало б 1001*1001 комбінацій, які підлягають випробуванню, тобто цільову функцію довелося б розрахувати 1002001 раз. Якби ми зібралися взяти три змінних замість двох і зажадали б точності 0,001, то нам довелося б обчислити цільову функцію 1001*1001*1001 разів, що дорівнює 1003003001, тобто нам довелося б обчислити цільову функцію більшеодного мільярда разів. Адже ми використовуємо лише три змінних і вимагаємо лише 0,001 точності!
Хоча розглянутий примітивний випадок оптимізації найбільш зрозумілий порівняно з використанням всіх інших методів оптимізації, він має сумнівною гідністю бути занадто повільним, для застосування до більшості завдань.
Чому не перебрати всі значення першої змінної і знайти оптимум для неї, потім, зафіксувавши першу змінну на оптимумі, перебрати всі значення другої змінної і, знайшовши її оптимум, отримати таким чином оптимуми для перших двох змінних, після чого шукати оптимум для третьої змінної при фіксованих перших двох на їх оптимумах і так далі, доки завдання не буде вирішено?
Недоліком цього другого підходу є те, що часто у такий спосіб неможливо знайти оптимальний набір значень змінних. Зауважте, що коли ми добираємося до третьої змінної, значення перших двох рівні своїм максимумам, начебто інших змінних немає. Тому при оптимізації по третій змінній перші дві, зафіксовані на своїх оптимумах, заважають знаходженню її оптимуму. Те, на чому це може закінчитися, є не оптимальний набір значень, а, швидше, оптимальне значення для першої змінної, оптимум для другої, коли перша зафіксована на своєму оптимумі, оптимум для третьої, коли перша зафіксована на своєму оптимумі, а друга встановлена на певному субоптимумі, який є оптимальним за умови перешкод з боку першої змінної, і так далі. Іноді вдається провести такий перебір по всіх змінних і в результаті отримати-таки оптимальний набір значень змінних, але коли змінних більше трьох, він стає все більш тривалим, якщо взагалі здійсненним, враховуючи вплив інших змінних.
Крімдвох описаних грубих методів математичної оптимізації існують і досконаліші. Це — чудова гілка сучасної математики, і я наполегливо закликаю вас познайомитися з нею, просто сподіваючись, що ви витягнете з цього якусь частку того задоволення, яку я отримав від її вивчення.
Екстремум, максимум це або мінімум, може бути або глобальним (дійсно найбільше чи найменше значення), або локальним (найбільше чи найменше значення у безпосередній околиці). Напевно, знати глобальний екстремум майже неможливо, тому що ви не уявляєте собі область значень незалежних змінних. Але якщо область значень вам відома, ви просто знайшли локальний екстремум. Тому часто, коли люди говорять про глобальне
екстремумі, вони насправді мають на увазі локальний екстремум на дуже широкій області значень незалежних змінних.
Для відшукання максимумів чи мінімумів у разі існує маса методів. Кожен з них, як правило, накладає на змінні деякі обмеження, які повинні задовольнятися стосовно екстремуму. Наприклад, у нашому випадку ці обмеження полягають у тому, щоб усі незалежні змінні (значення J) були б більшими або рівними нулю. Нерідко потрібно виконання функцій, що обмежують (тобто, щоб значення інших функцій від використовуваних змінних були б більше/менше або дорівнюють деяким величинам). Лінійне програмування з його симплекс-методом - ця добре розроблена область такої оптимізації в умовах обмежень - застосовна лише, коли і оптимізована, і обмежуючі функції є лінійними (багаточленами першого ступеня).
Загалом різні методи математичної оптимізації можуть бути класифіковані за принципом використовуваногоапарату наступним чином:
2. З того, лінійний метод чи нелінійний. Якщо, як зазначалося раніше, і функція, що підлягає оптимізації, і обмежуючі функції є лінійними (тобто не містять жодного зі своїх аргументів у ступеню, більшому за 1), є маса дуже добре розроблених методів вирішення задачі відшукання екстремуму.
3. По використанню похідних. Деякі методи вимагають обчислення першої похідної цільової функції. У багатовимірному випадку перша похідна є векторною величиною, яка називається градієнтом.
4. За ефективністю обчислень. Тобто такі методи, які застосовуються, коли вам потрібно знайти екстремум якнайшвидше (тобто з меншою кількістю обчислень) і можливо простіше (щось, що поєднується з методами, що потребують обчислення похідних) та з використанням можливо меншої комп'ютерної пам'яті.
5. За стійкістю. Пам'ятайте, ви хотіли знайти локальний екстремум на дуже широкій області значень незалежних змінних та використовувати його замість глобального екстремуму. Тому, якщо в цій області є більше одного екстремуму, ви не захочете потрапити в обійми такого з них, який менш екстремальний.
У нашій дискусії ми розглядатимемо лише багатовимірний випадок. Тобто ми займемося лише тими алгоритмами оптимізації, які належать до двох і більше змінних (тобто з числом наборів сценарних, великим двох). Як це докладно показано у «Формулах управління портфелем», при знайденні єдиного значення /, тобто /для однієї ринкової системи або одного сценарного набору, як правило, найбільш ефективним та швидкодіючим методом буде параболічна інтерполяція.
Незважаючи на безліч хороших алгоритмів для багатовимірного випадку, ідеального все ж таки немає. Якісь методи ефективнішіінших стосовно певних типів завдань. Як правило, основним критерієм відбору серед методів багатовимірної оптимізації є особисті переваги (за наявності комп'ютерних потужностей, необхідних обраного методу).
По-перше, це симплекс-методи якнайшвидшого підйому. Вони, мабуть, стають найменш ефективними з усіх, якщо обчислювальне навантаження трохи збільшується. Разом з тим вони зазвичай легко застосовні і не вимагають обчислення приватних похідних першого порядку. На жаль, їм властива повільність, а необхідний обсяг пам'яті, що використовується, має порядок п2.
Друге сімейство утворюють direction set methods, відомі також як line minimization methods або (методи сполучених напрямних) conjugate direction methods. Найбільш примітними серед них різні методи Пауела. У сенсі швидкості вони ефективніші за симплекс-методи якнайшвидшого підйому (не плутайте з симплекс-алгоритмом для лінійних функцій,
згаданим раніше), не вимагають обчислення приватних похідних першого порядку, але вимоги пам'яті, як і раніше, мають порядок л2.
Третє сімейство утворюють метод пов'язаних градієнтів консугате gradient methods. Серед них виділяються методи Флет-Чера-Рівза і тісно примикають до них методи Полака-Ріб'єра. Вони тяжіють до групи найбільш ефективних методів у сенсі швидкості та пам'яті (порядку л), але вимагають обчислення приватних похідних першого порядку.
Четверте сімейство методів багатовимірної оптимізації утворюють квазіньтонові, або методи зі змінною метрикою variable metric methods. Туди входять алгоритми Девідсона-Флет-Чера-Пауела (DFP) та Бройдена-Флетчера-Голдфарба-Шанно (ВДСБ). Подібно до conjugate gradient methods, вони вимагають обчислення приватних похідних першого порядку, звичайно швидко приводятьдо екстремуму, проте ці алгоритми вимагають більшої пам'яті (порядку і2). Разом з тим вони врівноважують переваги conjugate gradient methods тим, що довше відомі, ширше використовуються та краще документально забезпечені.
П'яте сімейство – це імітаційні методи багатовимірної оптимізації. Вони набагато примітніші, оскільки рухаються до екстремуму за допомогою процесів моделювання, запозичених у природі. У їх число входять метод генетичного алгоритму (genetic algorithm) і відпалу (simulated annealing), що імітується, що моделює процес кристалізації, в ході якого система знаходить свій мінімальний енергетичний стан. Серед інших ці методи відрізняються найбільшою стійкістю, майже імунітетом по відношенню до локальних екстремумів і можуть вирішувати завдання величезної складності. Але вони не завжди найшвидші і стати такими здебільшого не зможуть. Разом з тим, вони такі нові, що про них ще мало що відомо.
Хоча ви можете використовувати будь-який згаданий алгоритм багатовимірної оптимізації, я віддав перевагу генетичному алгоритму тому, що він є, можливо, єдиним найбільш стійким методом математичної оптимізації, за винятком дуже грубих прийомів перебору всіх можливих комбінацій значень змінних.
Це метод загальної оптимізації та пошуку, який був застосований до вирішення багатьох завдань. Нерідко його застосовували у нейронних мережах, бо він добре скорочує перешкоди та розмірність великих нелінійних завдань. Оскільки цей метод не вимагає інформації про градієнт, його можна застосовувати і до розривних, і до емпіричних функцій так само, як він застосовується до аналітичних функцій.
Застосовність даного алгоритму, хоча часто використовується в нейронних мережах, не обмежується виключно ними. У наших умовах ми можемовикористовувати його як метод відшукання оптимальної точки на (л + 1)-мірному зображенні.