УМК (1013374), страница 2
Текст из файла (страница 2)
определение1.3), т.е. перпендикулярно к касательной плоскости, проведенной в точке x , в сторонунаибольшего возрастания функции в данной точке.Определение 1.5. Матрицей Гессе H ( x) дважды непрерывно дифференцируемойв точке x функции f ( x) называется матрица частных производных второго порядка, вычисленных в данной точке:⎛⎜⎜⎜⎜H ( x) = ⎜⎜⎜⎜⎜⎜⎝где hij =∂ 2 f ( x)∂x12∂ 2 f ( x)∂x2 ∂x12∂ f ( x)∂xn ∂x1∂ 2 f ( x) ⎞⎟∂x1∂xn ⎟⎟ ⎛ h11∂ 2 f ( x)∂ 2 f ( x) ⎟ ⎜h21∂x2 ∂xn ⎟ = ⎜∂x22⎟ ⎜⎟ ⎜⎟ ⎝ hn122∂ f ( x)∂ f ( x) ⎟…⎟∂xn ∂x2∂xn2 ⎠∂ 2 f ( x)∂x1∂x2h12h22hn 2h1n ⎞⎟h2n ⎟,⎟⎟hnn ⎠∂ 2 f ( x), i , j = 1,...
, n .∂ xi ∂ x jЗ а м е ч а н и я.1. Матрица Гессе является симметрической размеров (n × n ) .2. Вместе с градиентом можно определить вектор антиградиента, равный по модулю вектору градиента, но противоположный по направлению. Он указывает в сторонунаибольшего убывания функции в данной точке.3. С помощью градиента и матрицы Гессе, используя разложение в ряд Тейлора,приращение функции f ( x) в точке x может быть записано в формеΔf ( x) = f ( x + Δ x) − f ( x) = ∇f ( x)T Δ x +21 T2Δ x H ( x) Δ x + o ( Δ x ) ,2(1.2)где o ( Δ x ) – сумма всех членов разложения, имеющих порядок выше второго;Δ xT H ( x) Δ x – квадратичная форма.8Пример. Для функции f ( x) = x12 + x24 вычислить градиент и найти матрицу Гессе вточках x 0 = (0, 0) , x 1 = (1,1) .TT Согласно определениям 1.4 и 1.5 имеем:(∇f ( x) = 2 x1 , 4 x23)T0 ⎞⎛2, H ( x) = ⎜;⎜ 0 12 x 2 ⎟⎟2⎠⎝∇f ( x1 ) = ( 2, 4 )T⎛ 2 0⎞T∇f ( x 0 ) = ( 0, 0 ) , H ( x 0 ) = ⎜⎟;⎝0 0⎠⎛2 0 ⎞, H ( x1 ) = ⎜⎟.
⎝ 0 12 ⎠Определение 1.6. Квадратичная форма ΔxT H ( x) Δ x (а также соответствующая матрица Гессе H ( x) ) называется:• положительно определенной ( H ( x) > 0 ) , если для любого ненулевого Δ xвыполняется неравенство Δ xT H ( x) Δ x > 0 ;• отрицательно определенной ( H ( x) < 0 ) , если для любого ненулевогоΔxвыполняется неравенство Δ xT H ( x) Δ x < 0 ;• положительно полуопределенной ( H ( x) ≥ 0 ) , если для любого Δx выполняетсянеравенство Δ xT H ( x) Δ x ≥ 0 и имеется отличный от нуля вектор Δ x , для которого Δ xT H ( x) Δ x = 0 ;• отрицательно полуопределенной ( H ( x) ≤ 0 ) , если для любого Δ x выполняетсянеравенство Δ xT H ( x) Δ x ≤ 0 и имеется отличный от нуля вектор Δx , для которого Δ xT H ( x) Δ x = 0 ;x , что• неопределенной ( H (x ) >< 0 ) , если существуют такие векторы Δx , Δ ~выполняются неравенства Δ xT H ( x) Δ x > 0 , Δ xT H ( x) Δ x < 0 ;• тождественно равной нулю ( H ( x) ≡ 0 ) , если для любого Δx выполняетсяравенство Δ xT H ( x) Δ x = 0 .2.
НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ БЕЗУСЛОВНОГОЭКСТРЕМУМАПостановка задачиДана дважды непрерывно дифференцируемая функция f ( x) , определенная намножестве X = R n .Требуется исследовать функциюf ( x) на экстремум, т.е. определить точкиx ∗ ∈ R n ее локальных минимумов и максимумов на R n :f ( x∗ ) = min f ( x) ;x∈Rf ( x∗ ) = max f ( x) .nx∈R9n(2.1)Стратегия решения задачиНаходятся точки x ∗ локальных экстремумов с помощью необходимых условийпервого и второго порядка (порядок условий определяется порядком используемых производных), а также достаточных условий безусловного локального экстремума.
Вычисляются значения f ( x∗ ) функции в найденных точках локальных экстремумов.Утверждение 2.1 (необходимые условия экстремума первого порядка).Пусть x ∗ ∈ R n есть точка локального минимума (максимума) функции f ( x) намножестве R n и f ( x) дифференцируема в точке x ∗ . Тогда градиент функции f ( x)в точке x ∗ равен нулю, т.е.∇f ( x ∗ ) = 0(2.2)или∂ f ( x∗ )= 0,∂ xii = 1,... , n .(2.3)Определение 2.1. Точки x ∗ , удовлетворяющие условию (2.2) или (2.3), называютсястационарными.Утверждение 2.2 (необходимые условия экстремума второго порядка).Пусть точка x ∗ есть точка локального минимума (максимума) функции f ( x) намножестве R n и функция f ( x) дважды дифференцируема в этой точке. Тогда матрица Гессе H ( x∗ ) функции f ( x) , вычисленная в точке x ∗ , является положительно полуопределенной (отрицательно полуопределенной), т.е.H ( x∗ ) ≥ 0 ,(2.4)( H ( x∗ ) ≤ 0 ) .(2.5)Утверждение 2.3 (достаточные условия экстремума).Пусть функция f ( x) в точке x ∗ ∈ R n дважды дифференцируема, ее градиент равен нулю, а матрица Гессе является положительно определенной (отрицательно определенной), т.е.∇f ( x ∗ ) = 0 и H ( x ∗ ) > 0 ,(2.6)( H ( x∗ ) < 0 ) .(2.7)Тогда точка x ∗ есть точка локального минимума (максимума) функции f ( x) на множестве R n .10Определение 2.2.
Рассмотрим определитель матрицы Гессе H ( x∗ ) , вычисленнойв стационарной точкеdet H ( x∗ ) =1. Определители Δ1 = h11 ,h11h12h1nh21h22h2 nhn1hn 2hnnΔ2 =h11h12h21h22.h11h1n,..., Δ n =называютсяhn1hnnугловыми минорами.2. Определители m -го порядка ( m ≤ n ), получающиеся из определителя матрицыH ( x∗ ) вычеркиванием каких-либо ( n − m ) строк и ( n − m ) столбцов с одними и теми женомерами, называются главными минорами.Для проверки выполнения достаточных условий экстремума и необходимых условий второго порядка используются два способа.Первый способ (с помощью угловых и главных миноров – табл. 1).• Критерий проверки достаточных условий экстремума (критерий Сильвестра).Для того чтобы матрица Гессе H ( x∗ ) была положительно определенной( H ( x∗ ) > 0 ) и точка x ∗ являлась точкой локального минимума, необходимо и достаточно, чтобы знаки угловых миноров были строго положительны:Δ1 > 0 , Δ 2 > 0 ,..., Δ n > 0 .(2.8)Для того чтобы матрица Гессе H ( x ∗ ) была отрицательно определенной( H ( x ∗ ) < 0 ) и точка x ∗ являлась точкой локального максимума, необходимо и достаточно, чтобы знаки угловых миноров чередовались, начиная с отрицательного:Δ1 < 0 , Δ 2 > 0 , Δ 3 < 0 ,...,(−1)n Δ n> 0.(2.9)• Критерий проверки необходимых условий экстремума второго порядка.1.
Для того чтобы матрица Гессе H ( x∗ ) была положительно полуопределенной( H ( x∗ ) ≥ 0 ) и точка x ∗ может быть являлась точкой локального минимума, необходимо и достаточно, чтобы все главные миноры определителя матрицы Гессе были неотрицательны.2. Для того чтобы матрица Гессе H ( x∗ ) была отрицательно полуопределенной( H ( x∗ ) ≤ 0 ) и точка x ∗ может быть являлась точкой локального максимума, необходимо и достаточно, чтобы все главные миноры четного порядка были неотрицательны,а все главные миноры нечетного порядка – неположительны.11∗1п/п∗∇f ( x ) H ( x )Первый способТаблица 1Тип стационарной точки x ∗Локальный минимум10>0Δ1 > 0, Δ 2 > 0,..., Δ n > 020<030≥0Δ1 < 0, Δ 2 > 0,..., ( −1) Δ n > 0Все главные миноры определителяматрицы H ( x∗ ) неотрицательны40≤0Все главные миноры четногопорядка неотрицательны, а нечетного порядка неположительныМожет быть локальныйминимум, требуется дополнительное исследованиеМожет быть локальныймаксимум, требуется дополнительное исследование50=0Матрица Гессе состоит из нулевыхэлементовТребуется дополнительноеисследование60>0<Не выполняются условия п.
1–5Нет экстремумаnЛокальный максимумВторой способ (с помощью собственных значений матрицы Гессе – табл. 2).Определение 2.3. Собственные значения λ i , i = 1,..., n , матрицы H ( x∗ ) размеров(n × n)находятся как корни характеристического уравнения (алгебраического уравненияn -й степени):h11 − λh12h1nh21h22 − λh2 n(2.10)H ( x∗ ) − λ E == 0.hn1hn 2… hnn − λЗ а м е ч а н и е. Собственные значения вещественной симметрической матрицыH ( x ) вещественные.Таблица 21Второй способТип стационарной точки x ∗п/п1Локальный минимумλ1 > 0,..., λ n > 0*2λ1 < 0,..., λ n < 0Локальный максимум3λ1 ≥ 0,..., λ n ≥ 04λ1 ≤ 0,..., λ n ≤ 05λ1 = 0,..., λ n = 0Может быть локальный минимум, требуетсядополнительное исследованиеМожет быть локальный максимум, требуетсядополнительное исследованиеТребуется дополнительное исследование6λ i имеют разныезнакиНет экстремума12Алгоритм решения задачиШаг 1. Записать необходимые условия экстремума первого порядка в виде (2.3) инайти стационарные точки x ∗ в результате решения системы n в общем случае нелинейных алгебраических уравнений с n неизвестными.
Для численного решения системы могут использоваться методы простой итерации, Зейделя, Ньютона.Шаг 2. В найденных стационарных точках x ∗ проверить выполнение достаточных,а если они не выполняются, то необходимых условий второго порядка с помощью одного из двух способов (см. табл. 1 и 2).Шаг 3. Вычислить значения f ( x* ) в точках экстремума.Описанный алгоритм отображен на рис. 1, где показана последовательность действий в случаях выполнения и невыполнения соответствующих условий экстремума приприменении первого способа.З а м е ч а н и я.1.
Продолжение исследований, которое требуется в ряде случаев, разобранных втабл. 1 и 2, при решении практических задач, как правило, не проводится, за исключением небольшого числа модельных примеров.2. Часто на практике, особенно при применении численных методов поиска экстремума, рассматриваемых в последующих разделах, требуется проверить, выполняютсяли необходимые и достаточные условия экстремума в некоторой точке. Такой анализ необходим, так как многие численные методы позволяют найти лишь стационарную точку,тип которой требует уточнения.Необходимые условия экстремумапервого порядкаДостаточные условияэкстремумаВычислить значения функциив точках экстремумаНет экстремумаНеобходимые условия экстремумавторого порядкаПродолжениеисследованийРис. 113Нет экстремумаЛекция 23.
НЕОБХОДИМЫЕ И ДОСТАТОЧНЫЕ УСЛОВИЯ УСЛОВНОГОЭКСТРЕМУМАПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ОПРЕДЕЛЕНИЯОбщая постановка задачи и основные положения изложены в разд. 1. Здесь мы рассмотрим случаи, когда множество допустимых решений X задается равенствами и неравенствами, т.е.f ( x∗ ) = min f ( x) ;x ∈Xf ( x∗ ) = max f ( x) ,(3.1)x∈X⎧⎪ g j ( x) = 0, j = 1,… , m; m < n ⎪⎫где X = ⎨ x⎬ , m и p – числа; f ( x) –g(x)≤0,j=m+1,…,pj⎩⎪⎭⎪g j ( x), j = 1,… , p , – функции, задающие ограничения (условия).целевая функция,Будем считать функции f ( x) ; g j ( x), j = 1,… , p , дважды непрерывно дифференцируемыми на множестве R n , а функции g j ( x) , задающие ограничения, – называть длякраткости просто ограничениями.
При p = m задача (3.1) со смешанными ограничениямипреобразуется в задачу с ограничениями типа равенств, а при m = 0 в задачу с ограничениями типа неравенств.Определение 3.1. ФункцияpL ( x, λ 0 , λ ) = λ 0 f ( x ) + ∑ λ j g j ( x )(3.2)j =1называется обобщенной функцией Лагранжа, числа λ 0 , λ1 ,… , λ p – множителями Ла-(гранжа, λ = λ1 , … , λ p)T . Классической функцией Лагранжа называется функцияpL ( x, λ ) = f ( x ) + ∑ λ j g j ( x ) .(3.3)j =1Определение 3.2. Градиентом обобщенной (классической) функции Лагранжа по xназывается вектор-столбец, составленный из ее частных производных первого порядка поx i , i = 1,... , n :⎛ ∂ L (x , λ 0 , λ ) ⎞⎜⎟∂ x1⎜⎟⎟,∇ x L (x , λ 0 , λ ) = ⎜(3.4)⎜ ∂ L (x , λ 0 , λ ) ⎟⎜⎜⎟⎟∂ xn⎝⎠⎡⎛ ∂ L (x , λ ) ⎞ ⎤⎟⎥⎜⎢x∂⎟⎥⎜1⎢⎟⎥.⎜()Lx,∇λ=⎢ x⎟⎥⎜()Lx,∂λ⎢⎜⎢⎜ ∂ x n ⎟⎟ ⎥⎠⎦⎝⎣14Определение 3.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
