Диссертация (1149223), страница 20

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 20)

для любого x ∈ X существует λ ∈ Λ такое, что ϕλ (x, 0) = 0.Замечание 4.4.1. Отметим, что семейство {ϕλ (x, ·)}, λ ∈ Λ, может и не быть исчерпывающимсемейством слабых неодн. в.в.а. функции f в точке x.101Зафиксируем любые µ > 0 и 1 < r < +∞. Напомним, что1k(a, p)kr = (|a|r + kpkr ) r∀(a, p) ∈ R × X ∗ .Для любого x ∈ X определим множестваΛµ (x) = {λ ∈ Λ | ϕλ (x, 0) 6 µ},Λ0 (x) = {λ ∈ Λ | ϕλ (x, 0) = 0}.Согласно сделанным предположениям Λ0 (x) 6= ∅.Воспользовавшись теоремой о необходимом условии минимума в терминах неодн. в.в.а.4.3.1 и теоремой о субдифференциале супремума выпуклых функций 1.3.10, нетрудно получить, что если x является точкой локального минимума функции f , то0 ∈ Cλ (x) ∀λ ∈ Λ0 (x).(4.19)Точку x ∈ X в которой выполнено условие (4.19) будем называть inf–стационарной точкойфункции f .Теоретическая схема метода спуска имеет следующий вид:1.

Выбрать x0 ∈ X.2. k-ая итерация (k > 0):(a) Для каждого λ ∈ Λµ (xk ) найти (ak (λ), pk (·; λ)) ∈ Cλ (xk ) такое, чтоinf(a,p)∈Cλ (xk )k(a, p)kr = k(ak (λ), pk (·; λ))kr .(b) Для каждого λ ∈ Λµ (xk ) вычислить ∆xk (λ) ∈ X такое, чтоinf pk (∆x; λ) = pk (∆xk (λ); λ)∆x∈SX(если pk (·; λ) = 0, то положим ∆xk (λ) = 0).(c) Для каждого λ ∈ Λµ (xk ) вычислить αk (λ) по правилуinf f (xk + α∆xk (λ)) = f (xk + αk (λ)∆xk (λ)).α>0(d) Выбрать ∆xk ∈ X и αk ∈ [0, +∞) по правилуinfλ∈Λµ (xk )f (xk + αk (λ)∆xk (λ)) = f (xk + αk ∆xk )и положить xk+1 = xk + αk ∆xk .Если на некотором шаге алоритма получится, что для любого λ ∈ Λ0 (xk ) будетinf{k(a, p)kr | (a, p) ∈ Cλ (xk )} = 0, то нетрудно проверить, что точка xk является inf–стационарной точкой функции f .Замечание 4.4.2.

Предложенный метод спуска тесно связан с методами минимизации функций, обладающих верхним коэкзостером, изучавшимися в работах [1, 3].1024.4.2Исследование метода спускаИзучим свойства последовательности, определяемой по методу спуска, описанному выше. Для этого, как и в случае метода кодифференциального спуска, предположим, что пространство X рефлексивно и строго выпукло.Пусть на k-м шаге метода была получена точка xk .Предложение 4.4.2.

Если для некоторого λ ∈ Λ0 (xk ) будет 0 ∈/ Cλ (xk ), то pk (·; λ) 6= 0 и∆xk (λ) 6= 0.Доказательство. Поскольку 0 ∈/ Cλ (xk ), то по следствию 3.6.1 имеем, что для любых (a, p) ∈Cλ (xk ) будет− sign(ak (λ))|ak (λ)|r−1 a + kpk (·; λ)kr−1 p(∆xk (λ)) ≤ −(k(ak (λ), pk (·; λ))kr )r < 0.Откуда для любого (0, p) ∈ Cλ (xk ) будетkpk (·; λ)kr−1 p(∆xk (λ)) ≤ −(k(ak (λ), pk (·; λ))kr )r < 0.Следовательно pk (·; λ) 6= 0 и ∆xk (λ) 6= 0.Покажем теперь, что предложенный метод действительно является методом спуска.Предложение 4.4.3.

Пусть функция f дифференцируема по направлениям в точке xk .Тогда, если xk не является inf–стационарной точкой функции f , то существует λ ∈ Λ0 (xk )такое, что f 0 (xk , ∆xk (λ)) < 0, откуда следует, чтоf (xk+1 ) < f (xk ).Доказательство. Поскольку xk не является inf–стационарной точкой функции f , то существует λ ∈ Λ0 (xk ) такое, что 0 ∈/ Cλ (xk ). Откуда, рассуждая как и при доказательстве предыдущего предложения получим, что для любого (0, p) ∈ Cλ (xk ) справедливо неравенствоp(∆xk (λ)) 6 σ = −1(k(ak (λ), pk (·; λ))kr )r .kpk (·; λ)kr−1Следовательно, с учётом теоремы 1.3.6 о производной по направлениям выпуклой функции,имеемϕ0λ,k (0, ∆xk (λ)) =max(0,p)∈Cλ (x)p(∆xk (λ)) 6 σ < 0,где ϕλ,k (·) = ϕλ (xk , ·). Поэтому по предложению 4.4.1 будетf 0 (xk , ∆xk (λ)) 6 ϕ0λ,k (0, ∆xk (λ)) < 0,что и требовалось.103Оценим убывание функции f вдоль каждого из направлений ∆xk (λ).

Для упрощениязаписи введём обозначенияξk (λ) =1/kpk (·; λ)kr−1 , если kpk (·; λ)k =6 0,1, в противном случае.иηk (λ) =− sign(ak (λ))|ak (λ)|r−1 /kpk (·; λ)kr−1 , если kpk (·; λ)k =6 0,− sign(ak (λ))|ak (λ)|r−1 , в противном случае.Предложение 4.4.4. Если xk ∈ X не является inf–стационарной точкой функции f , тодля любого λ ∈ Λµ (xk ) существует αλ > 0 такое, чтоf (xk + α∆xk (λ)) 6 f (xk ) − αξk (λ)(k(ak (λ), pk (·; λ))kr )r +(1 − αηk (λ))bk (λ) + o(α, xk ) ∀α ∈ (0, αλ ),где o(α, xk )/α → 0 при α ↓ 0 и bk (λ) = max{a | (a, p) ∈ Cλ (xk )}.Доказательство. Зафиксируем произвольное λ ∈ Λµ (xk ). Пусть 0 ∈/ Cλ (xk ), тогда по следствию 3.6.1 имеем, что для любых (a, p) ∈ Cλ (xk ) будет− sign(ak (λ))|ak (λ)|r−1 a + kpk (·; λ)kr−1 p(∆xk (λ)) ≤ −(k(ak (λ), pk (·; λ))kr )r .(4.20)Если же 0 ∈ Cλ (xk ), то данное неравенство очевидно.

Из (4.20) имеем, чтоp(∆xk (λ)) 6 −ξk (λ)(k(ak (λ), pk (·; λ))kr )r − ηk (λ)a ∀(a, p) ∈ Cλ (xk ).Откуда, с учётом того, что ϕλ (xk , ·) является слабой неодн. в.в.а. функции f в точке xk ,получаем, чтоf (xk + α∆xk (λ)) − f (xk ) 6 ϕλ (xk , α∆xk (λ)) + oλ (α, xk ) =+ oλ (α, xk ) 6 −αξk (λ)(k(ak (λ), pk (·; λ))kr )r +max(a,p)∈Cλ (xk )max(a + αp(∆xk (λ)))+(a(1 − αηk (λ))) + oλ (α, xk ),(a,p)∈Cλ (xk )где oλ (α, xk )/α → 0 при α ↓ 0. При достаточно малых α > 0 будет (1 − αηk (λ)) > 0, откудаf (xk + α∆xk (λ)) − f (xk ) 6 −αξk (λ)(k(ak (λ), pk (·; λ))kr )r + (1 − αηk (λ))bk (λ) + o(α, xk ),что и требовалось.Замечание 4.4.3. Отметим, что для любого λ ∈ Λµ (xk ) будет bk (λ) ∈ [0, µ], поэтому, как и вслучае метода кодифференциального спуска, направление ∆xk (λ) может и не быть направлением спуска.

В этом направлении функция f может сначала возрастать, а потом убывать.Таким образом, предложенный метод спуска позволяет “обходить” некоторые точки локального минимума.1044.4.3Сходимость метода спускаПокажем, что при некоторых предположениях все предельные точки последовательности, построенной по методу спуска, если они существуют, являются inf–стационарнымиточками функции f . Для этого нам потребуется вспомогательное определение.Определение 4.4.1. Будем говорить, что семейство {ϕλ }, λ ∈ Λ, равномерно аппроксимирует функцию f в окрестности точки x, если для любого λ ∈ Λ0 (x) существует окрестностьO точки x такая, что для любых y ∈ O и ∆y ∈ X справедливо неравенствоf (y + ∆y) − f (y) 6 ϕλ (y, ∆y) + oλ (∆y, y),где oλ (α∆y, y)/α → 0 при α ↓ 0 равномерно по y ∈ O и ∆y ∈ SX .Справедлива следующая теорема о стационарности предельных точек последовательности, построенной по методу спуска.Теорема 4.4.1.

Пусть X — строго выпуклое рефлексивное нормированное пространствои inf x∈X f (x) > −∞. Предположим также, что существует предельная точка x∗ ∈ Xпоследовательности {xk } построенной по методу спуска для функции f , а семейство {ϕλ },λ ∈ Λ, равномерно аппроксимирует функцию f в окрестности точки x∗ . Тогда x∗ являетсяinf–стационарной точкой функции f .Доказательство. Без ограничения общности можно считать, что последовательность {xk }сходится к точке x∗ . Предположим, что точка x∗ не является inf–стационарной.

Тогда существует λ0 ∈ Λ0 (x∗ ) такое, что 0 ∈/ Cλ0 (x∗ ). Положимmin(a,p)∈Cλ0 (x∗ )k(a, p)kr = k(a∗ , p∗ )kr .Поскольку 0 ∈/ Cλ0 (x∗ ), то по предложению 4.4.2 будет kp∗ k > 0.По предположению многозначное отображение Cλ0 (·) непрерывно, поэтому при k → ∞будетbk (λ0 ) → 0 =max(a,p)∈Cλ0 (x∗ )a,k(ak (λ0 ), pk (·; λ0 ))kr → k(a∗ , p∗ )kr ,(4.21)а тогда, начиная с некоторого номера, имеем kpk (·; λ0 )k > 0 и при k → ∞ξk (λ0 ) → ξ ∗ =1,∗kp kr−1ηk (λ0 ) → η ∗ =− sign(a∗ )|a∗ |r−1.kp∗ kr−1(4.22)Из (4.22) следует, что существует такое α∗ > 0, что при достаточно больших k будет (1 −α∗ ηk (λ0 )) > 0 (см.

доказательство предложения 4.4.4) и поэтому для любого α ∈ (0, α∗ ) будетf (xk + α∆xk (λ0 )) 6 f (xk ) − αξk (λ0 )(k(ak (λ0 ), pk (·; λ0 ))kr )r + (1 − αηk (λ0 ))bk (λ0 ) + o(α, xk ),105где o(α, xk )/α → 0 при α ↓ 0. Также из (4.22) получаем, что начиная с некоторого номера,f (xk + α∆xk (λ0 )) 6 f (xk ) −3α ∗ξ (k(a∗ , p∗ )kr )r + (1 − αηk (λ0 ))bk (λ0 ) + o(α, xk ).4Поскольку семейство {ϕλ }, λ ∈ Λ, равномерно аппроксимирует функцию f в окрестноститочки x∗ , то найдется 0 < α0 < α∗ такое, что при достаточно больших k будетf (xk + α0 ∆xk (λ0 )) 6 f (xk ) −α0 ∗ξ (k(a∗ , p∗ )kr )r + (1 − α0 ηk (λ0 ))bk (λ0 ).2Так как bk (λ0 ) → 0 и ηk (λ0 ) → η ∗ (см. (4.21) и (4.22)), то при k больше некоторого k0 ∈ N,имеемf (xk + α0 ∆xk (λ0 )) 6 f (xk ) −α0 ∗ξ (k(a∗ , p∗ )kr )r .4Тем более f (xk+1 ) 6 f (xk ) − α40 ξ ∗ (k(a∗ , p∗ )kr )r .

Отсюда следует, что при k → ∞ будет f (xk ) →−∞, а это противоречит предположению inf x∈X f (x) > −∞.Замечание 4.4.4. В случае когда пространство X конечномерно, выполнение одного из условий:1. множество {x ∈ X | f (x) 6 f (x0 )} ограничено,2. limkxk→∞ f (x) = +∞гарантирует существование предельных точек у последовательности, построенной по методуспуска.4.4.4Метод спуска и метод кодифференциального спускаУкажем как с помощью предложенного выше метода спуска можно упростить методкодифференциального спуска в случае, когда гипердифференциал исследуемой функции является выпуклым многогранником.

Для этого нам потребуется вспомогательное определение,выделяющее определённый класс кодифференцируемых функций.Определение 4.4.2. Пусть функция f : Ω → R непрерывно кодифференцируема на Ω. Будем говорить, что кодифференциал функции f разложим на множестве Ω, если существуеткодифференциальное отображение функции f на множестве Ω видаdf (x) = co{(ai (x), pi (·; x)) ∈ R × X ∗ | i ∈ I},df (x) = co{(bj (x), qj (·; x)) ∈ R × X ∗ | j ∈ J},где I = {1, . . .

Характеристики

Список файлов диссертации