Математическая энциклопедия - максимизация и минимизация функций

конечного числа переменных задача поиска экстремума функции под этой задачей понимается:

1) нахождение

2) отыскание точек максимума или минимума, если достигаются на допустимом множестве (см. Максимум и минимум функции).

3) построение максимизирующей последовательности {xi} или мини м и з и р у roll; ей последовательности {х i} таких, что

если недостижимы на X.

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

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

вычисляются на практике чаще всего одним из многочисленных методов последовательных приближений (см. [3]). С другой стороны, каждую задачу решения конечных функциональных уравнений вида

можно интерпретировать как задачу М. и м. ф., напр. функции

и применить для решения последней один из специфич. методов М. и м. ф.

Прямые методы М. и м. ф. основываются на непосредственном сравнении значений f(x).в двух или нескольких точках.

Для практич. отыскания экстремумов применяются итеративные алгоритмы вида:

где i номер итерации, а нек-рый оператор. При этом обычно предполагается:

1) сходимость алгоритма в том или ином смысле, чаще всего в смысле

2) локальность итерационной процедуры, т. е. алгоритм "помнит" значения хтолько для итераций в нек-рой окрестности текущего положения х;. При получается простой марковский вычислительный процесс без памяти.

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

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

к-рый при ai = 0 совпадает с градиентным методом, а при bi = 0 с методом Ньютона.

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

Алгоритмы большинства из перечисленных методов укладываются в схему метода спуска (п о д ъ е м а): причем для всех i (условие релаксации). Они различаются между собой либо выбором вектора направления yi спуска, либо выбором способов движения вдоль вектора спуска, определяемым шаговым множителем эе.

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

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

Для испытания методов разработаны наборы стандартных тест-функций, характерных для различных функциональных классов (см. [1]). Усиленно исследуется сходимость методов М. и м. ф. (см. [6], [8]). Однако сходимость это качество, к-рое не является ни необходимым, ни достаточным для эффективного окончания вычислений.