МАКСИМІЗАЦІЯ І МІНІМІЗАЦІЯ ФУНКЦІЙ
кінцевого числа змінних - завдання пошуку екстремуму функції під цим завданням розуміється:
2) відшукання точок максимуму або мінімуму, якщо досягаються на допустимому безлічі (див. Максимум і мінімум функції).
3) побудова максимизирующей послідовності i> або міні м і з і р у roll; їй послідовності i> таких, що
якщо недосяжні на X.
Дослідженням екстремумів функцій дискретних аргументів займається дискретне програмування і цілочисельне програмування. Нижче висвітлені тільки методи М. і м. Ф. безперервних аргументів.
Класичні (непрямі) методи М. і м. Ф. застосовні тільки для гладких функцій. Вони використовують необхідна умова екстремуму для пошуку стаціонарних точок. нулі похідних
обчислюються на практиці частіше за все одним з численних методів послідовних наближень (див. [3]). З іншого боку, кожне завдання вирішення кінцевих функціональних рівнянь виду
можна інтерпретувати як задачу М. і м. ф. напр. функції
і застосувати для вирішення останньої один з специфічний. методів М. і м. ф.
Прямі методи М. і м. Ф. ґрунтуються на безпосередньому порівнянні значень f (x) .в двох або декількох точках.
Для практич. відшукання екстремумів застосовуються ітеративні алгоритми виду:
де i - номер ітерації, а - недо-рий оператор. При цьому зазвичай передбачається:
1) відповідність алгоритму в тому чи іншому сенсі, найчастіше в сенсі
2) локальність итерационной процедури, т. Е. Алгоритм "пам'ятає" значення хтолько для ітерацій в деякої околиці поточного становища х ;. При виходить простий марковский обчислювальний процес без пам'яті.
Оператор може бути детермінованим в детермінованих методах або містити стохастіч. параметри. У обчислювальній практиці часто поєднують стохастіч. методи з детермінованими, напр. в покоордінатного спуску методі напрямок спуску може визначатися випадковим чином. Імовірнісні характеристики стохастичних параметрів, в свою чергу, можуть змінюватися від ітерації до ітерації (пошук з адаптацією і "самонавчанням", випадковий пошук).
Широко застосовують і комбінування різних детермінованих методів, к-рому належить послідовне і паралельне обчислення екстремуму декількома методами, композиції алгоритмів виду і т. П. Напр. метод Левенберга - Марквардта
к-рий при ai = 0 збігається з градієнтним методом, а при bi = 0 з методом Ньютона.
Одновимірна оптимізація, тобто М. і м. Ф. f (x), крім самостійного інтересу, є необхідним етапом більшості застосовуваних методів. До специфічно одновимірним відносяться, напр. Фібоначчі метод, половинного ділення метод (дихотомії метод), парабол метод. Методами М. і м. Ф. багатьох змінних є градієнтний метод, найшвидшого спуску метод, покоордінатного спуску метод, симплексний пошук, сканування метод, сполучених градієнтів метод, важкого кульки метод, встановлення метод і ін.
Алгоритми більшості з перерахованих методів укладаються в схему методу спуску (п о д ь е м а): причому для всіх i (умова релаксації). Вони розрізняються між собою або вибором вектора напрямку yi спуску, або вибором способів руху вздовж вектора спуску, визначеним кроковим множником ее.
Яружні методи розроблені для функцій, рельєф яких брало має вигляд "ярів з крутими схилами" (див. Яружно функцій методи мінімізації). Ординарні (НЕ яр) методи, будучи застосованими тут, дають звивистий релаксаційний шлях, що вимагає надмірно великих витрат машинного часу для обчислення екстремуму.
Порівняльна ефективність методів оцінюється за багатьма і суперечливим критеріям. Сюди входять: точність рішення, швидкість рішення, надійність методу, час підготовки завдання до рахунку, збіжність алгоритму та ін. Область застосування кожного з апробованих методів вельми обмежена.
Для випробування методів розроблені набори стандартних тест-функцій, характерних для різних функціональних класів (див. [1]). Посилено досліджується збіжність методів М. і м. Ф. (Див. [6], [8]). Однак збіжність - це якість, до-рої не є ні необхідним, ні достатнім для ефективного закінчення обчислень.
Допомога пошукових систем