Метод штрафних функцій
виклад методу
Основне завдання методу штрафних функцій полягає в перетворенні завдання мінімізації функції
з відповідними обмеженнями, накладеними на х, в завдання пошуку мінімуму без обмежень функції
Функція є штрафною. Необхідно, щоб при порушенні обмежень вона «штрафувала» функцію Z, тобто збільшувала її значеніе.В цьому випадку мінімум функції Z буде знаходитися всередині області обмежень. Функція, що задовольняє цій умові, може бути не єдиною. Завдання мінімізації можна сформулювати наступним чином:
при обмеженнях 0, j = 1,2, \ dots, m "> 0, j = 1,2, \ dots, m" >.
Функцію зручно записати в такий спосіб:
де r - позитивна величина.
Тоді функція приймає вид
Якщо х приймає допустимі значення, тобто значення, для яких, то Z приймає значення, які більше відповідних значень (істинної цільової функції даної задачі), і різниця можна зменшити за рахунок того, що r може бути дуже малою величиною. Але якщо х приймає значення, які хоча і є допустимими, але близькі до кордону області обмежень, і принаймні одна з функцій близька до нуля, тоді значення функції, і отже значення функції Z стануть дуже великі. Таким чином, вплив функції полягає в створенні «гребеня з крутими краями» уздовж кожної кордону області обмежень. Отже, якщо пошук почнеться з допустимої точки і здійснюється пошук мінімуму функції без обмежень, то мінімум, звичайно, буде досягатися всередині допустимої області для завдання з обмеженнями. Вважаючи r досить малою величиною, для того щоб вплив був малим в точці мінімуму, ми можемо зробити точку мінімуму функції без обмежень збігається з точкою мінімуму завдання з обмеженнями.
Алгоритм методу штрафних функцій
Нехай є наступна задача: Мінімізувати при обмеженнях, ">.
Початковий етап Вибрати 0 "> 0" > в якості константи зупинки, початкову допустиму точку ∈, для якої 0 "> 0" >, ">, скаляр і 0" > - параметр, значення якого зменшуються з кожною ітерації при; - позитивні вагові коефіцієнти.
Прикладами штрафних функцій є:
1) зворотна функція ">
2) логарифмічна функція
Покласти "> рівним оптимальному вирішенню завдання мінімізації і перейти до другого кроку.
Мінімізація штрафний функцію може бути виконана будь-яким методом безумовної оптимізації, наприклад, градієнтним.
Якщо, то зупинитися. Рішення є шуканим.
В іншому випадку покласти = \ beta ">. Змінити і перейти до першого кроку (k + 1) -й ітерації.
Метод бар'єрних функцій
виклад методу
Метод штрафних функцій відноситься до групи методів внутрішньої точки, тобто він починає працювати з допустимої точки і генерує послідовність допустимих точок. Метод бар'єрних функцій, навпаки, належить до групи методів зовнішньої точки, він починає пошук з неприпустимою точки і генерує послідовність неприпустимих рішень, яка наближається до оптимального рішення ззовні допустимої області.
Нехай є завдання мінімізувати при обмеженнях
Зокрема, для шуканих функцій - обмежень доцільно використовувати бар'єрну функцію такого вигляду:
^ R_1 (g_i (x)) + "> - безперервні функції, які задовольняють умовам:. Якщо = 0" > = 0 "> і 0" > 0 ">. Якщо. Якщо і 0" > 0 ">. якщо.
Типовими є такі вирази для функцій:
) ^ P ">,, де р - ціле позитивне число.
Далі від початкового завдання переходимо до задачі безумовної оптимізації допоміжної функції: мінімізувати, де 0 "> 0" > - штрафний коефіцієнт.
Нехай α- безперервна функція. Позначимо ">.
Підхід, пов'язаний з бар'єрної функцією полягає у вирішенні завдання виду:
максимізувати при обмеженні
Алгоритм методу бар'єрних функцій
Нехай є наступна задача:
Мінімізувати при обмеженнях,, де функції.
Початковий етап Вибрати 0 "> 0" > Вибрати початкову точку, параметр штрафу і число 1 "> 1" >. Покласти k = 1 і перейти до основного етапу.
Основний етап. k-я ітерація.
Перший крок. При початковій точці і параметрі штрафу вирішити наступне завдання:
Покласти "> рівним оптимальному вирішенню завдання і перейти до другого кроку.
з наступними обмеженнями
0 "alt =" 8-x_1 ^ 2 - x_2 ^ 2 - x_3 ^ 2 - x_4 ^ 2 - x_1 + x_2 - x_3 + x_4> 0 "> 0" alt = "10 -x_1 ^ 2-2x_2 ^ 2 x_3 ^ 2-2x_4 ^ 2 + x_1-x_4> 0 "> 0" alt = "5 - 2x_1 ^ 2 - x_2 ^ 2 - x_3 ^ 2 - 2x_1 + x_2 + x_4> 0" >
Нижче наведена таблиця проміжних результатів алгоритму.
Значення міімізіруемой функції
Координати першої точки
Оптимальну точку ми отримуємо на 114й ітерації з оптимальним значенням функції
рекомендація програмісту
Використання штрафних функцій для вирішення завдань пов'язано з певною обчислювальної труднощами. Перш за все пошук може починатися з допустимої точки х, для якої, "> .Для деяких завдань знаходити таку точку досить складно. Крім того, внаслідок використання в алгоритмі оптимізації дискретних кроків біля кордону можливий крок, який виводить за межі допустимої області. Він приводить до зменшення значень функції, тобто до фіктивного успіху. Таким чином, потрібна явна перевірка допустимості кожної наступної точки, для чого на кожній ітерації необхідно обчислювати значення функції,.
На ефективність методу бар'єрних функцій істотно впливають вибір початкового значення і метод скорочення значень в процесі мінімізації, а також вибір вагових коефіцієнтів. Якщо в функції значення, вибирають занадто малим, то вже на початковій стадії процесу приходять до мінімуму функції, який навряд чи виявиться поблизу дійсного умовного мінімуму в точці. З іншого боку, якщо значення, вибирається занадто великим, то на перших ітераціях обчислювального процесу поточна точка неминуче виявиться занадто далеко за межами допустимої області, і пошук через необхідність повернення в межі допустимої області виявиться вельми затяжним.