програмування
Метод умовного градієнта або метод лінійної апроксимації (лінеаризації) цільової функції. Застосування даного методу виправдане лише в тому випадку, коли завдання виду? (X)? Min, x Є X, тобто завдання мінімізації лінійної функції на X, вирішується досить просто. Але якщо безліч X має складну структуру, то завдання важке.
Метод наведеного градієнта заснований на скороченні розмірності задачі за допомогою представлення всіх змінних через підмножина незалежних змінних.
Метод можливих напрямків заснований на русі з однієї допустимої точки до іншої з кращим значенням цільової функції.
Проектні методи утворюють ціле сімейство. Іноді їх називають методами допустимих напрямків або градієнтними методами з великою довжиною кроку. Сутність цих методів полягає в наступному: лінійні і линеаризировать обмеження утворюють лінійне різноманіття (обумовлений перетинанням обмежень), на яке можна спроектувати обраний напрям пошуку S в просторі рішень. Те, що в методах мається на увазі під проекцією, асоціюється з поняттям проекції вектора, що описує локальне приріст функції при переміщенні в заданому напрямку.
. 2 Оцінка чисельних методів нелінійного програмування
нелінійний програмування антіградіентом проекція
На питання про те, який з методів нелінійного програмування найкращий можна сказати при оцінюванні «якості» того чи іншого алгоритму. Критерії оцінювання:
1) час, необхідний для реалізації серії обчислювальних процедур (число операцій і час їх виконання);
2) ступінь складності завдання (розмірність, число обмежень у вигляді рівностей, число обмежень у вигляді нерівностей);
3) точність рішення по відношенню до оптимального значення х * або по відношенню до? (х *), h (x *), g (x *) і? (х *);
) простота практичного використання алгоритму (час, необхідний для введення вихідних даних і запису функцій в пам'ять ЕОМ);
) простота машинної програми, що реалізує розглянутий алгоритм;
) алгоритм повинен дозволяти вирішувати завдання, які представляють практичний інтерес (не можна вважати, що який-небудь з алгоритмів виявиться ефективним при вирішенні будь-якої задачі).
2. Метод проекції антіградіента
антіградіентом дає тільки напрямок мінімізації, але не довжину кроку. Напрямок проекції антіградіента є локально найкращим напрямком руху до умовного мінімуму цільової функції. При пошуку умовного максимуму використовують проекцію градієнта. Разом з градієнтом можна визначити вектор антіградіента, рівний за модулем вектору градієнта, але протилежний за напрямком. Він вказує бік найбільшої спадання функції в даній точці. Всі проектні методи припускають реалізацію на кожному k-му етапі зазначеній нижче послідовності кроків:
1) алгоритм починає роботу в допустимої точці х;
) визначається допустиме напрямок s;
) в допустимому напрямку вибирається крок довжиною, минимизирующий? (х), але в той же час зберігає вектор х=х + s допустимим.
Цільова функція методу проекції антіградіента має вигляд. І завдання оптимізації задана наступним чином. Основна ідея методу полягає в тому, щоб йти в напрямку найшвидшого спуску, а цей напрямок задається антпградіентом:
(2)
Де вибирається
· постійною, в цьому випадку метод може розходитися;
· дробовим кроком, тобто довжина кроку в процесі спуску ділиться на деяке число;
· найшвидшого спуску.
Алгоритм:
1) обчислити.
) якщо, то обчислити за формулою і закінчити обчислення. В іншому випадку - продовження обчислення переходячи до пункту 3.
) визначити максимальну довжину кроку:
4) вирішити завдання одновимірного пошуку:
) покласти.
Критерії зупинки процесу наближеного знаходження мінімуму можуть бути засновані на різних міркуваннях. Деякі з них:
1.
.
Здеcь - значення, отримане після -го кроку оптимізації.- Наперед заданий позитивне число
Даний алгоритм можна легко поширити на нерівності, використовуючи або додаткові змінні, які активні обмеження.
Малюнок 1
lt; # 12 src= doc_zip37.jpg / gt; раз" .
Лінійні обмеження типу рівності. Нехай в задачі оптимізації допустима безліч? визначено обмеженнями типу рівності, тобто має вигляд
?={x Є R?:(Ai; x)=bi, i =} (3)
а цільова функція? (х) диференційовна в R ?. Припустимо, що відома точка х ?. Розглянемо функцію (у) =? (Х + P * y), yR? де матриця P визначена співвідношенням
...
