Минимизация функции многих переменных градиентными методами

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

Введение. Данная задача формулируется как задача безусловной оптимизации, сутью которой является поиск минимума функции многих переменных на всем пространстве соответствующей размерности. Функцию многих переменных будем рассматривать как функцию, заданную в точках X n-мерного эвклидова пространства Eⁿ.

Рассмотрим основные методы решения задач безусловной минимизации вида:

где (2.1.)

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

или (2.2)

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

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

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

Постановка задачи.

Дана функция y=f(X) . Требуется найти минимум функции, используя градиентный метод или метод наискорейшего спуска

Градиентный метод.

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

( 2.3)

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

Так как направление наибыстрейшего возрастания функции в точке X совпадает с направлением градиента функции , т. е. вектора:

требуемое направление наибыстрейшего убывания соответствует направлению антиградиента, т.е. вектора , вычисленного в точке .

Таким образом, формула (2.3) принимает следующий вид:

(2.4)

Где норма градиента

Основную трудность представляет способ выбора величины градиентного шага. Существуют различные алгоритмы изменения шага в зависимости от того, удачной или нет оказались предыдущие итерации. Наиболее простым алгоритмом, обеспечивающим приемлемую скорость сходимости является следующий: предлагается увеличивать в 1,25 раза шаг , если попытка оказалась удачной и, соответственно, уменьшать его в 2 раза, если попытка неудачна. При этом, в случае неудачной попытки, т.е. , в формуле (2.4) меняется только шаг , то есть повторяется k-ая итерация.

В качестве критерия окончания счета используется следующее условие:

, где -заданная положительная величина.