Методы поиска экстремума функции многих переменных.

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

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

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

f(x₁, x₂, …, x_n)=f(x)

Градиенты функции обозначают f(x) или g(x). Тогда g(x)=0. В случае глобального max f(x)< f(x₀).

Точно также как и для функции одной переменной имеем:

- максимум, если второе произведение от f по х, т.е. G(x)-гессиан, отрицательно определен

- минимум, если G(x) положительно определен.

Пример: f(x)=x₁²+x₂²+x₃²-2x₁-4x₂-6x₃+50

g(x)= x₁=1, x₂=2, x3=3.

G(x)= - положительно определен. Все собственные значения равны 2.

В точке (1, 2, 3) f(x) достигает максимума.

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

по координатам х задан Δ х. Он обычно одинаков для всех координат х.

Когда найдено значение всех координат в точке экстремума x₁^*, x₂^*, …, x^* (одна итерация), шаг уменьшаемся.

Процесс итерации заканчивается, если изменение шага не приводит к изменению функции.

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

Пример сепарабильной функции:

F(x)= F_i(x_i – x_i^*), где

F_i – унимодальные функции минимумом в начале координат.

Графическая иллюстрация для одной итерации:

- найдены x₁^* и x₂^*.

^- для малого шага Δ х= Δ х₁= Δ х₂. Значения x_1к^* и x_2к^* должны совпадать

для очередных приближений.

F=x₁²+x₂²+x₃²

F= (x₁ –1)²+(x₂ - 2)²+(x₃-3)²=0

Procedure COORD;

var I: integer; var E, B, C, L, H: real; label 1, 2;

begin

H: =0.1; E: =1E-5; L: =H;

2: for I: =1 to N do

begin

B: =1E+38;

1: x[I]: =x[I]+H; FUNK; C: =B; B: =F;

if (F-C)< 0 then goto 1;

H: =-H/3;

if abs(H)> =abs(L/3) then goto 2;

H: =L;

end;

L: =L/9; H: =L;

if E/9< =L then goto 1;

write(x);

end;

Число переменных N задано и описано в основной программе. Вектор Х должен быть задан по начальным приближениям Х⁰ и описан в основной программе.

Результат расчета процедуры FUNK должен содержаться в F. Входным параметром ее должен быть Х.

Разновидностью метода является метод спирального покоординатного спуска.

При использовании этого метода шаг по координатам меняется при переходе от одной переменной к другой.

Procedure COORDS;

var I: integer; var B, C, N, E: real; label 1, 2;

begin

H: =0.1; E: =1E-5;

2: for I: =1 to N do

begin

B: =1E+38;

1: x[I]: =x[I]+H; FUNK; C: =B; B: =F;

if (F-C)< 0 then goto 1;

end;

H: =-H/5;

if abs(H)> abs(E/3) then goto 2;

write(x);

end;

Методы покоординатного спуска плохо работают, если функция имеет “овраг”, дно которого не ориентировано вдоль координатных осей.