Здесь приводится только один из наиболее часто используемых методов – метод ньютона – рафсона.

Он основан на линейной аппроксимации первой производной минимизируемой функции f в окрестности текущей точки x_k:

В стационарной точке аппроксимации, которая принимается за очередное приближение x_{k+ 1}, производная равна нулю:

.

Отсюда следует рекуррентная формула для построения последовательности приближений к искомому минимуму:

(8.41)

Очевидно, что применение (8.41) возможно только при условии, что для каждого k. Поиск завершается по условию достижения точности, заданной величиной первой производной | f ' (x_k) | < e ₁ или расстоянием между двумя точками | x_{k+ 1}- x_k | < e. Возможно одновременное использование этих условий.

В общем случае процедура (8.41) не гарантирует сходимость к стационарной точке. Если начальная точка достаточно близка к стационарной, то метод сходится. При сходимости обеспечивается высокая скорость приближения к минимуму. На рис. 8.14 приведен случай сходимости метода. Очередному приближению соответствует точка пересечения оси x аппроксимирующей прямой. Как видно, последовательность точек x ₀, x ₁, x ₂,… приближается к минимуму x^*.

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

 

Многомерный поиск безусловного минимума

Здесь рассматриваются методы прямого поиска (разд. 8.8.1, 8.8.2 и 8.8.3), градиентные методы (разд.8.8.4), метод второго порядка, алгоритмы случайного поиска и приводятся краткие сведения о других методах.

8.8.1. Метод Гаусса-Зейделя (покоординатного спуска)

Процедура поиска сводится к решению последовательности задач одномерной минимизации по каждой переменной. Пусть выбрана начальная точка

.

Зафиксируем все переменные, кроме первой, на начальных значениях и решаем задачу

одним из одномерных методов. Фиксируем х ₁ на полученном в решении значении x₁' и делаем свободной переменную х ₂. Приходим к очередной одномерной задаче

.

Аналогично строятся и решаются последующие одномерные задачи, последняя из которых имеет вид:

.

Эти n задач составляют один цикл. Его результатом является точка X¹. Она принимается за начальную точку для следующего аналогичного цикла. Поиск заканчивается, когда расстояние между двумя последовательными точками становится меньше заданной величины:

.

Работу метода иллюстрирует рис. 8.16, на котором показана траектория поиска минимума функции f= (2- x ₁)⁴+2(x ₁-2 x ₂)².

x2

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

Из анализа траекторий поиска в приведенных примерах можно заключить, что эффективность поиска повысится, если к описанным однотипным циклам добавить движение в направлении, проходящем через точки X^{( k )} и X^{( k +1)}. Это движение называют ускоряющим шагом. Он используется в методе, рассматриваемом в следующем разделе.

Метод Хука-Дживса (метод конфигураций)

Метод первого порядка

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

Рассматриваемый метод средней точки алгоритмически является самым простым из методов одномерной оптимизации на заданном интервале. Он заключается в определении средней точки интервала c= (a+b) / 2 и вычислении в ней производной.

Если f ' (c) < 0, полагают а = с, при f ' (c) > 0, принимают b = с. Условие окончания поиска учитывает точность по координате e и по производной функции e ₁:

((b-a)< e) & (| f ' (c) | < e ₁).

Эффективность метода зависит от трудоемкости вычисления производной. Задаваемая точность e ₁ не дожна быть выше точности вычисления производной. С ростом трудоемкости и снижением точности вычислений производной следует отдавать предпочтение прямым методам.

Методы второго порядка

Методы применимы к дважды дифференцируемым функциям. При этом предъявляются высокие требования к точности вычисления производных. Наиболее удачными считаются задачи, в которых известно аналитическое выражение первой производной, а еще лучше – и второй.