МНОГОЭКСТРЕМАЛЬНАЯ ЗАДАЧА

- экстремальная задача, имеющая несколько или неизвестное число локальных экстремумов.

Проблема отыскания глобального экстремума f{x), решена для основных классов унимодальных функций (прежде всего для выпуклых и родственных им, см. Выпуклое программирование). Для мультимодальных функций, даже для гладких и медленно меняющихся, в настоящее время (1982) отсутствуют методы достоверного вычисления глобального экстремума за исключением сканирования по траекториям, образующим всюду плотное множество в допустимом множестве X. На практике трудоемкое сканирование комбинируют с алгоритмами поиска локального экстремума: с помощью сканирования и априорных сведений об f(x)(оценок производных, функциональных уравнений и неравенств и др.) оконтуривается область притяжения каждого локального экстремума и мертвые зоны, где конкретный локальный алгоритм теряет эффективность (напр., для градиентного метода мертвыми зонами являются окрестность седловой точки и "дно оврага"). Затем экстремумы оцениваются или ищутся с помощью локальных методов и сравниваются между собой.

Для функций, удовлетворяющих условию Липшица

наиболее универсальным является метод покрытий (перебор на неравномерной сетке), к-рый к тому же легко реализуем в многомерном случае.

Для нахождения локальных экстремумов, близких к глобальному, в приложениях используются эмпирические "эвристические" способы, к-рые можно назвать квазиглобальными:

1. Алгоритмы типа тяжелого шарика метода или овражных методов (см. Овражных функций методы минимизации), способные "проскакивать" через нек-рые локальные экстремумы или "огибать" области их притяжения.

2. Случайный перебор значений с помощью Монте-Карло метода.

3. Модификация локальных методов путем введения стохастич. параметров. Напр., траектория рандомизированного градиентного метода

где - случайный процесс типа белого шума, при нек-рых условиях способна попадать из точки локального в точку глобального экстремума.

4. "Огрубление" функции путем ее аппроксимации последовательностью унимодальных функций. Аппроксимация может производиться по значениям f(х)в нек-рых точках, разложением по параметрам, входящим в аналитич. выражение функции, мажорантами или минорантами и т. п.

5. Поиск локального экстремума осредненной функции (скользящее среднее)

Примеры:

Физич. смысл такого усреднения заключается в "сглаживании" исходной функции и "отфильтровании" от нее колеблющихся слагаемых.

Если (быстроосциллирующая функция f(x)), то перед усреднением исходную функцию можно "продетектировать" с помощью нелинейного преобразования, напр.

В качестве взвешивающей при усреднении функции можно взять и

Последнее соотношение возможно также использовать для получения оценок существенных максимума и минимума.

Формулы (1) и (2) можно интерпретировать как формулы математич. ожиданий для функции случайной величины , распределенной с плотностью вероятностей . Поэтому данную М. з. можно трактовать как задачу стохастического программирования и применять к ней его методы.

После нахождения экстремума аппроксимирующей или усредненной функции (обзорный поиск) можно произвести в окрестности найденной точки детальный поиск экстремума исходной функции.

Глобальную оптимизацию отдельных функций можно произвести с помощью частных специфич. приемов. Напр., построить такую динамич. систему, для к-рой точка глобального экстремума является асимптотически устойчивой точкой покоя.

Одним из источников идей новых методов (квази) глобальной оптимизации является моделирование процессов в физических и биологических системах.

Громоздкие вычислительные процессы нелокального поиска можно оптимизировать по ряду показателей с учетом ограничений на вычислительные средства, априорной и последовательно накапливаемой информации об исследуемой функции f(x), вероятностных характеристиках случайных факторов и пр. Один из подходов, к-рые здесь пытаются применить, основан на теории статистич. решений.

Помимо отыскания глобального экстремума возникают и иные М. з., напр. определение колебания функции, перечисление и отыскание всех локальных экстремумов в заданной области.

Для многочленов разработаны весьма эффективные правила подсчета и отделения корней производных.

Для точек экстремума трансцендентных функций здесь могут быть полезны соображения типа Ролля теоремы или сравнения теорем для решений дифференциальных уравнений.

Число стационарных точек аналитич. функции может быть оценено с помощью аргумента принципа.

Если функция имеет бесконечную последовательность экстремумов, то на практике вычисляется непосредственно несколько из них, а остальные - с помощью асимптотич. разложения (напр., Г-функция).

Квазиклассич. приближение для дифференциальных уравнений можно рассматривать как асимптотич. разложение решения уравнения по числу его экстремумов.

О М. з. в бесконечномерном случае см. Вариационное исчисление в целом. Дискретные аналоги освещены в ст. Целочисленное программирование и Дискретное программирование.

Лит. см. при ст. Максимизация и минимизация функций. Ю. П. Иванилов, В. В. Охрименко.