close

Вход

Забыли?

вход по аккаунту

?

Неоднородные выпуклые аппроксимации негладких функций.

код для вставкиСкачать
Известия вузов. Математика
2012, № 12, c. 34–50
http://www.ksu.ru/journals/izv_vuz/
e-mail: izvuz.matem@ksu.ru
М.В. ДОЛГОПОЛИК
НЕОДНОРОДНЫЕ ВЫПУКЛЫЕ АППРОКСИМАЦИИ
НЕГЛАДКИХ ФУНКЦИЙ
Аннотация. В данной статье вводится понятие неоднородной верхней выпуклой и нижней
вогнутой аппроксимаций приращения негладкой функции, определенной на нормированном
пространстве. Изучаются исчерпывающие семейства неоднородных верхних выпуклых и нижних вогнутых аппроксимаций. В терминах введенных аппроксимаций получены условия безусловного минимума и максимума, условия минимума и максимума на замкнутом выпуклом
множестве и условия оптимальности в задаче математического программирования.
Ключевые слова: негладкий анализ, неоднородная верхняя выпуклая аппроксимация, неоднородная нижняя вогнутая аппроксимация, исчерпывающее семейство аппроксимаций, коэкзостер.
УДК: 517.988
1. Введение
Положительно однородные функции играют очень важную роль в негладком анализе,
поскольку условия экстремума негладких функций часто выражаются в терминах производной по направлениям или ее обобщений (таких, как верхние и нижние производные Дини
и Адамара, производная Кларка и т. д. [1], [2]). Все эти производные являются положительно однородными функциями направления. Поэтому очень важно иметь эффективные
инструменты исследования положительно однородных функций.
Б.Н. Пшеничный в [3] ввел понятие верхней выпуклой аппроксимации и нижней вогнутой
аппроксимации (далее соответственно в. в. а. и н. в. а.) положительно однородной функции,
а именно: если функция h : Rd → R положительно однородна, то выпуклая положительно
однородная функция p : Rd → R называется в. в. а. функции h, если h(g) ≤ p(g) для всех g ∈
Rd . Вогнутая положительно однородная функция q : Rd → R называется н. в. а. функции h,
если h(g) ≥ q(g) для всех g ∈ Rd .
Ясно, что отдельной в. в. а. (или н. в. а.) недостаточно для того, чтобы изучать с ее помощью свойства исходной положительно однородной функции, поэтому необходимо рассматривать семейства в. в. а. (или н. в. а.). А.М. Рубинов в [4] предложил рассматривать
исчерпывающие семейства в. в. а. (н. в. а.). Семейство {pλ }, λ ∈ Λ, в. в. а. положительно однородной функции h называется исчерпывающим, если h(g) = inf pλ (g) для всех g ∈ Rd .
λ∈Λ
Аналогично, семейство н. в. а. {qα }, α ∈ A, положительно однородной функции h называется исчерпывающим, если h(g) = sup qα (g) для всех g ∈ Rd .
α∈A
Поступила 24.10.2011
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, грант № 09–01–00360.
34
НЕОДНОРОДНЫЕ ВЫПУКЛЫЕ АППРОКСИМАЦИИ НЕГЛАДКИХ ФУНКЦИЙ
Оказалось, что если
sup
35
h(g) < +∞ и функция h полунепрерывна сверху, то суще-
{g,g=1}
ствует исчерпывающее семейство в. в. а. функции h; если же
inf
{g,g=1}
h(g) > −∞ и функция
h полунепрерывна снизу, то существует исчерпывающее семейство н. в. а. функции h ([1],
лемма III.5.2).
Значит, для достаточно широкого класса дифференцируемых по направлениям функций f : Rd → R существует исчерпывающее семейство в. в. а. (или н. в. а.) производной
по направлениям функции f . Поскольку выпуклые положительно однородные функции
устроены значительно проще, чем произвольные положительно однородные функции, то
исчерпывающее семейство в. в. а. (или н. в. а.) является удобным инструментом исследования производной по направлениям — одного из важнейших объектов негладкого анализа.
Исчерпывающие семейства в. в. а. (н. в. а.), а также непосредственно связанное с ними понятие экзостера изложены в [5]–[8]. Отметим, что в работах [9], [10] были обобщены понятия
исчерпывающих семейств в. в. а. и н. в. а. для функций, определенных на нормированном
пространстве.
Существенной проблемой при использовании исчерпывающих семейств в. в. а. или н. в. а.
является то, что исследуемый с помощью них объект (например, производная по направлениям), как правило, не является непрерывной функцией точки. Отсутствие непрерывности
серьезно затрудняет исследование этого класса задач и построение численных методов их
решения. Для того чтобы добиться непрерывности, необходимо использовать неоднородные
аппроксимации приращения функции. Одними из таких аппроксимаций являются верхний
и нижний коэкзостеры, введенные В.Ф. Демьяновым [5].
Напомним определение верхнего и нижнего коэкзостера. Пусть S ⊂ Rd — открытое множество, x ∈ S, и предположим, что функция f : S → R непрерывна в точке x. Будем
говорить, что в точке x у функции f существует верхний коэкзостер в смысле Дини (в
смысле Адамара), если имеет место разложение
f (x + ∆) = f (x) + min
max [a + (v, ∆)] + o(∆, x),
C∈E(x) [a,v]∈C
где E(x) — семейство выпуклых компактов в Rd+1 , (·, ·) — скалярное произведение и
o(∆, x)
→ 0 при ∆ → 0.
∆
(1)
Множество E(x) называется верхним коэкзостером функции f в точке x.
Аналогично, будем говорить, что в точке x у функции f существует нижний коэкзостер
в смысле Дини (в смысле Адамара), если имеет место разложение
f (x + ∆) = f (x) + max
min [b + (w, ∆)] + o(∆, x),
C∈E(x) [b,w]∈C
где E(x) — семейство выпуклых компактов в Rd+1 и выполнено (1). Множество E(x) называется нижним коэкзостером функции f в точке x.
С помощью верхнего (или нижнего) коэкзостера строится неоднородная аппроксимация
приращения функции в точке. При этом для достаточно широкого класса функций эта
аппроксимация является непрерывной (в некотором смысле) функцией точки, что очень
удобно с позиции, например, численных методов.
В данной работе рассматривается новая неоднородная аппроксимация приращения функции, определенной на нормированном пространстве. Эта аппроксимация является обобщением понятия коэкзостера. Однако при введении новой аппроксимации был использован
36
М.В. ДОЛГОПОЛИК
подход, больше похожий на построение в. в. а. и н. в. а. положительно однородных функций, чем на непосредственное обобщение коэкзостера. С помощью этого подхода возможно
более глубоко понять свойства и структуру аппроксимации, а также сделать все свойства
аппроксимации и условия экстремума более геометрически наглядными и прозрачными,
чем в случае использования коэкзостера.
2. Неоднородные верхние выпуклые и нижние вогнутые аппроксимации
Введем некоторые обозначения. Пусть везде далее (E, · ) — нормированное пространство. Будем обозначать открытый шар с центром в точке x0 радиуса r через U (x0 , r) = {x ∈
E | x − x0 < r}, пространство, сопряженное к E, обозначим через E ∗ . Если множество
A ⊂ E и x ∈ E, то обозначим A− x = {z ∈ E | z = y − x, y ∈ A}, через co A будем обозначать
выпуклую оболочку множества A, а через int A — внутренность множества A.
Пусть функция F : E → R, где R = R ∪ {−∞} ∪ {+∞} — расширенная вещественная
прямая. Как обычно, будем обозначать dom F = {x ∈ E | F (x) = −∞, F (x) = +∞}.
Напомним также, что выпуклая функция F : E → R называется собственной, если она не
принимает значения −∞ и не равна тождественно +∞. Аналогично вогнутая функция F
называется собственной, если она не принимает значения +∞ и не равна тождественно −∞.
Перейдем к основному определению. Предположим, что Ω ⊂ E — открытое множество,
функция f : Ω → R, x0 ∈ Ω.
Определение 1. Полунепрерывную снизу (далее пн. сн.) собственную выпуклую функцию
ϕ : E → R ∪ {+∞} будем называть сильной неоднородной в. в. а. функции f в точке x0 ,
если выполнены следующие условия:
(1) 0 ∈ int dom ϕ и ϕ(0) ≥ 0,
(2) для любого ε > 0 существует r > 0 такое, что U (x0 , r) ⊂ Ω и
f (x0 + ∆) ≤ f (x0 ) + ϕ(∆) + ε∆ ∀∆ ∈ U (0, r).
Замечание 1. Определение в. в. а., похожее на определение 1, рассматривалось в [11]. Однако применение этого понятия в данной работе отличается от того, что предложено в [11].
Определение 2. Пн. сн. собственную выпуклую функцию ϕ : E → R ∪ {+∞} будем
называть слабой неоднородной в. в. а. функции f в точке x0 , если выполнены следующие
условия:
(1) 0 ∈ int dom ϕ и ϕ(0) ≥ 0,
(2) для любых ε > 0 и ∆ ∈ E существует α0 > 0 такое, что co{x0 , x0 + α0 ∆} ⊂ Ω и
f (x0 + α∆) ≤ f (x0 ) + ϕ(α∆) + εα∆
∀α ∈ [0, α0 ).
Очевидно, всякая сильная неоднородная в. в. а. является также и слабой неоднородной
в. в. а. Обратное в общем случае неверно.
Определение 3. Полунепрерывную сверху (далее пн. св.) собственную вогнутую функцию
ψ : E → R ∪ {−∞} будем называть сильной неоднородной н. в. а. функции f в точке x0 ,
если выполнены следующие условия:
(1) 0 ∈ int dom ψ и ψ(0) ≤ 0,
(2) для любого ε > 0 существует r > 0 такое, что U (x0 , r) ⊂ Ω и
f (x0 + ∆) ≥ f (x0 ) + ψ(∆) − ε∆ ∀∆ ∈ U (0, r).
По аналогии с определением слабой неоднородной в. в. а., определяется и слабая неоднородная н. в. а.
НЕОДНОРОДНЫЕ ВЫПУКЛЫЕ АППРОКСИМАЦИИ НЕГЛАДКИХ ФУНКЦИЙ
37
Точно так же, как и в однородном случае, отдельная неоднородная в. в. а. (н. в. а.) не дает
достаточной информации для исследования поведения функции в некоторой окрестности
рассматриваемой точки. Поэтому необходимо рассматривать семейства неоднородных аппроксимаций.
Определение 4. Семейство сильных (слабых) неоднородных в. в. а. {ϕλ }, λ ∈ Λ, функции f в точке x0 будем называть исчерпывающим, если
f (x0 + ∆) = f (x0 ) + inf ϕλ (∆) + o(∆) ∀∆ ∈ E : x0 + ∆ ∈ Ω,
λ∈Λ
где inf ϕλ (0) = 0 и
λ∈Λ
o(∆)
→ 0 при ∆ → 0.
∆
(2)
Определение 5. Семейство сильных (слабых) неоднородных н. в. а. {ψλ }, λ ∈ Λ, функции
f в точке x0 будем называть исчерпывающим, если
f (x0 + ∆) = f (x0 ) + sup ψλ (∆) + o(∆) ∀∆ ∈ E : x0 + ∆ ∈ Ω,
λ∈Λ
sup ψλ (0) = 0 и выполнено (2).
λ∈Λ
Наконец, если исчерпывающее семейство в. в. а. (н. в. а.) состоит из одной функции, то ее
назовем исчерпывающей неоднородной в. в. а. (н. в. а.) функции f в точке x0 .
Определение 6. Будем говорить, что функция f допускает сильную (слабую) неоднородную в. в. а. (н. в. а.) в точке x0 , если существует исчерпывающее семейство сильных (слабых)
неоднородных в. в. а. (н. в. а.) функции f в точке x0 .
Отметим некоторые очевидные свойства неоднородной в. в. а. (н. в. а.).
Предложение 1. Пусть функция f : Ω → R дифференцируема по Гато (Фреше) в точке
x0 ∈ Ω. Тогда линейная часть приращения x → f (x0 ), x, где f (x0 ) — градиент Гато
(Фреше) функции f в точке x0 , является исчерпывающей слабой (сильной) неоднородной
в. в. а., а также исчерпывающей слабой (сильной) неоднородной н. в. а.
Предложение 2. Пусть x0 ∈ Ω, функции f, g : E → R имеют вид f = inf ϕλ , g =
λ∈Λ
sup ψγ , где все ϕλ : E → R — пн. сн. собственные выпуклые функции, ψγ : E → R —
γ∈Γ
пн. св. собственные вогнутые функции. Тогда если x0 ∈ int dom ϕλ для всех λ ∈ Λ, то
семейство {ϕ
λ (·) = ϕλ (x0 + ·) − f (x0 ) | λ ∈ Λ} является исчерпывающим семейством
сильных неоднородных в. в. а. функции f в точке x0 ∈ Ω, а если x0 ∈ int dom ψγ для всех γ ∈
Γ, то семейство {ψγ (·) = ψγ (x0 + ·) − g(x0 ) | γ ∈ Γ} является исчерпывающим семейством
сильных неоднородных н. в. а. функции g в точке x0 ∈ Ω.
Предложение 3. Для того чтобы существовала сильная неоднородная в. в. а. функции f
в точке x0 ∈ Ω, необходимо и достаточно, чтобы существовали L > 0 и r > 0 такие, что
f (x) − f (x0 ) ≤ Lx − x0 ,
x ∈ U (x0 , r) ⊂ Ω.
Доказательство. Необходимость. Пусть функция ϕ : E → R является сильной неоднородной в. в. а. функции f в точке x0 , тогда существует r1 > 0 такое, что
f (x) − f (x0 ) ≤ ϕ(x − x0 ) + x − x0 ∀x ∈ U (x0 , r1 ).
38
М.В. ДОЛГОПОЛИК
Поскольку функция ϕ выпукла и пн. сн., то она локально липшицева на int dom ϕ ([12],
следствие 1.7.1), поэтому существуют L > 0 и r2 > 0 такие, что
|ϕ(∆) − ϕ(0)| ≤ L∆ ∀∆ ∈ U (0, r2 ).
Положим r = min{r1 , r2 }, тогда ясно, что
f (x) − f (x0 ) ≤ (L + 1)x − x0 ,
x ∈ U (x0 , r).
Достаточность. В качестве сильной неоднородной в. в. а. функции f в точке x0 можно
взять функцию ϕ(·) = L · .
Следствие 1. Для того чтобы существовала сильная неоднородная н. в. а. функции f в
точке x0 ∈ Ω, необходимо и достаточно, чтобы существовали L > 0 и r > 0 такие, что
f (x) − f (x0 ) ≥ −Lx − x0 ∀x ∈ U (x0 , r) ⊂ Ω.
Установим связь между исчерпывающими семействами неоднородных в. в. а. (н. в. а.) и
верхним (нижним) коэкзостером. Пусть Ω ⊂ E = Rd — выпуклое открытое ограниченное
множество, x0 ∈ Ω и функция f : Ω → R. Предположим, что существует исчерпывающее семейство сильных неоднородных в. в. а. функции f в точке x0 . Обозначим его через
{ϕλ }, λ ∈ Λ. Предположим также, что все функции ϕλ принимают конечные значения на
замыкании множества Ω.
Зафиксируем произвольное λ ∈ Λ. Поскольку функция ϕλ выпукла и конечна на замыкании Ω, то существует выпуклое компактное множество Cλ ⊂ Rd+1 такое, что
ϕλ (x) = max [a + (v, x)] ∀x ∈ Ω
(3)
[a,v]∈Cλ
(доказательство этого факта имеется в [1], с. 189 и [13], замечание 1.5.2). Обозначим E =
{Cλ ⊂ Rd+1 | λ ∈ Λ}. Из определения исчерпывающего семейства неоднородных в. в. а. и
(3) следует
f (x0 + ∆) = f (x0 ) + inf
max [a + (v, ∆)] + o(∆) ∀∆ : x0 + ∆ ∈ Ω,
Cλ ∈E [a,v]∈Cλ
где o(∆)/∆ → 0 при ∆ → 0. Значит, множество E можно рассматривать как обобщенный
верхний коэкзостер функции f в точке x0 .
Аналогичным образом по исчерпывающему семейству сильных неоднородных н. в. а. функции f в точке x0 можно построить семейство выпуклых компактных множеств E, которое
можно рассматривать как обобщенный нижний коэкзостер функции f .
3. Исчисление неоднородных верхних выпуклых
и нижних вогнутых аппроксимаций
В этом разделе рассмотрим вопрос вычисления исчерпывающих семейств неоднородных
в. в. а. (н. в. а.) некоторых функций. Все утверждения в этом разделе будут сформулированы
для семейств сильных в. в. а. (н. в. а.), однако все они, кроме последнего, справедливы и для
семейств слабых в. в. а. (н. в. а.).
Пусть везде далее Ω ⊂ E — открытое множество, x0 ∈ Ω, а также предположим, что все
рассматриваемые функции (за исключением неоднородной в. в. а. и неоднородной н. в. а.)
определены на множестве Ω и принимают вещественные значения.
Нетрудно убедиться в справедливости следующих утверждений.
НЕОДНОРОДНЫЕ ВЫПУКЛЫЕ АППРОКСИМАЦИИ НЕГЛАДКИХ ФУНКЦИЙ
39
Предложение 4. Пусть семейство {ϕλ }, λ ∈ Λ, является исчерпывающим семейством
сильных неоднородных в. в. а. (н. в. а.) функции f в точке x0 , число c из R. Тогда семейство
{ϕλ }, λ ∈ Λ, является исчерпывающим семейством сильных неоднородных в. в. а. (н. в. а.)
функции f + c в точке x0 .
Предложение 5. Пусть семейство {ϕλ }, λ ∈ Λ, является исчерпывающим семейством
сильных неоднородных в. в. а. (н. в. а.) функции f в точке x0 , c ∈ R. Тогда если c ≥ 0,
то семейство {cϕλ }, λ ∈ Λ, является исчерпывающим семейством сильных неоднородных
в. в. а. (н. в. а.) функции cf в точке x0 , если же c < 0, то семейство {cϕλ }, λ ∈ Λ, является
исчерпывающим семейством сильных неоднородных н. в. а. (в. в. а.) функции cf в точке x0 .
Предложение 6. Пусть семейство {ϕλβ }, λβ ∈ Λβ , является исчерпывающим семейством сильных неоднородных в. в. а. функции fβ в точке x0 , β ∈ B (B — произвольное
множество), т. е. для всех β ∈ B выполняется
fβ (x0 + ∆) = fβ (x0 ) + inf ϕλβ (∆) + oβ (∆)
λβ ∈Λβ
∀∆ ∈ E : x0 + ∆ ∈ Ω,
где
oβ (∆)
→ 0 при ∆ → 0.
(4)
∆
Тогда если f (x) = inf fβ (x) > −∞ для всех x ∈ Ω и соотношение (4) выполняется равβ∈B
номерно по β ∈ B, то семейство {ϕλβ + fβ (x0 ) − f (x0 ) | λβ ∈ Λβ , β ∈ B} является
исчерпывающим семейством сильных неоднородных в. в. а. функции f в точке x0 .
Замечание 2. Справедливо аналогичное утверждение о вычислении исчерпывающего семейства сильных неоднородных н. в. а. точной верхней грани множества функций, допускающих сильную неоднородную н. в. а.
Предложение 7. Пусть семейство {ϕλ }, λ ∈ Λ, является исчерпывающим семейством
сильных неоднородных в. в. а. (н. в. а.) функции f1 в точке x0 , а семейство {ψγ }, γ ∈ Γ,
является исчерпывающим семейством сильных неоднородных в. в. а. (н. в. а.) функции f2
в точке x0 . Тогда семейство {χλ,γ | χλ,γ = ϕλ +ψγ , λ ∈ Λ, γ ∈ Γ} является исчерпывающим
семейством сильных неоднородных в. в. а. (н. в. а.) функции f1 + f2 в точке x0 .
Доказательство. Докажем утверждение для случая в. в. а., случай н. в. а. доказывается
аналогично. Из определения исчерпывающего семейства сильных неоднородных в. в. а. следует, что для любого ∆ ∈ E такого, что x0 + ∆ ∈ Ω, выполняется
f1 (x0 + ∆) + f2 (x0 + ∆) = f1 (x0 ) + f2 (x0 ) + inf ϕλ (∆) + inf ψγ (∆) + o1 (∆) + o2 (∆),
λ∈Λ
γ∈Γ
(5)
где oi (∆)/∆ → 0 при ∆ → 0, i ∈ {1, 2}. Преобразуем (5):
f1 (x0 + ∆) + f2 (x0 + ∆) = f1 (x0 ) + f2 (x0 ) + inf inf (ϕλ (∆) + ψγ (∆)) + o(∆) =
λ∈Λ γ∈Γ
= f1 (x0 ) + f2 (x0 ) +
inf
(λ,γ)∈Λ×Γ
χλ,γ (∆) + o(∆),
где o(∆)/∆ → 0 при ∆ → 0. Отсюда нетрудно понять, что {χλ,γ }, (λ, γ) ∈ Λ × Γ, является
исчерпывающим семейством сильных неоднородных в. в. а. функции f1 + f2 в точке x0 . Предложение 8. Пусть семейство {ϕλβ }, λβ ∈ Λβ , является исчерпывающим семейством сильных неоднородных в. в. а. функции fβ в точке x0 , β ∈ B (B — произвольное
40
М.В. ДОЛГОПОЛИК
множество), т. е. для всех β ∈ B выполняется
fβ (x0 + ∆) = fβ (x0 ) + inf ϕλβ (∆) + oβ (∆)
λβ ∈Λβ
∀∆ ∈ E : x0 + ∆ ∈ Ω,
где
oβ (∆)
→ 0 при ∆ → 0.
(6)
∆
Пусть f (x) = sup fβ (x) < +∞ для всех x ∈ Ω. Предположим, что соотношение (6) выβ∈B
Λβ 1 выполняется
полняется равномерно по β ∈ B и для всех p ∈
β∈B
0 ∈ int dom(sup ϕp(β) ).
(7)
β∈B
Тогда семейство
Λβ
χp | χp = sup (ϕp(β) + fβ (x0 ) − f (x0 )), p ∈
β∈B
β∈B
является исчерпывающим семейством сильных неоднородных в. в. а. функции f в x0 .
Доказательство. Зафиксируем произвольное ∆ ∈ E такое, что x0 + ∆ ∈ Ω. Из определения
исчерпывающего семейства сильных неоднородных в. в. а. имеем
f (x0 + ∆) = sup fβ (x0 + ∆) = f (x0 ) + sup [fβ (x0 ) − f (x0 ) + inf ϕλβ (∆) + oβ (∆)].
β∈B
λβ ∈Λβ
β∈B
Поскольку соотношение (6) выполняется равномерно по β ∈ B, то
f (x0 + ∆) = f (x0 ) + sup inf (ϕλβ (∆) + fβ (x0 ) − f (x0 )) + o(∆),
β∈B λβ ∈Λβ
где o(∆)/∆ → 0 при ∆ → 0. Покажем, что
sup inf (ϕλβ (∆) + fβ (x0 ) − f (x0 )) =
β∈B λβ ∈Λβ
Для произвольных p ∈
p∈
inf
β∈B
sup (ϕp(β) (∆) + fβ (x0 ) − f (x0 )).
(8)
Λβ β∈B
Λβ и β ∈ B справедливо неравенство
β∈B
sup (ϕp(β) (∆) + fβ (x0 ) − f (x0 )) ≥ ϕp(β) (∆) + fβ (x0 ) − f (x0 ),
β∈B
откуда
sup (ϕp(β) (∆) + fβ (x0 ) − f (x0 )) ≥ inf (ϕλβ (∆) + fβ (x0 ) − f (x0 )) ∀β ∈ B, ∀p ∈
λβ ∈Λβ
β∈B
Поскольку p ∈
Λβ .
β∈B
Λβ и β ∈ B произвольны, то
β∈B
p∈
inf
β∈B
sup(ϕp(β) (∆) + fβ (x0 ) − f (x0 )) ≥ sup inf (ϕλβ (∆) + fβ (x0 ) − f (x0 )).
Λβ β∈A
β∈B λβ ∈Λβ
(9)
Покажем обратное неравенство. По определению точной нижней грани для любого β ∈ B
и для любого ε > 0 существует такое λβ ∈ Λβ , что
ϕλβ (∆) + fβ (x0 ) − f (x0 ) − ε ≤ inf (ϕλβ (∆) + fβ (x0 ) − f (x0 )),
λβ ∈Λβ
1Знак — прямое произведение множеств Λ .
β
НЕОДНОРОДНЫЕ ВЫПУКЛЫЕ АППРОКСИМАЦИИ НЕГЛАДКИХ ФУНКЦИЙ
41
откуда
sup (ϕλβ (∆) + fβ (x0 ) − f (x0 )) − ε ≤ sup inf (ϕλβ (∆) + fβ (x0 ) − f (x0 )),
β∈B λβ ∈Λβ
β∈B
тем более
p∈
inf
β∈B
sup (ϕp(β) (∆) + fβ (x0 ) − f (x0 )) − ε ≤ sup inf (ϕλβ (∆) + fβ (x0 ) − f (x0 )).
β∈B λβ ∈Λβ
Λβ β∈B
Ввиду произвольности ε > 0 получаем требуемое неравенство, из которого с учетом (9)
вытекает справедливость равенства (8).
В итоге имеем, что для всех ∆ ∈ E таких, что x0 + ∆ ∈ Ω, выполняется
f (x0 + ∆) = f (x0 ) +
То, что для любого p ∈
β∈B
p∈
inf
β∈B
sup (ϕp(β) (∆) + fβ (x0 ) − f (x0 )) + o(∆).
Λβ β∈B
Λβ функция χp = sup (ϕp(β) + fβ (x0 ) − f (x0 )) является сильной
β∈B
неоднородной в. в. а. функции f в точке x0 , проверяется непосредственно.
Замечание 3. Справедливо аналогичное утверждение о вычислении исчерпывающего семейства сильных неоднородных н. в. а. точной нижней грани множества функций, допускающих сильную неоднородную н. в. а.
Пусть (X, · X ) — нормированное пространство и пусть задан линейный непрерывный
оператор T : X → E. Предположим также, что y0 ∈ X, T y0 = x0 и в некоторой окрестности
точки y0 имеет смысл суперпозиция f ◦ T . Непосредственно проверяется
Предложение 9. Пусть семейство {ϕλ }, λ ∈ Λ, является исчерпывающим семейством
сильных неоднородных в. в. а. (н. в. а.) функции f в точке x0 . Тогда семейство {ϕλ ◦ T },
λ ∈ Λ, является исчерпывающим семейством сильных неоднородных в. в. а. (н. в. а.) функции f ◦ T в точке y0 .
4. Условия экстремума
Целью данного раздела является получение необходимых, а в некоторых случаях и достаточных условий экстремума функций, у которых существуют неоднородные в. в. а. (н. в. а.).
Теорема 1. Пусть функция ϕ является слабой неоднородной в. в. а. функции f в точке
x∗ ∈ Ω, ϕ(0) = 0 и предположим, что точка x∗ является точкой локального минимума
функции f . Тогда 0 является точкой минимума функции ϕ или, что то же самое, 0 ∈
∂ϕ(0), где ∂ϕ(0) — субдифференциал функции ϕ в точке 0.
Доказательство. Предположим, что точка 0 не является точкой минимума функции ϕ.
Тогда существует точка ∆ ∈ E такая, что x∗ + ∆ ∈ Ω и ϕ(∆) = −a < ϕ(0). По определению неоднородной в. в. а., функция ϕ выпукла, поэтому для любого α ∈ [0, 1] выполняется
неравенство
(10)
ϕ(α∆) = ϕ(α∆ + (1 − α)0) ≤ αϕ(∆) + (1 − α)ϕ(0) = −αa.
Поскольку функция ϕ является слабой неоднородной в. в. а. функции f в точке x∗ , то
существует 0 < α
< 1 такое, что для всех α ∈ (0, α
) справедливо неравенство
a
f (x∗ + α∆) ≤ f (x∗ ) + ϕ(α∆) + α.
2
42
М.В. ДОЛГОПОЛИК
С учетом (10) получим
a
),
f (x∗ + α∆) ≤ f (x∗ ) − α ∀α ∈ (0, α
2
а это противоречит тому, что точка x∗ является точкой локального минимума функции f .
Значит, точка 0 является точкой минимума функции ϕ, что с учетом необходимого и достаточного условия минимума выпуклой функции ([12], теорема 1.16.1) эквивалентно условию
0 ∈ ∂ϕ(0).
Следствие 2. Пусть ψ является слабой неоднородной н. в. а. функции f в точке x∗ ∈ Ω,
ψ(0) = 0 и предположим, что точка x∗ является точкой локального максимума функции f .
Тогда 0 является точкой максимума функции ψ, т. е. 0 ∈ ∂ψ(0), где ∂ψ(0) — супердифференциал функции ψ в точке 0.
Выведем теперь достаточные условия строгого локального минимума функции, допускающей неоднородную в. в. а.
Теорема 2. Пусть семейство {ϕλ }, λ ∈ Λ, является исчерпывающим семейством сильных неоднородных в. в. а. функции f в точке x∗ ∈ Ω. Если существует число r > 0 такое,
что
(11)
BE ∗ (0, r) = {p ∈ E ∗ | p ≤ r} ⊆ ∂ϕλ (0) ∀λ ∈ Λ,
то точка x∗ является точкой строгого локального минимума функции f .
Доказательство. Поскольку для любого λ ∈ Λ функция ϕλ выпукла, пн. сн. и 0 ∈ int dom ϕλ ,
то она дифференцируема по направлениям в точке 0 и ее производная по направлениям
имеет вид ([12], теорема 1.15.2 и следствие 1.16.1)
ϕ(αg) − ϕ(0)
= sup p(g) ∀g ∈ E.
α>0
α
p∈∂ϕλ (0)
ϕλ (0, g) = inf
(12)
Из (11) и (12) следует, что для любых α > 0 и λ ∈ Λ выполняется неравенство
ϕλ (αg) ≥ ϕ(0) + αrg ≥ αrg ∀g ∈ E.
(13)
Поскольку семейство {ϕλ }, λ ∈ Λ, является исчерпывающим семейством сильных неоднородных в. в. а. функции f в точке x∗ , то существует открытый шар U (0, a) (a > 0) такой,
что
r
f (x∗ + ∆) ≥ f (x∗ ) + inf ϕλ (∆) − ∆ ∀∆ ∈ U (0, a).
λ∈Λ
2
Тогда с учетом (13) получаем
r
r
f (x∗ + ∆) ≥ f (x∗ ) + r∆ − ∆ ≥ f (x∗ ) + ∆ ∀∆ ∈ U (0, a),
2
2
т. е. точка x∗ является точкой строгого локального минимума функции f .
Следствие 3. Пусть семейство {ψλ }, λ ∈ Λ, является исчерпывающим семейством сильных неоднородных н. в. а. функции f в точке x∗ ∈ Ω. Если существует число r > 0 такое,
что BE ∗ (0, r) ⊆ ∂ψλ (0) для всех λ ∈ Λ, то точка x∗ является точкой строгого локального
максимума функции f .
Пусть семейство {ϕλ }, λ ∈ Λ, является исчерпывающим семейством слабых неоднородных в. в. а. функции f в точке x∗ и предположим также, что x∗ является точкой локального
максимума функции f . Необходимое условие максимума функции f в точке x∗ не столь очевидно и наглядно, как условие минимума.
НЕОДНОРОДНЫЕ ВЫПУКЛЫЕ АППРОКСИМАЦИИ НЕГЛАДКИХ ФУНКЦИЙ
43
Пример 1. Пусть E = Ω = R, x0 = 1, f (x) = min{2 − x, x} для всех x ∈ R. Точка x0
является точкой строгого глобального максимума функции f . Определим ϕ1 (x) = 1 − x,
ϕ2 (x) = x − 1. Ясно, что {ϕ1 , ϕ2 } является исчерпывающим семейством сильных неоднородных в. в. а. функции f в точке x0 . При этом ∂ϕ1 (0) = {−1}, ∂ϕ2 (0) = {1}. Отметим, что
0 ∈ co{∂ϕ1 (0), ∂ϕ2 (0)}.
Теорема 3. Предположим, что семейство {ϕλ }, λ ∈ Λ, является исчерпывающим семейством слабых неоднородных в. в. а. функции f в точке x0 и пусть точка x0 является
точкой локального максимума функции f . Тогда
∂ϕλ (0).
(14)
0 ∈ cl co
λ∈Λ
Здесь замыкание берется в
слабой∗
топологии.
Доказательство. Пусть x0 является точкой локального максимума функции f . Покажем,
что тогда выполняется (14). Пусть
∂ϕλ (0).
0∈
/ cl co
λ∈Λ
Рассмотрим множества {0} и C = cl co ∪ ∂ϕλ (0) как подмножества топологического векλ∈Λ
торного пространства (E ∗ , w∗ ), где w∗ — слабая∗ топология. Множество C выпукло, замкнуто и не пересекается с выпуклым компактным множеством {0}. Поэтому по теореме
об отделимости существует такой слабо∗ непрерывный линейный функционал Φ : E ∗ → R,
который строго разделяет эти множества ([12], замечание 1.9.2), т. е. существует число a ∈ R
такое, что
∂ϕλ (0).
(15)
Φ(p) ≥ a > 0 ∀p ∈ cl co
λ∈Λ
слабо∗
непрерывен, то ([14], следствие 4.2.3) существует ∆0 ∈ E,
Поскольку функционал Φ
∆0 = 0, такое, что Φ(p) = p(∆0 ) для всех p ∈ E ∗ , откуда с учетом (15) имеем, что для
любого λ ∈ Λ выполяется неравенство
p(∆0 ) ≥ a > 0 ∀p ∈ ∂ϕλ (0).
(16)
Поскольку для всех λ ∈ Λ функция ϕλ выпукла пн. сн. и 0 ∈ int dom ϕλ , то
ϕλ (0, ∆0 ) = inf
α>0
ϕλ (α∆0 ) − ϕλ (0)
= sup p(∆0 ).
α
p∈∂ϕλ (0)
Тогда с учетом (16) получаем
ϕλ (α∆0 ) ≥ αa + ϕλ (0) ≥ αa ∀α > 0, ∀λ ∈ Λ.
(17)
По определению исчерпывающего семейства слабых неоднородных в. в. а. существует α > 0
такое, что для любого α ∈ (0, α) выполняется
a
f (x0 + α∆0 ) ≥ f (x0 ) + inf ϕλ (α∆0 ) − α,
λ∈Λ
2
откуда, учитывая (17), имеем
a
a
f (x0 + α∆0 ) ≥ f (x0 ) + aα − α = f (x0 ) + α ∀α ∈ (0, α),
2
2
а это противоречит тому, что x0 является точкой локального максимума функции f .
44
М.В. ДОЛГОПОЛИК
Следствие 4. Предположим, что семейство {ψλ }, λ ∈ Λ, является исчерпывающим семейством слабых неоднородных н. в. а. функции f в точке x0 и пусть x0 является точкой
локального минимума функции f . Тогда
∂ψλ (0).
0 ∈ cl co
λ∈Λ
Здесь замыкание берется в
слабой∗
топологии.
Из доказательства теоремы 3 нетрудно усмотреть следующее необходимое условие максимума.
Теорема 4. Пусть семейство {ϕλ }, λ ∈ Λ, является исчерпывающим семейством слабых
неоднородных в. в. а. функции f в точке x∗ и предположим, что x∗ — точка локального
максимума функции f . Тогда для любого ∆ ∈ E и для любого ε > 0 существует λ ∈ Λ
такое, что
(18)
p(∆) ≤ ε ∀p ∈ ∂ϕλ (0).
Доказательство. Предположим, что существуют ∆0 ∈ E и число ε0 > 0 такие, что для
любого λ ∈ Λ существует p ∈ ∂ϕλ (∆0 ), для которого p(∆0 ) > ε0 . Рассуждая как при
доказательстве теоремы 3, заключаем
ϕλ (α∆0 ) ≥ αε0 ∀α > 0, ∀λ ∈ Λ.
Тогда, воспользовавшись определением исчерпывающего семейства слабых неоднородных
в. в. а., получим существование α > 0 такого, что
ε0
ε0
f (x0 + α∆0 ) ≥ f (x0 ) + inf ϕλ (α∆0 ) − α ≥ f (x0 ) + α ∀α ∈ (0, α),
λ∈Λ
2
2
а это противоречит тому, что x0 является точкой локального максимума функции f .
Следствие 5. Пусть семейство {ψλ }, λ ∈ Λ, является исчерпывающим семейством слабых
неоднородных н. в. а. функции f в точке x∗ и предположим, что x∗ — точка локального
минимума функции f . Тогда для любых ∆ ∈ E и ε > 0 существует λ ∈ Λ такое, что
p(∆) ≥ −ε для всех p ∈ ∂ψλ (0).
Покажем на примере, что условия экстремума, полученные с помощью неоднородной
в. в. а., лучше, чем классическое условие экстремума, выражаемое в терминах субдифференциала Кларка.
Пример 2. Пусть Ω = E = R2 , x0 = (0, 0), f (x) = |x1 | − |x2 |, где x = (x1 , x2 ) ∈ R2 .
Нетрудно проверить, что функция f является дифференцируемой по Кларку в точке x0 и
ее субдифференциал Кларка в точке x0 имеет вид
∂Cl f (x0 ) = co{(1, 1), (1, −1), (−1, 1), (−1, −1)}.
Отсюда получаем, что 0 ∈ ∂Cl f (x0 ), т. е. в точке x0 выполнено необходимое условие экстремума ([2], предложение 2.3.2), при этом x0 не является ни точкой минимума, ни точкой
максимума функции f .
Положим ϕ1 (x) = −x2 + |x1 |, ϕ2 (x) = x2 + |x1 |. Ясно, что семейство {ϕ1 , ϕ2 } является
исчерпывающим семейством сильных неоднородных в. в. а. функции f в точке x0 . Имеем
∂ϕ1 (0) = co{(−1, −1), (1, −1)} и ∂ϕ2 (0) = co{(−1, 1), (1, 1)}. Поскольку ϕ1 (0) = ϕ2 (0) = 0 и
0∈
/ ∂ϕi (0), i ∈ {1, 2}, то в точке x0 не выполнено необходимое условие минимума, указанное
в теореме 1. Так как 0 ∈ cl co(∂ϕ1 (0) ∪ ∂ϕ2 (0)), то выполнено условие максимума (14).
Однако для ∆ = (1, 0) не выполнено необходимое условие максимума (18). Значит, условие
(14) явлется более грубым, чем необходимые условия максимума (18).
НЕОДНОРОДНЫЕ ВЫПУКЛЫЕ АППРОКСИМАЦИИ НЕГЛАДКИХ ФУНКЦИЙ
45
Отметим, что функция f является квазидифференцируемой и в точке x0 не выполнены необходимые условия максимума и минимума квазидифференцируемой функции ([13],
теоремы 2.5.1 и 2.5.2).
Пример 3. Пусть Ω = E = R2 , x0 = (0, 0), f (x) = ( |x1 | + |x2 |)2 , где x = (x1 , x2 ) ∈
R2 . Нетрудно убедиться, что функция f не удовлетворяет условию Липшица ни в какой
окрестности точки x0 и не является квазидифференцируемой в точке x0 . Покажем, что
функция f допускает сильную неоднородную в. в. а. и проверим условия экстремума.
Можно показать [15], что функция f представима в виде
1
1
|x1 | +
|x2 | , где Λ = (0, 1).
f (x) = min
λ∈Λ λ
1−λ
1
|x2 |, λ ∈ Λ. Семейство {ϕλ }, λ ∈ Λ, является исчерпывающим
Положим ϕλ (x) = λ1 |x1 | + 1−λ
семейством сильных неоднородных в. в. а. функции f в точке x0 . Тогда
1
1
1
1
1
1
1
1
,
, − ,
,
,−
, − ,−
, λ ∈ Λ.
∂ϕλ (0) = co
λ 1−λ
λ 1−λ
λ 1−λ
λ 1−λ
Для всех λ ∈ Λ имеем ϕλ (0) = 0 и 0 ∈ ∂ϕλ (0), т. е. в точке x0 выполнено необходимое
условие минимума (теорема 1). Поскольку
1
1
+
≥ 4 ∀λ ∈ (0, 1),
λ 1−λ
то необходимое условие максимума (18) не выполнено, например, для ∆ = (1, 1). При этом
ясно, что точка x0 является точкой строго глобального минимума функции f . (По поводу
данного примера см. также [7], пример 12.1.)
Пусть A ⊂ Ω — замкнутое выпуклое множество. Рассмотрим задачу минимизации функции f на множестве A. Рассуждая как при доказательстве теоремы 1, нетрудно убедиться
в справедливости следующего утверждения.
Теорема 5. Пусть ϕ является слабой неоднородной в. в. а. функции f в точке x∗ ∈ A,
ϕ(0) = 0 и предположим, что точка x∗ является точкой минимума функции f на множестве A. Тогда 0 — точка минимума функции ϕ на множестве A − x∗ .
Напомним, что если выпуклая функция ϕ непрерывна на выпуклом замкнутом множестве A, то необходимым и достаточным условием минимума этой функции на множестве A
является
∂ϕ(x∗ ) ∩ (−N (A, x∗ )) = ∅,
где N (A, x∗ ) = {p ∈ E ∗ | p(a − x∗ ) ≤ 0 ∀a ∈ A} — нормальный конус к множеству A в точке
x∗ ([12], пример 1.16.4). Учитывая этот факт, получаем
Следствие 6. Пусть функция ϕ является слабой неоднородной в. в. а. функции f в точке
x∗ ∈ A, ϕ(0) = 0 и предположим, что точка x∗ — точка минимума функции f на множестве
A, а функция ϕ непрерывна на множестве A − x∗ . Тогда
∂ϕ(0) ∩ (−N (A − x∗ , 0)) = ∅.
Следствие 7. Пусть функция ψ является слабой неоднородной н. в. а. функции f в точке
x∗ ∈ A, ψ(0) = 0 и предположим, что точка x∗ — точка максимума функции f на множестве A. Тогда 0 является точкой максимума функции ψ на множестве A − x∗ . Если же ψ
непрерывна на множестве A − x∗ , то ∂ψ(0) ∩ N (A − x∗ , 0) = ∅.
46
М.В. ДОЛГОПОЛИК
Предположим, что функция f допускает неоднородную в. в. а. в точке x∗ ∈ A и рассмотрим задачу максимизации функции f на множестве A. Множество
γ(x∗ ) = {v = α(x − x∗ ) | α > 0, x ∈ A}
является выпуклым конусом, причем 0 ∈ γ(x∗ ). Замыкание конуса γ(x0 ) называется конусом возможных направлений множества A в точке x∗ и обозначается Γ(x∗ ). Ясно, что Γ(x∗ )
— замкнутый выпуклый конус, содержащий точку 0.
Справедлива схожая с теоремой 4
Теорема 6. Пусть семейство {ϕλ }, λ ∈ Λ, является исчерпывающим семейством слабых
неоднородных в. в. а. функции f в точке x∗ ∈ A и предположим, что точка x∗ является
точкой максимума функции f на множестве A. Тогда для любых v ∈ γ(x∗ ) и ε > 0
существует λ ∈ Λ такое, что
p(v) ≤ ε ∀p ∈ ∂ϕλ (0).
(19)
Доказательство. Предположим, что существуют v ∈ γ(x∗ ) и ε0 > 0 такие, что для любого
λ ∈ Λ существует pλ ∈ ∂ϕλ (0), для которого
pλ (v) > ε0 .
(20)
γ(x∗ )
существуют α0 > 0 и x0 ∈ A такие, что v = α0 (x0 − x∗ ).
Тогда по определению конуса
∗
Поскольку субградиент pλ ∈ E является линейным непрерывным функционалом, то из
(20) получаем
ε0
= a > 0 ∀λ ∈ Λ.
pλ (x0 − x∗ ) >
α0
Рассуждая далее как при доказательстве теоремы 4, получим противоречие с тем, что точ
ка x∗ является точкой максимума функции f на множестве A.
Следствие 8. Пусть семейство {ψλ }, λ ∈ Λ, является исчерпывающим семейством слабых
неоднородных н. в. а. функции f в точке x∗ ∈ A и предположим, что точка x∗ является
точкой минимума функции f на множестве A. Тогда для любых v ∈ γ(x∗ ) и ε > 0 существует
λ ∈ Λ такое, что p(v) ≥ −ε для всех p ∈ ∂ϕλ (0).
Замечание 4. Нетрудно показать, что если множество Λ конечно, то соотношение (19)
выполнено для всех v ∈ Γ(x∗ ).
Пусть множество S ⊂ Ω представимо в виде
S = {x ∈ E | gi (x) ≤ 0 ∀i ∈ I = {1, . . . , n}},
где gi : Ω → R, а множество A ⊂ Ω замкнуто и выпукло. Рассмотрим задачу минимизации
функции f на множестве S ∩ A.
Теорема 7. Пусть функция ϕ является слабой неоднородной в. в. а. функции f в точке
x∗ ∈ S ∩A, ϕ(0) = 0, а функция ϕi является слабой неоднородной в. в. а. функции gi в точке
x∗ , ϕi (0) = 0, i ∈ I. Предположим, что x∗ — точка минимума функции f на множестве
S ∩ A. Тогда 0 является точкой минимума функции
χ = max{ϕ, ϕ1 + g1 (x∗ ), . . . , ϕn + gn (x∗ )}
на множестве A − x∗ . Если же функция χ непрерывна на множестве A − x∗ , то
∂ϕi (0) ∩ (−N (A − x∗ , 0)) = ∅,
cl co ∂ϕ(0),
i∈R(x∗ )
где R(x∗ ) = {i ∈ I | gi (x∗ ) = 0}. Здесь замыкание берется в слабой∗ топологии.
(21)
НЕОДНОРОДНЫЕ ВЫПУКЛЫЕ АППРОКСИМАЦИИ НЕГЛАДКИХ ФУНКЦИЙ
47
Доказательство. Функция
F (x) = max{f (x) − f (x∗ ), g1 (x), . . . , gn (x)},
x ∈ Ω,
является неотрицательной для всех x ∈ A и F (x∗ ) = 0. Значит, точка x∗ — точка минимума
функции F на множестве A. Поскольку функция ϕ является слабой неоднородной в. в. а.
функции f в точке x∗ , а функция ϕi — слабой неоднородной в. в. а. функции gi в точке x∗ ,
i ∈ I, то для любого ε > 0 существует такое r > 0, что для всех ∆ ∈ U (0, r) выполняется
F (x∗ + ∆) − F (x∗ ) = max{f (x∗ + ∆) − f (x∗ ), g1 (x∗ + ∆), . . . , gn (x∗ + ∆)} ≤
≤ max{ϕ(∆), ϕ1 (∆) + g1 (x∗ ), . . . , ϕn (∆) + gn (x∗ )} + ε∆.
Отсюда ясно, что функция χ является слабой неоднородной в. в. а. функции F в точке x∗
и χ(0) = 0. По теореме 5 точка 0 — точка локального минимума функции χ на множестве A − x∗ . Если же функция χ непрерывна на множестве A − x∗ , то, учитывая формулу
для вычисления субдифференциала максимума выпуклых функций ([12], теорема 1.17.3),
получим справедливость формулы (21).
Пусть теперь множество S ⊂ Ω имеет вид
S = {x ∈ E | gi (x) ≥ 0 ∀i ∈ I = {1, . . . , n}}.
Рассмотрим задачу максимизации функции f на множестве S ∩ A. Аналогично теореме 7
получаем следующую теорему.
Теорема 8. Пусть функция ψ является слабой неоднородной н. в. а. функции f в точке
x∗ ∈ S, ψ(0) = 0, а функция ψi является слабой неоднородной н. в. а. функции gi в точке
x∗ , ψi (0) = 0, i ∈ I. Предположим, что x∗ является точкой максимума функции f на
множестве S ∩ A. Тогда 0 — точка максимума функции ω = min{ψ, ψ1 + g1 (x∗ ), . . . , ψn +
gn (x∗ )} на множестве A − x∗ . Если же функция ω непрерывна на множестве A − x∗ , то
∂ψλi (0) ∩ N (A − x∗ , 0) = ∅,
(22)
cl co ∂ψ(0),
i∈Q(x∗ )
где i ∈ Q(x∗ ) = {i ∈ I | gi (x∗ ) = 0}. Здесь замыкание берется в слабой∗ топологии.
Приведем несколько примеров применения разработанной теории.
Пример 4. Пусть E = Ω = R2 , x = (x1 , x2 ) ∈ R2 , A = co{(1, 1), (1, 3), (−1, 3), (−1, 1)} —
замкнутое выпуклое множество. Положим
g1 (x) = −x1 + x2 − 1,
g2 (x) = x1 + x2 − 1,
f1 (x) = max{−x1 + x2 , x1 + x2 },
S = {x ∈ R2 | gi (x) ≥ 0, i ∈ {1, 2}},
f2 (x) = max{−x1 − x2 + 2, x1 − x2 + 2},
f (x) = min{f1 (x), f2 (x)}.
Рассмотрим задачу максимизации функции f на множестве S ∩ A.
Проверим, что в точке x∗ = (0, 1) выполнены необходимые условия экстремума (22). Для
этого вычислим исчерпывающие семейства неоднородных н. в. а. функций g1 , g2 и f . Ясно,
что в качестве исчерпывающей сильной неоднородной н. в. а. функции g1 в точке x∗ можно
взять функцию ψ1 (x) = −x1 +x2 , а в качестве исчерпывающей сильной неоднородной н. в. а.
функции g2 в точке x∗ — функцию ψ2 = x1 + x2 . Введем функции
(1)
ψ2 (x) = x1 + x2 − 1,
(2)
ψ2 (x) = x1 − x2 + 1.
ψ1 (x) = −x1 + x2 − 1,
ψ1 (x) = −x1 − x2 + 1,
(1)
(2)
48
М.В. ДОЛГОПОЛИК
(i)
(i)
Нетрудно понять, что семейство {ψ1 , ψ2 } является исчерпывающим семейством сильных
неоднородных н. в. а. функции fi в точке x∗ , i ∈ {1, 2}. Учитывая замечание 3, получаем,
(1)
(2)
что семейство {ψij = min{ψi , ψj }}, i, j ∈ {1, 2}, является исчерпывающим семейством
сильных неоднородных н. в. а. функции f в точке x∗ .
Понятно, что N (A − x∗ , 0) = {(0, −α) | α ≥ 0} и R(x∗ ) = {1, 2}. Теперь нетрудно проверить, что условие
co{∂ψij (0), ∂ψ1 (0), ∂ψ2 (0)} ∩ N (A − x∗ , 0) = ∅
выполняется для всех i, j ∈ {1, 2}, т. е. в точке x∗ выполнено необходимое условие экстремума (22). Отметим, что x∗ действительно является точкой максимума функции f на
множестве S ∩ A.
Пример 5. Пусть a, b ∈ R, (E, · ) = (C[a, b], · ∞ ) — пространство непрерывных на
отрезке [a, b] функций, где
x∞ = max |x(t)|.
t∈[a,b]
Функционал
I(x) =
b
|f (x(t), t)| dt
a
определим на пространстве C[a, b], где функция f : R × [a, b] → R, f = f (x, t), непрерывна
по совокупности переменных и непрерывно дифференцируема по x для всех x ∈ R и t ∈
[a, b]. Рассмотрим задачу максимизации функционала I на замкнутом выпуклом множестве
A = {x ∈ C[a, b] | x(a) = x1 , x(b) = x2 }, где x1 , x2 ∈ R — фиксированные числа.
Покажем, что функционал I допускает слабую неоднородную н. в. а. в каждой точке
x ∈ C[a, b]. Обозначим Λ = {λ ∈ L∞ [a, b] | λ(t) ∈ [−1, 1] для почти всех t ∈ [a, b]}. Для
любых λ ∈ Λ и x ∈ C[a, b] имеем |f (x(t), t)| ≥ λ(t)f (x(t), t) для почти всех t ∈ [a, b], при
этом для λ0 (t) = sign(f (x(t), t)) ∈ Λ это неравенство выполняется как равенство, поэтому
b
b
|f (x(t), t)| dt = sup
λ(t)f (x(t), t) dt.
λ∈Λ a
a
Здесь в правой части равенства интеграл понимается в смысле Лебега. Отсюда имеем, что
I(x) = sup Iλ (x), где
λ∈Λ
b
Iλ (x) =
λ(t)f (x(t), t) dt.
a
Покажем, что функционал Iλ дифференцируем по Гато для любого λ ∈ Λ. Зафиксируем
произвольные x, h ∈ C[a, b]. Для любого λ ∈ Λ и α > 0 имеем
b
∂f
≤
Iλ (x + αh) − Iλ (x) − α
(x(t),
t)h(t)
dt
λ(t)
∂x
a
b
f (x(t) + αh(t), t) − f (x(t), t) − α ∂f (x(t), t)h(t) dt ≤ αg(α, x, h)h∞ ,
≤
∂x
a
где
g(α, x, h) =
a
b
∂f
∂f
(x(t), t) dt.
sup (x(t) + αθh(t), t) −
∂x
θ∈(0,1) ∂x
НЕОДНОРОДНЫЕ ВЫПУКЛЫЕ АППРОКСИМАЦИИ НЕГЛАДКИХ ФУНКЦИЙ
49
Поскольку функция ∂f
∂x (x, t) непрерывна при всех x ∈ R, t ∈ [a, b], то нетрудно понять, что
g(α, x, h) → 0 при α → 0. Отсюда следует
b
∂f
Iλ (x + h) − Iλ (x) =
λ(t) (x(t), t)h(t) dt + o(h, x),
∂x
a
где o(αh, x)/α → 0 при α → 0 равномерно по λ ∈ Λ. Учитывая замечание 2, получаем, что
для любого фиксированного x ∈ C[a, b] и для любого h ∈ C[a, b]
I(x + h) − I(x) = sup ψλ (h, x) + o(h),
λ∈Λ
где o(αh)/α → 0 при α → 0 и
b
b
∂f
ψλ (h, x) =
(λ(t)f (x(t), t) − |f (x(t), t)|) dt +
λ(t) (x(t), t)h(t) dt.
∂x
a
a
Выведем необходимое условие локального максимума. Пусть x∗ ∈ A — точка локального
максимума функционала I на множестве A. Нетрудно понять, что
N (A − x∗ , 0) = {p ∈ E ∗ | p(y) = 0 ∀y ∈ C[a, b] : y(a) = y(b) = 0}.
Из следствия 7 получаем, что для любого λ ∈ Λ такого, что ψλ (0, x∗ ) = 0, выполняется
условие ∂ψλ (0, x∗ ) ∩ N (A − x∗ , 0) = ∅ или, что эквивалентно,
b
∂f
λ(t) (x∗ (t), t)h(t) dt = 0 ∀h ∈ C[a, b] : h(a) = h(b) = 0.
∂x
a
Воспользовавшись основной леммой вариационного исчисления (например, [14], предложение 4.3.7), получаем
∂f
(23)
λ(t) (x∗ (t), t) = 0 для почти всех t ∈ [a, b].
∂x
Положим
sign(f (x∗ (t), t)), если f (x∗ (t), t) = 0;
λ0 (t) =
1,
если f (x∗ (t), t) = 0.
Ясно, что λ0 ∈ Λ и ψλ0 (0, x∗ ) = 0, поэтому для λ0 выполнено условие (23), но |λ0 (t)| ≡ 1,
откуда получаем следующее необходимое условие локального максимума.
Предложение 10. Пусть x∗ ∈ A — точка локального максимума функционала I на
∗
множестве A. Тогда ∂f
∂x (x (t), t) = 0 для почти всех t ∈ [a, b].
Автор выражает благодарность рецензенту за полезные замечания, позволившие улучшить содержание данной статьи.
Литература
[1] Демьянов В.Ф., Рубинов А.М. Основы негладкого анализа и квазидифференциальное исчисление (Наука, М., 1990).
[2] Кларк Ф. Оптимизация и негладкий анализ (Наука, М., 1988).
[3] Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи (Наука, М., 1980).
[4] Демьянов В.Ф., Рубинов А.М. Элементы квазидифференциального исчисления, в сб. Негладкие задачи
теории оптимизации и управления (Изд-во Ленингр. ун-та, Л., 1982), с. 5–127.
[5] Аббасов М.Э., Демьянов В.Ф. Условия экстремума негладкой функции в терминах экзостеров и коэкзостеров, Тр. ИММ УрО РАН 15 (4), 10–19 (2009).
[6] Demyanov V.F. Exhauster of a positively homogeneous function, Optimization 45 (1–4), 13–29 (1999).
[7] Demyanov V.F. Exhausters and convexificators — new tools in nonsmooth analysis, Quasidifferentiability and
Related Topics (Kluwer Acad. Publ., 2000), p. 85–137.
50
М.В. ДОЛГОПОЛИК
[8] Demyanov V.F. Roschina V.A. Optimality conditions in terms of upper and lower exhausters, Optimization
55 (5–6), 525–540 (2006).
[9] Bartels S.G., Pallaschke D. Some remarks on the space of differences of sublinear functions, Appl. Mat. 22
(3), 419–426 (1993).
[10] Uderzo A. Convex approximators, convexificators and exhausters: applications to constrained extremum
problem, Quasidifferentiability and Related Topics (Kluwer Acad. Publ., 2000), p. 297–327.
[11] Левитин Е.С., Милютин А.А., Осмоловский Н.П. Условия высших порядков локального минимума в
задачах с ограничениями, УМН 33 (6), 85–148 (1978).
[12] Половинкин Е.С., Балашов М.В. Элементы выпуклого и сильно выпуклого анализа (Физмалит, М.,
2007).
[13] Демьянов В.Ф., Васильев Л.В. Недифференцируемая оптимизация (Наука, М., 1981).
[14] Хелемский А.Я. Лекции по функциональному анализу (МЦНМО, М., 2004).
[15] Ishizuka Yo. Optimality conditions for quasidifferentiable programs with application to two-level optimization,
SIAM J. Control Optimization 26 (6), 1388–1398 (1988).
М.В. Долгополик
студент, кафедра математической теории моделирования систем управления,
Санкт-Петербургский государственный университет,
Университетская наб., д. 7–9, г. Санкт-Петербург, 199034, Россия,
e-mail: maxim.dolgopolik@gmail.com
M.V. Dolgopolik
Inhomogeneous convex approximations of nonsmooth functions
Abstract. In this paper we introduce notions of inhomogeneous upper convex and lower concave
approximations of the increment of a nonsmooth function defined in a normed space and study
exhaustive families of these approximations. In terms of the introduced notions we establish
optimality conditions for various constrained and unconstrained extremum problems.
Keywords: nonsmooth analysis, inhomogeneous upper convex approximation, inhomogeneous
lower concave approximation, exhaustive family of approximations, coexhauster.
M.V. Dolgopolik
Student, Chair of Mathematical Modeling of Control Systems,
St.-Petersburg State University,
7–9 Universitetskaya embankment, St.-Petersburg, 199034 Russia,
e-mail: maxim.dolgopolik@gmail.com
Документ
Категория
Без категории
Просмотров
4
Размер файла
254 Кб
Теги
негладкие, неоднородным, функции, выпуклых, аппроксимация
1/--страниц
Пожаловаться на содержимое документа