Початкові відомості про чисельні методи оптимізації
Іноді вдається, спираючись на умови оптимальності або на геометричну інтерпретацію, отримати рішення задачі оптимізації
в явному вигляді, але в більшості випадків завдання (2.1) доводиться вирішувати чисельно, із застосуванням ЕОМ. Так, наприклад, для розв'язання задачі мінімізації на R n диференціюється f можна скористатися будь-яким чисельним методом рішення системи рівнянь f '(x) = 0. Однак, як правило, найбільш ефек-тивними виявляються методи, розроблені спеціально для вирішення задачі оптимізації, так як вони дозволяють повніше врахувати її специфіку.
У наступних розділах будуть розглянуті чисельні методи розв'язання задач різних типів: одновимірних і багатовимірних, без-умовних і умовних, дискретних, а також завдань оптимального управління.
У цьому параграфі наводяться деякі загальні відомості, відно-сящіеся в першу чергу до чисельних методів безумовної та умовної мінімізації функції кінцевого числа безперервно змінюються змінних. Такі методи займають центральне місце в чисельної оптимізації; вони, зокрема, використовуються при ре-шении дискретних оптимізаційних задач і задач оптимального управління.
Будь-чисельний метод (алгоритм) рішення задачі оптимізації заснований на точному або наближеному обчисленні її характеристик (значень цільової функції, функцій, які задають допустимий безліч, а також їх похідних). На підставі отриманої інформації будується при-наближенні до вирішення завдання - шуканої точці мінімуму х * або, якщо така крапка не єдина, - до безлічі точок мінімуму. Іноді, якщо тільки це і потрібно, будується наближення до мі-мінімальними значенням цільової функції.
Для кожної конкретної задачі питання про те, які характери-стики слід вибрати для обчислення, вирішується в залежності від властивостей функції, що мінімізується, обмежень і наявних віз-можностей зі зберігання й обробки інформації. Так, для міні-мізації недиференційованої функції не можна скористатися алго-ритмом, що передбачають можливість обчислення в довільній точці градієнта функції. У разі, коли доступний невеликий обсяг пам'яті ЕОМ, при вирішенні задачі високої розмірності можна скористатися алгоритмом, що вимагає обчислення на кожному кроці, зберігання в пам'яті матриці других похідних і т.п.
Алгоритми, що використовують лише інформацію про значеннях міні-мізіруемой функції, називаються алгоритмами нульового порядку; алгоритми, що використовують також інформацію про значеннях перших похідних, - алгоритмами першого порядку; алгоритми, використовую-щие, крім того, інформацію про других похідних, - алгоритмами другого порядку.
В курсі розглядаються алгоритми тільки нульового, першого і другого порядку.
Робота алгоритму складається з двох етапів. На першому етапі ви-раховуються передбачені алгоритмом характеристики завдання. На другому етапі за отриманою інформацією будується наближення до вирішення. Для завдань оптимізації вибір на другому етапі способу побудови наближення, як правило, не викликає ускладнень. Наприклад, для методів спуску, в яких на кожному кроці відбувається із-дит перехід в точку з меншим, ніж попереднє, значенням функ-ції, за наближення до точки мінімуму зазвичай вибирається точка останнього обчислення. Тому для завдання алгоритму досить вказати спосіб вибору точок обчислення (звичайно, за умови, що вже вирішено питання про те, які саме характеристики розв'язуваної задачі слід обчислювати).
Якщо всі крапки вибираються одночасно до початку обчислень, то алгоритм мінімізації називається пасивним. Необхідність при-трансформаційних змін пасивних алгоритмів виникає, наприклад, у зв'язку з використанням багатопроцесорних ЕОМ, в зв'язку з умовами постановки і проведення фізичних експериментів, результатом яких є значення функції, що мінімізується, і т.д.
Однак для вирішення більшості завдань точки обчислення вибі-раются черзі, т. Е. Точка xi +1 вибирається, коли вже обрані точки попередніх обчислень х 1. х i і в кожній з них зроблені передбачені алгоритмом обчислення, результати кото-яких будемо позначати відповідно через у 1. у i. Такі алго-ритми називаються послідовними. Таким чином, послідовно-вальний алгоритм визначається точкою х 1 Î Х і набором відображені-ний виду
.
Надалі для запису методів мінімізації ми будемо поль-тися співвідношенням виду
При цьому конкретний алгоритм визначається завданням точки х 0, правилами вибору векторів h k і чисел ak на основі отриманої в результаті обчислень інформації, а також умовою зупинки. Таким чином, величини ak. hk у формулі (2.3) точно так же, як xi +1 у формулі (2.2), визначаються тими чи іншими видами функ-циональной залежності від точок і результатів усіх раніше прове-денних обчислень, причому на практиці зазвичай використовуються най-простіші види залежності. Правила вибору ak. h k можуть передбачати і додаткові обчислення, тобто обчислення деяких характеристик розв'язуваної задачі в точках, відмінних від x 0, х 1. х k. Саме тому в формулах (2.2) і (2.3) вжиті різні індекси.
Вектор h k визначає напрямок (k +1) -го кроку методу міні-мізації, а коефіцієнт ak - довжину цього кроку. При цьому слід мати на увазі, що при
|| h k || ¹ 1 довжина відрізка, що з'єднує точки х k. x k +1. звичайно, не дорівнює | ak |. Зазвичай назва методу мінімізації визначається способом вибору h k. а його різні варіанти зв'язок-ються з різними способами вибору ak. Поряд з терміном крок методу ми будемо користуватися також терміном ітерація методу.
Серед методів мінімізації можна умовно виділити кінцево-крокові та бесконечношаговие методи. Конечношаговимі, або конеч-ними, називаються методи, що гарантують відшукання рішення задачі за кінцеве число кроків. Конечношаговие методи вдається побудувати лише для деяких спеціальних типів завдань оптимізації, напри-мер завдань лінійного і квадратичного програмування. Для бесконечношагових методів досягнення рішення гарантується лише в межі.