2.2.4 Метод Фибоначчи

Метод, использующий числа Фибоначчи, позволяет наиболее эффективно достичь заданной точности в поиске экстремума функции Q (u). Числа Фибоначчи определяются соотношением

F0 = F1 = 1; Fk = Fk-1 + Fk-2; k = 2, 3, …

При большом "k" отношение соседних чисел Фибоначчи близко к отношению "золотого сечения".

Этот метод делит интервал неопределенности не в постоянном соотношении, а в переменном и предполагает некоторое, вполне определенное, зависящее от , число вычислений значений функцииQ (u).

По заданному определяется количество вычислений n и соответствующее ему число Фибоначчи Fn, исходя из соотношения

В остальном схема метода близка к методу "золотого сечения" в котором значение x1 и x2 (см. рис.2.8) определяются отношением соответствующих чисел Фибоначчи.

Рис.2.8 - Блок-схема метода Фибоначчи

Методы многомерной оптимизации

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

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

В зависимости от принятого алгоритма и выбора начальной точки этим пределом может быть локальный или глобальный экстремум функции Q (u).

Метод Гаусса-Зайделя

Метод заключается в последовательном определении экстремума функции одной переменной с точностью до ε вдоль каждой координаты, т.е. фиксируются все координаты, кроме одной, по которой и осуществляется поиск экстремума Q. Потом та же процедура осуществляется при фиксации следующей координаты.

После рассмотрения всех n координат выполняется возврат к первой и вновь производится поиск локального экстремума вдоль каждой из n координат до тех пор, пока экстремум не будет локализован с заданной точностью (см. рис.2.9).

Рисунок 2.9 - Характер движения к оптимуму в методе Гаусса-Зейделя

Метод градиента

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

Идея метода заключается в том, что находятся значения частных производных по всем независимым переменным , = 1, n, которые определяют направление градиента в рассматриваемой точке =, и осуществляется шаг в направлении обратном направлению градиента, т.е. в направлении наибыстрейшего убывания целевой функции (если ищется минимум). Итерационный процесс имеет вид где параметрзадает длину шага.

Алгоритм метода градиента при непосредственном его применении включает в себя следующие этапы: 1) Задается начальное значение вектора независимых переменных (), определяющего точку, из которой начинается движение к минимуму. 2) Рассчитывается значение целевой функции в начальной точке (). 3) Определяется направление градиента в начальной точке (рис.2.10).

Рисунок 2.10 - Характер движения к оптимуму в методе градиента

4) Делается шаг в направлении антиградиента при поиске минимума, в результате чего попадают в точку .

5) Процесс поиска продолжается, повторяя все этапы с п.2, т.е. вычисляется) определяется направление градиента в точкеu¹, делается шаг и т.д.

Важной задачей в этом методе является выбор шага. Если размер шага слишком мал, то движение к оптимуму будет долгим из-за необходимости расчета целевой функции и ее частных производных в очень многих точках. Если же шаг будет выбран слишком большим, то в районе оптимума может возникнуть "рыскание", которое либо затухает слишком медленно, либо совсем не затухает. На практике сначала шаг выбирается произвольно. Если окажется, что направление градиента в точке u1 существенно отличается от направления в точке u², то шаг уменьшают, если отличие векторов по направлению мало, то шаг увеличивают. Изменение направления градиента можно определять по углу поворота градиента рассчитываемого на каждом шаге по соответствующим выражениям.

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