Диссертация (1149223), страница 15
Текст из файла (страница 15)
е. функция f удовлетворяет условию Липшица на S с константой L = 2R.Замечание 3.5.3. Локальная липшицевость непрерывно кодифференцируемой функции,определённой на конечномерном пространстве, была впервые доказана Кунцем в [105]. Однако отметим, что доказательство данного факта, предложенное в [105], отличается от данногонами и опирается на теорему 3.5.1.3.6Метод кодифференциального спускаПусть X — нормированное пространство, функция f : X → R кодифференцируема наX. Напомним, что если x∗ является точкой локального минимума (максимума) функции f ,то по предложению 3.4.20 ∈ df (x∗ ) + {(0, ψ)} ∀(0, ψ) ∈ df (x∗ )0 ∈ df (x∗ ) + {(0, ϕ)} ∀(0, ϕ) ∈ df (x∗ ) .(3.16)(3.17)Точку x ∈ X в которой выполнено условие (3.16) будем называть inf-стационарной точкойфункции f , а точку x в которой выполнено (3.17) — sup-стационарной точкой функции f .Как указано в замечании 3.5.1, условие (3.16) эквивалентно условию: f 0 (x, g) > 0 для всехg ∈ X.
Поэтому, если точка x не является inf-стационарной точкой функции f , то существуетg ∈ X такое, что f 0 (x, g) < 0.74Построим и исследуем теоретическую схему метода нахождения inf–стационарных точек функции f на всём пространстве X, который естественно называть методом кодифференциального спуска. Метод нахождения sup-стационарных точек (метод кодифференциальногоподъёма) строится аналогичным образом.3.6.1Формулировка методаЗафиксируем любые µ > 0 и 1 < p < +∞. Напомним, что1k(a, ϕ)kp = (|a|p + kϕkp ) p∀(a, ϕ) ∈ R × X ∗ .Для любого x ∈ X определим множествоdµ f (x) = {w ∈ df (x) | w = (b, ψ), 0 6 b 6 µ},а для любого w ∈ dµ f (x) положим L(xk , w) = df (xk ) + {w}.Теоретическая схема метода кодифференциального спуска задаётся следующим образом.1. Выбрать x0 ∈ X.2.
k-ая итерация (k > 0):(a) Вычислить df (xk ), df (xk ) и dµ f (xk ).(b) Для каждого w ∈ dµ f (x) найти (ak (w), ϕk (·; w)) ∈ L(xk , w) такое, чтоinf(a,ϕ)∈L(xk ,w)k(a, ϕ)kp = k(ak (w), ϕk (·; w))kp .(3.18)(c) Для каждого w ∈ dµ f (x) вычислить ∆xk (w) ∈ X такое, чтоinf ϕk (∆x; w) = ϕk (∆xk (w); w)∆x∈SX(3.19)(если ϕk (·; w) = 0, то положим ∆xk (w) = 0).(d) Для каждого w ∈ dµ f (x) вычислить αk (w) по правилуinf f (xk + α∆xk (w)) = f (xk + αk (w)∆xk (w)).α>0(3.20)(e) Выбрать ∆xk ∈ X и αk ∈ [0, +∞) по правилуinff (xk + αk (w)∆xk (w)) = f (xk + αk ∆xk )w∈dµ f (xk )и положить xk+1 = xk + αk ∆xk .75(3.21)Если на некотором шаге алоритма получится, что для любого w = (0, ψ) ∈ dµ f (xk )будет inf{k(a, ϕ)kp | (a, ϕ) ∈ L(xk , w)} = 0, то нетрудно проверить, что в точке xk выполненонеобходимое условие минимума (3.16), т.
е. xk является inf–стационарной точкой функции fи процесс прекращается.Замечание 3.6.1. (i) Предложенный в данном разделе метод кодифференциального спуска является обобщением соответствующего метода для конечномерных задач [16]. По поводу различных модификаций метода кодифференциального спуска, учитывающих специфику различных задач, а также других методов минимизации кодифференцируемых функцийсм. [5, 14, 69, 70, 82, 105].(ii) Если функция f гиподифференцируема (гипердифференцируема), то к ней такжеможно применить метод кодифференциального спуска (подъема), который в этом случаецелесообразно называть методом гиподифференциального спуска (гипердифференциальногоподъема). Отметим, что в этом случае будет dµ f (x) = {0}, и поэтому алгоритм в данномслучае упрощается.(iii) В приложениях множества df (x) и df (x) обычно являются выпуклыми многогранниками.
Поэтому в данном случае в множество dµ f (x) достаточно включать только вершины(b, ψ) множества df (x) такие, что b 6 µ. В результате такой редукции задачи (3.18)–(3.20)придётся решать лишь конечное число раз, а в задаче (3.21) придётся выбирать лишь между конечным числом направлений. Отметим также, что в случае когда множества df (x) иdf (x) являются многогранниками, на практике возникает задача нахождения вершин данных многогранников. Различные алгоритмы нахождения вершин выпуклых многогранниковобсуждались в [20, 25, 68, 71].Естественным образом возникают следующие вопросы: при каких условиях точныенижние грани в (3.18) и (3.19) достигаются, каковы свойства последовательности {xk }, построенной по методу кодифференциального спуска и когда эта последовательность сходитсяк inf-стационарной точке функции f .
Несколько следующих разделов посвящены решениюэтих вопросов.3.6.2Вспомогательные результатыЗадача (3.19) является задачей нахождения точной нижней грани значений линейногонепрерывного функционала ϕ ∈ X ∗ на единичной сфере SX . Укажем условия, при выполнении которых эта точная нижняя грань достигается.Предположим, что существует нормированное пространство E такое, что X изометри76чески изоморфно сопряжённому пространству E ∗ . Тогда X ∗ , очевидно, является изометрически изоморфным пространству E ∗∗ .
Предположим также, что функционалу ϕ соответствуетфункционал F ∈ E ∗∗ , входящий в образ канонического вложения E в E ∗∗ . По предложению 1.2.4 функционал F непрерывен в слабой∗ топологии. Учитывая, что единичный шарB(0, 1) в E ∗ слабо∗ компактен по теореме Банаха–Алаоглу, получаем, что функционал Fдостигает минимума на B(0, 1), а следовательно, и на SE ∗ . Отсюда следует, что ϕ такжедостигает минимума на сфере SX .
В частности, если пространство X рефлексивно, то функционал ϕ достигает минимума на единичной сфере. При этом ясно, что miny∈SX ϕ(y) = −kϕk.Для того чтобы получить условия, при которых точная нижняя грань в (3.18) достигается, и исследовать свойства элемента, на котором она достигается, нам потребуетсяспециальная форма теоремы об отделимости (точнее, теоремы о существовании опорной гиперплоскости).Теорема 3.6.1 (теорема об опорной гиперплоскости). Пусть X — строго выпуклое рефлексивное нормированное пространство, выпуклое множество A ⊂ X ∗ слабо компактно и0∈/ A. Пустьmin kϕk = kϕ0 k,ϕ∈Amax ϕ0 (y) = ϕ0 (y0 ).y∈SXТогда для любого ϕ ∈ A выполняется неравенствоϕ(y0 ) > kϕ0 k = ϕ0 (y0 ).Доказательство. Норма в X ∗ слабо пн.
сн. по теореме 1.3.2, а множество A слабо компактно,поэтому inf ϕ∈A kϕk достигается. Обозначим элемент, на котором достигается эта нижняягрань через ϕ0 ∈ A. Поскольку 0 ∈/ A, то ϕ0 6= 0.Так как нормированное пространство X — рефлексивно, то существует y0 ∈ SX такое,что supy∈SX ϕ0 (y) = ϕ0 (y0 ) = kϕ0 k, а поскольку пространство X — строго выпукло, то y0единственно. Введем множество A0 = (1/kϕ0 k)A. Ясно, что оно выпукло, слабо компактнои minϕ∈A0 kϕk = 1 = kϕk, где ϕ = (1/kϕ0 k)ϕ0 ∈ A0 .
Обозначим открытый единичный шар впространстве X ∗ через B = {ϕ ∈ X ∗ | kϕk < 1}. Ясно, что множества A0 и B не перескаются.Определим множество C = B − A0 + {ϕ}. Очевидно, что оно выпукло и 0 ∈ int C(здесь внутренность множества понимается относительно топологии, порожденной нормой),поскольку B ⊂ C.Рассмотрим функцию Минковского множества CpC : X ∗ → R,pC (ψ) = inf{t > 0 | ψ ∈ tC}.77Учитывая свойства множества C, получаем, что pC — это калибровочная функция.
Так как/ C, откуда pC (ϕ) > 1. Заметим, что pC (ψ) 6 1 длямножества A0 и B не пересекаются, то ϕ ∈всех ψ ∈ C.Определим линейный функционал f0 (λϕ) = λ = λϕ(y0 ) для любого λ ∈ R на одномерном подпространстве L = lin{ϕ}. Покажем, что калибровочная функция pC мажорирует функционал f0 . Если λ > 0, то f0 (λϕ) = λ 6 λpC (ϕ) = pC (λϕ); если же λ < 0, тоf0 (λϕ) < 0 6 pC (λϕ). Значит f0 6 pC на L. Тогда по теореме Хана–Банаха функционалf0 можно продолжить до линейного функционала f на X ∗ , удовлетворяющего неравенствуf (ψ) 6 pC (ψ) для всех ψ ∈ X ∗ . Отсюда следует, что f (ψ) 6 1 для любого ψ ∈ C, а посколькуB ⊂ C, то |f (ψ)| 6 1 для всех ψ ∈ B. Отсюда f ∈ X ∗∗ и kf k 6 1.Пусть ϕ ∈ A0 , ψ ∈ B, тогда ψ − ϕ + ϕ ∈ C иf (ψ) − f (ϕ) + 1 = f (ψ − ϕ + ϕ) 6 pC (ψ − ϕ + ϕ) 6 1,так как f (ϕ) = 1. Таким образом,f (ψ) 6 f (ϕ) ∀ϕ ∈ A0 , ∀ψ ∈ B.(3.22)Поскольку пространство X — рефлексивно, то существует x0 ∈ X такое, что f (ϕ) =ϕ(x0 ) для любого ϕ ∈ X ∗ .
Отметим, что kx0 k = kf k 6 1. Покажем, что x0 = y0 . Допустимпротивное. Пусть x0 6= y0 . Из определения y0 следует, что ϕ(y0 ) = kϕk = 1, откуда с учетомопределения функционала f имеемf (ϕ) = ϕ(x0 ) = 1 = kϕk = ϕ(y0 ).(3.23)Так как справедливо неравенство |ϕ(x0 )| 6 kϕkkx0 k = kx0 k 6 1, то из (3.23) следует, чтоkx0 k = 1, т. е. x0 ∈ SX . Значит supy∈SX |ϕ(y)| = kϕk достигается на x0 и на y0 , откуда, в силустрогой выпуклости пространства X, будет y0 = x0 .Учитывая (3.22) имеем, чтоϕ(y0 ) > ψ(y0 ) ∀ϕ ∈ A0 , ψ ∈ B.Откудаϕ(y0 ) > sup ψ(y0 ) = ky0 k = 1 ∀ϕ ∈ A0 ,ψ∈Bа тогдаϕ(y0 ) > kϕ0 k = ϕ0 (y0 )для любого ϕ ∈ A, что и требовалось доказать.78Замечание 3.6.2.
Условие строгой выпуклости пространства X в теореме отбросить нельзя. Покажем это на примере. Возьмем в качестве пространства X плоскость R2 с нормой kxk1 = |x1 | + |x2 |, тогда X ∗ изометрически изоморфно пространству R2 с нормойkxk∞ = max{|x1 |, |x2 |}. В качестве множества A возьмем множество функционалов, соответствующих на плоскости отрезку co{(1, −1), (1, 1)}.Ясно, что множество A — выпукло и слабо компактно. В качестве функционала сминимальной нормой, очевидно, можно взять любой функционал из A. Положим ϕ0 (x) =x1 − x2 .
Нетрудно понять, что y0 есть любая точка из отрезка co{(1, 0), (0, −1)}. Возьмемy0 = (1/2, −1/2), ϕ0 (y0 ) = 1. Пусть ϕ(x) = x1 + x2 , ϕ ∈ A, но тогда ϕ(y0 ) = 0 < ϕ0 (y0 ).Получим с помощью теоремы 3.6.1 условия, при которых точная нижняя грань в (3.18)достигается, а также опишем важные свойства элемента, доставляющего минимум. Если 0 ∈L(xk , w), то нижняя грань в (3.18), очевидно, достигается на элементе 0. Если же 0 ∈/ L(xk , w),то ответ на поставленный вопрос дает следующее утверждение.Следствие 3.6.1.
Пусть X — строго выпуклое рефлексивное нормированное пространство,выпуклое множество A ⊂ R × X ∗ компактно в топологии τ × w∗ , 0 ∈/ A. Пусть также1min k(a, ϕ)kp = k(a0 , ϕ0 )kp = (|a0 |p + kϕ0 kp ) p ,(a,ϕ)∈Amin ϕ0 (y) = ϕ0 (y0 ) = −kϕ0 ky∈SX(1 < p < +∞). Тогда для любых (a, ϕ) ∈ A выполняется неравенство− sign(a0 )|a0 |p−1 a − kϕ0 kp−1 ϕ(y0 ) 6 −(k(a0 , ϕ0 )kp )p .Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
