Лекция: ВЫПУКЛЫЕ КВАДРАТИЧНЫЕ ФУНКЦИИ
Важную роль в ряде вопросов минимизации играют квадратичные функции, которые в n-мерном случае являются обобщением квадратного трехчлена одной переменной .
Определение 3.5.Функция вида
(3.21)
называется квaдрaтичной функцией п переменных.
Положив ai j = ai j + aji, получим симметрическую матрицу A= (ai j ), помощью которой выражение (3.21) можно записать в другой форме:
, (3.22)
где b = (b,.., bn) Î Еn — вектор коэффициентов bj .
Пример 3.3. Функция f(x) = 2x21 — 2x1x2 + 3x1x3 + x22 — 2x2x3 + 4x23 + x1 + 3x3 + 5 является квадратичной. Запишем ее матрицу A, вектор b и коэффициент с из (3.22):
, b =, c = 5.
Перечислим основные свойства квадратичных функций.
1. Для градиента квадратичной функции (3.22) справедлива формула
f ¢(x) = Ax + b. (3.23)
Запишем k-ю координату вектора f '(х):
2. Гессиан квадратичной функции (3.22) совпадаетс матрицейA:
f ¢¢(x) = A. (3.24)
Вычислим элемент матрицы Гессе:
.
3. Квадратичная функция (3.22) с положительно определенной матрицей A сильно выпукла.
Так как мaтрицa f"(x)= A симметрична и положительно определена, то все ее собственные значения li положительны и существует ортонормированный базис из собственных векторов этой матрицы (см. разд. 3.1.1). В этом базисе:
, .
Поэтому угловые миноры матрицы A-lЕ равны Dk=и положительны при 0< l < min li. Таким образом, существует число l > 0, при котором матрица A — lЕ положительно определена. А это означает, что f(х) сильно выпукла.
Замечание. Для квадратичной функции f(x) из (3.22) с положительно определенной матрицей A точка глобального минимума существует и единственна, так как f(х) сильно выпукла.
Пример 3.4. Квадратичная функция f(х) из примера 3.3 сильно выпукла. D Матрица f "(х) = A — положительно определена, так как
D1 = 4 > 0; D2 =; D3 = .
Следовательно, f(х) сильно выпукла по свойству 3 квадратичных функций.
Выпуклые квадратичные функции играют важную роль в теории одномерной оптимизации. Некоторые алгоритмы, разработанные с учетом свойств таких функций, позволяют найти их точку минимума за конечное число итераций. Во многих случаях эти алгоритмы оказываются эффективными и для неквадратичных выпуклых функций, так как в достаточно малой окрестности точки минимума х* дважды дифференцируемая функция f(х) с положительно определенной матрицей Гессе f(х) хорошо аппроксимируется сильно выпуклой квадратичной функцией (см. (3.4), где f ¢(x*) = 0).