Исчисление коэкзостеров второго порядка

2018 ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА Т. 14. Вып. 4

ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ

ПРИКЛАДНАЯ МАТЕМАТИКА

УДК 519.853 МБС 49Л52

Исчисление коэкзостеров второго порядка*

М. Э. Аббасов

Санкт-Петербургский государственный университет, Российская Федерация, 1199034, Санкт-Петербург, Университетская наб., 7—9

Для цитирования: Аббасов М. Э. Исчисление коэкзостеров второго порядка // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2018. Т. 14. Вып. 4. С. 276-285. https://doi.org/10.21638/11702/spbu10.2018.401

Коэкзостеры — новое понятие в негладком анализе, позволяющее исследовать экстремальные свойства широкого класса функций. Этот класс вводится конструктивным образом. Аналогично «классическому» гладкому случаю здесь разработаны формулы исчисления. Коэкзостеры — семейства выпуклых компактов, дающие возможность аппроксимировать приращение изучаемой функции в окрестности рассматриваемой точки в виде либо максимина, либо минимакса аффинных функций. Для более тонкого исследования негладких функций было введено понятие коэкзостеров второго порядка, которые также являются семействами выпуклых компактов и применяются для представления аппроксимации приращения функции в виде максимина или минимакса квадратичных функций. Эти объекты используются для построения оптимизационных алгоритмов второго порядка. Однако вновь возникает важная для практики задача построения исчисления, решению которой и посвящена данная работа.

Ключевые слова: негладкий анализ, недифференцируемая оптимизация, коэкзостеры второго порядка.

Введение. Коэкзостеры — новое понятие в негладком анализе, позволяющее исследовать экстремальные свойства широкого класса непрерывных функций.

Рассмотрим функцию / X ^ М, X с М" — открытое множество. Пусть х е X и функция ] непрерывна в точке х.

Говорят, что в точке х у функции f существует верхний коэкзостер первого порядка в смысле Дини, если имеет место разложение

* Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект № 18-31-00014).

© Санкт-Петербургский государственный университет, 2018

/

CeE(x) [a,v]<iC

в котором E(x) — семейство выпуклых компактов в Rn+1, а wi(x, Д) удовлетворяет условию

=0 \/Д € R™.

aiü а

Если wi(x, Д) в (1) удовлетворяет условию

то говорят, что в точке х у функции / есть верхний коэкзостер первого порядка в смысле Адамара. Множество E(x) называется верхним коэкзостером функции f в точке x.

Говорят, что в точке x у функции f есть нижний коэкзостер первого порядка в смысле Дини (Адамара), если имеет место разложение

f (x + Д) = f (x)+ max min [b + (v, Д)] + u1(x, Д),

СеЕ(ж) [b,w]zC

в котором E_(x) — семейство выпуклых компактов в Rn+1, а и>i(x, Д) удовлетворяет (2) (или (3)). Множество Е_{х) называется нижним коэкзостером первого порядка функции f в точке x.

Понятие коэкзостеров первого порядка было введено в [1, 2]. Условия экстремума в терминах этих объектов были получены в [3, 4]. Исчисление для данных семейств описано в [5]. Можно выделить класс функций, имеющих непрерывное коэкзостер-ное отображение, что важно для оптимизационных алгоритмов, использующих эти объекты.

Для более тонкого исследования негладких функций было введено понятие коэкзостеров второго порядка [3, 6].

Говорят, что в точке x функция f обладает верхним коэкзостером второго порядка в смысле Дини, если справедливо представление

f(x + Д) = f(x) + min max

СеЕ(х) [a,v,A]<iC

a+

+ w2

где

=() уДбК„;

aiü а2

E(x) — семейство выпуклых компактов в R х R" х Rnxn. Если в (4) условие

lim = 0,

то говорят, что в точке х функция / имеет верхний коэкзостер второго порядка в смысле Адамара. Множество E(x) называется верхним коэкзостером второго порядка (в смысле Дини или Адамара) функции f в точке x.

Аналогично говорят, что в точке x у функции f есть нижний коэкзостер в смысле Дини второго порядка, если справедливо представление

f (x + Д) = f (x) + max min

CtE{x) [a,v,Ä]iC

+ w2

в котором Д) удовлетворяет (5) для всех Д € К™, Е_(х) — семейство выпуклых компактов в МхМ"хМ"х". Если в (7) ш2(х, Д) удовлетворяет (6), то в точке х функция / имеет нижний коэкзостер в смысле Адамара второго порядка. Множество Е_{х) называется нижним коэкзостером второго порядка (в смысле Дини или Адамара) функции / в точке х.

Если существуют верхний и нижний коэкзостеры второго порядка в смысле Дини (Адамара), то пару множеств Е(х) = [Е_(х)] Е(х)] называют бикоэкзостером второго порядка в смысле Дини (Адамара).

Получим основные формулы исчисления коэкзостеров второго порядка.

Исчисление коэкзостеров второго порядка.

Теорема 1. Пусть у функций /1,/2:X ^ М, где X с М" — открытое множество, в точке х е X есть бикоэкзостеры второго порядка в смысле Дини (Адамара) Е\{х) = \Е_1{х),Е\{х)\, Е2(х) = [Е_2(х), Е2(х)\ соответственно. Тогда функция -Р = /1 + /2 в точке х также имеет бикоэкзостер второго порядка в смысле Дини (Адамара) вида Е{х) = [Е_(х), Е(х)~\, где

Е{х) = Е1{х) + Е2{х) = [Е^х) + Е2(х),Ё1(х) + Ё2{х)] .

Теорема 2. Пусть функция /\-X ^ М, где X с М" — открытое множество, в точке х е X имеет бикоэкзостер второго порядка в смысле Дини (Адамара) Е\(х) = [Е_ 1(ж), а А — произвольное вещественное число. Тогда у функции

Е = Л/1 в точке х также есть бикоэкзостер второго порядка в смысле Дини (Адамара) вида

На основании теорем 1 и 2 можно заключить, что имеет место следующее утверждение.

Теорема 3. Пусть у функций /1,/2:X ^ М, где X с М" — открытое множество, в точке х е X есть бикоэкзостеры второго порядка в смысле Дини

соответственно, а Л1, Л2 — произвольные вещественные числа. Тогда у функции Е = ^1/1 + А2/2 в точке х есть бикоэкзостер второго порядка в смысле Дини (Адамара) вида Е{х) = [Е(х), Е{х)~\, где Е{х) = Х^Е^х) + А2Е2{х).

Говорят, что семейства £4 (ж), г = 1,2, ограничены в совокупности констан-

той Д > 0, если при любом С из х) или г = 1,2, выполняется неравенство

Отметим, что здесь используются евклидова норма и норма Фробениуса. Очевидно, отсюда следует, что для каждого г = 1, 2 справедливо неравенство

для любого С из Е_ЖХ) или Ег(х), г = 1,2. Здесь В 1(0„) — замкнутый шар из М™ единичного радиуса с центром в начале координат.

если Л ^ 0; если Л ^ 0.

Е\(х) = [^(аО.Я^х)], Е2(х) = [Е2(х),Е2(х)]

а+(у,А) + -(А,АА) <Н УДеВ^О«), V[а,у,А]еС,

1

Теорема 4. Пусть у функций X ^ М, где X с Мп — открытое .множе-

ство, в точке х е X есть бикоэкзостеры второго порядка в смысле Дини (Адамара) Е\(х) = [Е_х(х), Е\(х)], Е2(х) = [Е_2(х), Е2(х)] соответственно, причем семейства Е_{(х)> Ег(х), г = 1,2, ограничены в совокупности константой Е. Тогда у функции = /1 ' /2 в точке х также есть бикоэкзостер второго порядка в смысле Дини (Адамара) вида Е(х) = [Е_(х), Е(х)], и

где

Е{х) = -ЩЕ^х) + Е2{х)) + Е(х) + /1 Е2{х) + ¡2Е ^х), Е{х) = {х) + Ё2{х)) + Е{х) + ЬЕ2(х) + /2^1 (х),

Е{х) = \С = [а, ю,Л\ | а = а\а2 + Е{а\ + а2), ' =(и1 + У2)Е + о,1у2 + а2у1, А = А1(а2 + Е) +А2(ол + Е) + 2У1УТ2 }, [а1/и1,А1] еС\е Е^х), [а2,у2,А2] е С2 е Е2(х), Е_(х) = \С = [а, ю,Л\ | а = а\а2 + Е{а\ + а2), ' =(и1 + у2)Е + о,1у2 + а2у1, А = А1(а2 + Е) +А2(а1 + Е) + 2У1УТ2 }, [а1,у1,А1] € С1 еЕ^х), [а2,у2,А2] е С2 еЕ2(х).

Доказательство. Коэкзостеры описывают локальную аппроксимацию исследуемой функции в окрестности рассматриваемой точки, поэтому без ограничения общности можно считать, что Д € Вц(0п), где 6 е(0,1) — некоторое малое число, а Вй(0п) — шар радиуса 6 с центром в начале координат.

Имеем равенство

Е(х + Д)= ¡1(х + Д)  ¡2(х + Д) = Ь(х)  ¡2(х) +

+ тт тах

Се В 1(ж) [а,и,А]еС

х тт тах

СеЕ2(х) [а,и,А]еС

а+<«,Д) + ±<ЛД,Д) а+<«,Д) + ±<ЛД,Д)

+ /1(х)' тш тт

СеЕ2(х) [а,у,А]^С

+ /2 (ж)- тт тах

СъЕ^х) [о.,у,А]£С

а+

а+{у,А} + -{АА,А)

+ Ш2(х, Д),

где ^2(х, Д) удовлетворяет (5) или (6) в зависимости от того, в каком смысле заданы бикоэкзостеры второго порядка Е\(х), Е2(х).

Очевидно, для любого 6 €(0,1) и для каждого г = 1, 2 справедливо неравенство

а+

<Е, УДеД;(Оп), М[а,у,А]еС, МСеЕ^х). Для первого слагаемого в (10) имеем выражение

тт тах

х тт тах

а+

а+{у,А} + -{А,АА)

тт тах

\с$Е2{х) [а,и,А]еС

а+ {у,А} + -{А,АА} + К

а+ {у,А}+ -{А,АА} + К

К

_ тт _ тах

СцЕг^х), С2$Е2{х) [о1,-У1,А1]ёС1, [а2,у2,А2]ёС2

а1 + («1, Д) +

+ к{ал + а2 + {VI + У2,А) + ^(Д, (А1 + А2)А)) - Д _ тт _ тах I + а2 +

СцЕг^х), С2£Е2{х) [а1,1л,А1]еС1, [а2,у2,А2]ёС2 \

+

Для первого слагаемого в (11) можно записать, что

тт

С\чЕ1(х), С2^Е2(х)[а1,у1,А1^С1, [а2,-и2,А2]ёС2 1.....\ / , . , 1

Д ^а! + а2 +

а1 + (у1, Д) + Д)) +

_ тт _ тах

СцЕг^х), С2£Е2{х) [а1,1л,А1]еС1, [а2,-и2,А2]ёС2

а1а2 + К(а1 + а2) + + (а1«2 + а2«1 + К(«1 + «2), Д) +

+ Ы2 (х, Д) =

+ -(А, (а^ + + + П(Аг + А2))Д|

= тт тах

а+

+ Ш2(х, Д),

здесь

Е{х) = \С = [а, V, А] \ а = а\а2 + К{а\ + а2), = («1 + V2)К + а1«2 + а2«1, А = А1(а2 + К)+А2(а1 + К) + 2у1у12 }, [«Ъ € Сх € Е 1(ж), [а2, -у2, А2] е С2 е Е2(х),

х

+

_ min _ min Ф(х, Д,г>ь ^4.1,^2,^4-2) ^

CitEi{x), C2zE2{x)[ai,vi,Ai]zCl, [a2,v2,A2]tC2

< W2(x, Д) <

^ _ max _ max Ф(х, Д, г>1, Ai, v2, A2),

CitEi{x), C2zE2{x)[ai,vi,Ai]zCl, [a2,v2,A2]<eC2

Ф(х,А,у1,А1,у2,А2) = ^{vuA){A,A2A) + ^{v2,A){A,AlA) + J (Д, ^Д) (Д, Д).

Отметим, что, в силу ограниченности в совокупности семейств Е^(х), Ei(x), i = 1,2, стремление

ф

II Д II 2 11ЛЦ-0

0

будет равномерным по совокупности переменных г^, А^, у2, А2, где [сь1, € С\ е

Е1(х), [а2,«2,А2] е С2 е Е2(х), а потому Ш2(х, Д) в (12) удовлетворяет условию (6). Для г = 1,2 имеем (см. (4), (7)) выражение

min max

CeEi(x) [a,v,A]<iC

a+

= max mm

СеВДж) [a,v,A]<iC

а +

2

Складывая равенства (13) при i = 1 и i = 2, получаем

+ W2(x, Д).

_ mm _ max \a,i + a2 +

C1&E1 (x), C'2eE2(x) [ai,ui,Ai]eCi, [a2,v2,A2]tC2 ^

+ (Vl + v2, А) + (Ai + А2)Д)| = max min ( a1 + a2 + {v1 + v2, Д) +

C1(iE_1(x), C2tE_2(x)[a1,v1,A1](iC1, [a2,v2,A2](iC2 \

+ l-(A,{Ai + A2)A)\+w2{x,A).

Для второго слагаемого в (11) с учетом (14) имеем цепочку равенств -R _ min _ max I ai + а2 +

CitEi{x), C2zE2{x) [ai,ui,Ai]eCi, [a2,v2,A2]<iC2 \

+ (Vl + V2,A) + Д, (Аг + А2)Д)| =

= -R max min (a1 + a2 +

C1(iE_1(x), C2tE_2(x)[a1,v1,A1](iC1, [a2,v2,A2](iC2

+ (Vl +V2,A) + {Ai + A2)A) I + lü2(X, Д) =

(a

= -Е тах

тт

С'£Е1(х)+Е2(х) [а,-и,а]ёс

тт

с^е1

-Е тт

[а,у,Л]^С

а+

а+{у,А} + -{А,АА)

тт тах

С€Е_1(х)+Е_2(х) [а,у,А]£С

тт тах

С^-НЕ1(х)-НЕ2(х) [а,у,А]£С

а+{у,А} + -{А,АА)

+ Ш2(х, Д) = + Ш2(х, Д) = + Ш2(х, Д) = + Ш2(х, Д).

Итак, окончательно из (10) с учетом (11), (12), (15) получаем разложение

Е (х + Д) = Е (х) + тт тах

СеЁ

а+<«,Д) + ±<Д,ЛД)

+ тт тах

Сч-Н(Е1{х)+Е2{х)) [а,у,А]£С

+ ЛС37) ' ™ тт

СеЕ2(х) [а,у,А]€С

а+{у,А} + -{А,АА)

а+

+ /2 (х)  тт тах

СъЕ^х) [О.,У,А]£С

а+{у,А} + -{АА,А)

+ Ш2(х, Д),

откуда и следует формула (8). Выражение (9) доказывается аналогично.

Теорема 5. Пусть функция Д:X ^ М, где X с Мп — открытое множество, в точке х е X имеет бикоэкзостер второго порядка в смысле Дини (Адамара) Е\(х) = [¿^(ж), Е\(х)\, причем семейства ^(х) и Е\(х) ограничены в совокупности константой Е и, кроме того, }\{х) Ф 0. Тогда и функция Е = в точке х также имеет бикоэкзостер второго порядка вида в смысле Дини (Адамара) Е(х) = [Е{х),Ё{х)], где

= ^ + ТзГТ ("2ДВД + 2/1(х)Е1(х) + Е(х)),

Е(х) = -ЩГТ + Тзгг + Шх)ЕЛх) + ад),

/1Vх) 11 Vх) Е{х) = \С = [а, V, А] \ а = а\а2 + Е{а\ + а2),

V = (и\ + У2)Е + а\У2 + 02У\, А = А\(о2 + Е) + А2(а\ + Е) + },

[а1,у1, А]] € С1 € Е 1(ж), [а2,у2,А2] е С2 е Е^х), Ш\х) = {С = [а;А] | а = а\а2 + Е(а\ + а2),

V = («1 + V2)Е + а1«2 + а2«1. А = А1(а2 + Е) + А2(а1 + Е) + 2«^^},

[аьг>1, А{\ € С1 еЯ^ж), [а2,у2,А2] е С2 еЕ^х).

Доказательство. Поскольку

111 1

=---тек н—-с? + о(а2),

то с учетом теоремы 4 получаем требуемое.

+

+

+

Теорема 6. Пусть I — конечное множество индексов, X с R" — открытое множество, функции fi(x):X R, г е I, имеют бикоэкзостеры второго порядка в смысле Дини (Адамара) Ei(xо) = [E_i(xo), Ei(xo)~\. Тогда

1) у функции Fi(x) = max fi(x) в точке x0 есть нижний коэкзостер второго

iiI

порядка в смысле Дини

Шхо) = иЖы,

iiI

где

Е,(хо) = {С+ [fi(xо) - Fi(xo), 0„, Опх„] | С е Е,(х0)} ;

2) у функции F2(x) = minfi(x) в точке x0 есть верхний коэкзостер второго

iiI

порядка в смысле Дини

Е2(хо) = \jEy(x0),

iiI

здесь л

Еу (х0) = {С + [fi (хо) - F2 (хо), 0„, Опх„] | С € % (х0)} .

Доказательство. Имеем цепочку равенств

F\(x0 + Д) = max fi(x0 + Д)= max fi(x0) + max

iiI iiI iiI

fi

iiI

+ max min СеЕДжо) [а,с,А]бС

а+(«,Д) + -(АД,Д>

+ ^2,i

= Fi(xo) + max Д) +u2Ax0, Д)],

iiI

для упрощения записи используем обозначение

фi(xo, Д) = fi(xo)- max fi(xo)+ max min

Ш СеЕ^хо) [а,и,А]еС

a+

Заметим, что, с одной стороны,

max [ф,i(x0, Д) + ш2 i(x0, Д)] ^ maxф^0, Д) + maxш2 i(x0, Д),

iiI iiI iiI

а с другой

max [фi(x0, Д) + &2,i(x0, Д)] ^ max

iiI iiI

Ф.

iiI

= maxФ.^0, Д) + min&2,i(x0, Д).

iiI iiI

Поэтому можем записать неравенства

min&2,i(x0, Д) ^ max [фi(x0, Д) + &2,i(x0, Д)] - maxф^0, Д) ^ max&2,i(x0, Д),

iiI iiI iiI iiI

откуда получаем

max [фi(x0, Д) +^2,i(x0, Д)] - maxф^0, Д) = ^2(^x0, Д),

iiI iiI

где в зависимости от того, в каком смысле задавались бикоэкзостеры Е^(хо), г е I, выполняется одно из условий

Пт"2(а\аА) =0 УДеМ™,

Таким образом, можно записать, что

(хо + Д) = ^\(хо)+шахфг(хо, Д)+^(хо, Д) = ^\(жо) +

+ max mm ш

Ш

+ fi

+ ^2(^0, Д).

Для Î2 доказательство проводится таким же образом.

Литература

1. Абанькин А. Е. Безусловная минимизация Я-гипердифференцируемых функций // Журн. вычисл. математики и матем. физики. 1998. Т. 38(9). С. 1500—1508.

2. Demyanov V. F. Exhausters and convexificators — New tools in nonsmooth analysis // Quasi-differentiability and related topics / eds by V. Demyanov, A. Rubinov. Dordrecht: Kluwer Academic Publ., 2000. P. 85-137.

3. Abbasov M. E., Demyanov V. F. Extremum conditions for a nonsmooth function in terms of exhausters and coexhausters // Proceedings of the Steklov Institute of Mathematics. 2010. Vol. 269(1). P. 6-15.

4. Abbasov M. E., Demyanov V. F. Adjoint coexhausters in nonsmooth analysis and extremality conditions // Journal of Optimization Theory and Applications. 2013. Vol. 156(3). P. 535-553.

5. Dolgopolik M. V. Inhomogeneous convex approximations of nonsmooth functions // Russian Mathematics. 2012. Vol. 56(12). P. 28-42.

6. Abbasov M. E. Second-order minimization method for nonsmooth functions allowing convex quadratic approximations of the augment // Journal of Optimization Theory and Applications. 2016. Vol. 171(2). P. 666-674.

Статья поступила в редакцию 23 марта 2018 г.

Статья принята к печати 25 сентября 2018 г.

Контактная информация:

Аббасов Меджид Эльхан оглы — канд. физ.-мат. наук, доц.; m.abbasov@spbu.ru

a

Calculus of second order coexhausters*

M. E. Abbasov

St. Petersburg State University, 7—9, Universitetskaya nab., St. Petersburg, 199034, Russian Federation

For citation: Abbasov M. E. Calculus of second order coexhausters. Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 2018, vol. 14, iss. 4, pp. 276-285. https://doi.org/10.21638/11702/spbu10.2018.401

Coexhasuter is a new notion in the nonsmooth analysis that allows one to study extremal properties of a wide class of functions. This class is introduced in a constructive manner analogous to the "classical" smooth case. Formulas of calculus were developed. Coexhausters are families of convex compact sets allowing one to approximate the increment of the studied function in the neighbourhood of the considered point in the form of MaxMin or MiniMax

*The work is supported by Russian Found of Fundamental Research (project N 18-31-00014 mol-a).

of affine functions. For a more detailed study of nonsmooth functions, a notion of second-order coexhausters was introduced. These are also families of convex compact sets which are used to represent the approximation of the increment of the studied function in the form of MaxMin or MiniMax of quadratic functions. These objects are used to build second-order optimization algorithms. However, an important problem of constructing calculus arises again. The solution to this problem is the subject of this paper.

Keywords: nonsmooth analysis, nondifferentiable optimization, second order coexhausters. References

1. Abankin А. Е. Bezuslovnaia minimizatsiia Я-giperdifferentsiruemykh funktsii [Unconstrained minimization of Я-hyperdifferentiable functions]. Computational Mathematics and Mathematical Physics, 1998, vol. 38

2. Demyanov V. F. Exhausters and convexificators — New tools in nonsmooth analysis. Quasi-dif-ferentiability and related topics. Eds by V. Demyanov, A. Rubinov. Dordrecht, Kluwer Academic Publ., 2000, pp. 85-137.

3. Abbasov M. E., Demyanov V. F. Extremum conditions for a nonsmooth function in terms of exhausters and coexhausters. Proceedings of the Steklov Institute of Mathematics, 2010, vol. 269(1), pp. 6-15.

4. Abbasov M. E., Demyanov V. F. Adjoint coexhausters in nonsmooth analysis and extremality conditions. Journal of Optimization Theory and Applications, 2013, vol. 156(3), pp. 535-553.

5. Dolgopolik M. V. Inhomogeneous convex approximations of nonsmooth functions. Russian Mathematics, 2012, vol. 56(12), pp. 28-42.

6. Abbasov M. E. Second-order minimization method for nonsmooth functions allowing convex quadratic approximations of the augment. Journal of Optimization Theory and Applications, 2016, vol. 171(2), pp. 666-674.

Received: March 23, 2018. Accepted: September 25, 2018.

Author's information:

Majid E. Abbasov — PhD in Physics and Mathematics, Associate Professor; m.abbasov@spbu.ru