Методы безусловной минимизации
Материал из Documentation.
Методы безусловной минимизации (МБМ) — методы, предназначенные для нахождения минимума функции многих переменных $f(x)$ в случае, когда на значения аргумента не налагаются дополнительные ограничения. МБМ составляют важный класс методов оптимизации. Задача о нахождении максимума изменением знака функции $f(x)$ сводится к задаче о нахождении минимума. В случае, когда $f$ зависит от одной скалярной переменной $x$, минимизацию функции $f(x)$ обычно называют одномерной. К группе методов одномерной минимизации относятся: метод половинного деления, случайный поиск, метод Фибоначчи, метод золотого сечения и др.[1]
В МБМ в процессе минимизации строится некоторая последовательность точек $x_1,\, x_2,\, …,\, x_k$ многомерного пространства и в зависимости от значений функции $f$ в этих точках находится новая точка $x_{k+1}$. Правило построения последовательности определяется выбранным методом минимизации.[2]
В МБМ важную роль играет гладкость функции $f$. Увеличение гладкости минимизируемой функции $f$ позволяет строить более эффективные методы.[3]
МБМ подразделяют на три основных класса.[4]
Один из классов составляют методы, не использующие производные функции $f$. В этот класс входят случайный поиск, метод покоординатного спуска и др.[5]
Другой класс образуют градиентные методы, в которых предполагается, что функция $f$ один раз дифференцируема. В методе градиентного спуска после вычисления значения функции $f$ и её градиента $f_x$ в точке $x_k$ новая точка находится по формуле xk+1=xk−αkfx(xk), где $α_k$ — неотрицательное число (шаг спуска). При некоторых условиях последовательность $x_1,\, x_2,\, …$ сходится к точке локального минимума функции $f(x)$. Если при каждом $k$ величина $α_k$ определяется из условия одномерной минимизации функции $f(x_{k+1})$ по $α_k$, то приходят к методу наискорейшего спуска. Существуют также методы, называемые $s$-шаговыми, в которых новая точка $x_k$ определяется по $s$ предыдущим точкам. Одним из простейших двухшаговых методов является метод сопряжённого градиента, в котором xk+1=xk−αkfx(xk)+βk(xk−xk−1),
где $α_k⩾0,\, β_k⩾0$ — параметры, определяемые решением задачи двумерной минимизации $f(x_{k+1})$ по $α_k$ и $β_k$.[6]
К третьему классу относится метод Ньютона и его модификации. Предполагается, что функция $f$ дважды дифференцируема. Точка $x_{k+1}$ вычисляется по формуле xk+1=xk−αkf−1xx(xk)fx(xk),
где $f_{xx}^{-1}(x_k)$ — матрица, обратная к матрице вторых производных $f_{xx}(x_k)$. При $α_k≡1$ этот метод называется методом Ньютона и часто применяется при решении прикладных задач. Недостатком этого метода является трудоёмкость вычислений и локальный характер сходимости.[7]
Существуют модификации метода Ньютона. В некоторых из них для уменьшения времени расчётов матрица $f_{xx}(x_k)$ фиксируется на нескольких подряд идущих шагах. В других вариантах шаг $α_k$ выбирается из условия минимума значения функции $f(x_{k+1})$ либо нормы её градиента.[8]
Перечисленные МБМ предназначены для отыскания локальных минимумов функции $f(x)$, и только для выпуклых функций найденные решения дают глобальный минимум. Задача о поиске минимума ещё более усложняется в случае отыскания условного минимума, когда на значения аргумента $x$ налагаются дополнительные ограничения.[9]
