При решении задач САПР чаще всего приходится иметь дело с математическими моделями, в которых нет аналитических зависимостей для первых производных минимизируемой функции (). Поэтому поиск локального минимума в этом случае приходится вести по результатам вычислений только значений функции () – с помощью прямых методов оптимизации.

Рассматривается следующая многомерная задача безусловной оптимизации (точнее говоря, задача многомерной локальной безусловной оптимизации): найти минимум критерия оптимальности (), определенного в -мерном евклидовом пространстве ,

(1)

(2)

где вектор определяет направление вдоль -й координатной оси и представляет собой -мерный вектор с компонентами

а величины , ,..., – определяются из условий

(3)

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

Если положить =, =, то формулы (2), (3) можно записать в виде

(4)

(5)

Таким образом, каждая итерация по методу Гаусса-Зейделя включает в себя шагов. Каждая последующая итерация начинается из точки, полученной на последнем шаге предыдущей итерации. Поиск заканчивается при выполнении одного из стандартных условий окончания итераций:

(6)

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

1. Задаем начальную точку и полагаем =0 , =1.
2. Последовательно для =1,2,..., решаем задачи (5), т.е. исходя из предыдущей точки, отыскиваем минимум функции () вдоль -го координатного направления;
3. Если условие окончания поиска (6) или (6') выполнено, то полагаем и заканчиваем вычисления. Иначе - полагаем =+1 и переходим к п. 2

Метод Гаусса-Зейделя иллюстрирует рис. 1, на котором показан фрагмент линий уровня функции Химмельблау . На рис. 1 точка представляет собой локальный минимум функции () вдоль оси X₁ при исходной точке . Точка представляет собой локальный минимум функции () вдоль оси X₂ при исходной точке . Отыскание точки завершает первую итерацию. Следующая итерация начинается из точки =. И т.д.

x=-6:0.05:0;
y=x;
[X,Y]=meshgrid(x);
Z=(X.^2+Y-11).^2+(X+Y.^2-7).^2;
V=[1,4,8,16,32,64,100,150,200,250];
contour(X,Y,Z,V);

Рис. 1.  Траектория поиска минимума не овражной функции Химмельблау методом Гаусса-Зейделя.

Метод Гаусса-Зейделя медленно сходится на овражных функциях, в которых овраг не ориентирован в направлении какой-либо из координатных осей (см. рис. 2). На рисунке показаны линии уровня функции Розенброка (=2). Линии уровня получены с помощью следующей MATLAB-программы:

x=-2:0.06:2;
y=x;
[X,Y]=meshgrid(x);
Z=100.*(Y-X.^2).^2+(1-X).^2;
V=[1,5,50,500];
[C,h]=contour(X,Y,Z,V);
clabel(C,h);

Рис. 2.  Траектория поиска минимума овражной функции Розенброка методом Гаусса-Зейделя. Текущая точка быстро (в данном случае – за один шаг) «скатывается» на дно оврага и очень медленно движется по дну оврага к минимуму функции Ф(Х).