 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Выпуклые квадратичные функции
|
|
Важную роль в ряде вопросов минимизации играют квадратичные функции, которые в n -мерном случае являются обобщением квадратного трехчлена одной переменной 
.
Определение 3.5. Функция вида
(3.21)
называется квaдрaтичной функцией п переменных.
Положив a i j = a i j + a ji, получим симметрическую матрицу A = (a i 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) = A x + b. (3.23)
Запишем k- ю координату вектора f '(х):
2. Гессиан квадратичной функции (3.22) совпадаетс матрицей A:
f ¢¢(x) = A. (3.24)
Вычислим элемент матрицы Гессе:
.
3. Квадратичная функция (3.22) с положительно определенной матрицей A сильно выпукла.
Так как мaтрицa f"(x)= A симметрична и положительно определена, то все ее собственные значения l i положительны и существует ортонормированный базис из собственных векторов этой матрицы (см. разд. 3.1.1). В этом базисе:
, 
.
Поэтому угловые миноры матрицы A -l Е равны D k = 
и положительны при 0< l < min l i. Таким образом, существует число 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).
Дата публикования: 2015-04-07; Прочитано: 675 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
