Условия экстремума в негладком анализе тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Аббасов, Меджид Эльхан оглы

• Аббасов, Меджид Эльхан оглы
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Аббасов, Меджид Эльхан оглы

ВВЕДЕНИЕ

1 Вспомогательные результаты

1.1 Некоторые сведения из выпуклого анализа.

1.2 Производные Дини, Адамара и условия экстремума.

1.3 Субдифференцируемые, супердифференцируемые и квазидифференцируемые функции.

1.4 Выпуклый случай

1.5 Кодифференцируемые функции

2 Описание условий экстремума с привлечением аппарата экзостеров

2.1 Экзостеры.

2.2 Условия экстремума без ограничений

2.2.1 Описание условий экстремума с помощью аппарата экзостеров.

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

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

2.2.4 Примеры

2.3 Условия экстремума с ограничениями.

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

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

2.4 Разрывность экзостерного отображения.

3 Описание условий экстремума с привлечением аппарата коэкзостеров

3.1 Коэкзостеры

3.2 Необходимые условия безусловного экстремума в терминах собственных коэкзостеров.

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

3.3.1 Эквивалентность минимаксного и максиминного представлений

3.3.2 Условия экстремума.

3.4 Необходимые условия безусловного экстремума в терминах несобственных коэкзостеров.

3.5 Метод наискорейшего коэкзостерного спуска.

3.5.1 Сходимость метода.

4 Коэкзостеры второго порядка

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

4.2 Конвертирование коэкзостеров второго порядка.

Введение диссертации (часть автореферата) на тему «Условия экстремума в негладком анализе»

Около трех веков в математике и ее приложениях безраздельно правил классический гладкий анализ, однако новые, все более усложняющиеся задачи, возникающие в технике и естествознании в 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]).

Список литературы диссертационного исследования кандидат физико-математических наук Аббасов, Меджид Эльхан оглы, 2011 год

1. Аббасов М.Э. Нахождение стационарных точек функций, допускающих неоднородные аппроксимации приращения // Тез. докл. Всеросс. конф. Устойчивость и Процессы Управления. СПб, СПбГУ ф-т ПМ-ПУ, 2010. С. 191-192.

2. Аббасов М.Э. Условия экстремума в терминах несобственных экзостеров // Вестник Санкт-Петербургского университета, серия 10, вып.2. 2011. С. 3-8.

3. Аббасов М.Э. Условия экстремума в терминах несобственных экзо-стеров // Информационный бюллетень АМП, N 12 (Тез. докл. Всеросс. конф. МпиП). Екатеринбург, Уро РАН, 2011. С. 17-18.

4. Аббасов М.Э., Демьянов В.Ф. Условия экстремума негладкой функции в терминах экзостеров и коэкзостеров. // Труды института математики и механики УрО РАН, Т. 15, 2009. С. 10-19.1. Переведена:

5. Abbasov М. Е., Demyanov V. F. Extremum conditions for a nonsmooth function in terms of exhausters and coexhausters // Proceedings of the Steklov Institute of Mathematics, Volume 269, Supplement 1, 2009. P. 6-15.

6. Андрамонов М.Ю. Вычисление квазидифференциалов и экзостеров по значениям функции // Вычислительные методы и программирование: новые вычислительные технологии, Научно-исследовательский вычислительный центр МГУ им. М.В. Ломоносова, Т. 7, 2006. С. 190194.

7. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Наука. 1987. 600 с.

8. Васильев Ф.П. Методы оптимизации. М.: Факториал Пресс. 2002.824 с.

9. Гороховик В.В. Конечномерные задачи оптимизации. Минск: Издательский центр БГУ. 2007. 239 с.

10. Демидович Б.П., Марон И.А. Основы вычислительной математики. М.: Наука. 1970. 664 с.

11. Демьянов В.Ф. Негладкий анализ на плоскости. Часть 1 // Соросов-ский образовательный журнал, №8, 1997. С. 122-127.

12. Демьянов В.Ф. Условия экстремума и вариационное исчисление М: Высшая школа, 2005. 335 с.

13. Демьянов В.Ф., Васильев JI.B. Недифференцируемая оптимизация. М: Наука, 1981. 384 с.

14. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М: Наука, 1972. 368 с.

15. Демьянов В.Ф., Полякова Л.Н. Условия минимума квазидиффе-ренцируемой функции на квазидифференцируемом множестве //Ж. вычисл. матем. и матем. физ., Т. 20, JV2 4, 1980. С. 849-856.

16. Демьянов В.Ф., Рощина В.А. Обобщенные субдифференциалы и экзостеры в негладком анализе // Доклады РАН, Т. 416, № 1, 2007. С. 18-21.

17. Демьянов В.Ф., Рубинов А.М. Основы негладкого анализа и ква-зидифференциальное исчисление М.: Наука, 1990. 432 с.

18. Демьянов В.Ф., Рубинов А.М. Элементы квазидифференциаль-ного исчисления // «Негладкие задачи теории оптимизации и управления» под ред. В.Ф.Демьянова. Л.: Изд-во Ленингр. ун-та. 1982. С. 5-127.

19. Дудов С. И. Необходимые и достаточные условия максимина функции разности аргументов // Журн. «Выч.мат-ка и выч.физика», т.32, № 12, 1992. С. 1869-1884.

20. Дудов С. И. Дифференцируемость по направлениям функции расстояния // Мат.сб., т.186, № 3, 1995. С. 29-52.

21. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. М.: Наука. 1975. 320 с.

22. Еремин И. И. Сигма-кусочные функции и задачи дизъюнктивного программирования // Сборник научных трудов, Тр. ИММ УрО РАН,5, 1998. С. 357-380.

23. Ермольев Ю.М. Методы стохастического программирования. М.: Наука, 1976. 285 с.

24. Иоффе А.Д, Тихомиров В.М. Теория экстремальных задач. М.: Наука. 1974. 480 с.

25. Карманов В.Г. Математическое программирование. М.: ФИЗМАТ-ЛИТ. 2004. 264 с.

26. Кларк Ф. Оптимизация и негладкий анализ. М.: Наука, 1988. -288 с.

27. Колатц Л., Крабе В. Теория приближений. Чебышевские приближения и их приложения. М.: Наука. 1978. 272 с.

28. Кусраев А.Г., Кутутеладзе С.С. Субдифференциалы. Теория и приложения. Новосибирск: Наука, 1992.-270 с.

29. Мину М. Математическое программирование.Теория и алгоритмы. М.: Наука. 1990. 488 с.

30. Минченко Л. И., Борисенко О. Ф. О вычислении производных по направлениям в максиминных задачах с линейными ограничениями // Ж. вычисл. матем. и матем. физ. Т. 31, № 3, 1991. С. 454-456.

31. Минченко Л. И., Борисенко О. Ф. О дифференцируемости по направлениям функции максимума // Ж. вычисл. матем. и матем. физ. Т. 23, № 3, 1983. С. 567-575.

32. Мордухович Б.Ш. Методы аппроксимаций в задачах оптимпзацик и управления. М.: Наука 1988. 360 с.

33. Нурминский Е.А. Численные методы выпуклой оптимизации. М.: Наука 1991. 168 с.

34. Полак Е. Численные методы оптимизации. Единый подход М.: Мир, 1974. - 376 с.

35. Половинкин Е.С., Балашев М.В. Элементы выпуклого и сильно выпуклого анализа. М.: ФИЗМАТЛИТ. 2004. 416 с.

36. Поляк Б.Т. Введение в оптимизацию. М.: Наука. 1983. 384 с.

37. Полякова Л,Н. Минимизации функции максимума сильно выпуклых функций с постоянным шагом // Вестник С.-Петерб. ун-та, Сер. 1, Вып. 4 (22), 1998. С. 59-63.

38. Полякова Л.Н. О методе точных штрафных квазидифференцируе-мых функций // Журн. вычисл. математики и мат. физики, Т.41, № 2,2001. С. 225-238.

39. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.: Наука. 1980. 320 с.

40. Пшеничный Б.Н. Необходимые условия экстремума. М.: Наука. 1969. 151 с.

41. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах. М.: Наука. 1976. 192 с.

42. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973. 472 с.

43. Федерер Г. Геометрическая теория меры. М.: Наука, 1987. 760 с.

44. Федоров В.В. Численные методы максимина. М.: Наука, 1979. 280 с.

45. Чебышев П.Л. Избранные труды. М.: АН СССР, 1955. 929 с.

46. Шор Н.З. О классе почти-дифференцируемых функций и одном методе минимизации функций этого класса // Кибернетика, N 4, 1972. С. 65-70.

47. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979. 200 с.

48. Borwein J. M., Zhu Q. J. A survey of subdifferential calculus with applications // Nonlinear Analysis Ser. A: Theory and methods., Volume38, 1999. P. 687-773.

49. Castellani M. A Dual Representation for Proper Positively Homogeneous Functions. // Journal of Global Optimization, Volume 16, Number 4, 2000. P. 393-400.

50. Clarke F.H., Ledyaev Y.S., Stern R.J., Wolenski P.R. Nonsmooth Analysis and Control Theory. New York: Springer-Verlag, 1998. 276 p.

51. Demyanov V.F. Exhausters and Convexificators New Tools in Nonsmooth Analysis // In: V. Demyanov and1 A. Rubinov (Eds.) Quasidifferentiability and related topics. Dordrecht: Kluwer Academic Publishers, 2000. P. 85-137.

52. Demyanov V.F. Exhausters of a positively homogeneous function // Optimization. Vol. 45, 1999. P. 13-29.

53. Demyanov V. F., Bagirov A. M., Rubinov A. M. A method of truncated codifferential with application to some problems of cluster analysis, Springer Netherlands: Journal of Global Optimization, Volume 23, Issue 1,2002. P. 63-80.

54. Demyanov V.F., Caprari E. Conically equivalent sets and their minimality // Generalized Convexity and Optimization for Economic and Financial Decisions, G. Giorgi and F. Rossi (eds.), Verona, 1998. P. 81-93.

55. Demyanov V.F., Roschina V.A. Optimality conditions in terms of upper and lower exhausters // Optimization. Vol. 55, N 5/6, 2006. P. 525-540.

56. Glover B.M., Ishizuka Y., Jeyakumar V., Tuan H.D. Complete charactirizations of global optimality for problems involving the pointwiseminimum of sublinear functions. // SIAM J. Optimization, Volume 6, Number 2, 1996. P. 362-372.

57. Ioffe A. D. Approximate subdifferentials and applications 3: the metric theory // Mathematika, Volume 36, 1989. P. 1-38.

58. Ioffe A. D. Proximal Analysis and Approximate Subdifferentials // J. London Math. Soc., Volume s2-41, 1990. P. 175-192.

59. Michel P., Penot J.-P. Calcul sous-diffe’rentiel pour les fonctions lips-chitziennes et non lipschitziennes // C.R. Acad. Sci. Paris, vol. 298, 1984. P. 269-272.

60. Mordukhovich B. S. Variational Analysis and Generalized Differentiation, I: Basic Theory, II: Applications, Grundlehren Series (Fundamental Principles of Mathematical Sciences), Vols. 330 and 331, Springer, 2006.

61. Mordukhovich B. S. Maximum principle in problems of time optimal control with nonsmooth constraints // J. Appl. Math. Mech., 40 1976. P. 960-969.

62. Mordukhovich B. S. Metric approximations and necessary optimality conditions for general classes of nonsmooth extremal problems // Soviet Math. Dokl. 22, 1980. P. 526-530.

63. Moreau J.-J. Fonctions Convexes en Dualite, Multigraph, Seminaires Mathematique, Faculte des Sciences, Univ. de Montpellier, 1962.

64. Pallaschke D., Scholtes S., Urban’ski R. On minimal pairs of compact convex sets // Bull. Polish Acad. Sci. Math. 39, 1991. P. 1-5.

65. Rockafellar R.T., Wets J.-B. Variational Analysis. Springer-Verlag, 2005. 733 p.

66. Roschina V.A. Topics in Optimization: Solving Second-Order Conic Systems with Finite Precision; Calculus of Generalized Subdifferentials for Nonsmooth Functions Supervisor Prof. Felipe Cucker// City University of Hong Kong, 2009. - 229 p.

67. Uderzo A. Convex approximators, convexificators and exhausters: applications to constrained extremum problems // Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, vol. 43, 2000. P. 297-327.

68. Warga J. Derivative containers, inverse functions and controllability // Proc. Intern. Symp. on the Calculus of Variations and Control Theory / Ed. D. L. Russell.: Acad. Press, 1976.