Безусловной минимизации методы

БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ МЕТОДЫ, методы, предназначенные для нахождения минимума функции многих переменных f(х) в случае, когда на значения аргумента не налагаются дополнительные ограничения. Безусловной минимизации методы составляют важный класс методов оптимизации. Задача о нахождении максимума изменением знака функции f(х) сводится к задаче о нахождении минимума. В случае, когда f зависит от одной скалярной переменной х, минимизацию функции f(х) обычно называют одномерной. К группе методов одномерной минимизации относятся: метод половинного деления, случайный поиск, метод Фибоначчи, метод золотого сечения и др.

В безусловной минимизации методе в процессе минимизации строится некоторая последовательность точек х₁, х₂ x_k многомерного пространства и в зависимости от значений функции f в этих точках находится новая точка х_к+1. Правило построения последовательности определяется выбранным методом минимизации.

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

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

Другой класс образуют градиентные методы, в которых предполагается, что функция f один раз дифференцируема. В методе градиентного спуска после вычисления значения функции f и её градиента f_x в точке x_k новая точка находится по формуле

где α_k - неотрицательное число (шаг спуска). При некоторых условиях последовательность х₁, х₂, ... сходится к точке локального минимума функции f(х). Если при каждом k величина α_k определяется из условия одномерной минимизации функции f(x_k+1) по α_k, то приходят к методу наискорейшего спуска. Существуют также методы, называемые s- шаговыми, в которых новая точка х_k определяется по s предыдущим точкам. Одним из простейших двухшаговых методов является метод сопряжённого градиента, в котором

где α_k ≥ 0, β_k ≥0 - параметры, определяемые решением задачи двумерной минимизации f(x_k+1) по α_k и β_k.

К третьему классу относится метод Ньютона и его модификации. Предполагается, что функция f дважды дифференцируема. Точка x_k+1 вычисляется по формуле

где f^-1_xx(x_k) - матрица, обратная к матрице вторых производных f_xx(x_k). При α_k= 1 этот метод называется методом Ньютона и часто применяется при решении прикладных задач. Недостатком этого метода является трудоёмкость вычислений и локальный характер сходимости.

Существуют модификации метода Ньютона. В некоторых из них для уменьшения времени расчётов матрица f_xx(x_k) фиксируется на нескольких подряд идущих шагах. В других вариантах шаг α_k выбирается из условия минимума значения функции f(x_k+1) либо нормы её градиента.

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

Лит.: Химмельблау Д. Прикладное нелинейное программирование. М., 1975; Евтушенко Ю. Г. Методы решения экстремальных задач и их применение в системах оптимизации. М., 1982; Поляк Б. Т. Введение в оптимизацию. М., 1983; Васильев Ф. П. Методы оптимизации. М., 2002.