Поиск экстремумов функции нескольких переменных

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

Многомерная задача оптимизации формулируется следующим образом:

f(x)min, x Rⁿ, Rⁿ-n-мерное пространство

(т.е. ограничения на х отсутствуют),

где х=(x₁, x₂,…, x_n)^T – вектор управляемых переменных размерностью n, f - скалярная целевая функция.

Т очка х является точкой глобального минимума, если для всех x Rⁿ, выполняется неравенство: f = f(x)-f(x)0 (1).

Точку глобального минимума будем обозначать х**.

Если формула (1) справедлива лишь в некоторой -окрестности точки х, т.е. для всех х, таких, что ||x-x||<, при заданном >0, то х есть точка локального минимума. Ее будем обозначать х*. Норма (модуль, длина) вектора

| |x||=(x, x)=x^T x=x₁² + x₂² + … +x_n²

(x, x)=x^T x – скалярное произведение х на себя x^T = (x₁, x₂, …, x_n)

Е сли же выполняется f = f(x) - f(x)  0, (2)

т о х есть точка максимума (локального или глобального в соответствии с данными ранее определениями).

Исключение знака равенства из формул (1) и (2) позволяет определить точку строгого минимума или максимума.

В случае, когда f принимает как положительные и отрицательные, так и нулевые значения в зависимости от выбора точек из  - окрестности, точка х представляет собой седловую точку.

Точка х, в которой находится минимум или максимум, или седловая точка, должна удовлетворять условию стационарности:

 f(x) = 0 (x – стационарная точка)

f f f ^T

f(x) = x₁, x₂, …, x_n - градиент функции f(x) = f(x₁, x₂, …, x_n)

Приведем некоторые сведения из линейной алгебры.

Квадратичной формой называется функция n переменных вида:

A(x₁, x₂, …, x_n) = A(x) = _i=1ⁿ_j=1ⁿ q_ijx_ix_j = x^TQx, где

x

x = x , Q_(n*n) = [q_ij] – матрица.

…

x

Q будем считать симметрической матрицей.

Определения:

1. матрица Q является положительно определенной тогда и только тогда, когда x^TQx > 0 для всех х  0.

2. матрица Q является положительно полуопределенной тогда и только тогда, когда значения квадратичной формы x^TQz  0, для всех х и существует вектор х  0 такой, что x^TQz = 0.

3. матрица Q является отрицательно определенной тогда и только тогда, когда -Q есть положительно определенная матрица. Другими словами – тогда и только тогда, когда x^TQx < 0 для всех х  0.

4. матрица Q является отрицательно полуопределенной тогда и только тогда, когда -Q есть положительно полуопределенная матрица.

5. матрица Q является неопределенной, если квадратичная форма x^TQx может принимать как положительные, так и отрицательные значения.

Справедливы следующие утверждения:

1 ) Стационарная точка х есть точка минимума, если H_f(x) = ²f(x) - положительно полуопределенная матрица.

H_f(x) = ²f(x) = [²f/(x_ix_j)] – матрица Гессе (гессиан)

2) Стационарная точка х есть точка максимума, если H_f(x) = ²f(x) - отрицательно полуопределенная матрица.

1. Стационарная точка х есть седловая точка, если H_f(x) = ²f(x) - неопределенная матрица.

Необходимые условия: для наличия в точке х* локального минимума необходимо, чтобы выполнялось равенство:

f(x*) = 0 (чтобы точка х* была стационарной)

и матрица H_f(x*) = ²f(x*) была положительно полуопределенной. (неотрицательно определенной) H_f(x) = ²f(x) = [²f/(x_ix_j)] – матрица Гессе (гессиан).

Достаточные условия: Если f(x*) = 0 и матрица H_f(x*) = ²f(x*) – положительно определена, то х* точка изолированного (строгого) локального минимума функции f(x).

Примечание. Если удастся показать, что x^T²f(x)  0 для всех х, то f(x) является выпуклой функцией, а локальный минимум оказывается глобальным.