Условия экстремума в негладком анализе

Около трех веков в математике и ее приложениях безраздельно правил классический гладкий анализ, однако новые, все более усложняющиеся задачи, возникающие в технике и естествознании в XX веке, все чаще требовали использования негладких функций. Такого рода возникающие проблемы пытались решать, аппроксимируя негладкие функции с некоторой степенью точности гладкими. Но скоро стало очевидно, что такие аппроксимации не могут быть применены для изучения существенно негладких свойств недифференцируемых функций (таких, как, например, нахождение нескольких направлений наискорейшего спуска или подъема [14]), хотя они и позволяют приближенно находить точки экстремума. Поэтому этот подход хотя и помогал эффективно решать ряд задач, не смог обеспечить растущих потребностей исследователей и представлял собой по существу «бегство» от негладкости.

Негладкий анализ занимается изучением свойств функций, не имеющих производной в «классическом смысле», а также множеств, порожденных этими функциями. Можно считать, что научное направление «негладкий анализ» сформировалось в середине XX века как продолжение идей классического гладкого анализа, хотя первые существенно негладкие задачи были поставлены и решены еще П. Л. Чебышевым [30,49]. Первыми подробно изученными классами недифференцируемых функций явились выпуклые функции и функции максимума (см. работы [17,22,23,27,29,33,34,42,45, 68,69]). Было показано, что эти функции являются дифференцируемыми по направлениям, откуда, опираясь на производную по направлениям, удалось получить локальные аппроксимации таких функций. Таким образом появилась возможность поиска направлений спуска и подъема, а, значит, и построения новых оптимизационных алгоритмов [16,44], что повлияло на развитие математического программирования [11,24,28,32,37,39]. Для выпуклых функций и функций максимума были построены эффективные численные методы [11,17,26,36,39,48,51].

Эти исследования легли в основу теории минимакса и выпуклого анализа [16,17,27,38,42,43,45,48] и привели к появлению понятия субдифференциала (см. например [70]), являющегося обобщением «классического» понятия градиента: в точках гладкости субдифференциал совпадает с градиентом, а в точках существенной негладкости (то есть таких, в которых не существует «обычной» производной) субдифференциал превращается в выпуклый компакт.

Изучению субдифференциалов в абстрактных пространствах посвящена работа [31]. Оказалось, что необходимым условием минимума на всем пространстве является принадлежность нуля субдифференциалу, а направление наискорейшего спуска есть вектор* направленный от ближайшей к началу координат точки, этого множества. Было построено исчисление, руководствуясь которым можно достаточно просто находить субдифференциалы. Успехи в этой области заставили задуматься о поиске обобщений понятия субдифференциала на случай более широкого класса функций. Одной из наиболее успешных попыток в этом направлении явились субдифференциал Шора [50] и его выпуклая оболочка — субдифференциал Кларка [29,54].

Введение

этих понятий позволило изучать произвольные липшицевые функции, но применение этих объектов на практике оказалось затруднительным — они не позволяли получать аппроксимацию функции в точке, давая возможность лишь проверять условия экстремума в ней. Известны и другие попытки, не лишенные указанного недостатка. Среди них субдифференциал Мордуховича [35,65−67], субдифференциал Мишеля-Пено [64], приближенные и геометрические субдифференциалы Иоффе [62,63], контейнеры Варги [73]. Подробный анализ различных подходов к этой проблеме приведен в [52]. Авторы этих обобщений субдифференциала опирались, как правило, не на производную по направлению, а на некоторые иные конструкции. Кроме того, само построение этих объектов вызывало трудности.

Исследователям пришлось искать компромисс между простотой построения объекта, возможностью получения на его основе аппроксимаций исследуемых функций и мощностью класса функций, которые этот объект обслуживает. В [16] были введено понятие квазидифференциала, позволившее получать положительно однородные аппроксимации функции в окрестности точки. Квазидифференциалы явились плодотворным объектом для исследования негладких функций — с их помощью удалось выразить условия экстремума, находить направления спуска и подъема, а следовательно и строить численные методы оптимизации [17,21,40,41]. Но, как выяснилось, квазидифференциальное отображение не является непрерывным, из-за чего возникают трудности со сходимостью численных методов, построенных на его базе. Для того, чтобы избавиться от этой проблемы, были введены кодифференциалы [21,60], позволившие получать аппроксимации функции в окрестности точки в виде суммы максимума и минимума аффинных функций. Кодифференциалы сохранили преимущества квазидифференциалов (они так же просто вычисляются, множество кодиффе-ренцируемых функций совпадает с множеством квазидифференцируемых функций), но ради непрерывности пришлось пожертвовать положительной однородностью.

Введение

кодифференциалов позволило строить более совершенные численные методы. Следующим естественным желанием было расширить класс изучаемых функций и попытаться там применить хорошо зарекомендовавший себя аппарат кодифференциального исчисления к большему числу функций. Это привело к появлению новых инструментов в негладком анализе — коэкзостеров и, явившихся промежуточным этапом на пути к ним, экзостеров. У истоков этих понятий лежат идеи Б. Н. Пшеничного, В. Ф. Демьянова и А. М. Рубинова. В [42] было введено определение верхних выпуклых и нижних вогнутых аппроксимации (в.в.а. и н.в.а.). А. М. Рубиновым было предложено рассматривать исчерпывающие семейства в.в.а и н.в.а. [20]. В. Ф. Демьянов предложил понятия верхних и нижних экзостеров (являющихся обобщением квазидифференциалов), а затем и коэкзостеров (являющихся обобщением кодифференциалов) и развил теорию этих объектов [46,55,56,59,60].

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

Целью диссертации является дальнейшее развитие теории экзостеров и коэкзостеров и их применение к решению новых возникающих задач.

Теоретическая значимость работы состоит в том, что она является дальнейшим развитием исследований в области аппроксимаций негладких функций с помощью аппарата экзостеров и коэкзотеров, впервые условия экстремума выписываются в терминах несобственных экзостеров и коэкзостеров. Эти результаты обобщают результаты В. А. Рощиной [46]. Кроме того, в диссертации обобщается теорема А. М. Рубинова [20] о существовании экзостеров.

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

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

Апробация работы. Результаты, изложенные в диссертации, докладывались и обсуждались на II международной конференции «Control and Optimization with Industrial Applications» (Баку, 2−4 июня 2008 г.), Всероссийской конференции «Устойчивость и процессы управления», посвященной 80-летию В. И. Зубова (г. Санкт-Петербург, 1−2 июля 2010 г.), Всероссийской конференции «Математическое программирование и приложения» Уро РАН (Екатеринбург, 28 февраля — 2 марта 2011 г.), XXXVIII, XXXIX, XL, XLI конференциях «Процессы управления и устойчивость» факультета прикладной математики — процессов управления (г. Санкт-Петербург,-апрель 2007 г., апрель 2008 г., апрель 2009 г., апрель 2010 г.), а также на семинарах кафедры математической теории моделирования систем управления (факультет прикладной математики — процессов управления, СПб-ГУ). .

По результатам исследований опубликовано 8 печатных работ [1−8], две из которых [3,6] в изданиях, рекомендуемых ВАК.

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

Список литературы

включает 73 наименований, 17 рисунков.

Заключение

.

Приведем краткий обзор полученных в работе результатов.

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

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

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

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

Глава 4 посвящена изучению коэкзостеров второго порядка. Здесь построено исчисление этих объектов и изучается вопрос их конвертирования.

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