Аппроксимация и оптимизация липшицевых функций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САНКТ - ПЕТЕРБУРГСКИЙ ГОСУЛДРПТПР.НПНПМЙ УНИВЕРСИТЕТ

42050

ПРУДНИКОВ Игорь Михайлович

АППРОКСИМАЦИЯ И ОПТИМИЗАЦИЯ ЛИПШИЦЕВЫХ

ФУНКЦИЙ

01.01.09 — Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

7АПР 2011

Санкт - Петербург - 2011

4842050

Работа выполнена в Санкт Петербургском государственном университете

Научный консультант — заслуженный деятель науки РФ, профессор, доктор физико-математических наук В. Ф. Демьянов

Официальные оппоненты:

доктор физико-математических наук, профессор, зав. кафедрой Московского физико-технического института — Евгений Сергеевич Половинкин

доктор физико-математических наук, профессор Санкт-Петербургского университета — Андрей Юрьевич Гарнаев

доктор технических наук, профессор, зав. отделом Института проблем управления РАН им. В. А. Трапезникова — Борис Теодорович Поляк

' Ведущая организация — Институт системного анализа РАН

Защита диссертации состоится " " 2011 г. в

/У часов на заседании специализированного совета Д.212.232.59 по присуждению ученой степени доктора физико-математических наук в Санкт Петербургском университете по адресу: 199004, Санкт-Петербург, Средний проспект ВО, д. 41/43, ауд. 513.

С диссертацией можно познакомиться в. библиотеке имени М. Горького Санкт Петербургского университета по адресу: 199034, Санкт-Петербург, Университетская наб. 7/9.

Автореферат разослан " " 2011 г.

Ученый секретарь специализированного совета доктор физико-математических наук, профессор В. Д. Ногин

Общая характеристика работы

Актуальность темы исследования. ХХ-ый век ознаменовался применением вычислительных методов для решения важнейших экономических задач. J1.B. Канторович впервые изучил задачу планирования и оптимальных перевозок грузов (транспортная задача), и были построены алгоритмы ее решения. Первые задачи такого рода сводились к поиску максимума или минимума линейной функции на множестве, заданном в виде системы неравенств. Позднее стали изучать задачу нахождения минимума (максимума) квадратичной функции на произвольном выпуклом множестве. Далее перешли к оптимизации произвольной выпуклой функции.

Развитие техники, экономики, теории управления привело к необходимости разработки методов оптимизации негладких (недифферен-цируемых) или недостаточно гладких функций, у которых, например, нет вторых производных по переменным. Первый прогресс в этом направлении был сделан в работах математических школ Москвы, Ленинграда, Новосибирска, Екатеринбурга, Киева, Минска. Следует упомянуть работы В. В. Гороховика, В. Ф. Демьянова, И. И. Еремина, Ю. М. Ермольева, Я. И. Заботина, А. Д. Иоффе, С. С. Кутателадзе, А. Г. Кусраева, В. Н. Малоземова, Б. Ш. Мордуховича, Е. А. Нур-минского, Б. Т. Поляка, Б. Н. Пшеничного, А. М. Рубинова, В. М. Тихомирова, Н.З. Шора и др.

Среди зарубежных ученых, внесших значительный вклад в развитие негладкого анализа и методов недифференцируемой оптимизации, были R. T. Rockafellar, F. Clarke, J.-P. Aubin, J.-P. Penot, E. Polak, J. Hiriart-Urruty, C. Lemarechal, B. Luderer, D. Pallaschke, К, C. Kiwiel, A. Shapiro, F. Giannessi, L. Thibault, J. -J. Moreau, J. Warga, R. Mifflin, J. Gwinner, J. V. Outrata, I. Ekeland.

Задача оптимизации функций тесно примыкает к задачам, связанным с изучением оптимальных процессов в теории управления, разработанной Л. С. Понтрягиным и его учениками. Здесь надо отметить работы В. Г. Болтянского, Ф. П. Васильева, Р. В. Гамкрелидзе, А. Я. Дубовицкого, Ю. Г. Евтушенко, В. И. Зубова, H. Н. Красовского, А. Б. Куржанского, А. М. Летова, А. А. Милютина, Е. Ф. Мищенко, Н. Н. Моисеева, А. И. Пропоя, А. Н. Тихонова, Ф. Л. Черноусько и др. Современные исследователи в этом направлении расширили класс оптимизируемых функций. Рассматриваются функции, представимые разностью выпуклых функций. Здесь уместно упомянуть работы В. Ф. Демьянова, С. И. Дудова, Е. С. Половинкина, Л. Н. Поляковой. _

! *

Широкое применение методов негладкой оптимизации началось тогда, когда были разработаны методы оптимизации произвольной выпуклой функции. Были введены обобщенные градиенты (субградиенты), выпуклая оболочка которых в каждой точке образует субдифференциал. Численные методы оптимизации таких функций основывались на поиске направления наискорейшего спуска. Впервые такие методы были предложены Н. 3. Шором.

Дальнейшим шагом вперед было введение обобщенных градиентов для лишшщевых функций, как элементов из некоторого выпуклого компактного множества, называемого субдифференциалом функции в точке. В отличие от выпуклого случая здесь нет однозначного определения субдифференциала. Разные авторы определяют субдифференциал по-своему. Достаточно обратиться к работам Ф. Кларка, Ж. Пено и Б. Ш. Мордуховича.

Другие авторы (В. Ф. Демьянов, А. М. Рубинов) пошли по пути изучения дифференцируемых по направлению функций и различного вида представления производной по направлению. Был введен класс квазидифференцируемых функций. Производная по направлению таких функций представляется как сумма максимума и минимума скалярных произведений векторов из некоторых выпуклых компактных множеств на вектор направления.

Актуальным на сегодняшний день является введение таких многозначных отображений, которые можно было бы использовать для построения непрерывных расширений субдифференциала Кларка и поиска на их основе стационарных точек, в которых нуль принадлежит субдифференциалу Кларка. Кроме того, важно показать связь различных методов аппроксимаций липшицевых функций, и, возможно, указать новые способы построения субдифференциалов.'

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

Для нахождения вида производной по направлению маргинальной функции требуется строить аппроксимацию одного многозначного отображения относительно другого многозначного отображения, находить вид различных конусов, а также вид субдифференциала Кларка для таких функций.

Для построения более ускоренных методов оптимизации негладких или недостаточно гладких функции функций требуется опреде-

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

Проблема нахождения условий представимости произвольной липшицевой функции в виде разности выпуклых функций интересна для математиков разных специальностей, Получение условий представимости функции в виде разности выпуклых, а также условий ква-зидифференцируемости функции в точке важно для специалистов в области оптимизации.

Цель работы. Основной целью диссертации является разработка новых методов аппроксимации широкого класса функций - локально липшицевых функций и построение на их основе новых методов оптимизации негладких или недостаточно гладких функций, к которым неприменимы или для которых не выполняются условия сходимости оптимизационных процессов высокого порядка. Исследуются новые виды многозначных отображений (МО), различные способы аппроксимаций МО и их взаимосвязь, поскольку основными объектами изучения в негладкой оптимизации являются обобщенные градиенты, образующие в совокупности множества, являющиеся образами некоторых МО. Другой, не менее важной, целью работы является применение аппроксимационных методов к задачам теории управления.

Научная новизна. В диссертации вводится новый способ аппроксимации локально липшицевых функций и показана связь с уже существующими. Доказано, что для функций, локально представи-мых разностью выпуклых, введенный метод аппроксимации совпадает с аппроксимацией Кларка. Усредненные интегральные градиенты, используются для построения непрерывных равномерных аппроксимаций субдифференциала Кларка, что важно для нахождения стационарных точек.

Вводятся МО, связанные с новым способом аппроксимации. Доказывается их липшицевость и определяется для них субдифференциал Кларка. В работе разрабатываются оптимизационные методы нахождения стационарных точек липшицевых функций. Для этой цели вводятся а- и (а, <5)-обобщенные матрицы.

На основе развитой теории строятся нижние выпуклые аппроксимации для липшицевых функций и определяются правила их постро-

ения для различных их комбинаций. Строится исчисление главных нижних выпуклых аппроксимаций, то есть определяются правила их построения для суммы (разности), произведения (частного) и произвольной сложной комбинации функции, главные нижние аппроксимации которых известны. Если главные нижние аппроксимации в окрестностях точек, подозрительных на экстремум, построены, то в дальнейшем оптимизируется не сама функция, а функция, составленная из главных нижних аппроксимаций исходной функции.

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

Важным применением всего этого является нахождение производной по направлению маргинальных функций при более слабых требованиях, чем это делалось ранее, что важно для оптимизации таких функций. Удается найти субдифференциал Кларка маргинальной функции в точке. Строятся главные нижние аппроксимации для маргинальных функций.

Развивается новый нелокальный способ аппроксимации негладких и недостаточно гладких функций, в результате которого получаем дважды дифференцируемые функции, сохраняющие е(Б)-стационарные точки. С помощью таких функций строятся ускоренные методы оптимизации, сходящиеся к £(Г>)-стационарным точкам.

. Рассматривается нелокальный поисковый алгоритм нахождения глобального оптимального управления для систем, описываемых обыкновенными дифференциальными уравнениями. Для оптимизации используются уравнения Пуассона и теплопроводности, для решений которых применяется метод овыпукления, позволяющий сделать решения этих уравнений выпуклыми (вогнутыми) по управлению и регуляризационному параметру а в окрестности точки глобального минимума по обоим переменным. Предлагается строить главные нижние выпуклые аппроксимации для целевой функции в некоторых достаточно больших окрестностях фиксированных точек, что делает

оптимизационный процесс более устойчивым к изменениям аргумента.

Даются условия представимости произвольной липшицевой функции двух переменных в виде разности выпуклых, что важно для задач оптимизации.

Методы исследования. Общая методика исследования базируется на теории функций, теории меры и интеграла Лебега, выпуклом анализе, теории многозначных отображений и их аппроксимации, теории необходимых условий экстремума, численных методах решения задач нелинейного программирования и задач на минимакс, аналитической геометрии.

Практическая ценность и реализация результатов. Выше была отмечена важность развития методов оптимизации второго порядка для липшицевых функций, чему и посвящена работа. Введены новые способы аппроксимации липшицевых функций, с помощью которых удается построить непрерывные расширения субдифференциала Кларка, что находит применение в оптимизационных методах. В диссертации устанавливается вид производной по направлению маргинальной функции и ее субдифференциала Кларка, что важно для развития оптимизационных методов таких функций. Впервые предложен метод поиска глобального оптимального управления, использующий идею овыпукления решения уравнения Пуассона и уравнения теплопроводности. Применение нижней выпуклой аппроксимации к целевой функции задачи теории управления существенно упрощает оптимизационную задачу. Целевая функция после применения нижней выпуклой аппроксимации становится полунепрерывной снизу, а сама задача - устойчивой для малых изменений управления и. Разработаны и отлажены программы для нахождения глобальной точки экстремума, использующие эту идею. Предложена интегральная аппроксимация функции, сохраняющая е(1))-стационарные точки, на основе которой разработан алгоритм ускоренного поиска таких точек. Теорема, дающая условия представимости липшицевой функции в виде разности выпуклых функций, имеет как теоретический, так и практический интерес, так как с ее помощью возможно построить алгоритм разложения положительно-однородной многогранной функции с конечным числом граней в виде разности выпуклых.

Апробация работы. Большая часть результатов была опубликована в статьях центральных издательств, а также за рубежом. Результаты докладывались и обсуждались на международных конфе-

ренциях:

- Негладкий анализ и оптимизация, ЛОМИ, Ленинград, 1995;

- International Conference of Asia-Pacific, APORS 97, Melbourne, Australia, 1997;

- Америко - австралийский математический съезд, Мельбурн, 1999;

- Международная конференция, посвященная 75-летию член-корреспондента АН СССР Зубова В.И., 2005;

- Международная конференция по современным проблемам кибернетики, Казань, 2005;

- Конференция, посвященная 90-летию академика H.H. Моисеева, 2007;

- 2-ая международная конференция по социальной и экономической динамике, Москва, 2007;

- Международная конференция "Индентификация систем и задачи управления, SICPRO'08", 2008;

- 10-ая математическая школа-семинар по проблемам теории функций, Саратов, 2008;

- Международная конференция "Дифференциальные уравнения и топология", посвященная 100-летию академика Л.С. Понтрягина, Москва, 2008;

- Международная конференция "Актуальные вопросы теории устойчивости и управления", посвященная 85-летию академика H.H. Красовского, Екатеринбург, 2009;

На семинарах:

- В Московском физико-техническом институте,

- В Институте проблем управления РАН,

- В Институте системного анализа РАН,

- В Санкт Петербургском университете на факультете прикладной математики и процессов управления.

Структура и объем работы. Диссертация состоит из Введения, пяти глав, приложения, 22 рисунков и списка литературы. Объем диссертации 296 страницы. В Приложение включены 22 рисунка и таблица с результатами численных экспериментов. Список литературы состоит из 99 наименований. Общий объем диссертации 327 страниц.

Публикация результатов. По материалам диссертации опубликовано 27 работ, из которых 17 входит в перечень ВАК РФ рецензируемых журналов.

Содержание работы

Во Введении даются основные понятия о градиентных методах первого порядка и методах второго порядка для функций / € C2(D) , т.е. дважды непрерывно дифференцируемых на D. Описаны общие проблемы негладкой оптимизации. Первая из которых — это определение и введение градиентов для негладких функций, которая была решена путем введения обобщенных градиентов, образующих в совокупности для липшицевых функций выпуклые компактные множества. С множеством обобщенных градиентов связаны методы оптимизации первого порядка, т.е. градиентные методы, и запись необходимых условий экстремума, а также методы аппроксимаций.

Наиболее трудной является вторая задача — определение и введение обобщенных матриц - аналога матриц вторых смешанных производных, без решения которой невозможно строить аналоги методов второго порядка для негладких функций. Трудность заключается в том, что нет однозначности введения таких матриц. Главным критерием правильности выбранного пути является, конечно, совпадение результатов для гладкого и негладкого случаев. Вначале вводятся a-обобщенные матрицы, а затем их непрерывные аналоги {а, 5)-обобтценные матрицы, с помощью которых строятся численные методы нахождения a-стационарных точек.

Во втором параграфе главы 1 вводятся основные термины, связанные с многозначными отображениями (МО) и используемые при доказательстве теорем, как, например, полунепрерывность сверху (П.СВ), снизу (П.СН), а также непрерывность МО, теорема Какута-ни. В процессе изложения материала читателю напоминаются необходимые сведения из теории функций и МО, как, например, теория аппроксимации МО, конусы возможных направлений, конусы Були-гана.

Основным моментом излагаемой теории является разработка новых аппроксимационных и оптимизационных методов как первого, так и второго порядков.

В третьем параграфе главы 1 для произвольной локально липши-цевой функции / : R™ —► R рассматривается множество r¡(x) кривых г(х, а,д) — х + ад.+ ог(а) , обладающих следующими свойствами

1. ог{а)/а —► +0 при а —>■ +0 равномерно для всех кривых г(-),

2. функция о непрерывно дифференцируема и ее производная о' ограничена вблизи начала координат: существуют констан-

ты с > 0 и üo > 0 одни и те же для всех кривых, что тахт€[о,ао] ||о'(т)|| < с.

3. производная V/ существует почти всюду (ПВ) вдоль кривой г(х,а,д).

Вводится следующее множество векторов

£?/(®o) = {«eRn:3afc,afc-+0)(3<7eS?-1(0)),(3r(xo,-,i) € ф0)),

Г<*к

v= lim aj1 / V/(r(xo,T, g))dr

ак~*+0 JQ

где V/— градиент функции / в точках, где он существует, и интеграл понимается в смысле Лебега. Здесь и далее используются обозначения S7_1(0) и В"(0) для сферы и шара радиуса 1 в п-мерном пространстве с центром в начале координат. Выпуклость множества Df(x) очевидна. Доказывается замкнутость, а также устанавливается связь множества Df(x) и субдифференциала Кларка дсьЦх).

Теорема 1.3.1. Если функция / представима в виде разности выпуклых функций fi(x) и /2(2:) в окрестности точки xq, то Df(xo) = dcbf{x 0).

Приводится пример, доказывающий важность требования представления функции в виде разности выпуклых функций для. выполнения утверждения теоремы.

Для установления более тесной связи множеств Df(x0) и <9cx/(zo) между собой вводится также множество Df(x), которое немного отличается от определения множества Df(x): .

Df(x) = co{v е Rn I (3{ak}, ak -fc +0), (3{/im}, K, 0), 3g e '(0),

3r(x + hm,a,g) = x + hm + ag + oT>m(a) 6 r](x + hm),

]i?2 nakl [ Vf{r(xo + hm,T,g))dT}, ak—>+0,hm-*0 JQ J

где Orjn— равномерно бесконечно малые по г и т. Доказывается замкнутость множества Df(x).

Теорема 1-3.2. Множество Df(x) совпадает с субдифференциалом Кларка дсь}{х)-

Чтобы понять связь между собой множеств Df(x), дмр/(х), Df(x) введем

D{hm}f(x) = со {г; е Rn | (3{ак},ак -к +0),3^ 6 S?"1^),

}, Df(x0) = со Ef(x0),

/•"fc

3r(x+hm,.,g) e r)(x+hm),v = lim o^1 / Vf{r(x+hm,T,g))d,T},

ak-*+0,hm-+0 JQ

где дмр/(х)— субдифференциал Мишеля-Пено функции / в точке х.

Легко можно видеть, что если положить {/im} = 0 для всех т, то D{ilm)f(x) = Df(x), а если положить {hm} ~ {сад} для всех к, то D{hm}J(x) — дмр/(х). Интересно, что другие виды аппроксимаций можно получить, меняя соотношение между последовательностями {hm} и {а*}.

В Теореме 1.3.3 для случая разности двух выпуклых функций устанавливается связь между разностью В.Ф. Демьянова субдифференциалов этих функций в точке х и множеством Df(x).

Множество Df(x) играет важную роль для аппроксимации функции / в окрестности рассматриваемой точки. На основе приведенных ниже теорем формулируются необходимые и при определенных условия достаточные условия оптимальности в точке х € R™ для произвольной локально липшицевой функции / : Мп —► Е как на всем пространстве, так и на выпуклом компактном множестве fi С К™.

Теорема 1.3.4. Для случая равномерной бесконечной малости ог в определении множества г](хо) по г верно следующее равенство f(r(xo,a,9'))-f(xо)= тах

g'^g a .«€i>W у

гег](хо)

а->+0

Также справедливо "двойственное" утверждение, если заменить sup на inf ( Теорема 1.3.5.)

Так, если выполняется включение 0 € int Df(x), то х— локальная точка оптимальности в пространстве К™. Необходимым условием точки минимума на выпуклом компактном множестве П является следующее условие Df(x)f)K+(x,Q) ^ 0, где К(х,С1) — конус касательных направлений к множеству О. в точке х, К+(х)— сопряженный конус. Важно, что'для дифференцируемого случая условия оптимальности превращаются в хорошо известное условие V/, так как в этом случае Df(x) = {V/0г)}.

МО DJ : R™ —у 2К", как субдифференциал Кларка дсь/, также не является непрерывным в метрике Хаусдорфа, поэтому важной для оптимизационных задач является проблема непрерывного расширения таких отображений. Для субдифференциала выпуклой функции / : R™ —► К такая проблема была решена введением е-субдифференциального отображения def, которое не только непрерывно, но и липшицево в метрике Хаусдорфа.

Вводится осубдифференциал для произвольной липшицевой функции / и а > 0.

Daf(x0) = cö{v е Rn I (Эг € Фо)), (Эй е 5ГН0)), v = а"1 £vf(r(x0,r,g))dT}

где со— замыкание выпуклой оболочки.

Теорема 1.4.3. МО Daf непрерывно в метрике Хаусдорфа.

Кроме того, установлено, что МО Daf липшицево в метрике Хаусдорфа (Теорема 1.4.5).

С помощью МО Daf, проблема непрерывного расширения МО Df и дсь! решается следующим образом. По определению положим D0f = Df. Рассмотрим МО А$/ : W1 2R" для любого 6 > 0 :

Dsf{x) = cöU^e[o,i] Dr,f{x).

Теорема 1.4.4. МО D^f есть непрерывное расширение субдифференциала Кларка в метрике Хаусдорфа, если f может быть представлено как разность выпуклых функций.

В параграфе 1.4.3 рассматривается применение непрерывного расширения субдифференциала выпуклой функции с помощью МО Daf для нахождения точки минимума. Развивая эту идею, в параграфе 1.8.5 применяется непрерывное расширение субдифференциала Кларка для нахождения стационарных точек. Автор использовал разработанный ранее пошаговый градиентный метод наискорейшего спуска для равномерных непрерывных расширений субдифференциала Кларка, предварительно показав, что МО Д5/ и есть такой тип отображения.

В параграфе 5 главы 1 рассматривается одно из возможных применений нового метода аппроксимаций, а именно: построение нижних выпуклых аппроксимаций (НВА) для липшицевых функций, которые можно строить в любой, а не только в достаточно малой окрестности рассматриваемой точки. Построение НВА значительно упрощает вид исходной функции, что позволяет ускорить методы локальной и глобальной оптимизации. Необходимость построения НВА возникает также потому, что даже для простых случаев функция Кларка не очень хорошо описывает поведение функции в малой окрестности рассматриваемой точки. Для того, чтобы получить необходимые условия оптимальности, надо строить главные нижние выпуклые аппроксимации (ГНВА) для функции f{x) = f(x)+L || х—хо ||, где /- липшицева с константой L, Xq— точка, в малой окрестности которой строится аппроксимация. Геометрически график ГНВА подпирает снизу график

функции Указанный подход оказывается удобным для неквазидиф-ференцируемых функций или для функций, для которых построить субдифференциал или супердифференциал очень сложно.

Нахождение ГНВА в окрестности точки хо

1. Построим множество для любого д е. 5"_1(0)

ВД*о) = Мд) е К" : 3{а,}, ак - +0,

(Зг{х0,-,д) е ф0)),у(9) = а^1 / У/(г(х0,т,д))йт }.

2. Находим множество А — со{-ш в | (ги,д) < [и(д),д) Уу(д) €

Ед!ЫУд € ягЧо)}.

Множество А не пусто, поскольку 0 € А. В окрестности точки хо функцию / аппроксимируем разностью двух выпуклых функций к(х0,д) = и Ь || д ||, где А = дЦхо,0), д = х - х0.

Пару множеств (д!г(хо,0),ЬВ11 (0)) будем называть квазидифференциалом ГНВА функции / в точке х0.

Далее определяются правила построения ГНВА для суммы лип-шицевых функций (Теорема 1.6.1), произведения (Теорема 1.6.2), а также для произвольной гладкой комбинации липшицевых функций.

Теорема 1.6.3. Пусть : Кп —> К, г € 1 : п, - липшицевы с константой Ь, дифференцируемые по направлениям функции, а ИЗГИБА для функции /¿(х) = /¿(х) + Ь Ц х - Хо ||, г € 1 : к. Пусть тако/се Р(д1,?2: К* —► К. — произвольная гладкая функция от переменных д^г € 1 : к. Будем считать, что дF(q0)/дqi > 0, где = /»(^о), г € 1 : к, д0 = (яю,<120>—,Яко)- Тогда квазидифференциал ГНВА для функции /(х) = ^(/^х),/2(х),..., Д(х)) в точке. х0 есть пара множеств {А,В), где А, В с К™, В = 0),

¿2 = (Е< №)/%)£ :

А = дГ(до)/дд1дк1(0) + дГ(д0)/дд2дН2СО) + • • • + дГ( до)/ддкд}гк(0).

В Следствии 1.6.2 отмечается о несущественности предположения насчет положительности производных Р^ю, <72<ъ • • •, Чт)/Ч1 > 0, г 6 1 : к, и показывается, как получить результат в общем случае.

Теоремы 1.6.4 и 1.6.5 формулируют правила построения ГНВА для негладких операций тах и тт от произвольного конечного числа липшицевых дифференцируемых по направлениям функций.

В параграфе 1.7 вводится субдифференциал Кларка для произвольного локально лишицевого МО G : Rn —► 2®m, т.е. для любых Xi,X2 6 Rn : Ph{G{xi), G(x2)) < L || Xi — x2 ||, для чего первоначально доказывается, что опорная функция почти всюду (ПВ) дифференцируема на множестве R" х 5™(0) (Теорема 1.7.1). Рассмотрим множества

М(х, g) = со {л € Rmx" I Э{(£*, ?*)} е N : А = Ит p^fa, дк), (&, дк) (х, ?)},

М(х) = со Uî65r-i(0) М{х, q). Аналогично функции Кларка введем функцию

, . рс(х + и + ад,е)-ра(х + и,в)

ф{х, д, q) = lim sup | —5- | .

a-t+O a

Теорема 1.7.2. Верно равенство

i>(x,9,q) = max (Лд,д).

А€М(х)

Как показано в Теореме 1.7.3 , МО Е : R™ —2а™, ставящее каждой точке х множество матриц М(х), обладает всеми свойствами субдифференциала Кларка. Поэтому М(х) назовем субдифференциалом Кларка МО G в точке х. Отсюда и из Теоремы 1.4.5 следует, что все сказанное выше верно для МО Daf, т.е. функция

PD*(x,q)= maх M

v€Daf(x)

ПВ в пространстве R" х R™ имеет вторую смешанную производную и Il Pxq{x>Q) \\<La,

где Ьа

константа Липшица МО Daf.

Для МО Daf в параграфе 1.8.1 строится субдифференциал Клар-

2

ка. Определяется МО £>г,а/ : Rn —> 2Ж" с образами

D2,af(x) = со {А[п х п] | 3{ат},ат +0,3$,? € S?-1(0),3(ri(a:m,-,ff), г2 „(•,?)) £т(хт),хт -*т х,А = Ишт_юо a"1 J Pxqi.ri(xm,T,g),r2m(r,q))dT},

Jo

где г]2(хт)- множество всех пар кривых (г^ж^, ■,g),r2m{-, <?)) для для всех g,q е R": ri(xm,a,g) - xm + ад + olm(a),r2m(a,q) = q + 02m(a), удовлетворяющих всем свойствам кривых множества rj(xm) (Определение 1.3.1), и вдоль которых матрицы p"q(-,-) существуют ПВ для

а € (О,ао],ао > 0. Показывается, что множество Д2,а/(х) обладает всеми свойствами субдифференциала Кларка, т.е. оно выпукло, замкнуто и полунепрерывно сверху (П.СВ).

Теорема 1.8.1. Множество М{х), построенное для МО Д*/, совпадает с В2га/(х), или, иначе говоря, 021а/(х) есть субдифференциал Кларка МО Оа/ в точке х.

Произвольную матрицу из множества Оа/(х) назовем а-обобщенной матрицей функции /, которая в общем случае не есть непрерывная матрица от х. Для построения численных методов надо использовать ее непрерывное расширение.

Для произвольных а, 5 > 0 введем следующее множество

= сд{А[п х п] | Зд, д 6 Э(гх(а;, •, д), г2(г, д)) 6 щ(х),

А = 6~1 [ р1я(г1(х,т,д),г2{т,д))с1т}, J о

где р— опорная функция для МО Ва/ . Элементы множества Дг,а,бЦх) будем называть а, 6 - обобщенными матрицами. Показывается, что МО Д,<*,г/ непрерывно в метрике Хаусдорфа и имеет выпуклые, замкнутые, ограниченные образы (Теорема 1.8.2). Также установлено другое важное свойство этого отображения.

Теорема 1.8.3. Дг.а.г/ есть липшицево МО.

' ' _ 2

При некотором допущении МО Дг,а,г/ '■ К™ —2К" , определяемое по правилу

1>2,а,б}{х) = С0 им€[0,г] В2,а^(х),

есть непрерывное расширение МО 02:О/-

Теорема 1.8.4. МО £>2,<*,<$/ есть непрерывное МО в точке х, если Дг,а, о!(х) = 02<а/(х).

Для применения изложенной выше теории важно уметь вычислять матрицу рхг, для отображения Оа/, что делается в параграфе 1.8.3. Нахождение рхд осуществляется в несколько этапов.

1. Функция /— дважды непрерывно дифференцируема, т.е./ е С2ф). Тогда р''ч{хА) = = ¡0а^/(г(х,т,д))с1г, где кривая г(х,-,д) удовлетворяет условию, что вектор у(х,д) = оГ1 У/(г(х, г, д))(1т есть экстремальный с нормальным вектором q, причем Чяр{х,д) = и(х,д).

2. Функция / есть кусочно дважды непрерывно дифференцируе-' мая. Тогда

р1ч{х, д) = а-1 £ У2/(Ф, г, д)), ¿г + а"1 £(>Дг(х, & + 0,9))-

-v/(r(*,6-olff))).(Mfl II2),

где & (или т(х,&,д)) есть точки на кривой г{х,-,д), в которых функция Vf(r(x,-,g) разрывная и имеет скачок V/(r(x,£; + 0,<?)) — 0,fiO), д- вектор, равный д = (г(х,а,д)-х)/ (|| г(х,а,д)~ х || cosß),ß— угол между векторами д и д, последний из которых соединяет точки х и г(х, а, <?), и операция а • Ь— матричное умножение вектора-столбца а на вектор-строку Ь.

3. Функция 4f{r(x,-,g)) : R™ R" кусочно-непрерывна на кривой г(х,.,д). Разделим отрезок [0,а] на конечное или счетное число интервалов (aj,ai+i), , где функция f(r(x,-,g)) непрерывна. В этом случае

г4',(х, д) = V^a"1 J2 (V/(r(*, - 0,д)) - Vf(r(x, сц + 0, g))))+ i

£ (V/(r(x, <4 + 0,5)) - V/(r(z, Qi - 0l5))) . (д/ || g ||2), i

Заметим, что приведенную выше формулу можно переписать в виде

я) = а-1 vä( (V/(r(x, а-0, д)) - V/(r(*, +0, д))) - ]T(V/(r(z, + °< я))~

i

-V/CrCx^-O.g^Ha--1 ^(V/(r(i,ai + 0,5))-V/(r(x,<*-0,9))).(g/ j| § ||2). i

Формулой можно воспользоваться, если сумма и предельные значения для точек cti, расположенных в возрастающем порядке, существуют. Эти требования могут не выполняться для произвольной липши-цевой функции. Справедлива следующая теорема.

Теорема 1.8.5. Для любой функции f : Rn —»• R, представимой в виде разности выпуклых функций в окрестности точки х, вторая смешанная производная для опорной функции МО Daf задается формулой для p'xq{x, q).

Если функция / представима в виде разности выпуклых функций, то существуют кривые r(x,-,g), для которых указанные суммы и предельные значения для точек г существуют. Приводятся примеры расчета матрицы p"q .

В параграфе 1.8.4. описывается оптимизационный метод для лип-шицевых функций с использованием обобщенных матриц для нахождения a-стационарных точек и доказывается его сверхлинейная скорость сходимости. Сложность применения алгоритма заключается в

трудоемкости вычисления в общем случае обобщенных матриц. Ниже предложен интегральный способ аппроксимации, в результате которого получаем дважды дифференцируемые функции, вычислить которые несложно и к которым применимы методы второго порядка.

В параграфе 1.8.5 дана равномерная аппроксимация субдифференциала Кларка и метод, разработанный Полаком, Майне и Вар-ди для нахождения стационарной точки для субдифференциального отображения Кларка, использующий такой способ аппроксимации.

Глава 2 посвящена аппроксимации липшицевых выпуклозначных многозначных отображений (МО) и нахождению производных по направлению маргинальных функций. Введенные понятия являются обобщением соответствуютцих понятий для функций. Рассматриваются:

1. Конус возможных направлений, введенный В. Ф. Демьяновым и А. В. Певным

-у(х, д, v) = € Rm | 3a0 > 0 : y+aw 6 G{x+ag) Va e [0, a0]}, T(i, g, v) = j(x, g, v),

где черта есть замыкание множества.

2. Конус касательных направлений:

Г'(х, д, v) = {ш е Rm I За0 > 0, г; + aw + ol(а) € G(x + ад + о2(а)) Va € [0, а0]}

для некоторых бесконечно малых функций 01,02. Заметим, что для липшицевых МО, т.е. для которых pn{G(x\)) G(z2)) L II xi ~ x2 II Vxi,x2 6 R", где рн~ метрика Хаусдорфа, можно ограничиться только одной функцией Oj, г = 1,2.

3. Конус допустимых направлений (конус Булигана)

= со е Rm I 3{afc},afc ->fc +0,2/+a^+oi(afc) € G{x+akg+o2(ak)) Vfc}.

Ясно, что всегда Г(:е, <?,г;) С Г'(x,g,v) С Г(x,g,v).

Многозначными отображениями стали описывать многие технические и экономические модели. Это объясняется тем, что на сто неизвестно точное решение системы или значение функции. В оптимизации потребность изучения МО объясняется тем, что для негладких функций не существует градиента в какой-то точке, а существует целое множество обобщенных градиентов.

Вводится понятие аппроксимации МО относительно произвольного множества В. (Определение 2.2.1). Если два МО допускают аппроксимацию относительно некоторого множества В, то их сумма и

разность также допускает аппроксимацию относительно того же множества В. В параграфе 2.3 выводится формула для конусов возможных направлений для суммы и пересечения МО. Пусть заданы МО с выпуклыми компактными образами: : Е" 2®т,г € 1 : 3,

в3(х) = С,(х)+С2(х) = € Кт | у3 = «1-Н* V«! € в^х), \/ь2 € в2(х)}.

Зафиксируем произвольные х, д е Жп. Обозначим через д, V.) множества возможных направлений МО Gi в точках у^уг е С{(х), по направлению д соответственно. Предположим, что отображения С{,г = 1,2, допускают аппроксимацию первого порядка в точках ь\ по направлению д относительно множеств Г»(сс, дг, и») соответственно. Пусть У(х,у3) = {(VI,у2) | VI е Сг(х),у2 € С2(х),+ у2 = и3}.

Верна теорема.

Теорема 2.3.1. Справедливо равенство

Гз(х,д,р3) = и(щ1„2)еу(х,*г) (ГЛх,д, + Г2(х,д,у2)).

Показано, что для МО, заданных в виде системы неравенств вида

<34(х) = {у € ЕГ | Нц{х,ь) < 0 Уз е 1: * = 1,2,

где функции /г^ непрерывны по совокупности аргументов х и V, выпуклы по у, производные дНц(х,у)/дд, дк^(х,у)/ду непрерывны по I и с и ииС^х) ф 0 (условие Слейтера), замыкание в Теореме 2.3.1, можно убрать (Теорема 2.3.2). Для МО Сз с образами С3(х) = (^(х) П С2(х) верно утверждение. ■

Теорема 2.3.3.Для любого у £ С?3(х) верно равенство Ых,д,у) = Гз(х,д,у)Г\Т2(х,д,у).

В Замечании 2.3.1 отмечается, что Теоремы 2.3.1-2.3.3 верны для конусов касательных направлений, если МО С;, г = 1,2, допускают аппроксимацию первого порядка относительно Т'(х,д,у) в точке у по направлению д.

В параграфе 7 главы 1 было доказано, что для липшицевого МО опорная функция р(х, д) имеет ПВ в Е" х Ет вторую смешанную производную р"д. В параграфе 2.4. находится вид матрицы р"ч для двух часто встречающихся видов МО: выпуклой оболочки конечного числа вектор-функций и МО, заданного в виде системы неравенств

б(х) = {у 6 Кт | Ы(х,у) <.0 V» 6 1 : /},

где Лг : К" х Кт —► Е, г е 1 : /,— непрерывно дифференцируемые, сильно выпуклые по у функции с непрерывными по х и у производными второго порядка:

д2Ы(х,у) д2Ы(х,у) дхду ' ду2

Нахождение вида р"Г1(х, д) важно для доказательства кодиффе-ренцируемости функции экстремума по МО и нахождения вида ее кодифференциала. Так для указанного МО С матрица рхч имеет вид

„ ,д21г{х,у(х)) ^_хд2к{х,у{х))

Р^Х'У>- ду2 > дхду '

где у(х) — у{х,д) - граничный вектор множества С(х) с нормалью д е £Г-1(0)> если индекс г(д), для которого Н^{х,у(х)) — 0, единственен. Если существуют т индексов, для которых Ъ(х,у(х)) = 0,г € 1 : т, то

¿у{х, д) = /дЫ(х,у)у1 /дЫ(х,у)\ (¿Г V йу / г€1:ттг V (¿Г /гё1:ш' дЫ(х, у)

при условии, что векторы--для г € 1 : т линейно независимы.

ау

Для маргинальных функций, максимума или минимума по МО или выпуклой оболочки конечного числа вектор-функций находится вид кодифференциала. Так, например, для функции ф{х) = тахуеа(х) <р(х, у) доказывается, что она гиподифференцируема и ее кодифференциал есть Оф(х) = \фр{х), 0„+1], где

¿ф(х) = {(а,и) | о е А{х), V е У(х)},

т+1

А(х) = со{ф, £ ац/(х,д,))-Мх) | а< € В?*1,* 6 ЯГ'ДО}.

1=1

К(х) = со 2_, <цу(х, «?,))-((^ а4(-^-) -дхду ) •

т+1

<^(х, ацу(*,®))) | 04 6 Ъ € л 6 1 : /,» € 1 : (т+1)}.

т+1

Нф,у(х,Я*)) = О, ВГ+1 = {<* I 0 < а( < 1, £ а4 = 1}. '

1

В этом случае функция гр может быть представлена в виде ■ф(х + Ах) = гр(х) + тах [а + (у, Д)] + о(|| Д ||).

Аналогичное справедливо для функции min по МО G. Доказывается, что она гипердифференцируема.

В параграфе 2.5. введено определение аппроксимации липшице-вого выпуклозначного МО G : R™ -> 2К" относительно другого МО, например, относительно конуса допустимых направлений Г, который был введен в параграфе 1 главы 2. Приведен вид Г.

Для произвольных и € G(x),x,g G Rn, введем множество

п/_ „ ,л_ / {^еЕ1т|(«.',9)<тахАбВ(х,«)Ир,?) 4q&P(x,v)}, если Р(х, v) ф 0, Щх, 9, V) - | R™ если ^ =

где

т+1 т+1 т+1

B{x,v) = со {А[гп х п] | А = Y, ßiA{vt),v= £ frvi, ^ ft = 1, ßi > 0,¿fa) = t=i «=i >=i

= lim ^(x.(e),<fl(e))1(x<(a),e(a))€«(G)},B(a:i(e),«(a)) = {f74(a)>1

«•(a)-77*1

+o

Xi(a) =x + ag + Oi(a),qi(a) e P(xi(a),Vi(a)),Vi(a)

a-t+O

Oi(a)/a-0, qi(a)-q, || ®(a) - q || /а < c,

a—++0 a—»+0

а также

R{xi{a),qi{a)) = {ye G(Xi(a)) | (y,®(a)) = max (u,®(a))},

ueG(xi(a))

P(x,v) = {q€ S?-\0) I (v,q) = max (y,g)},

y€G(i)

— всюду плотное множество в Rn х Rm, где существуют p"q. Здесь Гг(а) = (а;»(а),5»(а))- непрерывно дифференцируемые по о кривые, вдоль которых ПВ существуют р^ с предельными значениями при а +0, с— некоторая константа. Далее будем считать, что В{х,д,у)фЪ.

Показывается, что для липшицевого МО множество Г всегда не пусто (Теорема 2.5.1) и f(x,g,v) С B(x,g,v)(Лемма 2.5.1), а если B(x,g,v) ф 0, то T'(x,g,v) не пусто и T'(x,g,v) = Г(x,g,v) = B(x,g,v) (Теорема 2.5.3). При условии непустоты множеств T(x,g,v) и B(x,g,v) для V G G(x) и J £ 1™ верно равенство T(x,g,v) — B(x,g,v)(Теорема 2.5.4). Также доказывается, что МО G допускает аппроксимацию первого порядка в точке v € G(x) по направлению д € R" относительно множества V(x,g,v) , если B(x,g,v) ф 0 (Теорема 2.5.5).

Для часто встречаемого случая задания МО в виде G(x) = {у € Rm | hi(x,y) <0 г € 1 : I}, при условиях, наложенных выше на функции hi, г 6 1 : и В(х, и) 0, имеем

Пх,д,у)=Г'(х,д,у) = Г(х,д,у) = { Жт,еатР(х,у) =0,

где R{x,y) = {г 6 1 :11 /ц(ж,г/) = 0}.

В параграфе 2.6. изучаются маргинальные функции и осуществляется вывод производной по направлению маргинальной функции. Идею перехода от предельных значений градиентов к усредненным значениям интегралов вдоль кривых из ц{х) можно развить дальше. Для этого перейдем к рассмотрению аппроксимации функции /(х) = тахуес(х) <р(х,у), где х G(x) : Rn —► 2хт— выпуклозначное МО с выпуклыми компактными образами и с константой Липшица L. Функция <р непрерывна вместе с производными ip'x, >р'у по совокупности переменных. Условия дифференцируемости функции / по направлениям подробно изучались В.Ф. Демьяновым, A.B. Певным, Б.Н. Пшеничным, Л.И. Минченко, О.Ф. Борисенко и др. Эти условия можно ослабить, что и сделано далее.

Обозначим R{x) = {у £ G(x) \ f(x) = <р(х.у)}. Для произвольных V £ G(x),x,g е Rn, введем множество

_/ {™eRm I Kg) <maxAeAf(l|U)(A^,9) Vq € P(x,v)}, если P(x, v) ф 0, tfti.^t/j ~ \ Em, если P(x,v) = 0,

где

m+1 m+1 ro+1

M{x,v) = со {A[m x n] | А = ßiA(vitq),v = ^ ß{ = > 0,

i=l >=1 ¡=1

A(Vi, q) = lim оГ1 [ i4',(zi(T), 9i(r))dr }, ,Л(х4(г), ®(т)) = {«,(r)}, а—+0 Jo

и (а) = г + ар + 0<(а),ф(а) €P(ii(a),Ui(a)), (i<(r), ф(г)) 6 N(G),

-?> -II <?•(<*) ~ 9 II /а < с.

а—*+0 а—

Остальные обозначения такие же, как и выше. Далее будем считать, что B(x,g,v) ф 0 для любого q € P(x,v) и любого v € G(x).

Теорема 2.6.1. При сделанном предположении относительно B(x,g,v) множество Г'(x,g,v) ф 0 и T'(x,g,v) = Г(х,<?,и) = B(x,g,v), а если T{x,g,v) ф 0, то Г(x,g,v) = B(x,g,v).

Остальная часть параграфа посвящена нахождению производной функции /.

Теорема 2.6.2. Если В(х,д,у) ^ 0 для всех V € Я(х), а также существуют непрерывные производные <р'х, <р'у по совокупности переменных, то функция / дифференцируема в точке £ € К"по направлению д б!" и верно равенство

3/(х)

= max

max \{<p'x{x,y),g) + (<p'y(x,g),w)} =

dg

= max max \{ф*(х,у),д) + {ч>'у{х,у),А(х,у)д)\.

Для МО G , заданного в виде системы неравенств (см. выше), производную по направлению функции / можно записать в явном виде:

<9 f(x)

—т—= max max [(<р'х{х,у),д) + iA*ix,y)ip'ix,y),g)},

од y€R(x) i€H(®,y)

где

В параграфе 2.7 речь идет о нижних выпуклых аппроксимациях маргинальных функций вида

fix) = тех ф,у),

y£G(z)

где \р— липшицева с константой Li по совокупности переменных, G— вынуклозначное липшицевое МО с константой Липшица L. В Лемме 2.7.1 доказывается липшицевость функции / с константой L\(\ + L). Для построения главной нижней выпуклой аппроксимации (ГНВА) функции / в окрестности точки х0 рассматривается функция

f(x) = f(x) + Li(l + L) || ж - io || •

Образуем множество для

любого д € £?-1(0)

Dj(xо) = {z(g) 6 R" I 3{at}, ak - +0, A(g) = lim a^1 / р'^г(х(т), q{r)))dr,

если <p'y(xo,y) ф 0; A(g) =0тхп,если <р'у(хц,у) = Q;z(g) = !р'х(х0,у)+А*(g)<p'v(x0,y')+ +L1(l+L)V%),0(z-xo) =|| x-xo II, у € Rixo), r(i(r),9(r)) e N(G) п.в. для г <= 6 [0, öo],x(r) = xo+rg+oiir), g(r) = ^х0+тд+о^т), у+о2(т)), о<(г)/т -»т_+0 0}, где N(G) — множество, всюду плотное в R° х Rm, где существуют матрицы р"Х1v *- знак транспонирования ( глава 1, параграф 1.7). Здесь кривая г (а) = {x{a),q{a)), х{а) = xo+ag+Oiia), д(а) = tfy{xo+ ag + 0iia),y + 02ia)), у £ Rix о), удовлетворяет следующим условиям:

1. Вдоль г ПВ существуют производные р'Ц.

2. Интегральное выражение в определении £>д/(хо) существует.

3. о*, г = 1,2— непрерывно дифференцируемые бесконечно малые функции.

Построим множество В, аналитически задаваемое следующим образом:

В = со{Ш 6 К" | (ю,д) < Ш,9) Мз) е А,/Ы, Чд 6 ЗГ^О)}.

Очевидно, что множество В всегда не пусто, так как 0 € В. Определим функцию д Ь,(ха,д) : Е™ —>• Е : К(х0,д) = тах„€в (и, д). Функция Ь(х0, ■)— выпуклая ПО степени 1 и дН(х0,0) = В.

Теорема 2.7.1. Функция к(хо,-) является ГНВА функции / в окрестности точки хо.

Условие минимума функции / на Е™ задается следующей теоремой.

Теорема 2Л.2.Для того чтобы точка хо была точкой минимума функции / : Ен —> Е на Еп, необходимо выполнение включения Ьх(1 + 0) С дк(хо,0), а при строгом включении оно является и достаточным условием минимума.

Далее в том же параграфе изучается задача минимизации функции / на множестве

П = {г е Ета | ВД < 0 Чг € 1 : /}, ■

где функции Ы : Е" —► Е— липшицевы с константой Ь, дифференцируемы по направлениям. Будем считать, что выполнено условие невырожденности для всех х0 £ П. В этом случае вместо функции / рассматривается функция

7/ \ _ / /(х) + Ь\\х-хй ||, если х € ~ | ¡{х0) + Ь || х-хо ||,если х £ П,

где Ь > Ь. Определяется ГНВА для функции / в виде функции Кхо, д) — тах„€с (и, д), где множество С строится аналогично описанному выше алгоритму. Следующая теорема задает условия минимума функции / на множестве П.

Теорема 2.7.3. Для того чтобы точка хо была точкой минимума функции / на П, необходимо, чтобы ЬВ±(0) С дй(хо,0). Если

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

В параграфе 2.8 обсуждаются дифференциальные свойства маргинальной функции вида f[x) = maxy€G(i) <р{х,у), где <р, <р'х, <р'у-непрерывные функции по совокупности переменных, G : Rn —> Rm— липшицево МО. Через N(G) обозначим множество точек в Rn х Rm, где существуют^. Известно (Теорема 1.7.1), что N(G) всюду плотно вГх Rm. Определим множества

= (2/ 6 G(x) |р(х,?) = (У,Я)}, Д(*) = {у € G(s) | /(х) = v(x,y)},A(x,y,q) =

= со {А[т х п] I А(х, у, g) = ton.^^, ft), ft = ft + o(||sj - x||), ii—4

ft = tp'y{xi,yi)/ II ^(Xj.j/i) II, (Xi,ft) € N{G),Vi € R{xi,qt),yi y,y 6 й(х)}, если Ф °> Л-(х,2лд) = {°mxn}, если = 0.

Теорема 2.8.1. Субдифференциал Кларка функции f в точке удовлетворяет соотношению

dCbf{x) = со{<р'х{х,у) + A*{x,y,q)y'y{x,y) | A(x,y,q) € A{x,y,q),

у 6 R(x), q = <р'у(х>У)/ II <р'уМ II Wy{x,v) Ф 0)},

В Следствии 2.8.1 задано более простое правило получения предельных матриц, участвующих в формулировке Теоремы 2.8.1, используя которое получаем включение для субдифференциала Кларка. Введем множество

В{х, q) = со {В[т х п] | Б(х, q) = lim p"q{xi,qi), [хи q{) € N{G)},

если ч?'у(х,у) Ф 0, B(x,q) - {0[mxn]}, если <р'у(х,у) = 0, у € R{x). Следствие 2.8.1. Верно включение

дсьЦх) С соШх,у) + B*{x,q)<p'y(x,y) \ B{x,q) € B(x,q),

у 6 ВД, g = у'у{хЛ,)/ || <р'у(х,у) || &'у(х,у) ф 0)}.

Результаты параграфа 2.8 важны для нахождения стационарных точек субдифферентщарла Кларка маргинальных функций указанного типа. Можно развивать теорию в указанном направлении для более сложных видов маргинальных функций.

В параграфе 2.9 рассматриваются выпуклые коэрцитивные функции / : Rn —> R, для которых выполняется предельное соотношение

/(*)

Tii-* 00' И находитс,я вид конуса возможных направлений

Г(x,g,v) для е— субдифференциала

dtf(x) = {и е R" I f(z) - f(x) >(v,z-x)-sVze Ж"}

таких функций. Пусть г, и) = /(а;) — /(z) + (и, z — а:) — Введем множества Q{x,v) = {z е £>я(:го) | h(x,z,v) = 0},

В(х a v) — I еСЛИ =

1 j 1 {weR"| (ш, 2Г - - (и, + < О 4zeQ{x,v)}.

Лемма 2.9.3. Если х е intB™(xо), то Г(x,g,v) = B(xsg,v). Можно переписать в ином виде множество Г(х, д, v), а именно для граничной точки v G dcf(x) имеем

Г(х, д, v) = {vj € Rn I К 9) < ¿у К», Я)-Щ~] Vg € Р(х, v), Мя) € ©(х, v,q)}, где

e(I|t,l9) = (а > о I /(' + «0-/(')+* = ^ /(* + ft)-/(*)H-*}

а /з>о /? J

и

P(x,r;) = {ieR"|||9||=l)^ = (t;ig)}.

Если V е int 9£/(х), то Q(a;,u) = 0 и Г(х,5,г>) = R™.

Воспользовавшись предыдущими результатами, можно получить формулу для производной по направлению д функции <р(х) ~ таxvedef(z) [- II v ||2]. Пусть 0 $ d£f(x), т.е. ip(x) < 0. Множество R(x) — {^о HI vo ||= min„e0£/(i) || v ||} состоит из единственной точки vq. Из полученных результатов окончательно имеем следующую ßiß(x)

формулу —^— = sup [—2(и0,гу)], откуда после некоторых преобразований можно получить направление до наискорейшего спуска 9о = || _ ||, где || vq - V ||= xrnnv<z9f(x) ¡I vo - v. II, v € df(x).

•Направление до имеет ясный геометрический смысл, и его можно использовать для нахождения точки минимума функции /.

d£f{x)

Далее исследуется функция <рг(х) = —= max (и, г), где г €

ОТ v€dcf(x)

Rn. Если / не имеет линейных участков, то

—7г—= sup sup (г,ш)= sup — (V|i)-—— ,

vg v€R(x,r) w€VT{x,g,v) v€R(x,r) Ot{r) L Og J

где Я(х,г) = Ег(х) = {иё д£/(х) \ {у,г) = £^ }. Для г = д получим

= д<р>(х) = 1 тдМ д/(х)1 дд2 8д а{д) [ дд дд У

Так как а(д) —► 0 при е —+ +0, то при условии, что функция / дифференцируема в точке х + а(д)д, справедливо предельное соотношение д2 ¡(х)/дд2 -> д2 ¡{х)/дд2, если функция / имеет вторую производную по направлению д в точке х.

В главе 3 развивается новый нелокальный способ аппроксимации негладких функций, в результате которого получаем дважды дифференцируемые функции, сохраняющие е{П) - стационарные точки. С помощью таких функций можно строить методы оптимизации второго порядка, сходящиеся к е(1)) - стационарным точкам. Описан алгоритм оптимизации, сходящийся к стационарной точке липшице-вой функции / со сверхлинейной скоростью, т.е. имеющий скорость сходимости более быструю, чем любая геометрическая прогрессия.

Пусть / : Еп —► К— липшицева с константой Ь функция, и х„— ее точка локального минимума(максимума) в Е™. Возьмем произвольное выпуклое компактное множество О С К". Введем определение стационарной точки.

Определение 3.1. Точку х* назовем е(О) стационарной точкой функции /, если множеству х£ + Б принадлежит стационарная точка функции /.

Если функция /— сильно выпуклая, то данное определение хорошо согласуется с определением е(£>) - стационарной точкой для выпуклой функции. Доказана следующая теорема.

Теорема 3.1. Для произвольной липшицевой функции / : К™ —* К функция

где Б — произвольная область в Мп,0 € гпмера области О, ц(О) > 0, есть непрерывно дифференцируемая функция с производной

Замечание 3.1. Интеграл здесь понимается в лебеговом смысле. Производная берется в точках, где она существует. Общеизвестные правила дифференцирования под знаком интеграла в данном случае не выполняются (подинтегральная функция недифференцируе-

ма). Поэтому применить дифференцирование под знаком интеграла без дополнительного обоснования нельзя.

Функция наряду с новыми свойствами также сохраняют некоторые важные свойства функции / .

Теорема 3.2. Если /— конечная выпуклая функция в К", то <р— также конечная выпуклая е 1".

Также верна теорема.

Теорема 3.3. Если / липшицевая функция в К™, то <р'— липши-цевая с константой Липшица Ь, зависяшей от О.

Поскольку функция липшицевая, то ПВ дифференцируемая в К™.

Теорема 3.4. Для функции <р, определенной выше, функция

имеет липшицевую с константой V вторую производную.

Замечание 3.2. Интегрирование функции кр" понимается в лебеговом смысле. В случае шара и куба коэффициент Липшица Ь зависит от области Б как 1/й, а Ь'— как 1/сР, где й- диаметр множества Б.

Доказана важная теорема для построения ускоренных методов минимизации.

Теорема 3.5. Все стационарные точки функции <р являются е{Б) - стационарными точками функции /.

Для нахождения е(2О) стационарных точек функции / следует применять методы второго порядка к функции ф.

Замечание 3.4. Для поиска стационарных точек функции / мы должны в процессе поиска е(2£>) - стационарных точек уменьшать диаметр множества И. Для обеспечения высокой скорости сходимости надо уменьшать диаметр множества О согласованно с уменьшением шага оптимизационного процесса.

Метод поиска е(2Ю) - стационарной точки функции

Рассмотрим функцию ф : у € К™ К, ф(у,х) = ф(у) + 2Ь\\у - х||2, для у € Еп. Для функции ф верно неравенство

Ц\г\\2 < (Ч2ф{х,х)г,г) < ЗЬ\\г\\2 Чг е Кп,

где У2ф(-,х) = ф"(-,х)—матрица вторых производных функции ф(-, х) по переменной у. Ясно, что Чф(х, х) = Чф(х). Пусть точка на к - ом

шаге уже построена. Построим точку Хк+1- Положим по определению фк — Ф{',%к), т.е. функция фк равняется функции ф при фиксированном Хк-

1. Вычисляем Ль = -{^2фк{хк))~1^фк(хк)-

2. Находим такое целое неотрицательное число 1к, для которого фк(хк + 2~1*Ак) < фк(хк) - 2~2Ц ||2 .

3.Полагаем Хк+г = хк + 2~1кАк, к—к + 1 и переходим к операции

1. ,

Теорема 3.6. Последовательность {хк}, построенная согласно алгоритму 1 — 3, сходится к единственной стационарной точке х* функции ф. Для больших к верна следующая оценка для скорости сходимости метода: Цх^ — х»|| < 1^(Дй)||х1 — х*||, где 0;

когда ЦД^Ц 0.

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

Одним из эффективных методов решения некорректных задач типа

./(и) = 7(х(Г,и),и(Г)) —т^у,

где <7— полунепрерывный снизу функционал на множестве II в банаховом пространстве, является метод регуляризации, разработанный А.Н. Тихоновым и его учениками. При пользовании этим методом нужно найти стабилизатор, выбор которого зависит от пространства, в котором ищется глобальный минимум или максимум.

Пусть таким стабилизатором является функция П, определенная на множестве [¡п. Далее берется какая-либо положительная последовательность {ат}, сходящаяся к нулю, и при каждом т = 1,2,3,...

на множестве С/п определяется функция

Ф(и) = 3(и) + аП(и) \ZueUn,

которую принято называть функцией Тихонова.

Так в качестве Ф(и) для и € II С /^[0,1] на множестве кусочно-непрерывно-дифференцируемых функций может быть взята тихоновская функция

Ф(м) = 7(и) и{Ь).

Добавление к исходной функции 3 слагаемого аО. делает задачу минимизации функции Ф более "устойчивой" по аргументу. Поэтому часто метод Тихонова называют методом стабилизации.

Задача минимизации Ф решается в конечномерном пространстве по переменным а и для кусочно непрерывно-дифференцируемой вектор-функции и с конечным числом точек переключения с использованием методов глобальной оптимизации, основанных на применении решения уравнения теплопроводности либо уравнения Пуассона с одновременным их овыпуклением (метод овыпукления) по г = {и,а). Метод овыпукления позволяет построить регулярные, т.е. устойчивые методы оптимизации. В диссертации приведены оптимизационные методы и результаты численных экспериментов.

Предлагается использовать нижнюю выпуклую аппроксимацию функции <7, что обеспечивает большую устойчивость и улучшение сходимости процесса к множеству оптимальных решений 17«. Оптимизация функционала, получающегося в результате построения нижней выпуклой аппроксимации, обеспечивает его полунепрерывность снизу и упрощает процедуру регуляризации по параметру а.

Задача поиска глобального минимума (максимума) функционала на заданном компакте сводится к задаче нахождения глобального минимума (максимума) решения уравнения теплопроводности или уравнения Пуассона. Причем можно так изменить оптимизируемый функционал, не изменив точку глобального минимума (максимума), чтобы решение уравнения теплопроводности или уравнения Пуассона было выпуклым (вогнутым) по пространственному аргументу (метод овыпукления). Для уравнения теплопроводности определяется правило изменения времени 4 —»■ +0, чтобы решение оставалось выпуклым (вогнутым) по аргументу в малой окрестности точки оптимума. Используя оптимизационные методы второго порядка, можно строить оптимизационный процесс со сверхлинейной скоростью сходимости.

Для поиска глобального минимума непрерывного по и функционала 3 на множестве кусочно-непрерывно-дифференцируемых функций и с конечным числом точек переключения применяется видоизмененное уравнение Пуассона

Аф) = ¥(г), Цг) = \ ™ах(°>с- *(*» + 1. если 2 € 0-к ' 4 ' [0, если г £ Э,

где с = /0 Ф{г)р{г)(1г, /3 — малый положительный параметр. р— плотность распределения случайного вектора Z е 0 , 0— область, в которой производится поиск. Функция ¡р является гладкой дважды дифференцируемой функцией с матрицей вторых смешанных производных \72у(2) > вид которой в удобной для анализа форме получили А. И. Пропой и А. И. Каплинский. Воспользовавшись их результатами, можно получить следующую теорему.

Теорема 4.1. Для малых (3 > 0 и области поиска 0 = -В™ (.г) = {£ в К™ ||| £ —г || < р} существуют такие Ь\{р,р, Ф), Ь2{Р,р, Ф) > О, что для функции <р, являющейся решением написанного выше уравнения Пуассона, верно неравенство

ЬМрЛШ2 < (У1Ж*)9,9) < Ш,РЛ)Ы? Уд е

Также используется уравнение теплопроводности для задач глобальной оптимизации. Решение на к - ом шаге получается из решения уравнения следующего вида

—= а2А<р{г,Ь), <р{г,0) = ткФк(г), г = (и,а) е11кх [-а0,а0] где

Ф*(г) = тах(0, -с^+Ф^^г)), дая к > 1,Ф0(г) = Ф(г), Ф^г) = тах(0, С1-Ф0(г)),

°к - 1с/кх1-аоЫ Фк-1(€)рм-1(0<%, Рк ~ плотность распределения случайного вектора Z £ ик х [—о:0, сю], 11к С II— область поиска на к- ом шаге, г 6 Еп+1.

Теорема 4.2. Для любого г £ и х (—ао,ао) и достаточно малых 2 существуют большие тк> 0, а также положительные числа М\{и х (—ао,ао),£,т*) и М2(С/ х (~ао,ао),1,тк) такие, что верно неравенство

Щ\9\? <1 Ш^д) |< М,\\д\\2 € К"

Если

Ч£еих (-00,00),

то матрица <р"г2(г,{) отрицательно определена.

Теоремы 4.1 и 4.2 дают правило овыпукления решения уравнений Пуассона и теплопроводности, которое надо применять вблизи точки оптимума, что позволяет строить методы оптимизации со сверхлинейной скоростью сходимости вблизи точки оптимума.

Функции, представимые в виде разности выпуклых, находят широкое применение в оптимизации. В пятой главе автор изучает вопрос о представимости произвольной липшицевой функции / с константой Липшица I/ от двух переменных (х, у) —> /(х, у) : П —► К, где Б есть выпуклое открытое ограниченное множество в К2, так что замыкание О — компакт, в виде разности выпуклых функций.

Ранее автор изучал этот вопрос применительно к положительно однородным функциям степени 1 от двух и трех переменных. Доказательство представимости ПО функции двух и трех переменных в виде разности выпуклых построено таким образом, что из него нетрудно получить алгоритм, который можно запрограммировать. Был получен следующий результат.

Следствие 5.1 Положительно однородная функция степени 1 двух переменных { :Ж2 —>Ж представима в виде разности выпуклых функций тогда и только тогда, когда справедливо неравенство

У(Ф';0,2тг) < оо,

где $(4) = /(КО) для I € [0,2?г], г(£)— единичная окружность на плоскости с центром в начале координат. Символ V означает вариацию функции Ф' на отрезке [0,27г].

Переход от одномерного случая к двумерному представляет собой качественный шаг вперед по трудности. Для изучения представимости произвольной липшицевой функции / от двух переменных, определенной на Б, определяется р(-О) - класс кривых на плоскости ХОУ в области £>, ограничивающих выпуклые компактные множества и параметризованные естественным образом, т.е. параметр £ точки М на кривой г равен длине кривой между М и начальной точкой. Обозначим такую кривую как г(£), 4 € [О, ТТ], где Тг— наибольшее значение параметра соответствующее начальной точке. С помощью кривых г е р(В) и функций Ф(£) = /(?-(£)) \/£ 6 [О, Тг] записываются

условия представимости функции / в виде разности выпуклых функций. Дается геометрическая трактовка этих условий, через поворот кривых Д(г) = (г(£), /(г{1))), где г е р(-О), на графике Tf функции /.

В Приложении приведены результаты численных экспериментов программ, написанных на С++.

Результаты, выносимые на защиту.

1. В диссертации вводится новый способ аппроксимации локально липшицевых функций и показана связь с уже существующими. Изучаются МО, связанные с новым способом аппроксимации, и доказывается их липшицевость.

2. Строятся непрерывные равномерные аппроксимаций субдифференциала Кларка, которые используются в оптимизационных процессах поиска стационарных точек. В работе разрабатываются оптимизационные методы нахождения а-стационарных точек липшицевых функций, для чего вводятся а- и (а, ^-обобщенные матрицы.

3. Строятся нижние выпуклые аппроксимации для липшицевых функций и определяются правила их построения для различных их комбинаций, т.е. определяются правила их построения для суммы (разности), произведения (частного) и произвольной сложной комбинации функции, главные нижние аппроксимации которых известны.

4. Вводится понятие аппроксимации МО относительно другого МО. Определяется вид конуса Булигана через предельные интегральные значения матриц вторых смешанных производных опорной функции, которые, как доказывается, существуют почти всюду в декартовом произведении соответствующих пространств. С помощью таких матриц определяется субдифференциал Кларка для липшицевых МО и находится вид производной по направлению маргинальной функции и ее субдифференциал Кларка.

5. Развивается новый нелокальный способ аппроксимации негладких и недостаточно гладких функций, в результате которого получаем дважды дифференцируемые функции, сохраняющие е{В)-стационарные точки. С помощью таких функций строится метод оптимизации, сходящийся со сверхлинейной скоростью к е(-О)-стационарной точке липшицевой функции.

6. Вводится нелокальный поисковый алгоритм нахождения глобального оптимального управления для систем, описываемых обык-

новенными дифференциальными уравнениями. Для поиска оптимального управления среди кусочно непрерывно-дифференцируемых функций с конечным числом переключений используются уравнения Пуассона или теплопроводности, для решений которых применяется метод овыпукления, позволяющий сделать решения этих уравнений выпуклыми (вогнутым) по управлению и регуляризационному параметру а в окрестности точки минимума. Применение нижних выпуклых аппроксимаций к оптимизируемому функционалу позволяет ускорить процесс поиска и сделать его более устойчивым к изменению аргумента.

Результаты работы опубликованы в следующих работах:

Статьи в журналах, входящих в Перечень ВАК РФ:

1. Демьянов В. Ф., Лупиков И.М. Функции экстремума по г - субдифференциальному отображению // Вестник ЛГУ. 1983, № 1. С. 27-32.

2. Лупиков И.М. К условию дифференцируемости многозначного отображения с многогранными образами // Вестник ЛГУ. 1985, № 15. С. 95-98.

3. Прудников И.М. Субдифференциал Кларка для липшицевых многозначных отображений // Кибернетика. 1992, № 1. С. 21-28.

4. Прудников И.М. Необходимые и достаточные условия представимости положительно-однородной функции трех переменных в виде разности двух выпуклых функций // Известия РАН. 1992, Т. 56. № 5. С. 1114-1126.

5. Прудников И.М. Метод глобальной оптимизации и оценка скорости его сходимости // Автоматика и Телемеханика. 1993, № 12. С. 72-81.

6. Прудников И.М. Дифференциальные свойства функции экстремума по липшицевому многозначному отображению // ЖВМ и МФ. 1994, Т. 34, № 10, С. 1347-1357.

7. Прудников И.М. Нижние выпуклые аппроксимации для липшицевых функций // ЖВМ и МФ. 1994, Т. 34, № 10, С. 1347-1357.

8. Прудников И.М. Об аппроксимации многозначных отображений // ЖВМ и МФ. 1997, Т. 37. № 11. С. 1319-1326.

9. Proudnikov I.M. New constructions for local approximation of

Lipschitz functions. I. // Nonlinear Analysis. 2003, V. 54. P. 373-390.

10. Прудников И.М. Правила построения нижних выпуклых аппроксимаций // ЖВМ и МФ. 2003, Т.43. № 7. С. 939-950.

11. Прудников И.М. Применение некоторых уравнений математической физики для глобальной оптимизации функции на множестве. I. // Автоматика и. Телемеханика. 2000, № 11. С. 76-87.

12. Прудников И.М. Применение некоторых уравнений математической физики для глобальной оптимизации функции на множестве. И. // Автоматика и Телемеханика. 2000, №12. С. 80-91.

13. Прудников И.М. Применение метода потенциалов для оптимизации функции на множестве, заданном в виде системы линейных неравенств // Автоматика и Телемеханика. 1996, № 1. С. 66-82.

14. Proudnikov I.M. New constructions for local approximation of Lipschitz functions. II // Nonlinear Analysis. 2007, V. 66. P. 1443-1453.

15. Прудников И.М. C2{D) интегральные аппроксимации негладких функций, сохраняющие e{D) точки локальных экстремумов // Труды Института математики и механики УрО РАН. Том 16, N 5. Доп. номер. Екатеринбург: ИММ УрО РАН, 2010. С. 159 - 169.

16. Прудников И.М. Интегральная аппроксимация лишшщевых функций // Вестн. С. - Петерб. ун-та. сер. 10. 2010. Вып. 2. С. 7083.

17. Proudnikov I. М. Generalized matrices for Lipschitz functions // Journal of Mathematical Sciences: Advances and Applications. 2010. V.4. № 2. P. 227-244.

Другие публикации по теме диссертации:

19. Прудников И.М. Необходимые и достаточные условия строгой дифференцируемости многозначного отображения с многогранными образами // Вестн. ЛГУ. Деп. № 4197-84, 1984.

20. Лупиков И.М. Многозначные отображения, их описание и применение к оптимизации // Автореферат кандидат, диссертации, ЛГУ. 1985, 16 с.

21. Прудников И.М. Необходимые и достаточные условия квази-дифференцируемости функции двух переменных // Конференция молодых ученых Кавказских республик. Груз. АН, Тбилиси. 1986.

22. Прудников И.М. Алгебра множеств возможных направлений многозначных отображений // Сборник работ Саранского университета. 1990, С. 13-21.

23. Прудников И.М. Новый аппроксимационный метод для липшицевых функций // Доклады конференции APORS 97, Мельбурн, Австралия. 1997. С. 79-82.

24. Прудников И.М. К вопросу о представимости функции двух переменных в виде разности выпуклых функций // Сборник трудов Смоленского гуманитарного университета. 2003. № 3. С. 23-32.

25. Прудников И.М. Необходимые и достаточные условия представимости функции двух переменных в виде разности выпуклых функций /,/ Тезисы школы семинара, Саратов, 2008. С. 97-99.

26. Прудников И.М. Некорректные задачи и метод овыпукления // Московская международная конференция посвященная 90 - летию акад.Моисеева H.H., 2008. С. 200-202.

27. Прудников И.М. Применение метода овыпукления для решения задач теории управления // Международная конференция по теории управления,SICPRO'08. Москва, Институт проблем управления РАН им. В. А. Трапезникова, С. 526-535.

Подписано в печать Формат 60x84'Аs Печ. л./,/?Тираж экз. Заказ

ИзПК СПбГИЭУ 191002, Санкт-Петербург, ул. Марата, 31