Содержание к диссертации
Введение
1 Аппроксимация функций 25
1.1 Введение 25
1.2 Выпуклозначные многозначные отображения и их свойства 29
1.3 Аппроксимация липшицевых функций 32
1.3.1 Аппроксимация Кларка и Мишеля-Пено 32
1.3.2 Новый способ аппроксимации и связь с аппроксимацией Кларка 35
1.3.3 Необходимые условия оптимальности 52
1.4 Построение непрерывных конструкций для липши
цевых функций 59
1.4.1 е- субдифференциалы для выпуклых функций 61
1.4.2 а-субдифференциал для липшицевых функций 66
1.4.3 Применение непрерывных расширений субдифференциала Кларка для нахождения точки минимума выпуклой функции 78
1.5 Нижние выпуклые аппроксимации 81
1.5.1 Определения и примеры 83
1.5.2 Алгоритм построения ГНВА 85
1.6 Исчисление ГНВА 89
1.6.1 Сумма функций 89
1.6.2 Произведение функций 91
1.6.3 Общая теорема для гладкой комбинации лип-шицевых функций 95
1.6.4 Негладкие операции типа max и min 98
1.7 Обобщение субдифференциала Кларка для липши-цевых выпуклозначных многозначных отображений 102
1.8 Обобщенные матрицы для липшицевых функций 114
1.8.1 Субдифференциал Кларка для отображения Daf(-) 114
1.8.2 a, S- обобщенные матрицы 118
1.8.3 Равномерная непрерывная аппроксимация субдифференциала Кларка и ее применение в оптимизации 126
2 Аппроксимация многозначных отображений 129
2.1 Введение 129
2.2 Определения и примеры МО. Способы аппроксимаций МО 130
2.3 Исчисление множеств возможных направлений 139
2.4 Вычисление матрицы Р(-,-) Для некоторых видов липшицевых МО 144
2.5 Аппроксимация МО. Вид конуса Булигана для лип-шицевого МО через матрицы вторых частных производных опорной функции 152
2.6 Маргинальные функции. Вывод производной по направлению маргинальной функции 166
2.7 Нижние выпуклые аппроксимации для маргинальных функций 172
2.8 Дифференциальные свойства функции экстремума по липшицевому МО 180
2.9 Функции экстремума по є- субдифференциальному отображению 184
3 C2(D) Интегральные аппроксимации негладких функций, сохраняющие e(d) точки локальных экстремумов 193
3.1 Введение 194
3.2 Сглаживающие интегральные функции 196
3.3 Алгоритм нахождения є(2))-стационарньіх точек, сходящийся со сверхлинейной скоростью 208
4 Применение метода овыпукления и нижних выпуклых аппроксимаций в глобальной оптимизации 213
4.1 Применение метода овыпукления для решения некорректных задач 214
4.2 Постановка задачи 217
4.3 Решение задачи 219
4.4 Заключение 227
5 К Вопросу о представимости функции двух переменных в виде разности выпуклых функций 229
5.1 Введение 230
5.2 Доказательство теоремы 232
5.3 Геометрическая интерпретация теоремы 1 246
6 Метод построения исчерпывающего множества верхних выпуклых аппроксимаций 249
6.1 Введение 249
6.2 Метод построения верхнего экзостера для функции 256
6.3 Заключение 268
7 Способ определения обобщенных градиентов и обобщенных матриц вторых частных производных липшицевой функции с помощью интеграла стеклова 269
7.1 Введение 270
7.2 Построение субдифференциала первого порядка 272
7.3 Построение субдифференциала второго порядка 285
7.4 Применение субдифференциалов первого и второго порядков в оптимизации 293
7.5 Исчисление для субдифференциалов первого и второго порядков
- Аппроксимация липшицевых функций
- Обобщение субдифференциала Кларка для липши-цевых выпуклозначных многозначных отображений
- Аппроксимация МО. Вид конуса Булигана для лип-шицевого МО через матрицы вторых частных производных опорной функции
- Алгоритм нахождения є(2))-стационарньіх точек, сходящийся со сверхлинейной скоростью
Введение к работе
Актуальность темы исследования. ХХ-ый век ознаменовался применением вычислительных методов для решения важнейших экономических задач. Л.В. Канторович впервые изучил задачу планирования и оптимальных перевозок грузов (транспортная задача), и были построены алгоритмы ее решения. Первые задачи такого рода сводились к поиску максимума или минимума линейной функции на множестве, заданном в виде системы неравенств. Позднее стали изучать задачу нахождения минимума (максимума) квадратичной функции на произвольном выпуклом множестве. Далее перешли к оптимизации произвольной выпуклой функции.
Развитие техники, экономики, теории управления привело к необходимости разработки методов оптимизации негладких (недифферен-цируемых) или недостаточно гладких функций, у которых, например, нет вторых производных по переменным. Первый прогресс в этом направлении был сделан в работах математических школ Москвы, Ленинграда, Новосибирска, Екатеринбурга, Киева, Минска. Следует упомянуть работы В. В. Гороховика, В. Ф. Демьянова, И. И. Еремина, Ю. М. Ермольева, Я. И. Заботина, А. Д. Иоффе, С. С. Кутателадзе, А. Г. Кусраева, В. Н. Малоземова, Б. Ш. Мордуховича, Е. А. Нур-минского, Б. Т. Поляка, Б. Н. Пшеничного, А. М. Рубинова, В. М. Тихомирова, Н.З. Шора и др.
Среди зарубежных ученых, внесших значительный вклад в развитие негладкого анализа и методов недифференцируемой оптимизации, были R. Т. Rockafellar, F. Clarke, J.-P. Aubin, J.-P. Penot, E. Polak, J. Hiriart-Urruty, C. Lemarechal, B. Luderer, D. Pallaschke, К, С Kiwiel, A. Shapiro, F. Giannessi, L. Thibault, J. -J. Moreau, J. Warga, R. Mifflin, J. Gwinner, J. V. Outrata, I. Ekeland.
Задача оптимизации функций тесно примыкает к задачам, связанным с изучением оптимальных процессов в теории управления, разработанной Л. С. Понтрягиным и его учениками. Здесь надо отметить работы В. Г. Болтянского, Ф. П. Васильева, Р. В. Гамкрелидзе, А. Я. Дубовицкого, Ю. Г. Евтушенко, В. И. Зубова, Н. Н. Красовского, А. Б. Куржанского, А. М. Летова, А. А. Милютина, Е. Ф. Мищенко, Н. Н. Моисеева, А. И. Пропоя, А. Н. Тихонова, Ф. Л. Черноусько и др. Современные исследователи в этом направлении расширили класс оптимизируемых функций. Рассматриваются функции, представимые разностью выпуклых функций. Здесь уместно упомянуть работы В. Ф. Демьянова, С. И. Дудова, Е. С. Половинкина, Л. Н. Поляковой. _
І \ 3
Широкое применение методов негладкой оптимизации началось тогда, когда были разработаны методы оптимизации произвольной выпуклой функции. Были введены обобщенные градиенты (субградиенты), выпуклая оболочка которых в каждой точке образует субдифференциал. Численные методы оптимизации таких функций основывались на поиске направления наискорейшего спуска. Впервые такие методы были предложены Н. 3. Шором.
Дальнейшим шагом вперед было введение обобщенных градиентов для липшицевых функций, как элементов из некоторого выпуклого компактного множества, называемого субдифференциалом функции в точке. В отличие от выпуклого случая здесь нет однозначного определения субдифференциала. Разные авторы определяют субдифференциал по-своему. Достаточно обратиться к работам Ф. Кларка, Ж. Пено и Б. Ш. Мордуховича.
Другие авторы (В. Ф. Демьянов, А. М. Рубинов) пошли по пути изучения дифференцируемых по направлению функций и различного вида представления производной по направлению. Был введен класс квазидифференцируемых функций. Производная по направлению таких функций представляется как сумма максимума и минимума скалярных произведений векторов из некоторых выпуклых компактных множеств на вектор направления.
Актуальным на сегодняшний день является введение таких многозначных отображений, которые можно было бы использовать для построения непрерывных расширений субдифференциала Кларка и поиска на их основе стационарных точек, в которых нуль принадлежит субдифференциалу Кларка. Кроме того, важно показать связь различных методов аппроксимаций липшицевых функций, и, возможно, указать новые способы построения субдифференциалов.'
При оптимизации функций сложного, например, колебательного вида, полезно упрощать эти функции, строя главные нижние выпуклые аппроксимации в некоторой окрестности точки или даже на некотором множестве.
Для нахождения вида производной по направлению маргинальной функции требуется строить аппроксимацию одного многозначного отображения относительно другого многозначного отображения, находить вид различных конусов, а также вид субдифференциала Кларка для таких функций.
Для построения более ускоренных методов оптимизации негладких или недостаточно гладких функции функций требуется опреде-
лить такие конструкции, к которым применимы методы оптимизации второго порядка для дважды дифференцируемых функций. Но для выполнения последнего необходимо, чтобы при построении этих конструкций точки экстремума не исчезали и не появлялись новые точки, о которых мы не знаем, как далеко они находятся от точек экстремума исходной функции.
Проблема нахождения условий представимости произвольной липшицевой функции в виде разности выпуклых функций интересна для математиков разных специальностей. Получение условий представимости функции в виде разности выпуклых, а также условий ква-зидифференцируемости функции в точке важно для специалистов в области оптимизации.
Цель работы. Основной целью диссертации является разработка новых методов аппроксимации широкого класса функций - локально липпшцевых функций и построение на их основе новых методов оптимизации негладких или недостаточно гладких функций, к которым неприменимы или для которых не выполняются условия сходимости оптимизационных процессов высокого порядка. Исследуются новые виды многозначных отображений (МО), различные способы аппроксимаций МО и их взаимосвязь, поскольку основными объектами изучения в негладкой оптимизации являются обобщенные градиенты, образующие в совокупности множества, являющиеся образами некоторых МО. Другой, не менее важной, целью работы является применение аппроксимационных методов к задачам теории управления.
Научная новизна. В диссертации вводится новый способ аппроксимации локально липпшцевых функций и показана связь с уже существующими. Доказано, что для функций, локально представи-мых разностью выпуклых, введенный метод аппроксимации совпадает с аппроксимацией Кларка. Усредненные интегральные градиенты, используются для построения непрерывных равномерных аппроксимаций субдифферешщала Кларка, что важно для нахождения стационарных точек.
Вводятся МО, связанные с новым способом аппроксимации. Доказывается их липшицевость и определяется для них субдифференциал Кларка. В работе разрабатываются оптимизационные методы нахождения стационарных точек липпшцевых функций. Для этой цели вводятся а- и (а, <5)-обобщенные матрицы.
На основе развитой теории строятся нижние выпуклые аппроксимации для липпшцевых функций и определяются правила их постро-
ения для различных их комбинаций. Строится исчисление главных нижних выпуклых аппроксимаций, то есть определяются правила их построения для суммы (разности), произведения (частного) и произвольной сложной комбинации функции, главные нижние аппроксимации которых известны. Если главные нижние аппроксимации в окрестностях точек, подозрительных на экстремум, построены, то в дальнейшем оптимизируется не сама функция, а функция, составленная из главных нижних аппроксимаций исходной функции.
Вводится понятие аппроксимации МО относительно некоторого множества, используя которое в достаточно общем случае для произвольного локально липшицевого МО устанавливается связь различных видов аппроксимаций МО. Доказывается, что такие МО почти всюду в декартовом произведении соответствующих пространств имеют матрицы вторых смешанных производных опорной функции по аргументу и опорному вектору. Эти матрицы используются для построения конуса касательных направлений, конуса Булигана, а также конуса возможных направлений. Вводится субдифференциал Кларка для липшицевых МО.
Важным применением всего этого является нахождение производной по направлению маргинальных функций при более слабых требованиях, чем это делалось ранее, что важно для оптимизации таких функций. Удается найти субдифференциал Кларка маргинальной функции в точке. Строятся главные нижние аппроксимации для маргинальных функций.
Развивается новый нелокальный способ аппроксимации негладких и недостаточно гладких функций, в результате которого получаем дважды дифференцируемые функции, сохраняющие e(D)-стационарные точки. С помощью таких функций строятся ускоренные методы оптимизации, сходящиеся к ,(Г>)-стационарным точкам. . Рассматривается нелокальный поисковый алгоритм нахождения глобального оптимального управления для систем, описываемых обыкновенными дифференциальными уравнениями. Для оптимизации используются уравнения Пуассона и теплопроводности, для решений которых применяется метод овыпукления, позволяющий сделать решения этих уравнений выпуклыми (вогнутыми) по управлению и регуляризационному параметру а в окрестности точки глобального минимума по обоим переменным. Предлагается строить главные нижние выпуклые аппроксимации для целевой функции в некоторых достаточно больших окрестностях фиксированных точек, что делает
оптимизационный процесс более устойчивым к изменениям аргумента.
Даются условия представимости произвольной липшицевой функции двух переменных в виде разности выпуклых, что важно для задач оптимизации.
Методы исследования. Общая методика исследования базируется на теории функций, теории меры и интеграла Лебега, выпуклом анализе, теории многозначных отображений и их аппроксимации, теории необходимых условий экстремума, численных методах решения задач нелинейного программирования и задач на минимакс, аналитической геометрии.
Практическая ценность и реализация результатов. Выше была отмечена важность развития методов оптимизации второго порядка для липшицевых функций, чему и посвящена работа. Введены новые способы аппроксимации липшицевых функций, с помощью которых удается построить непрерывные расширения субдифференциала Кларка, что находит применение в оптимизационных методах. В диссертации устанавливается вид производной по направлению маргинальной функции и ее субдифференциала Кларка, что важно для развития оптимизационных методов таких функций. Впервые предложен метод поиска глобального оптимального управления, использующий идею овыпукления решения уравнения Пуассона и уравнения теплопроводности. Применение нижней выпуклой аппроксимации к целевой функции задачи теории управления существенно упрощает оптимизационную задачу. Целевая функция после применения нижней выпуклой аппроксимации становится полунепрерывной снизу, а сама задача - устойчивой для малых изменений управления и. Разработаны и отлажены программы для нахождения глобальной точки экстремума, использующие эту идею. Предложена интегральная аппроксимация функции, сохраняющая е(1))-стационарные точки, на основе которой разработан алгоритм ускоренного поиска таких точек. Теорема, дающая условия представимости липшицевой функции в виде разности выпуклых функций, имеет как теоретический, так и практический интерес, так как с ее помощью возможно построить алгоритм разложения положительно-однородной многогранной функции с конечным числом граней в виде разности выпуклых.
Апробация работы. Большая часть результатов была опубликована в статьях центральных издательств, а также за рубежом. Результаты докладывались и обсуждались на международных конфе-
ренциях:
Негладкий анализ и оптимизация, ЛОМИ, Ленинград, 1995;
International Conference of Asia-Pacific, APORS 97, Melbourne, Australia, 1997;
Америко - австралийский математический съезд, Мельбурн, 1999;
Международная конференция, посвященная 75-летию член-корреспондента АН СССР Зубова В.И., 2005;
Международная конференция по современным проблемам кибернетики, Казань, 2005;
Конференция, посвященная 90-летию академика Н.Н. Моисеева, 2007;
2-ая международная конференция по социальной и экономической динамике, Москва, 2007;
Международная конференция "Индентификация систем и задачи управления, SICPRO'08", 2008;
- 10-ая математическая школа-семинар по проблемам теории
функций, Саратов, 2008;
Международная конференция "Дифференциальные уравнения и топология", посвященная 100-летию академика Л.С. Понтрягина, Москва, 2008;
Международная конференция "Актуальные вопросы теории устойчивости и управления", посвященная 85-летию академика Н.Н. Красовского, Екатеринбург, 2009;
На семинарах:
В Московском физико-техническом институте,
В Институте проблем управления РАН,
В Институте системного анализа РАН,
В Санкт Петербургском университете на факультете прикладной математики и процессов управления.
Структура и объем работы. Диссертация состоит из Введения, пяти глав, приложения, 22 рисунков и списка литературы. Объем диссертации 296 страницы. В Приложение включены 22 рисунка и таблица с результатами численных экспериментов. Список литературы состоит из 99 наименований. Общий объем диссертации 327 страниц.
Аппроксимация липшицевых функций
Кривая г(хо,-,д) будет состоять из частей кривых г(жо,-, ?«) и кривых 7«-Для того чтобы представить кривую г(жо, , д) в виде, указанном в определении 7.2.1, заменим вектор gi кривой г(жо,-, ?«) на вектор д. После этого получим дополнительный вектор a(gi(a) д) = о(а).
Проверим, что кривая г(жо, -,д) из множества г](хо). Для этого необходимо проверить, что функция о(-) удовлетворяет всем требованиям в определении 7.2.1: При переходе от кривой r(xo,-,gi) к кривой г(хо,-,д) значение параметра ОІІ немного изменится на некоторое другое значение бц. Но поскольку верно соотношение между этими параметрами бц/оц - І ОО 1, что следует из построения, и нормы векторов, стоящих под интегралами, ограничены сверху, то, как нетрудно видеть из приведенных ниже предельных соотношений, параметр (li можно оставить без изменения.
Вычислим средние интегральные значения градиентов функции /() вдоль кривых 7«( ) соединяющих кривые г(жо, -, ?«).
Обозначим длину кривой 7«( ) через Ъ(а) (Здесь отмечаем, что і зависит от а.) Поскольку, выбирая кривые г(жо, -, ?«), мы можем всегда добиться того, чтобы выполнялось неравенство где R(a) есть длина радиус - вектора, соединяющего точку Хо с наиболее удаленной точкой кривой 7«( ) ci— константа, зависящая от оценки нормы с/(а) для а Є (0,«о],«о 0, и г(-) Є гу(жо). Следующая теорема дает связь между субдифференциалом Кларка и множеством Df(xo). Теорема 1.3.1 Если функция /() представимо, в виде разности выпуклых функций /і(-) и /2(-)
Пусть теперь д Є bdK{v\) V\ Є dfi(xo). Покажем, что для любого крайнего (экстремального) вектора v\ Є df\(xo) с нормальным конусом K(v\), intK(vi) = 0, существует множество Q(v\) (см. Рис. 1.3.2.2), для которого верно следующее: если кривая г(хо, -,д) Є mtQ(vi) для а Є [0, «о], «о 0, то
Искомая кривая будет состоять из частей кривых г(хо, -,дк) Возьмем первую кривую г(хо, -,ді) Є г)(хо). Для а Є [0,(єі)] p#(V/i(r(iEo, , ?i)),fi) Єь Для малых а, для которых верно это неравенство, сделаем плавный переход к кривой г(жо, -,#2), не выходя из множества кривых г](хо). Далее двигаемся вдоль кривой г(жо, , #2) по направлению к точке жо до тех пор, пока для а Є [0, (єг)] не будет выполняться неравенство V/i(r( o, -,#2)) і) є2- Аналогично, для малых а, для которых верно написанное неравенство, переходим к кривой г(жо, , ?з), не выходя из множества кривых г)(хо), и так далее для всех к. В итоге получим некоторую кривую г(хо, а, д) = Хо+ад+о(а)} для которой функцию о(-) : К. — Мп можно выбрать так, чтобы для малого «о 0
Возьмем произвольные построенные кривые Tj(-) Є i](xo),j Є N, для которых (1.9) верно. Поскольку согласно определению множества г](хо) вектор-функции Oj{-)— липшицевы с одной и той же константой с на отрезке [0,«о], то можно выбрать подпоследовательность Ojk(-)7 для которой существует равномерный предел, т.е. Ojk(-) = о(-) для к — +оо и а Є [0, «о]. Поскольку Ojk(-) равномерно бесконечно малые, то предельная функция о(-) будет также бесконечно малой, липшицевой с константой с на отрезке [0,«о]. Множество Q{v\) будет состоять из всех таких предельных кривых г(жо, -,#).
Вернемся теперь к доказательству пункта 3. Если кривая г(жо, -,д) не принадлежит для а Є [0, «о] одному из множеств Q(VJ), построенных выше для крайних векторов Vj Є df\(xo) из одной и той же гиперплоскости с нормальным вектором д7 то мы можем разбить ее (кривую) на интервалы , соответствующие значениям параметра а Є [а ,а +1], где г(жо, -,#) принадлежит одному какому-то множеству Q{VJ1). Тогда интеграл
Обобщение субдифференциала Кларка для липши-цевых выпуклозначных многозначных отображений
В этой главе будут рассмотрены свойства различных МО, главным образом— липшицевых МО. В действительности, МО — это обобщение функций, отображающих точку в точку, т.е. однозначных отображений. МО отображают точку в целое множество. Многие понятия, характерные для однозначных функций, можно распространить для МО. К таким понятиям относятся: график, выпуклость, вогнутость, непрерывность, производная, двойственность.
Для аппроксимации МО используют различные подходы. Это — конус возможных направлений, конус касательных направлений, конус Булигана, которые для дифференцируемых однозначных функций являются обычной линейной аппроксимацией. Перечисленные конусы в общем случае отличны друг от друга, но в некоторых случаях они совпадают. Будут даны такие условия и построена алгебра конусов возможных направлений. В действительности, будет введено понятие аппроксимации относительно заданного множества, при наличии которой можно объединить все способы аппроксимаций. Большое внимание уделено маргинальным функциям вида непрерывное МО, и выводу их производной по направлению. Последнее получено при более слабых условиях на функцию (/?(.,.), чем это было сделано предыдущими исследователями.
В формулах для производных маргинальных функций участвуют матрицы вторых частных производных опорной функции Рщ( і ) многозначного отображения С(-), которые рассматривались в главе 1, параграф 1.7. Для некоторых распространенных МО, как, например, МО, заданных в виде системы неравенств или выпуклой оболочки конечного числа вектор-функций, удается получить вид матрицы p"xq{--, )
Разработанная теория применяется для оптимизации маргинальных функций и построения методов наискорейшего спуска. Одно из таких приложений есть нахождение направления наискорейшего спуска для функции экстремума по є- субдифференциальному отображению выпуклой функции.
Определения и примеры МО. Способы аппроксимаций МО Функции являются частным случаем МО. По определению МО G(-) : Шп — 2 сопоставляет каждой точке х Є К элемент пространства 2 , элементами которого являются множества всех подмножеств пространства Ж171. Функции, которые обычно изучают в функциональном анализе, сопоставляют каждой точке х Є Rn единственную точку из Ж171. Нас будут интересовать в дальнейшем выпуклозпачпые компактные многозначные отображения (ВКМО), т.е. МО с выпуклыми компактными образами.
Для любой точки z графика grG можно построить конусы допустимых и касательных направлений. Поскольку эти конусы в пространстве Rn х Мт, то, проектируя их на Мт, получим следующие множества:
Многозначными отображениями стали описывать многие технические и экономические модели. Это объясняется тем, что часто неизвестно точное решение системы или значение функции. В оптимизации потребность изучения МО объясняется тем, что для негладких функций не существует градиента в какой-то точке, а существует целое множество обобщенных градиентов.
Для липшицевых функций определено отображение dcbf( ) Rn 2 — субдифференциальное отображение Кларка, которое так же, как МО df(-) для выпуклых функций, есть разрывное и П.СВ. Дальнейшим шагом, как и выше, является построение непрерывного расширения для дсь/( )- Эта задача оказалась значительно более сложной, чем для выпуклого случая. Она была решена в главе I, параграф 1.4.2.
Для вывода вида производной по направлению маргинальной функции потребовалось понятие аппроксимации МО. Впервые это понятие было введено в [20], где рассматривалась аппроксимация относительно множества T(x,g,v). Это свойство характеризует насколько хорошо множество T(x,g,v) аппроксимирует МО G(-) в точке -и, -и Є G(x) по направлению д. В дальнейшем стало понятно, что аппроксимацию можно рассматривать относительно любого из трех введенных множеств, но лучше, более естественно, было бы рассматривать аппроксимацию относительно конуса Булигана T(x,g,v), что и было сделано в [53] для липшицевых МО.
Аппроксимация МО. Вид конуса Булигана для лип-шицевого МО через матрицы вторых частных производных опорной функции
С статье приводится новый нелокальный способ аппроксимации негладких функций, в результате которого получаем дважды дифференцируемые функции, сохраняющие е(1))-стационарные точки. С помощью таких функций можно строить методы оптимизации второго порядка, сходящиеся к s(D)-стационарным точкам. Описан алгоритм оптимизации, сходящийся к стационарной точке функции /() со сверхлинейной скоростью, т. е. имеющий скорость сходимости более быструю, чем любая геометрическая прогрессия. Результаты главы опубликованы в работах [68], [69]
Негладкие (недифференцируемые) или недостаточно гладкие функции, которые, например, не имеют вторых производных, стали в наши дни обычным инструментом исследования. Такими функциями описываются многие процессы в экономике, планировании, теории управления и т.д. Примером таких функций могут быть, например, функции, получаемые при взятии операций минимума или максимума. Методы оптимизации таких функций отличаются от методов оптимизации гладких (дифференцируемых) функций. Обычного в нашем понимании определения градиента у негладких функций не существует. Было введено определение обобщенных градиентов, которые в совокупности в каждой точке образуют субдифференциал Кларка. Субдифференциал Кларка, как функция точки, есть многозначное отображение (м.о.), являющееся не непрерывным, а только полунепрерывным сверху (п.св.). Известно, что лип-шицева функция почти всюду (п.в.) в Шп дифференцируема. Проблема еще заключается в том, что даже для точки дифференцируемости субдифференциал Кларка не совпадает с ее градиентом. Например, для функции
нетрудно видеть, что производная функции в нуле равна нулю, а субдифференциал Кларка в нуле есть отрезок [-1, 1], что подтверждает сказанное выше. А если мы имеем разрывные градиенты (обобщенные градиенты), как функции от точки, то построить методы оптимизации и оценить их скорость сходимости в общем случае весьма затруднительно. Попытка использовать полиномиальную или какую-нибудь другую аппроксимацию и перейти к оптимизации уже гладкой аппроксимирующей функции известными методами [75] приводит к появлению дополнительных точек экстремума. Как отделить в процессе оптимизации фиктивные точки экстремума от настоящих, которые нам неизвестны? Ответ на этот вопрос является еще более трудной задачей, чем исходная задача. Поэтому развитие теории оптимизации негладких функций пошло по пути разработки собственных методов, основанных на свойствах обобщенных градиентов липшицевых функций [57]-[73]. Здесь следует упомянуть работы Н. 3. Шора [84] , Б. Н. Пшеничного [73], В. Ф. Демьянова [15], Е. А. Нурминского [43], Ф. Кларка [30], Р. Рокафеллара [76] , Л. Н. Поляковой [51], упомянутые в списке литературы. Впервые методы сглаживания негладких функций и построения на их основе методов оптимизации предложил в своей докторской диссертации А. М. Гупал ([11], [40]).
Для построения более ускоренных методов оптимизации негладких функций требуется определить такие конструкции, к которым применимы методы оптимизации второго порядка для дважды дифференцируемых функций. Но для выполнения последнего необходимо, чтобы при построении этих конструкций точки экстремума не исчезали и не появлялись новые.
Ниже предлагается именно такой способ сглаживания негладкой Функции [69]. Получившаяся в итоге функция будет непрерывно дифференцируемой. Если же к ней повторно применить описанную ниже операцию, то получим дважды дифференцируемую функцию, имеющую точки экстремума, совпадающие с є- стационарными точками исходной функции. Новых (дополнительных) точек экстремума, кроме е- стационарных точек исходной функции, построенная функция иметь не будет. К дважды дифференцируемой функции вполне применимы методы оптимизации второго порядка, обладающие ускоренной сходимостью.
С помощью построенных ниже функций мы можем перейти от локальной оптимизации негладких функций к локальной оптимизации гладких функций, а также оценить скорость сходимости к точке экстремума, что безусловно важно, поскольку можно строить ускоренные оптимизационные методы для функций с разрывными градиентами. Подобных конструкций, насколько известно автору, никто ранее не предлагал.
Пусть /() : Шп — К. — липшицева с константой L функция, и х — ее точка локального минимума (максимума) в Шп. Как известно, необходимым условием экстремума для липшицевой функции является принадлежность нуля субдифференциалу Кларка, т. е.
Любая точка, для которой выполняется написанное выше условие, называется также стационарной. Не все стационарные точки являются точками минимума или максимума. Возьмем произвольное выпуклое компактное множество D С Шп. Введем определение s{D) стационарной точки.
Определение 3.2.1 Точку х назовем s{D) стационарной точкой функции /(); если множеству х + D принадлежит стационарная точка функции Если функция f(-)— сильно выпуклая, то данное определение хорошо согласуется с определением е-стационарной точкой для выпуклой функции [76], так как для сильно выпуклых функций расстояние от произвольной точки до множества є- стационарных точек оценивается сверху через изменения функции
Алгоритм нахождения є(2))-стационарньіх точек, сходящийся со сверхлинейной скоростью
Рассматривается нелокальный поисковый алгоритм нахождения глобального оптимального управления для систем, описываемых обыкновенными дифференциальными уравнениями. Для оптимизации в Шп используются уравнения Пуассона и теплопроводности, для решений которых применяется метод овыпукления, позволяющий сделать решения этих уравнений выпуклыми по управлению и и регуляризационному параметру а в окрестности точки глобального минимума по обоим переменным. Высказанная идея упрощает проблему регуляризации по параметру а и позволяет строить устойчивые оптимизационные методы. Также предлагается строить нижние выпуклые аппроксимации для целевой функции в некоторых достаточно больших окрестностях фиксированных точек, что делает оптимизационный процесс более устойчивым к изменениям аргумента, а сам функционал — полунепрерывным снизу, что важно для оптимизации в бесконечномерных пространствах. для любой последовательности {щ},Щ - k и, U— заданное множество в банаховом пространстве, является метод регуляризации, разработанный А.Н. Тихоновым и его учениками. При пользовании этим методом нужно выбрать какой-либо стабилизатор рассматриваемой задачи. Заметим, что выбор стабилизатора зависит от выбора банахова пространства.
Пусть таким стабилизатором является функция Г2(ІІ), определенная на множестве UQ С U. Далее берется какая-либо положительная последовательность {ато}, сходящаяся к нулю, и при каждом т = 1, 2,.. на множестве UQ определяется функция
Как показывает практика, добавление к исходной функции J (и) слагаемого amQ(u) делает задачу минимизации функции Тт{и), как правило, более "устойчивой" по аргументу. По этой причине часто метод Тихонова называют методом стабилизации.
После этого рассматривается задача минимизации функции Тт{и) на UQ как задача первого типа. А именно, при каждом т = 1,2,..., определяется точка ит, удовлетворяющая условиям
Однако, тот факт, что задача минимизации функции Тт{и) на UQ обладает запасом устойчивости, не меньшим, чем исходная задача, сам по себе не гарантирует того, что последовательность {ит} будет р- регулярной (р- метрика рассматриваемого пространства). Это связано с тем, что, чем меньше значение параметра ат, тем меньше слагаемое amQ(u), входящее в выражение (4.2), и, следовательно, тем меньше запас устойчивости задачи минимизации Тт{и)
Оказывается, что для получения последовательности {ит} с требуемыми свойствами уменьшение запаса устойчивости следует компенсировать согласованным изменением величин ат, єт, являющихся параметрами метода. Произвол в выборе этих параметров может привести к тому, что последовательность {мто}, определяемая условиями (4.3), даже в простейших задачах может не сходиться к множеству оптимальных решений.
Как правило, задача минимизации функции Тто(-) на U более простая, чем задача минимизации функции J(-) на U, так как функция Тто(-) обладает "запасом" устойчивости в виде члена amQ(u). Но при уменьшении ат запас устойчивости также уменьшается, поэтому важно согласованно уменьшать ат и єт, в противном случае последовательность {ит} может не сходиться в метрике рассматриваемого пространства U к множеству решений U задачи (4.1).
Трудность применения метода регуляризации заключается в том, что выполнить условия согласования последовательностей {ат} и {єт} достаточно трудно, так как на каждом шаге приходится решать оптимизационную задачу, точность решения которой, т.е. значение параметра єт: неизвестна. которую называют функцией Тихонова. Для каждого т рассматривают задачу минимизации функции Фт(и) на U, а именно, для каждого т находится ит из решения следующей задачи
Применение метода Тихонова, который также называют методом стабилизации, осложняется тем, что на каждом шаге надо находить ит из достаточно малой окрестности множества решений задачи (4.4), что сделать практически сложно. Предлагаемый далее метод упрощает выбор последовательности ат. Параметр стабилизации ат получается на каждом шаге как решение оптимизационной задачи где z = (и, а). В бесконечномерном банаховом пространстве функций делают дискретизацию по t и и, т.е. инфимум ищется среди кусочно непрерывно-дифференцируемых функций с конечным числом переключений. Будем считать, что функционал J(-) непрерывен по и и задача (4.5) имеет решение для любого а Є [0,ск0].
Задача (4.5) решается в конечномерном пространстве с использованием методов глобальной оптимизации, основанных на применении решения уравнения теплопроводности либо уравнения Пуассона с одновременным их овыпук-лением (метод овыпукления) по z [60]. Метод овыпукления позволяет построить регулярные, т.е. устойчивые методы оптимизации для любого шага дискретизации и описан в предыдущих статьях автора [60], [61], где приведены оптимизационные методы и результаты численных экспериментов.
Регуляризация функционала J(-) по Тихонову обеспечивает регулярность по аргументу. Поскольку процесс оптимизации построен таким образом, что оптимизируется не сам функционал, а решение уравнения в частных производных (уравнение Пуассона либо уравнение теплопроводности), которое является липшицевым по совокупности аргументов с одной и той же константой Липшица независимо от номера итерационного шага (см теоремы 4.3.1, 4.3.2), то метод регуляризации по Тихонову совместно с методом овыпукления обеспечивает также регулярность по функционалу.
