close

Вход

Забыли?

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

?

Условия экстремума в терминах обобщенных несобственных экзостеров.

код для вставкиСкачать
2013
ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА
Сер. 10
Вып. 3
ПРИКЛАДНАЯ МАТЕМАТИКА
УДК 519.3+519.7
М. Э. Аббасов
УСЛОВИЯ ЭКСТРЕМУМА В ТЕРМИНАХ ОБОБЩЕННЫХ
НЕСОБСТВЕННЫХ ЭКЗОСТЕРОВ∗)
В работе рассмотрено обобщение понятия экзостеров – новых инструментов изучения негладких функций, введенных в работах В. Ф. Демьянова, А. М. Рубинова,
Б. Н. Пшеничного. Экзостеры – это семейства выпуклых компактов, позволяющие
представлять главный член приращения функции в исследуемой точке в виде inf max
или sup min, причем верхний экзостер используется для первого представления, а нижний – для второго. С помощью данных объектов удалось получить новые условия экстремума, строить направления спуска и подъема и, тем самым, конструировать новые
оптимизационные алгоритмы для широкого класса функций. Оказалось, что наиболее
органично условия максимума выписываются в терминах нижнего экзостера, а минимума – верхнего. Поэтому нижний экзостер был назван собственным для задачи
на максимум, а верхний – на минимум. Соответственно нижний экзостер был назван
несобственным для задачи на минимум, а верхний – несобственным для задачи на максимум.
Настоящая работа посвящена получению условий экстремума в терминах несобственного обобщенного экзостера, обобщающих условия, полученные В. Ф. Демьяновым, В. А. Рощиной, М. Э. Аббасовым. Обобщенные экзостеры – это семейства выпуклых компактов, позволяющие представлять главный член приращения функции
в исследуемой точке в inf sup-м либо sup inf-м виде. Использование обобщенных экзостеров дает возможность расширить класс рассматриваемых функций по сравнению
с классом функций, которые можно исследовать с помощью экзостеров.
Необходимые сведения. Пусть f : X −→ R, где X ⊂ Rn – открытое множество,
и имеет место разложение
f (x + g) = f (x) + hx (g) + ox (g).
(1)
В (1) ox (g) удовлетворяет одному из условий:
lim
α↓0
ox (αg)
=0
α
∀ g ∈ Rn
(2)
Аббасов Меджид Эльхан оглы – кандидат физико-математических наук, доцент, 199034, СанктПетербургский государственный университет; e-mail: abbasov.majid@gmail.com.
∗) Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант № 12-01-00752).
c М. Э. Аббасов, 2013
3
либо
ox (g)
=0
||g||→0 ||g||
lim
∀ g ∈ Rn .
(3)
Заметим, что если hx (g) положительно однородная (п.о.) функция, то в случае справедливости (2) hx (g) – производная Дини функции f в точке x по направлению g, в случае
справедливости (3) – производная Адамара функции f в точке x по направлению g.
Если справедливо представление hx (g) = inf∗ sup (v, g), где E ∗ (x) – семейство
C∈E (x) v∈C
выпуклых множеств в Rn , а ox (g) удовлетворяет (2), говорят, что E ∗ (x) – обобщенный
верхний экзостер в смысле Дини функции f в точке x; если справедливо (3), – то
в смысле Адамара.
Когда справедливо представление hx (g) = sup inf (v, g), где E∗ (x) – семейство
C∈E∗ (x) v∈C
выпуклых множеств в R , а ox (g) удовлетворяет (2), говорят, что E∗ (x) – обобщенный
нижний экзостер в смысле Дини функции f в точке x; если справедливо (3), – то
в смысле Адамара.
max(v, g) или max min(v, g), где E ∗ (x)
Если же hx (g) представима в виде min
∗
n
C∈E (x) v∈C
C∈E∗ (x) v∈C
и E∗ (x) – семейства выпуклых компактов, то говорят о верхнем и нижнем экзостере
соответственно. Причем при справедливости (2) говорят об экзостере в смысле Дини,
при справедливости (3) – в смысле Адамара.
Замечание 1. Отметим, что (обобщенный) экзостер функции f в точке x совпадает с (обобщенным) экзостером функции hx в точке 0n . Поэтому далее, если не будет
оговорено особо, будем рассматривать функцию hx отдельно и использовать обозначение h(g).
Замечание 2. Отметим, что везде далее, если не оговорено отдельно, речь будет
идти об (обобщенных) экзостерах в смысле Дини. Как ясно из определения, (обобщенный) экзостер в смысле Адамара является также (обобщенным) экзостером в смысле
Дини.
Понятие экзостеров было введено в работах Б. Н. Пшеничного [1], А. М. Рубинова
[2], В. Ф. Демьянова [3], посвященных исследованию невыпуклых функций.
При справедливости условия (2) и п.о. hx (g) необходимым условием минимума является h(g) 0 ∀g ∈ Rn , а h(g) 0 ∀g ∈ Rn – необходимым условием максимума.
Если выполнено условие (3) и по-прежнему hx (g) – п.о., то h(g) > 0 ∀g ∈ Rn –
необходимое и достаточное условие строгого минимума, а h(g) < 0 ∀g ∈ Rn – строгого
максимума.
Изучаемые в данной работе обобщенные экзостеры являются дальнейшим развитием аппарата экзостеров.
Условия экстремума. Впервые условия экстремума в терминах экзостеров были получены В. Ф. Демьяновым [3–8]. Причем оказалось, что условия минимума выражаются при помощи верхнего экзостера, а условия максимума – нижнего, поэтому верхний экзостер был назван собственным для задачи на минимум, а нижний –
собственным для задачи на максимум. Соответственно нижний экзостер был назван
несобственным для задачи на минимум, а верхний – несобственным для задачи на максимум. Затем В. А. Рощиной [9] были получены выражения для условий экстремума,
использующие несобственные экзостеры, но они не позволяли определять направления
спуска и подъема и не обладали той же наглядной и ясной геометрической интерпретацией, которую имели условия экстремума в терминах собственных экзостеров. В работах [10, 11] были представлены новые условия экстремума в терминах несобственных
4
экзостеров, лишенные этих недостатков. В настоящей работе предпринимается попытка
обобщения указанных условий.
Условия
в терминах несобственных обобщенных экзостеров.
экстремума
Пусть S = g ∈ Rn ||g|| = 1 . В [10] впервые были сформулированы следующие результаты.
Теорема 1. Для того чтобы h(g) = max min(v, g) 0 для любого g ∈ S, где
C∈E∗ v∈C
E∗ – семейство выпуклых контактов, необходимо и достаточно, чтобы произвольная гиперплоскость, проходящая через нуль, разделяла какие-то два множества се ∈ E∗ такое, что для
мейства E∗ , т. е. для любого g ∈ S должно существовать C
справедливо неравенство (v, g) 0.
всех v ∈ C
Теорема 2. Для того чтобы h(g) = min∗ max(v, g) 0 для любого g ∈ S, где
C∈E
v∈C
E∗ – семейство выпуклых контактов, необходимо и достаточно, чтобы произвольная гиперплоскость, проходящая через нуль, разделяла какие-то два множества се ∈ E∗ такое, что для
мейства E ∗ , т. е. для любого g ∈ S должно существовать C
справедливо неравенство (v, g) 0.
всех v ∈ C
Сформулируем и докажем аналогичные теоремы для обобщенных экзостеров.
Теорема 3. Для того чтобы
h(g) = sup inf (v, g) 0
C∈E∗ v∈C
∀g ∈ S,
(4)
где E∗ – семейство выпуклых множеств в Rn , необходимо и достаточно, чтобы выполнялось условие
∀ε > 0 ∃Cε ∈ E∗ : (v, g) −ε ∀v ∈ Cε .
(5)
Д о к а з а т е л ь с т в о. Докажем сначала необходимость. Пусть (4) верно. Выберем
и зафиксируем произвольное g из S и пусть
sup inf (v, g) = a, a 0.
C∈E∗ v∈C
Если a > 0, то по определению точной верхней грани существует множество C
что
из E∗ , такое что inf (v, g) > a/2 > 0, откуда (v, g) > 0 для любого v из cl C,
v∈C
означает справедливость (5).
Если a = 0, то непосредственно по определению точной верхней грани получаем,
что для любого ε > 0 существует Cε ∈ E∗ такое, что
inf (v, g) > a − ε = −ε.
v∈Cε
Отсюда следует, что для любого ε > 0 существует Cε из E∗ , для которого выполнено
(v, g) > −ε для любого v из cl Cε , а это означает справедливость (5).
Теперь докажем достаточность. Выберем и зафиксируем произвольное g из S
и пусть (5) верно. Возьмем последовательность {εk } такую, что εk > 0, εk −→ 0.
Тогда с ее помощью найдем соответствующую последовательность {Cεk }, для которой
(v, g) −εk при любом v ∈ Cεk , т. е. inf (v, g) −εk . Предположим, что
v∈Cεk
sup
inf (v, g) = a, a < 0.
C∈E∗ v∈Cεk
(6)
5
Так как εk −→ 0, то существует K > 0 такое, что для любого k > K будет a < −εk .
Тогда
inf (v, g) −εk > a ∀k > K,
v∈Cεk
откуда
sup inf (v, g) > a,
C∈E∗ v∈C
что противоречит (6). Таким образом, a 0, что означает выполнение (4).
Замечание 3. Если необходимое условие максимума из теоремы 3 не выполнено,
то
∃g ∈ S ∃ε > 0 : ∀C ∈ E∗ ∃vε ∈ C (vε , g) < −ε.
Любое такое направление есть направление спуска, а направление g ∈ S, где
sup inf (v, g) = inf sup inf (v, g),
C∈E∗ v∈C
g∈S C∈E∗ v∈C
является направлением наискорейшего спуска.
Точно так же доказывается теорема, описывающая условия максимума с помощью
обобщенного верхнего экзостера, являющегося в данном случае несобственным.
Теорема 4. Для того чтобы h(g) = inf ∗ sup (v, g) 0 для любого g ∈ S, где E ∗ –
C∈E v∈C
семейство выпуклых множеств в Rn , необходимо и достаточно, чтобы выполнялось
условие
∀ε > 0 ∃Cε ∈ E ∗ : (v, g) ε ∀v ∈ Cε .
Замечание 4. Если необходимое условие максимума из теоремы 4 не выполнено,
то
∃g ∈ S ∃ε > 0 : ∀C ∈ E ∗ ∃vε ∈ C (vε , g) > ε.
Любое такое направление есть направление подъема, а направление g ∈ S, где
inf sup (v, g) = sup inf ∗ sup (v, g),
C∈E ∗ v∈C
g∈S C∈E v∈C
является направлением наискорейшего подъема.
Условия строгого экстремума в терминах несобственных экзостеров (см. [10]) имеют
следующий вид.
Теорема 5. Для того чтобы h(g) = max min(v, g) > 0 для любого g ∈ S, где E∗ – сеC∈E∗ v∈C
мейство выпуклых компактов из Rn , необходимо и достаточно, чтобы произвольная
гиперплоскость, проходящая через нуль, строго разделяла какие-то два множества
∈ E∗ такое, что для любого
семейства E∗ , т. е. для любого g ∈ S должно найтись C
v ∈ C будет (v, g) > 0.
Теорема 6. Для того чтобы h(g) = min∗ max(v, g) < 0 для любого g ∈ S, где E ∗ –
C∈E
v∈C
семейство выпуклых компактов из Rn , необходимо и достаточно, чтобы произвольная гиперплоскость, проходящая через нуль, строго разделяла какие-то два множе ∈ E ∗ такое, что для
ства семейства E ∗ , т. е. для любого g ∈ S должно найтись C
любого v ∈ C будет (v, g) < 0.
Теперь сформулируем и докажем условия строгого экстремума в терминах обобщенных экзостеров.
6
Теорема 7. Для того чтобы
h(g) = sup inf (v, g) > 0
C∈E∗ v∈C
∀g ∈ S,
(7)
где E∗ – семейство выпуклых множеств из Rn , необходимо и достаточно, чтобы
∃
ε > 0 : ∀g ∈ S ∃Cg ∈ E∗ , (v, g) > ε ∀v ∈ cl Cg .
(8)
Д о к а з а т е л ь с т в о. Сначала докажем необходимость. Пусть (7) верно.
Выберем и зафиксируем произвольное g ∈ S. Тогда существует a > 0 такое, что
sup inf (v, g) = a.
C∈E∗ v∈C
∈ E∗ , для которого
По определению точной верхней грани для a/2 должно найтись C
inf (v, g) > a/2, откуда
v∈C
(v, g) > a/2 ∀v ∈ cl C.
Таким образом, беря ε = a/2, получим (8).
Достаточность очевидна. Действительно, пусть (8) верно, тогда
inf (v, g) ε ∀g ∈ S,
v∈Cg
откуда окончательно имеем
sup inf (v, g) ε > 0 ∀g ∈ S.
C∈E∗ v∈C
Аналогично формулируется и доказывается
Теорема 8. Для того чтобы
h(g) = inf ∗ sup (v, g) < 0
C∈E v∈C
∀g ∈ S,
где E ∗ – семейство выпуклых множеств из Rn , необходимо и достаточно, чтобы
∃
ε > 0 : ∀g ∈ S ∃Cg ∈ E ∗ , (v, g) < −
ε ∀v ∈ cl Cg .
(9)
Пример. Рассмотрим в точке 0n функцию
0,
если g/||g|| ∈ Qn или g = 0n ,
h(g) =
||g||, если g/||g|| ∈
/ Qn ,
здесь Q – множество рациональных чисел. Очевидно, в исследуемой
точке эта функция
достигает нестрогого минимума. Имеем E ∗ (0n ) = E0 ∗ (0n ) E1 ∗ (0n ), где
E0 ∗ (0n ) = {C0 (Δ)| Δ ∈ Qn , Δ ∈ S}, C0 (Δ) = {v ∈ Rn | (v, Δ) < 0},
/ Qn , Δ ∈ S}, C1 (Δ) = {v ∈ Rn | (v, Δ) < 1},
E1 ∗ (0n ) = {C1 (Δ)| Δ ∈
7
E∗ (0n ) = E∗ 0 (0n )
E∗ 1 (0n ) – нижний экзостер в точке 0n , причем
E∗ 0 (0n ) = {C 0 (Δ)| Δ ∈ Qn , Δ ∈ S}, C 0 (Δ) = {v ∈ Rn | (v, Δ) > 0},
E∗ 1 (0n ) = {C 1 (Δ)| Δ ∈
/ Qn , Δ ∈ S}, C 1 (Δ) = {v ∈ Rn | (v, Δ) > 1}.
Условие максимума (см. теорему 4) в терминах обобщенного верхнего (несобственного) экзостера не выполняется: для любого g ∈ S, g ∈
/ Qn и всякого C ∈ E ∗ (0n )
найдется v ∈ C, для которого, к примеру, (v, g) > 1/2. Поэтому все направления g ∈ S,
g ∈
/ Qn по замечанию 4 являются направлениями подъема. Так как для всех таких g
выполняется равенство inf
sup (v, g) = 1, то все эти направления являются направ∗
C∈E (0n ) v∈C
лениями наискорейшего подъема.
Если g принадлежит S и g ∈ Qn , тогда для любого v из C 0 (g) выполняется неравенство (v, g) > 0. Если g принадлежит S и g ∈
/ Qn , тогда для любого v из C 1 (g)
выполняется неравенство (v, g) > 1. Потому для всех g из S выполняется условие (5)
из теоремы 3. Следовательно, в точке 0n выполнено необходимое условие минимума
в терминах нижнего (несобственного) экзостера.
Литература
1. Пшеничный Б. Н. Выпуклый анализ и экстремальные задачи. М.: Наука, 1980. 320 с.
2. Demyanov V. F., Rubinov A. M. Constructive Nonsmooth Analysis, Approximation & Optimization.
Frankfurt am Main: Peter Lang, 1995. Vol. 7. 416 p.
3. Demyanov V. F. Exhausters and convexificators – new tools in nonsmooth analysis, quasidifferentiability and related topics // Nonconvex Optim. Appl. Dordrecht: Kluwer Acad. Publ., 2000. Vol. 43.
P. 85–137.
4. Demyanov V. F., Rubinov A. M. Exhaustive families of approximations revisited, from convexity to
nonconvexity // Nonconvex Optim. Appl. Dordrecht: Kluwer Acad. Publ, 2001. Vol. 55. P. 43–50.
5. Аббасов М. Э., Демьянов В. Ф. Условия экстремума негладкой функции в терминах экзостеров
и коэкзостеров // Труды Ин-та математики и механики Урал. отд. РАН. 2009. Т. 15, № 4. C. 10–19.
6. Demyanov V. F., Roschina V. A. Optimality conditions in terms of upper and lower exhausters //
Optimization. 2006. Vol. 55. P. 525–540.
7. Demyanov V. F. Proper Exhausters and Coexhausters in Nonsmooth Analysis // Optimization. 2012.
DOI:10.1080/02331934.2012.700929.
8. Demyanov V. F. Exhausters of a positively homogeneous function // Optimization. 1999. Vol. 45,
N 1–4. P. 13–29.
9. Demyanov V. F., Roshchina V. A. Constrained Optimality Conditions in Terms of Proper and Adjoint
Exhausters // Appl. Comput. Math. 2005. Vol. 4, N 2. P. 114–124.
10. Аббасов М. Э. Условия экстремума в терминах несобственных экзостеров // Вестн. С.-Петерб.
ун-та. Сер. 10: Прикладная математика, информатика, процессы управления. 2011. Вып. 2. С. 3–8.
11. Abbasov M. E., Demyanov V. F. Proper and adjoint exhausters in Nonsmooth analysis: optimality
conditions // J. of Global Optimization. 2013. Vol. 56, issue 2. P 569–585.
Статья рекомендована к печати проф. В. Ф. Демьяновым.
Статья поступила в редакцию 21 марта 2013 г.
Документ
Категория
Без категории
Просмотров
8
Размер файла
304 Кб
Теги
условия, обобщенные, экзостеров, несобственные, терминал, экстремума
1/--страниц
Пожаловаться на содержимое документа