Минимум функции многих переменных

Поиск минимумов (экстремумов) в многомерном пространстве рассмотрим на примере функции двух переменных F(x,y). Данная функция представляет собой трехмерную поверхность в пространстве (x,y,F). Нас интересует поиск точек, в которых достигается min F(x,y).

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

Рассмотрим характерные примеры рельефов. Для изображения различных рельефов поверхностей будем строить линии уровня. Если мысленно провести равноотстоящие плоскости F = const до пересечения с поверхностью (x,y,F) и полученные линии спроектировать на плоскость (x,y), то это и есть линии уровня. По виду линий уровня будем различать три типа рельефов: котловинный, овражный и неупорядоченный.

При котловинном рельефе линии уровня похожи на эллипсы. На рис.5,а приведен пример линий уровня эллиптической формы функции F(x,y) = x² + (x - y)².

Необходимыми условиями точки минимума являются уравнения:

. (15)

Если разложить функцию F(x,y) в окрестности невырожденного минимума в ряд Тейлора до второго порядка малости, то с учетом (15) получим выражение:

, (16)

причем линии уровня имеют эллиптическую форму в окрестности минимума, когда квадратичная форма (16) положительно определена©.

Рис.5,а. Пример котловинного рельефа	Рис.5,б. Овражный тип рельефа с кусочно-гладкими линиями уровнями
Рис.5,в. Пример разрешимого оврага	Рис.5,г. Пример неупорядоченного типа рельефа

При овражном типе рельефа рассмотрим два случая. Если линии уровня кусочно-гладкие, как на рис.5,б, то выделим на них точки излома. Совокупность точек излома назовем истинным оврагом или гребнем в зависимости того, растет или падает значение функции в направлении угла между линией излома и линией уровня. Если функция F гладкая, то и линии уровня являются гладкими, однако на них могут быть участки с большой кривизной. Геометрическое место точек с максимальной кривизной называют разрешимыми оврагами и гребнями. На рис.5,в приведен пример длинного разрешимого оврага, “дно” которого имеет форму синуса, а минимальная точка — начало координат. Наличие овражного рельефа указывает на то, что в задаче не учтена некая скрытая связь между переменными. Так, если в примере функции рис.5,в ввести замену переменных x = x, h = y - sinx, то функция F предстанет в виде: F = 10h ² + 0,1x ² и уже после замены переменных рельеф котловинный.

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

На листинге_№4 приведен код программы построения линий уровня поверхностей, представленных на рис.5.

Листинг_№4

%Примеры поверхностей для задачи минимизации

%функций двух переменных

%очищаем рабочее пространство

clear all

%построение котловинного рельефа, линии

%уровня похожи на эллипсы

% [x y]=meshgrid(-1.1:0.1:1.1,-1.5:0.1:1.5);

% F=x.^2+(x-y).^2;

% v=0:0.2:1;

% contour(x,y,F,v);

%построение овражного типа рельефа

% [x y]=meshgrid(-1.6:0.05:2.6,-2.2:0.05:2.2);

% F=abs(abs(x.^2+y.^2-1)-x);

% v=0:0.2:3;

% contour(x,y,F,v);

%построение рельефа типа разрешимого оврага

% [x y]=meshgrid(-3.5:0.05:3.5,-2.2:0.05:2.2);

% F=10*(y-sin(x)).^2+0.1*x.^2;

% v=[0.2 0.5 1 2.5 4 7];

% contour(x,y,F,v);

%построение примера неупорядоченного рельефа

[x y]=meshgrid(-2*pi:0.05:2*pi,-2*pi:0.05:2*pi);

lx=size(x); ly=size(y);

for i=1:lx(1)

for j=1:ly(1)

F(i,j)=(1+sin(x(i,j))^2)*(1+sin(y(i,j))^2);

end

end

v=[1.2 1.5 2 2.5 3 3.5];

contour(x,y,F,v);