Максимизация и минимизация функций

Максимиза́ция и минимиза́ция фу́нкций конечного числа переменных, задача поиска экстремума функции ${\displaystyle f(x)}$, ${\displaystyle x=\left(x^{1},\ldots ,x^{n}\right)\in X\subseteq \mathbb {R} ^{n}}$; под этой задачей понимается:

1) нахождение ${\displaystyle {\bar {f}}=\sup _{x\in X}f(x)}$ или ${\displaystyle {\underline {f}}=\inf _{x\in X}f(x)}$;

2) отыскание точек максимума или минимума, если ${\displaystyle {\bar {f}}}$ или ${\displaystyle {\underline {f}}}$ достигаются на допустимом множестве;

3) построение максимизирующей последовательности ${\displaystyle \left\{x_{i}\right\}}$ или минимизирующей последовательности ${\displaystyle \left\{x_{i}\right\}}$ таких, что

${\displaystyle \lim _{i\rightarrow \infty }f\left(x_{i}\right)={\bar {f}},\quad \lim _{j\rightarrow \infty }f\left(x_{j}\right)={\underline {f}}}$,

если ${\displaystyle {\bar {f}}}$ или ${\displaystyle {\underline {f}}}$ недостижимы на ${\displaystyle X}$.

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

Классические (непрямые) методы максимизации и минимизации функций применимы только для гладких функций. Они используют необходимое условие экстремума для поиска стационарных точек. Нули производных ${\displaystyle {\frac {\partial f}{\partial x^{\alpha }}}}$, ${\displaystyle \alpha =1,\ldots ,n}$, вычисляются на практике чаще всего одним из многочисленных методов последовательных приближений (Берёзин. 1966^[1]). С другой стороны, каждую задачу решения конечных функциональных уравнений вида

${\displaystyle \varphi _{m}\left(x^{1},\ldots ,x^{n}\right)=0,\quad m\leqslant n}$,

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

${\displaystyle f(x)=\varphi _{1}^{2}(x)+\ldots +\varphi _{m}^{2}(x)\longrightarrow \min }$,

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

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

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

${\displaystyle x_{i+1}={\hat {X}}\left(i,x_{i},x_{i-1},\ldots ,x_{i-j}\right)}$,

где ${\displaystyle i}$ – номер итерации, а ${\displaystyle {\hat {X}}(\cdot )}$ – некоторый оператор. При этом обычно предполагается:

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

${\displaystyle x_{\infty }={\bar {x}}\left(x_{\infty }={\underline {x}}\right){\text{ или }}f\left(x_{\infty }\right)={\bar {f}}\left(f\left(x_{\infty }\right)={\underline {f}}\right)}$;

2) локальность итерационной процедуры, т. е. ${\displaystyle j\ll i}$ [${\displaystyle j=o(i)}$ при ${\displaystyle i\rightarrow \infty }$]; алгоритм «помнит» значения ${\displaystyle x}$ только для итераций в некоторой окрестности текущего положения ${\displaystyle x_{i}}$. При ${\displaystyle j\equiv 0}$ получается простой марковский вычислительный процесс без памяти.

Оператор ${\displaystyle {\hat {X}}(\cdot )}$ может быть детерминированным в детерминированных методах или содержать стохастические параметры. В вычислительной практике стохастические методы часто сочетают с детерминированными: например, в методе покоординатного спуска направление спуска может определяться случайным образом. Вероятностные характеристики стохастических параметров, в свою очередь, могут меняться от итерации к итерации (поиск с адаптацией и «самообучением», случайный поиск).

Широко применяют и комбинирование различных детерминированных методов, к которому относятся последовательное и параллельное вычисление экстремума несколькими методами, композиции алгоритмов вида ${\displaystyle {\widehat {X}}={\widehat {X}}_{2}\left({\hat {X}}_{1}(\cdot )\right)}$ и т. п. Например, метод Левенберга – Марквардта

${\displaystyle x_{i+1}=x_{i}-\left(\alpha _{i}\nabla \nabla f\left(x_{j}\right)+\beta _{i}I\right)^{-1}\nabla f\left(x_{i}\right)}$,

который при ${\displaystyle \alpha _{i}=0}$ совпадает с градиентным методом, а при ${\displaystyle \beta _{i}=0}$ с методом Ньютона.

Одномерная оптимизация, т. е. максимизация и минимизация функций ${\displaystyle f(x)}$, ${\displaystyle x\in \mathbb {R} ^{1}}$, помимо самостоятельного интереса, является необходимым этапом большинства применяемых методов. К специфически одномерным относятся, например, метод Фибоначчи, метод половинного деления (метод дихотомии), метод парабол. Методами максимизации и минимизации функций многих переменных являются градиентный метод, метод наискорейшего спуска, метод покоординатного спуска, симплексный поиск, метод сканирования, метод сопряжённых градиентов, метод тяжёлого шарика, метод установления и др.

Алгоритмы большинства из перечисленных методов укладываются в схему метода спуска (подъёма):

${\displaystyle x_{i+1}=x_{i}\mp \varkappa _{i}y_{i}}$,

причём ${\displaystyle f\left(x_{i+1}\right)\leqslant f\left(x_{i}\right)}$ или ${\displaystyle f\left(x_{i+1}\right)\geqslant f\left(x_{i}\right)}$ для всех ${\displaystyle i}$ (условие релаксации). Они различаются между собой либо выбором вектора направления ${\displaystyle y_{i}}$ спуска, либо выбором способов движения вдоль вектора спуска, определяемым шаговым множителем ${\displaystyle {\text{æ}}}$.

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

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

Для испытания методов разработаны наборы стандартных тест-функций, характерных для различных функциональных классов (Аоки. 1977^[2]). Усиленно исследуется сходимость методов максимизации и минимизации функций (Карманов. 1975^[3]; Пшеничный. 1975^[4]). Однако сходимость – это качество, которое не является ни необходимым, ни достаточным для эффективного окончания вычислений.

Все перечисленные выше методы приводят к одному из локальных экстремумов, если начальное приближение принадлежит области притяжения точки этого экстремума. Нахождение глобального экстремума гарантируется лишь для выпуклых и родственных им унимодальных функций. Теория отыскания глобального экстремума находится (1982) в начальной стадии развития (см. в статье Многоэкстремальная задача). Другим развивающимся направлением максимизации и минимизации функций является оптимизация негладких функций (Васильев. 1974^[5]; Федоров. 1979^[6]). В частности, к негладкой функции, как правило, приводит задача минимизации функции максимума (см. в статье Максимин; численные методы). По-видимому, все общеупотребительные методы оптимизации имеют содержательный физический, экономический или биологический смысл. Соответствующие исследования только разворачиваются (Разумихин. 1975^[7]) и приводят к созданию новых методов (см. также в статье Непрерывные аналоги итерационных методов). Если значения исследуемой функции определяются статистически со стохастической помехой, то для отыскания экстремума применяется один из методов стохастической аппроксимации. Сюда же примыкает и планирование эксперимента.

Экспериментальные методы максимизации и минимизации функций используют воспроизведение различных физических процессов для поиска экстремумов. К ним относится и моделирование на ${\displaystyle \operatorname {ABM} }$ (Towards global optimisation. 1975–1978^[8]). Несмотря на удобство и дешевизну использования в простейших автоматических оптимизаторах, последнее не обеспечивает высокой точности вычисления.

Графические методы пригодны только для прикидочных расчётов и построения начального приближения для итеративных методов.

Если допустимое множество задано в виде функциональных условий

${\displaystyle \varphi _{m}(x)\leqslant 0}$

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