2.2. Постановка задачи многомерной оптимизации
Пусть f(x) = f(x1, x2, … ,xn) – действительная функция n переменных, определенная на множестве X Rn. Точка x* X называется точкой локального минимума f(x) на множестве X, если существует такая -окрестность этой точки, что для всех x из этой окрестности, т. е., если x x* < , выполняется условие f(x*) f(x). Если выполняется условие f(x*) < f(x), то x* называется точкой строгого локального минимума. У функции может быть несколько локальных минимумов. Точка x* X называется точкой глобального минимума f(x) на множестве X, если для всех x X выполняется условие f(x*) f(x). Значение функции f(x*) называется минимальным значением f(x) на множестве X, Для нахождения глобального минимума необходимо найти все локальные минимумы и выбрать наименьшее значение. В дальнейшем будем рассматривать задачу нахождения локального минимума.
2.3. Необходимые сведения из курса математического анализа
Множество точек, для которых функция принимает постоянное значение f(x) = c, называется поверхностью уровня. Если число переменных n = 2, это множество называют линией уровня. На рис 2.1 показано, как получаются линии уровня для функции двух переменных. Функция f(x1, x2) задает в трехмерном пространстве некоторую поверхность u = f(x1, x2), низшая точка которой и дает решение задачи минимизации. Для того, чтобы изобразить рельеф этой поверхности, проведем несколько равноотстоящих плоскостей u = const. Проекции на плоскость (x1 x2) линий пересечения этих плоскостей с поверхностью u = f(x1, x2) и дают линии уровня.
Рис. 2.1
Вектор из первых частных производных
g(x)
= f
'(x)
=
называется градиентом. Если в точке x градиент не равен нулю, то он перпендикулярен проходящей через эту точку поверхности уровня и указывает направление наискорейшего возрастания функции. Вектор – g(x) называется антиградиентом и указывает направление наискорейшего убывания функции (рис. 2.2).
Рис. 2.2
Точка x, для которой градиент равен нулю, т.е.
f '(x) = 0, (2.11)
называется стационарной точкой. Условие (2.11) является необходимым условием того, чтобы точка x была точкой локального минимума дифференцируемой функции f(x).
Равенство (2.11) представляет собой систему n нелинейных уравнений с неизвестными x1, x2, …, xn, которая в развернутом виде выглядит так:
=
0,
……………………. (2.12)
=
0
Достаточным условием того, чтобы стационарная точка x была точкой локального минимума, является положительная определенность (см. п. 2.1) матрицы
G(x)
= f
"(x)
=
, (2.13)
составленной из вторых частных производных функции f(x). Матрица (2.13) называется матрицей Гессе.
Важную роль в задачах безусловной оптимизации играют квадратичные функции, которые имеют следующий вид:
f(x)
=
+
+
с.
(2.14)
Используя матричные обозначения, квадратичную функцию f(x) можно записать так:
f(x) = (Ax, x) + (b, x) + c, (2.15)
где A – симметричная положительно определенная матрица, b – вектор-столбец коэффициентов bj.
Вычислим градиент и матрицу Гессе для квадратичной функции (2.15). Продифференцировав f(x) по xk, получим
=
+
+
bk.
Так как aik = aki в силу симметрии матрицы A, получим формулу
= + bk. (2.16)
Матричная форма (2.16) имеет вид:
f '(x) = Ax + b. (2.17)
Дифференцируя обе части равенства (2.16) по xi, получим
=
aik.
Это означает, что для квадратичной функции (2.14) матрица Гессе не зависит от x и равна A.
Пример 2.1.
Дана квадратичная функция
f(x)
=
2x
–
2x1x2
+ 3x1x3
+x
–
2x2x3
+ 4x
+ x1
–
x2
+
3x3
+5.
Запишем матрицу A, вектор b и коэффициент c:
4 -2 3 1
A = -2 2 -2 , b = -1 , c = 5.
3 -2 8 3
Найдем первые производные f(x):
=
4x1–2x2
+3x3+1,
= –2x1+2x2
–
2x3
–
1,
= 3x1–2x2
+8x3
+
3.
Найдем вторые производные f(x):
=
4,
=
= –2,
=
= 3,
=
2,
=
= –2,
= 8.
Легко убедиться, что матрица Гессе равна A.
Пример 2.2.
f(x)
=
sinx1
+
е
+
x1x2.
Найдем первые производные f(x):
= cosx1 +x2, = е + x1.
Найдем вторые производные f(x):
= – sinx1, = = 1, = е .
Матрица Гессе равна
– sinx1 1
1 е .