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

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

РГ6 ОД

£ Г. II ' На правах рукописи

ПОЛЯКОВА Людмила Николаевна

РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ ТЕОРИИ И ЧИСЛЕННЫХ МЕТОДОВ ДЛЯ РЕШЕНИЯ НЕКОТОРЫХ КЛАССОВ НЕГЛАДКИХ ЗАДАЧ ОПТИМИЗАЦИИ

01.01.07 - вычислительная математика

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

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

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

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

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

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

Гороховик Валентин Викентьевич, доктор физико-математических наук, профессор Петров Николай Николаевич.

Ведущая организация: Московский государственный университет им. М.В.Ломоносова, факультет вычислительной математики и кибернетики.

дании диссертационного совета Д 063.57.30 по защите диссертаций на соискание ученой степени доктора физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, Санкт-Петербург. Петродворец, Библиотечная пл.,д.2, магематико-механический факультет.

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

Защита состоится

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

Ученый секретарь диссертационного совета Д 003.57.30

Ю.А.Сушков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В последние десятилетия вопросы негладкого анализа и недифференцируемой оптимизации привлекают большое внимание ученых и инженеров. Негладкий анализ находит многочисленные применения в теоретической механике, теории упругости, экономике и многих других областях, но преимущественно там, где исследуются задачи экстремального характера. Поэтому в настоящее время особое внимание уделяется конструированию численных методов, позволяющих отыскивать решения подобных задач. Проблематикой негладкого анализа, в частности, развитием теоретической базы и построением численных методов, активно занимается большая группа отечественных и зарубежных математиков, среди которых Р.Габасов, В.Ф.Демьянов, Ю.Г.Евтушенко, Ю.М.Ермольев, А.Д.Иоффе, Ж.- Б. Ириа-Уррути, Ф. Кларк, Ф.М.Кириллова, Б.Ш.Мордухович, Ж.- П. Обен, Ж.-П. Пено, Б.Т.Поляк, Б. Н. Пшеничный, Р.Рокафеллар, А.М.Рубинов, В.М.Тихомиров, Х.Туй, Н.З.Шор, И.Экланд и многие другие.

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

Среди негладких оптимизационных задач одно из центральных мест принадлежит минимаксным задачам. Задача о наилучшем равномерном приближении функции многочленами рассматривалась более века

назад П.Л.Чебышевым. Дальнейшее развитие теории минимаксных задач принадлежит И.В.Гирсанову, Дж. Данскину, В.Ф.Демьянову, Я.И. Забогину, В.Н.Малоземову, Э.Полаку, Б. Н. Пшеничному, В.В.Федорову и др.

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

другие ученые.

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

Большое внимание в теории недифференцируемой оптимизации также уделяется изучению экстремальных свойств и построению численных методов минимизации разности выпуклых функций. Эта задача является актуальной, поскольку из теоремы Стоуна - Вейершхрагса следует, что любую непрерывную функцию на компакте можно аппроксимировать с нужной точностью разностью выпуклых функций. В этой области стоит отметить работы А.Д.Александрова, В.П.Булатова. Ж.Б.Ириа-Уррути, А.С.Стрекаловского, Х.Туя'и других.

В нелинейном программировании широкое распространение имеют методы штрафных функций, как внешних, так и внутренних. Решение оптимизационных задач этими методами сводится к минимизации гладких функций, так как этот аппарат наиболее хорошо изучен. Идея введения штрафной функции восходит еще к Лагранжу. Интерес к ней возродился в 60-е годы XX столетия в применении к задачам математического программирования. При этом выяснилось, что "платой'' за существование точной штрафной функции является негладкость функции, задающей ограничение. Однако прогресс в области методов недифференцируемой оптимизации позволяет преодолеть трудности, связанные с упомянутой негладкостью. Впервые существование точного штрафного параметра для задач выпуклого программирования было замечено И.И.Ереминым и У.И.Зангвилом. Впоследствии этому вопросу были посвящены работы Ю.Г.Евтушенко, В.Г.Жадана, Ди Пилло, В.В.Федорова и др.

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

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

- изучение оптимизационных свойств класса квазидифференцируемых функций: вывод необходимых и достаточных условий экстремума квазидифференцируемой функции в задачах безусловной и условной оптимизации, построение направлений наискорейшего спуска и подъема квазидифференцируемой функции в задачах оптимизации;

- конструирование численных методов минимизации некоторых классов квазидифференцируемых функций: класса гиподифференцируемых функций (функции максимума, функции суммы модулей), разности выпуклых функций;

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

Методика исследования базируется на основных фактах математического анализа, выпуклого анализа, негладкого анализа и теории математического программирования.

Научная новизна работы. Все основные результаты диссертации являются новыми. Среди них:

1) Доказаны некоторые новые факты выпуклого анализа: доказана теорема о непрерывности по Какутани конических отображений (нормальных конусов к выпуклому замкнутому множеству), предложен новый подход к вопросу построения гладкой аппроксимации выпуклых замкнутых множеств и выпуклых функций и рассмотрены свойства этой аппроксимации; найдено другое, более конструктивное представление разности выпуклых множеств, введенное В.Ф. Демьяновым.

2) Изучены экстремальные свойства квазидифференцируемых функций. Доказаны необходимые и достаточные условия оптимальности

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

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

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

5) Рассмотрен метод точных внешних штрафных функций при недифференцируемости штрафных функций; сформулированы конструктивные достаточные условия существования точного штрафного параметра.

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

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

А.В.Фурсиков); на семинаре ВЦ РАН (рук. - чл.- корр. РАН Ю.Г.Евтушенко); на семинаре Аристотелевского университета ( Греция, г. Салоники, рук. - акад. П. Панагиотопулос); на Всесоюзной конференции по динамическому управлению (Свердловск, 1979); на УП Всесоюзной конференции "Проблемы теоретической кибернетики" (Горький, 1988); на Международном советско-польском семинаре "Математические методы оптимального управления и их приложения" (Минск, 1959); на XI - ой Всесоюзной конференции "Проблемы теоретической кибернетики " (Волгоград, 1990), на III Всесоюзной школе по оптимальному управлению (Кемерово, 1990); на Всесоюзной конференции "Негладкий анализ и его приложения к математической экономике" (Баку, 1991); на Всесоюзной научной конференции "Экстремальные задачи и их приложения" (Нижний Новгород, 1992); на Международном семинаре "Многозначное исчисление и негладкий анализ" (Санкт-Петербург, 1995); на Х-ой Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 1997); на семинаре, организованном 1Х-ой Саратовской зимней школой "Современные проблемы теории функций и их приложения" (Саратов, 1998).

Публикации. Основные результаты диссертации опубликованы в работах [1-26].

Объем и структура диссертации. Диссертация состоит из введения, пяти глав, разделенных иа 28 параграфов, и списка литературы из 258 наименований. Работа изложена на 291 странице.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе приводятся вспомогательные сведения из выпуклого анализа, необходимые для дальнейшего понимания излагаемого исследования. Изложение ведется, в основном, в терминологии и обозначениях, принятых в книге Р.Рокафеллара "Выпуклый анализ" (М., Мир,

1973). В этой главе доказывается ряд новых результатов выпуклого анализа.

В §§1.1, 1.2 приводятся некоторые сведения из теории выпуклых множеств, теории многозначных отображений и теории выпуклых фупкций в конечномерном евклидовом пространстве R".

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

Теорема 3.1. Если точка хо € R" не принадлежит границе выпуклого замкнутого множества X С К'1, то коническое отображение

N{X, •) : Шп —> 2^

непрерывно по Какугпани в точке хр, где N(X,x) - нормальный конус в точке х € Ж" к множеству X С

Из этой теоремы следует непрерывность по Хаусдорфу е - субдифференциального отображения выпуклой функции.

В §1.4 вводится понятие образующего множества. Пусть К - конус в Rrt и X С М" - непустое компактное выпуклое множество, g 6 М", р{д,Х) - опорная функция множества А', ||д'(з)|| = min ||г||. Вектор

. х€9р(<7,Л")

х(д) единствен и при этом я(д) £ Л'. Положим Х(К) =-- (J х(д). Множество Х(К) для каждого конуса К определяется единственным образом. Множество Х(К) называется образующим множеством компактного выпуклого множества X относительно копуса К. В дальнейшем понятие образующего множества будет использовано при построении разности выпуклых множеств по Демьянову.

В §1.5 исследуются свойства непрерывности по Хаусдорфу е - субдифференциального отображения выпуклой функции. Доказывается при фиксированном положительном £ дифференцируемость по произвольному направлению t € в точке я £ W опорной функции £-

fdcf(x) \

субдифференциала выпуклой функции / I с — I и выводится фор-

V dq J

мула ее производной по этому направлению. Данная формула имеет более простой вид, чем аналогичная формула, полученная К.Лемаре-шалем и Е.Нурминским.

В §1.6 изучаются свойства выпуклых множеств вида Хе = А'-Н5'| (0„), где (0П) - замкнутый шар единичного радиуса с центром в нулевой точке, и свойства гладких выпуклых функций /г(х) = полу-

ченных в результате взятия инфимальпой конволюции выпуклой функции / и функции

t -foo, в остальных точках.

В диссертационной работе используется евклидова метрика.

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

Во второй главе изучаются свойства квазидифференцируемых функций и квазидифференцируемых множеств. В §2.1 приводятся основные свойства квазидифференцируемых функций.

Пусть функция / определена на открытом множестве X С Ж", в каждой точке х £ X дифференцируема по любому направлению д 6 Rn и для ее производной по направлению справедливо разложение

f'{x,g) = lim + ~ = шах (v,g)+ min <w,g). Но л veof(x) шеаДх)

где QJ(x) С К", Of{x) С К" - выпуклые компактные множества.

Функцию /, удовлетворяющую этим свойствам, будем называть ква-зидифференцируемой в точке х € А'. Пара множеств T>f{x) — [QJ'(x), Of(x)] называется квазидифференциалом квазидифференцируемой функции / в точке х, а множества QJ(x) С R" и df(x) С - соответственно, субдифференциалом и супердифференциалом квазидифференцируемой функции / в точке х. Квазидифференциал квазидифференцируемой функции определяется неоднозначно.

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

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

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

Пусть функция / квазидифференцируема на Кп, точка х* £ Ж" и Т>/(х*) — [д/(х*),0/(х*)] - ее квазидифференциал в этой точке.

Теорема 1.4

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

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

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

Пусть функция / локально липпшцева и квазидифференцируема на К", Т)/(х) = [0/(х), д/(х)] - ее квазидифференциал в точке х. Предположим, что в разложении

(1)

-№*) с э/(.г*).

(2)

/(ж + ад) = f(x) + «/'(а:,д) + о(х ,а,д)

?—— —> 0 равномерно по д £ Ж.", 9 = 1. При этих условиях о «10 справедлива

Теорема 1.6 Если в точке х* £ К" выполнено включение

-df(x*) Cint dj(x'),

то точках* есть точка строгого локального минимума функции f на Шп.

Если в точке х* 6 R" выполнено включение

-dj(x*)cMdf(x*),

то то'чка х* есть точка строгого локального максимума функции ] на Шп.

Точку х*, для которой выполняется условие (1), назовем inf- стационарной точкой квазидифференцируемой функции / на К". Точку х*. для которой выполняется условие (2), назовем sup - стационарной точкой квазидифференцируемой функции / на R". Пусть точка х не является inf - стационарной точкой для функции /, тогда направление

, . «о (ж) + и>о (я) Зо{х = --г,—т-у--—г, где

IM*) + Wo (х-) ||

max min ||i» + w|| = Цг'о(-г) + "'о(-?')|i, wB9J(*) vGäJix)

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

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

Пусть (р локально лшпницевая квазидифференцируемая на М" функция, Vip(:с) = [99(х),0уэ(л:)] - ее квазидифференциал в точке х £ I". Множество

X — {х £ М" | <р(х) < 0 }

называется квазидифференцируемым. При рассмотрении оптимизационных задач с ограничениями такого вида на функцию ¡р накладываются условия регулярности. Будем говорить, что в точке х £ X для

множества Л' выполнено условие регулярности, если справедливо равенство

Г(Л» =71 (Л',*), (4)

где Г(Л',.т) - конус Булигана в точке х £ А':

г<зд ={аеш"\ {,,} е а, ,, Ф ,, „ _ ,, ^ -> ,

Условие регулярности (4) является обобщением известных условий, таких как условие Мангасаряна - Фромовица, условие Слейтера и др., накладываемых на множество А' и функцию <,з, в задачах с гладкой целевой функцией и задачах выпуклого программирования.

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

В §2.3 изучаются свойства квазидифференцируемых множеств, задаваемых в виде функционального равенства. Пусть множество Л' представлено в виде

Л'={16Г| 9(г)=0}, (5)

где ¡р - локально липшицевая квазидифференцируемая на М" функция. Будем говорить, что в точке х € X выполнено условие регулярности, если

Г(Х,х) = 7о(Х,х). (6)

Здесь через 7о(А', х) обозначен конус

7о(А',;г)= {<,£!" | р'(г,5) = 0}.

Зафиксируем произвольную точку х 6 А'. Положим <рх(д) = €

К".

Теорема 3.1. Пусть х € А'. Если функция <рх(д) не имеет точек строгого локального минимума па конусе у0(Х,х), то в точке х для множества X вида (5) выполнено условие регулярности (6).

В выпуклом анализе при исследовании экстремальных свойств выпуклой функции с ограничениями большую роль играет нормальный конус. В §2.4 исследуются свойства конуса N(X, x) — —Г*(А', г), названного нормальным конусом в точке igÍK множеству А'.

Пусть множество X задано с помощью локально лшшшцевой квази-дифференцируемой функции ip в виде неравенства (3) и точка х Е Л', тогда справедлива

Лемма 4.3. Если в точке х виполнено условие регулярности (4). то

N(X,x) = Р| cl cone {д<р{х) + го),

где через cl (А') обозначено замыкание множества А' С К", а через cone (Аг) - коническая оболочка множества X С К".

Пусть множество X задано с помощью квазидифференцируемой функции в виде равенства (5) и точка х € Л', тогда справедлива

Лемма 4.4. Если в точке х £ X выполнено условие регулярности (6), то

N(X, х) = Pi cl (cone (d<¿(x) + w) - cone (dip(x) + i>)) . v € (hp{x) w € d<p{x)

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

Так как функция ip дифференцируема по любому направлению g (Е К", то в каждой точке х G R" справедливо разложение

<р{х + ag) = ip(x) + а<р'(х,д) + о(а, х,д),

а а |о

Будем говорить, что для функции задающей множество Л' вида (3), в точке х* (Е 1н1 (X) выполняется условие регулярности, если найдутся такие числа е(х*) > 0 и В{х*) > 0, что

Va € (0,ф*)], Ух 6 Л(Л')П5е(,.,(*♦). VgeN(X,x), ||j»||= 1,

где -4(А) = {х € Ь<1(А) | Зг ^ А', х = проекция (л)}, Ь<1 (А')- множество граничных точек множества X С К". Тогда справедлива

Теорема 5.1. Если для функции -р в каждой граничной точке множества X выполнено условие регулярности (7), то в каждой граничной точке множества X выполнено условие регулярности (4).

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

Пусть квазидифференцируемые функции / и р локально лшппицевы на Ж" и Т>/(х) — \д/(х),д/(х)], Т>1р(х) = [д_1р(х),д'-р{х)] - их квазидифференциалы в точке х 6 М". Предположим, что множество X задано в виде неравенства (3). Рассмотрим оптимизационную задачу.

Теорема 6.3. Пусть точка х* € X. Если <р{х*) = 0, то предположим, что в точке х* для множества X выполнено условие регулярности (4). Тогда для того чтобы в ятой точке квазидифференцируемая функция f достигала своего наименьшего значения на квазидифферен-цируемом множестве X, необходимо, чтобы

о\

(7)

Найти

inf f(x). j€-Y

-Of(x*) С 2/(аг*), если <р(х*) < О,

~д/(х*)С П [§/(!*)+ с1(соасШ^*)+ №'))]. (8)

Теорема 6.5. Если в точке х* ё X, ф(х*) = 0, выполнено условие регулярности (2.11), то для того чтобы в этой точке квазидифферен-цируемая функция / достигала своего наименьшего значения на квазидифференцируемом лтожестве X, необходимо, чтобы выполнялось включение

Необходимые условия, приведенные в теоремах 6.3 и 6.5, являются эквивалентными. Точку х* 6 А", <р(х*) = 0, для которой выполнено условие (8), назовем Ш - стационарной точкой квазидифференцируе-мой функции / на квазидифференцируемом множестве Л'.

Пусть точка х 6 ЛГ, -- 0, не является ш£ - стационарной точкой квазидифференцируемой функции / на квазидифференцируемом множестве X. Будем предполагать, что в этой точке выполнено условие регулярности (4). Тогда можно выписать направления наискорейшего спуска в этой точке. А именно, вектор

является направлением наискорейшего спуска квазидифференцируемой функии / в точке х на квазидифференцируемом множестве X, где точки го(а'), £о(я) € К" определяются в результате решения задачи:

9а(х) =

го(-г)-Ио(др

Цг0(зг) + «0(®)11

О > ?(х,д0{х)) = Пип /'{£,(]) = 5 е Г (Л, г)

!Ы1 = 1

1|г + *И =

где

го(а-) € д/(х) + ю0(х), и>0(я) б 01(х),

w'o(x) € д<р(х), t0(r) e cl cone (Oip(x) + u>'0(x)).

Теорема 6.9. Пусть точка x* g X, <p(x*) = 0, является точкой .минимума квазидиффсренцгьруелюй функции f на квазидифференцируемом множестве X. Тогда, если в этой точке для множества X выполнено условие регулярности (4), то для каждого w £ df(x*) и ги' £ dip(x*) найдутся число А(:с*) = А (ж*, ш, ш') < 0 и векторы

v{x*) = v(x\ w, w') € dj(x*), v'(x*) = v'{x\ w, w') e d<p(x*),

такие, что справедливо равенство

v(x*) + w +- А(ж*) («V) + «>') = On-

При некоторых предположениях на функции / и ¡¿> справедлива Теорема 6.11.

1) Пусть х* е Л", <р(х*) < 0.

Если в точке х* выполнено включение

-0f(x*) ciat9f(x*), •

то точка х* является точкой строгого локального минимума квази-дифференцируемой функции f на квазидифференцируемом множестве X.

Если в точке х* виполнено включение

-№*) eint df(x*),

то точка х* является точкой строгого локального максимума квазидиффсренцируемой функции f на квазидифференцируемом множестве X.

2) Пусть >р(х') = 0.

Если в точке х* 6 X выполнено включение

-df(x*) с int f) \df(x*) + d(conе(йф*) + «-'))],

то точка х* является точкой строгого локального минимума квази-дифференцируемой функции f на квазидифференцируемом лтожестве X , причем существуют такие числа s > 0 и S > 0, что

f{x) > f(x*) +фг- х*||, Ух € S6(x")nX. Если в точке х* € X выполнено включение

-äf{x*) С int [dfix*) - с1(соае{дф*) + «>'))] ,

то точка х* является точкой строгого локального максимульа квази-дифференцируемой функции / на квазидифференцируемом множестве X , причем сущеснгвуют такие числа е > О и 5 > О, что

f(x) < f(x*) - е\\х - II, v.r € Sj(/)nA'.

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

Предположим, что множество X задано в виде равенства (5).

Теорема 7.1. Пусть в точке х* £ X выполнено условие регулярности (6). Для того чтобы в точке х* квазидифференцируемая функция / достигала своего наименьшего значения на квазидифференцируемом множестве X, необходимо, чтобы

-df(x*)c р| [ЭДх*)-с1 (Г* («,№))].

V € chp(x*) w € дф")

Для того чтобы в точке х* квазидифференцируемая функция f достигала своего наибольшего значения на квазидифференцируемом множестве X, необходимо, чтобы

-0/ОО С Pl [ад**) + ci (Г>, „,))],

V £ д(р(х*) w е dip(x*)

где

T*(v, w) = cone (dip(x*) 4- v) — cone (<hp(x*) + iv), v £ u> £ dip{x*).

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

Пусть функция / определена на открытом множестве X С К™ и точка X £ Л'. Будем говорить, что функция / гиподифференцируема в точке х, если существует выпуклый компакт dj{x) С К"+1, такой что справедливо разложение

f{x + A) = f{x)+*x(A) + o(x,A),

где

Ф,(Д)= max Га + (и,А)], °(*'аА) —» о УД е К", [<м]е<Ш*Г « «40

а £ К1, V £ Ж", со {х, X + Д} £ А".

Семейство гиподифференцируемых функций совпадает с семейством субдифференцируемых функций. Функция / называется непрерывно гиподифференцируемой в точке х € А', если она гиподифференцируема в некоторой окрестности данной точки и если существует гиподиффе-ренциальпое отображение df : R" —»■ , непрерывное по Хаусдорфу.

Пусть / - непрерывно гиподифференцируемая функция на R", тогда несложно проверить, что для того чтобы в точке х* Е R" функция / достигала своего наименьшего на R" значения, необходимо, чтобы

о n+1 е <*/(**). (9)

Если в точке х € М" выполнено условие (9), то данная точка называется стационарной точкой функции / на М". Если в точке х условие (9) не выполняется, то для нахождения направления гипо дифференциального спуска требуется спроектировать точку 0„+1 на гиподифференциал df(x), т.е. решить оптимизационную задачу:

min |Н| = ||ф)||, z(x) = [t(x),w(x)] etfx К".

zedHx)

Направление — ю[х) называется направлением гиподифференциально-го спуска функции / в точке х на М.". Оно единственно и непрерывно по х. Это обстоятельство позволяет конструировать численные методы минимизации непрерывно гиподифференцируемых функций аналогичные градиентным методам в гладком случае.

Лемма 1.1. Если точка х не является стационарной точкой функции / на Ж", то

Пх,-Ы(х))<- ||ф)||2.

В §3.3 описывается метод гиподифференциальыого спуска для минимизации непрерывно гиподифференцируемой на К" функции. Доказывается теорема сходимости.

Опишем метод гиподифференциального спуска функции / на Ми.

Выберем произвольную точку х0 € К". Если оказалось, что 0„+1 € ¡1/(х0), то точка а:о является стационарной точкой функции /.

Пусть уже найдена точка х^ € К". Если 0,,.+1 € (//(ач), то точка хч-является стационарной точкой функции / на Ж". В противном случае, следующая точка определяется по правилу = хк — сц.м>(:гц,.), где —т[хк) = —и-'к есть направление гиподифференциального спуска в точке х/г, а шаговый множитель выбирается либо по правилу Арми-хо, либо с помощью одномерной минимизации (без ограничений или с ограничениями).

Если последовательность {¿ч} конечна, то, по построению, последняя полученная точка будет стационарной точкой / на К". Если последовательность {ач} бесконечна, то последовательность {/(яч)} будет монотонно убывающей, следовательно, данный метод будет релаксационным.

Предположим, что множество С(хп) = {а; € К" | /(х) < /(ж0)} ограничено. Тогда справедлива

Теорема 3.1. Любая предельная точка последовательности {а-*} является стационарной точкой непрерывно гиподифференцируемой ф\)нкции / на М".

Очевидно, что наиболее трудоемким шагом в данном методе является нахождение направления гиподифференциального спуска. Задача

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

В §3.5 приводится метод минимизации с постоянным шагом функции максимума сильно выпуклых функций.

Пусть

f(x) = max ji(x), tei

где fi(x), г £ I = {1,...,ä}, - дважды непрерывно дифференцируемые сильно выпуклые на R" функции. Пусть т > 0 - константа сильной выпуклости функции /. Рассмотрим оптимизационную задачу.

Найти

min f[x).

•rgR"

Предположим, что существует такая константа М > 1, что выполнено неравенство

(f"{x)w, w) < м\и |2 v.r € R", Vw е r\ Vi е I,

где /¡'(х) - матрицы вторых производных функций /г- в точке х.

С каждой точкой х € К™ свяжем оптимизационную задачу

min max {(/¡(г) - f(x))M + {Г,(х),гг) + 1||„,||2) = (10)

гобк" 16/ (_ Z J

= max |(/,-(*) - f(x))M + (fi{x), w(x)) + ¿|М*)||2}.

Метод гиподифференциального спуска для минимизации гиподиф-ференцируемой функции на М." состоит в следующем.

Выберем произвольную точку го 6 И.". Если выполнено включение 0п 6 (//(.г0), то точка ./'о - точка минимума функции / на К™, и процесс останавливается.

Пусть уже найдена точка х^ g R". Предположим, что точка хд. не является точкой минимума функции / на К." ( 0n £ df(xk)). Найдем направление iv(x¡,), то есть, решим оптимизационную задачу (10) при X — Xk- Положим

« = Y7 и Xfc+1 = Xk + Спс(хк).

Пусть последовательность точек бесконечна. Тогда справед-

лива

Теорема 5.1. В данном методе при произвольной начальной точке .го € М" последовательность {а-ч} сходится к точке минимума х* функции f на М" со скоростью геометрической прогрессии:

f{Xk+i)-f(x*)<q(J(xk)-f (**)),

где q = 1 — —, и существует такое положительное число Q, что спра-М

ведливо неравенство

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

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

Пусть

/(*) = /!(*)-/2(*), xeR'\

где /], /2 - конечные выпуклые на R" функции. При рассмотрении задачи минимизации функции j на R" предположим, что doin С doni /*, где f* 1 ¡2 ' функции, сопряженные к функциям /ь/21 соответственно.

Положим

Л®) = /2»-Л», «6Rn,

r(v)=i f°(»), vedom/i,

J~K ' I+OO, v 0 dorn fi.

При этих предположениях справедлива

Теорема 1.2. Пусть т,очка, х* 6 К" является точкой глобального минимума функции f на R", тогда любой субградиент v* 6 dft{x*) явлется точкой глобального минимума функции на Е™.

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

I+оо, 1М1>е\

Образуем гладкие функции /) Е и /■/ > путем взятия инфимальной конволюции функций /2 с функцией

Ы*) = (Ше)(*), /2е = (Ше)(х), X 6 М".

Положим

Л(*) = Ы*)-Ы*)> геа».

Тогда верна

Теорема 2.2. Если точка х* £ Ж.™ является стационарной точкой функции /£ ив К11, то в точке

= х -

\А+Ш**)1Ги ' л/1 + \№е{*'

справедливы соотношения

/(О = Л(^), /;г(ж*) = /Ж) е [ад (г*) П 0/2(г*)].

В §4.3 строится релаксациопный метод минимизации разности выпуклых функций на К™, на каждом шаге которого в качестве вспомогательной задачи решается задача минимизации сильно выпуклой функции. Доказывается теорема сходимости. Приводятся различные модификации данного алгоритма.

Рассмотрим задачу минимизации функции

/(.г )=Мх)-Мх), х£Ш'\

где fi, /2 - конечные сильно выпуклые на Ж" функции с константой сильной выпуклости т > 0. Если точка х* £ К™ является точкой минимума функции / на R", то справедливо включение

дЫх*)сдМх*), (11)

где dji(x*) - субдифференциалы функций /¿, г = 1,2, d точке х*. Если в точке х* £ Ж" выполнено условие (11), то точка х* называется inf -стационарной точкой функции / на Ж".

Поскольку обе функции /1 и /2 сильно выпуклы, то, в силу свойств сильно выпуклых функций, функция

/» = /2»-/i»> является непрерывно дифференцируемой на М" и при этом

inf f(x) = inf f°(v). л-effi" ^ ueiR" v y

Таким образом, задача нахождения глобального минимума функции / на R™ эквивалентна задаче нахождения глобального минимума непрерывно дифференцируемой функции f на К.'1.

Зафиксируем точку 2 £ R" и произвольный субградиент w(z) € df2(z). Положим

Функция ф(х,г), как функция аргумента х, сильно выпукла на ¡R" с константой сильной выпуклости т > 0 при каждом фиксированном и iv(z) £ dj')(z). Следовательно,

inf f(x)= inf inf гЬ(х,г)— inf min ti(x\z).

В методе минимизации исходной функции / на каждом шаге решается задача минимизации на К" сильно выпуклой функции ip. 1. Выберем произвольную точку хо £ 3R". Если

<?/г(ж0) С dfi(xo),

то точка .г« - inf-стационарннл точка функции / па М" и процесс закончен.

2. Пусть найдена точка хк £ R™, которая не является mf-стационар-ной точкой функции / на R"'. Тогда выберем произвольный субградиент wk — w(xk) £dfi(xk). Положим

срк(х) = ф(х, Хк) = f\ (х) - 12(хк) - {il'fc, X - Хк).

Найдем

min <рк(х) = <pk{xk+i). Тогда справедливы неравенства

Хк-Хк+[ -(П'К).

/(•T/t+i) < f(xk) - 2m||.rfc+i -a-fcll'2, f («»fe) < /"(«'fc-i) - Trl(llxM-i - -Tfcll2 + IK- - xfc-i||2) =

3. Если

0/2(^+1) С dfl(xk+1),

то процесс закончен, в противном случае переходим к шагу 2.

Если последовательность {ж;,} конечпа, то, по построению, последняя полученная точка является inf-стационарной точкой функции f на Ж".

Рассмотрим случай, когда последовательность {а:*,.} бесконечна.

оо

Теорема 3.1. Если ряд ll^i'+i ~ -тг||~ расходится, то функция /

;=о

неограничена снизу. Если данный ряд сходится и множество С(х0) — {з; G Ж." | /(ж) < /(а'о)} ограничено, то справедливо соотношение

(ГУЫхк)) о.

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

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

т{Л х) = Г, (12)

.тел

где / - локально литпицсвая квазидифференцируемая на Кп функция. Пусть множество X задано в виде

Х = {1£Г |<^(ж) = 0},

где >-р - также локально липшицевая квазидифференцируемая на К" функция, и

9 (а;) >0 Ух 0 А'.

Множество X есть замкнутое множество точек глобального минимума функции ¡р на К". Предположим, что множество X С М" непусто, ограничено и не состоит из изолированных точек.

Как обычно, для решения задачи (12) вводится штрафная функция

Р(с,х) = Г(х) + ар(х),

где с - некоторое неотрицательное число. Затем рассматривается задача безусловной минимизации:

iiif F(c,x), »es"

Особый интерес представляют точные штрафные функции, т.е. функции, для которых существует такой штрафной параметр с* (называемый точным штрафным параметром), что для любых с > с* множество точек минимума функции F(c, х) на К" будет совпадать с множеством

решений исходной задачи (1.1). Очевидно, что любое число, превосходящее точный штрафной параметр, является также точным штрафным параметром.

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

Поскольку при решении практических задач точный штрафной параметр заранее неизвестен, то строится последовательность чисел {с*,}, члены которой удовлетворяют условиям

О = со < ci < ■ ■ ■ < ск < ..., lim ск = +со.

к—>+оо

Затем определяются точки

х(ск) = arg min F(x,ck). •reu.

Теорема 1.2. Пусть множество X ограничено и для функции ¡р выполнено условие регулярности (7). Тогда для данного семейства штрафных функций F(ck,x) существует точный штрафной параметр с*, то есть,

x(ck)£ X Vcк>с*.

Заметим, что величина штрафного параметра с* прямо пропорциональна константе Липшица функции / на множестве

£(»")= {г

где х** = min fix), и обратно пропорциональна числу ß(x*), где точка ¡r£R"

х* - предельная точка последовательности {.;'(<"(,.)}. Причем в данном методе используется условие регулярности (7) только в окрестности

точки х*. При конструировании методов точных штрафов такого типа существенна недифференцируемость функции ¡р в граничных точках множества X.

В §5.2 более детально рассматривается метод точных штрафных функций в задачах выпуклого и нелинейного программирования. Рассматривается вариант использования метода точных штрафных функций при решении задачи выпуклого программирования, когда целевая функция и функции, задающие ограничения, являются сильно выпуклыми квадратичными функциями.

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

Автор благодарит Российский Фонд Фундаментальных Исследований за финансовую поддержку работы на ее заключительном этапе в рамках гранта 97-01-00499.

Основные работы автора по теме диссертации:

1. Войтон Е.Ф., Полякова JI.H. Об одном классе задач при связанных ограничениях // В кн.: Оптимизация, Новосибирск, вып.10. - 1973. - С. 41-46.

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

3. Демьянов В.Ф., Полякова Л.Н., Рубинов A.M. Об одном обобщении понятия субдифференциала //В кн.: Тезисы Всес. конф. по динамическому управлению. - Свердловск: 1979. - С. 79-84.

4. Полякова JI.H. Непрерывность нормальных конусов // Вестн. Ленингр. ун-та,- 1979. - N 7. - С. 112-113.

5. Полякова JI.H. Необходимые условия экстремума квазидиффе-ренцируемых функций // Вестн. Ленингр. ун-та. - 1980, - N 13. - С.

57-62.

0. Полпкопа Л.Н. Нормальный конус. Коническое отображение// В кн. Демьянов В.Ф., Васильев Л.В, Недифференцируемая оптимизация. - М.: Наука, 1980. - С. 137-140.

7. Полякова Л.Н. Необходимые условия оптимальности на М"// В кн. Демьянов В.Ф., Васильев Л.В. Недифференцируемая оптимизация. - М.: Наука, 1980. - С. 214-220.

8. Полякова Л.Н. Необходимые условия экстремума квазидиф-ференцируемой функции при квазидифференцируемом ограничении // Вестн. Ленингр. ун-та. - 1982,- N 7. - С. 75-80.

9. Полякова Л.Н. Об одной задаче негладкой оптимизации // Кибернетика, - 1982,- N 2,- С. 119 - 122.

10. Полякова Л.Н. О множестве возлюжных направлений в задачах со связанными ограничениями // Вестн. Ленингр. ун-та. - 1984,- N 1. - С. 32-37.

11. Полякова Л.Н. Достаточные условия локального экстремума квазидифференцируемой функции при квазидифференцируемом ограничении // Вестн. Ленингр. ун-та.- 1985. - N 22. - С. 26-30.

12. Полякова Л.Н. О гладкой аппроксимации выпуклой функции // Вестн. Ленингр. ун-та. - 1989. - Вып. 3. - Сер.1 - С. 31-34.

13. Полякова Л.Н. О минимизации разности выпуклых функций // Тезисы Международного советско-польского семинара. Мат. методы оптимального упр. и их приложения.Минск. - 1989. - С. 216-217.

14. Полякова Л.Н. Минимизация отношения функции максимума к функции минимума //В кн. Теория систем управления. Вопросы механики и процессов управления. Изд-во СПбГУ. - 1992. - Вып.15. -С. 150-153.

15. Полякова Л.Н. Условия оптимальности в задачах квазидифференциального исчисления //В кн. Вопросы механики и процессов управления. Изд-во СПбГУ. - 1995. - Вып.16. - С. 20-51.

16. Полякова Л.Н. Минимизация некоторых классов негладких функций //В кн. Мат.вопросы анализа негладких моделей. Вопросы механики и процессов управления. Изд-во СПбГУ. - 1995. - Вып.16. -С. 52-61.

17. Полякова Л.Н. Субдифференциал Кларка разности функций максимумов // Вестн. Санкт-Петерб. ун-та. - 1996. - Вып. 3.- Сер.1. -С. 121-123.

18. Полякова Л.Н. Разность выпуклых множеств//Вестн. Санкт-Петерб. ун-та. - 1998. - Вып. 1,- Сер.1. - С. 29 -35.

19. Demyanov V.F., Polyakova L.N., Rubinov A.M. Quasidifferential calculus and application // ICM Warszava.- 1983. - Section 9. - Part 1. - P. 48.

20. Demyanov Y.F., Polyakova L.N., Rubinov A.M. Nonsmoothness and quasidifferentiability // Mathematical Programming Study. - 1986. - V. 29. -P. 1-19.

21. Dem'yanov V.F., Stavroulakis G.E., Polyakova L.N. Quasidifferentiability in nonsmooth, nonconvex Mechanics // Journal of Global Optimization. -1995. - N 6.- P. 327-345.

22. Dem'yanov V.F., Stavroulakis G.E., Polyakova L.N., Panagioto-poulos P.D. Quasidifferentiability and nonsmooth modelling in Mechanics, Engineering and Economics. Kluwer Academic, Dordrecht, 1996. - 350p.

23. Polyakova L.N. On the minimization of a quasidifferentiable function subject to equality-type quasidifferentiable constraints // Mathematical Programming Study. - 1986. - V.29. - P. 44-55.

24. Polyakova L.N. On minimizing the sum of a convex and a concave function // Mathematical Programming Study. - 1986. - У.29. - P. 69-73.

25. Stavroulakis G.E., Polyakova L.N. Difference convex optimization techniques in Nonsmooth computational Mechanics // Optimization Methods & Software. -1996. - V.7. - P.57-81.

26. Stavroulakis G.E., Polyakova L.N. Nonsmooth and nonconvex structural analysis algorithms algoritms based on difference convex otimization techniques // Structural Optimization, Springer - Verlag. - 1996. - N 12. - P. 167-176.

/7Г, . А ^.м.^-зого/о^

* \ ч У

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

УНИВЕРСИТЕТ

На правах рукописи

ПОЛЯКОВА Людмила Николаевна

РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ ТЕОРИИ И ЧИСЛЕННЫХ МЕТОДОВ ДЛЯ РЕШЕНИЯ НЕКОТОРЫХ КЛАССОВ НЕГЛАДКИХ ЗАДАЧ

ОПТИМИЗАЦИИ

01.01.07 - вычислительная математика

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

Г^езид ^ России

19 г., №

Iя УДКА ученую ет^^нъ Л*

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

ОГЛАВЛЕНИЕ

Список используемых обозначений ................................ 5

ВВЕДЕНИЕ .........................................................10

ГЛАВА 1

НЕКОТОРЫЕ ВОПРОСЫ ВЫПУКЛОГО АНАЛИЗА.......... 31

1.1. Выпуклые множества. Многозначные отображения........ 31

1.2. Выпуклые функции........................................... 39

1.2.1. Основные определения и свойства...........................39

1.2.2. Сопряженная функция........................................ 41

1.2.3. Субдифференциал Выпуклой функции....................... 43

1.2.4. Инфимальная конволюция выпуклых функций.............. 45

1.2.5. Необходимые и достаточные условия минимума выпуклой функции............................................ 48

1.3. Нормальный конус........................................... 49

1.4. Опорная функция............................................. 55

1.5. е - субдифференциал выпуклой функции....................66

1.5.1. Геометрическая интерпретация £ - субдифференциала .... 67

1.5.2. в - производная по направлению выпуклой функции....... 59

1.6. Гладкая аппроксимация выпуклых функций................ 74

1.7. Разность выпуклых множеств ............................... 82

Г Л А В А 2

КВАЗИДИФФЕРЕНЦИРУЕМЫЕ ФУНКЦИИ КВАЗИДИФФЕРЕНЦИРУЕМЫЕ МНОЖЕСТВА .............. 90

2.1. Основные свойства квазидифференцируемых функций.....90

2.1.1. Основные формулы квазидйфференциального исчисления . 92

2.1.2. Необходимые и достаточные условия оптимальности квазидифференцируемой функции на Мп .................... 95

2.2. Условия регулярности для квазидифференцируемых

множеств..................................................... 99

2.3. Условия регулярности для квазидифференцируемых

множеств типа "равенств" ................................... 113

2.4. Нормальный конус к квазидифференцируемому множеству 116

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

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

2.6.1. Необходимые условия оптимальности....................... 124

2.6.2. Направления наискорейшего спуска и подъема............ 133

2.6.3. Достаточные условия локальных экстремумов.............137

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

2.7.1. Необходимые условия оптимальности....................... 140

2.7.2. Направления наискорейшего спуска и подъема............. 144

2.7.3. Достаточные условия локальных экстремумов............. 146

2.8. Субдифференциал Кларка квазидифференцируемых функций....................................................... 149

Г Л А В А 3

МИНИМИЗАЦИЯ ГИПОДИФФЕРЕНЦИРУЕМЫХ ФУНКЦИЙ .......................................................... 157

3.1. Гиподифференцируемые функции ........................... 157

3.1.1. Определения и основные свойства .......................... 157

3.1.2. Необходимые условия минимума гипо дифференцируемой функции ...................................................... 163

3.2. Связь между гиподифференциалом и е-субдифференциалом полиэдральной функции...................................... 167

3.3. Метод гиподифференциальноГо спуска ..................... 170

3.3.1. Безусловная минимизация .................................. 170

3.3.2. Условная минимизация ...................................... 175

3.4. Отыскание направления гиподифференциального спуска .. 177

3.5. Минимизация с постоянным шагом функции максимума сильно выпуклых функций................................... 182

3.6. Минимизация разности максимумов гладких функций.....189

Г Л А В А 4

МИНИМИЗАЦИЯ РАЗНОСТИ ВЫПУКЛЫХ ФУНКЦИЙ .... 198

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

4.1.1. Задача безусловной оптимизации........................... 198

4.1.2. Задача условной оптимизации............................... 213

4.2. Гладкая аппроксимация разности выпуклых функций ..... 215

4.3. Релаксационные методы минимизации разности выпуклых функций ...................................................... 220

4.4. г - методы минимизации разности выпуклых функций ..... 232

Г Л А В А 5

КВАЗИДИФФЕРЕНЦИРУЕМЫЕ ШТРАФНЫЕ ФУНКЦИИ ... 239

5.1. Точные штрафные функции ................................. 239

5.2. Выпуклый случай.

Задача классической оптимизации ......................... 251

5.3. Условная минимизация разности выпуклых функций ...... 266

ЛИТЕРАТУРА..................................................... 271

Используемые обозначения

3Rn - евклидово пространство размерности п, Оп - нулевой элемент пространства Rn, cl (X) - замыкание множества Ici",

int (X) - множество внутренних точек множества X С №п,

bd (X) - множество граничных точек множества 1сКп,

Lin (X) - линейная оболочка множества X С Мп,

L1- - ортогональное дополнение линейного пространства L,

äff (X) - аффинная оболочка множества X С Rn,

ri (X) - относительная внутренность множества X С Ш.п,

cone (X) - коническая оболочка множества X С Мп,

со (X) - выпуклая оболочка множества X С М",

ext (X) - множество экстремальных точек множества X С К

rext (X) - множество экстремальных лучей множества X С I

exp (X) - множество экспонированных точек множества X С

rexp X - множество экспонированных лучей множества X С

(х, у) ~~ скалярное произведение векторов х G Жп и у G Мп,

\\х\\ - евклидова норма вектора х G Еп:

INI =

К* - конус сопряженный конусу К:

к* = {w g мп | (v,w) >о Vue к}, Sr(x) - замкнутый шар радиуса г с центром в точке х G Мп:

Sr(x) = {yeRn\ \\у-х\\<г}, Вг(х) - открытый шар радиуса г с центром в точке х G IRn:

Br(x) = {у G Rn I ||y-a;||<r },

n

)П

)П

)П

О, х £ X, +оо, х £ X,

р(д,Х) - опорная функция множества X:

р(д,Х) = sup (х,д),

хех

6(х,Х) - индикаторная функция множества X:

6(х,Х) = {

fi(x,X) - калибровочная функция множества X:

ц(х, X) = inf{A >0\х е XX}, (fiOf2)(x) - инфимальная конволюция функций /1 и /2 в точке х:

(ЮЬ)(х)= inf {/1Ы + /2Ы},

Xi Х2 = х

xi,x2 £ Mn /* - функция, сопряженная к функции /:

f*{v) = sup {(ж,?;) - /(ж)},

п.

/'(ж) - градиент непрерывно дифференцируемой функции / в точке

ж е мп,

/'(х, <7) - производная до направлению д 6 функции / в точке 6

у Л4.0 Л

де!(х)

дд

жег

- е- производная по направлению д € Мп функции / в точке def(x) _ . f f(x + Лд) - f(x) + £

дд А>о Л

f'cl(x,g) - обобщенная производная Кларка по направлению д G функции / в точке G Ми,

) п

/н(х,д) - производная Адамара по направлению д Е Мп функции / в точке Е

д/(х) - субдифференциал выпуклой функции / в точке х Е К",

дf(x) = { V Е Еп | ¡(г) - ¡(х) >{и,г- х) Чх € Мп }, д£/(х) - £>субдифференциал выпуклой функции / в точке х Е Мп,

дЕ/(х) = { V Е Жп | ¡(г) - ¡(х) > (V, г - х) - е Ух Е Еп } дс1${%) ~ субдифференциал Кларка липшицевой функции / в точке

Vf{x) - квазидифференциал квазидифференцируемой функции / в точке ж Е Жп,

д$(х) - субдифференциал квазидифференцируемой функции / в точке ж Е

дf(x) - супер дифференциал квазидифференцируемой функции / в точке х Е Еп,

0/(х) - кодифференциал кодифференцируемой функции / в точке х Е

<И{х) - гиподифференциал кодифференцируемой функции / в точке ж Е Мп,

с1/(х) - гипердифференциал кодифференцируемой функции / в точке х Е М",

Г(Х, х) - конус Булигана в точке х Е X ,

Г(Х, х) = Е Мп | {ж*} Е X, хк ф х,

Ж/г-Ж д

\\xk-xW 1Ы1Г

Ы(Х, ж) - нормальный конус в точке х £ X,

7(Х, ж) = {д Е Мте | З^о > 0 х + ад еХ Уа Е [0, а0) } , х £ X, 71(Хух) = {деШп\Г(х,д)<0}, х Е X,

)П.

7о (X, х) = {д £ | ?{х, д) = 0 } , же X, 1_(Х,х) = {детп\Г(х,д)<0}, хех: 1+(Х,х) = {деШп\Г(х,д)>0}, х е х, 8(А, В) - уклонение множества X С Мп от множества У С

¿(Х,У) = 8ир -г/Ц,

рн(Х,У) - хаусдорфово расстояние между множествами X и У:

рн(Х,У) =тах{5(Х,У),5(У,Х)}, рх(у) ~ расстояние от точки у до множества X:

рх(у) = ||аг-2/||, X + У - сумма выпуклых множеств X С Мп и У С №п:

Х + У = {х + у\х£Х, у е У},

ХЧ-У - разность Минковского-Понтрягина двух выпуклых множеств ХсГиГсГ:

Хч-У = {г ег \г + У сх },

Тх - множество точек д Е М", в которых дифференцируема опорная функция р(д, X) компактного выпуклого множества X С Кп, X—У - разность Демьянова выпуклых компактных множеств X С Мп и У С мп:

я = = с1 СО {* = р'(д, X) - У), <7 € Т* П Ту} ,

)П

X - У = с1 со и {х(д) - у(д)} , где 1,Ус1и - выпуклые компакты,

Х(К) = и х(д), где 1с1"~ выпуклый компакт, дек

X = и х(д), где Хс1п~ выпуклый компакт,

д£Шп

рг {г) - проекция точки г Е Мп,

Л{Х) = {х Е ьа (X) | 32 0 X, ж = рг (2)}.

ВВЕДЕНИЕ

В последние десятилетия вопросы негладкого анализа и недиффе-ренцируемой оптимизации привлекают большое внимание ученых и инженеров. Негладкий анализ находит многочисленные применения в теоретической механике, теории упругости, экономике и многих других областях, но преимущественно там, где исследуются задачи экстремального характера. Поэтому в настоящее время особое внимание уделяется конструированию численных методов, позволяющих отыскивать решения подобных задач. Проблематикой негладкого анализа, в частности, развитием теоретической базы и построением численных методов, активно занимается большая группа отечественных и зарубежных математиков, среди которых Р.Габасов, В.Ф.Демьянов, Ю.Г.Евтушенко, Ю.М.Ермольев, А.Д.Иоффе, Ж.- Б. Ириа-Уррути, Ф. Кларк, Ф.М.Кириллова, Б.Ш.Мордухович, Ж.-П. Обен, Ж.-П. Пено, Б.Т.Поляк, Б.Н.Пшеничный, Р.Рокафеллар, А.М.Рубинов, В.М.Тихомиров, Х.Туй, Н.З.Шор, И.Экланд и многие другие.

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

В первой главе рассматриваются некоторые вопросы выпуклого анализа. Выпуклый анализ является одним из наиболее глубоко исследованных разделов негладкого анализа. В отсутствие гладкости свойство выпуклости дает возможность использовать богатый набор аналитических средств для развития содержательной теории условий экстремальности. Выпуклые множества и выпуклые функции -основной инструмент в теоретических исследованиях во многих вопросах недифференцируемой оптимизации. В этой главе формулируются некоторые известные сведения из выпуклого анализа, так как они необходимы для дальнейшего понимания излагаемого материала. Их доказательство можно найти в литературе по выпуклому анализу, например, в [98,138,147,195,196]. Также в этой главе доказывается ряд новых результатов выпуклого анализа. Изложение материала ведется, в основном, в терминологии и обозначениях, принятых в книге Р.Рокафеллара "Выпуклый анализ" (см. [153]). функций справедливо и обратное свойство, а именно, если ее субдифференциал в некоторой точке состоит из единственного субградиента, то в этой точке функция непрерывно дифференцируема. Роль субдифференциала в выпуклом программировании почти такая же, как и роль градиента в случае оптимизации гладких функций. С его помощью выписываются необходимые и достаточные условия минимума выпуклой функции, строятся численные методы, как при наличии ограничений, так и без ограничений. Так как субдифференциальное отображение не является непрерывным по Хаусдорфу, то это представляет большую трудность при конструировании численных методов.

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

Теорема 3.1. Если точка хо £ Мп не принадлежит границе выпу-

клого замкнутого множества X С М.п, то коническое отображение

ЩХ, •)

)П

непрерывно по Какутани в точке где х) - нормальный конус

в точке х Е Мп к множеству X С К".

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

Пусть К - конус в Г и I С 1" - непустое компактное выпуклое множество, д € Мп,

х€др(д,Х)

Вектор х(д) единствен и при этом х(д) € X. Положим

Х(К) = У х(д). дек

Множество Х(К) для каждого конуса К определяется единственным образом. Множество Х(К) называется образующим множеством компактного выпуклого множества X относительно конуса К. Если К = М.п, то примем обозначение X = Х(ЖП). Таким образом, зная образующее множество, мы можем восстановить и само множество. В дальнейшем понятие образующего множества будет использовано при построении разности Демьянова выпуклых множеств.

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

Хаусдорфу е - субдифференциального отображения выпуклой функции по х € М.п и е > 0. Впервые факт непрерывности по Хаусдорфу £ - субдифференциального отображения был отмечен Рокафел-ларом (см. также работы Нурминского [129,130]) Таким образом, в силу этих свойств £ - субдифференциального отображения выпуклой функции / при £ > 0, опорная функция £ - субдифференциала конечной выпуклой на Мп функции / в точке жо € К.п

max (viq)=p(q1def(x0))1 g € Rn,

oq ved£f(x0)

является непрерывной не только по параметру q £ Мп, но и по х Е Шп.

В этом параграфе также доказывается дифференцируемость по на-

d£f(x о)

правлениям функции —^—- и выводится ее производная по напра-

oq

влению t € К™. Данное представление имеет более простой вид, чем представление, полученное К.Лемарешалем и Е.Нурминским [207] (см. также [68,107]).

В шестом параграфе этой главы для произвольного выпуклого замкнутого множества строится его аппроксимация "гладкими" выпуклыми множествами.

Пусть X С Шп - выпуклое замкнутое множество и £ > 0. Рассмотрим множество Хе — X + e5i(0n,). При этих предположениях справедлива

Теорема 6.1. При фиксированном £ > 0 в произвольной граничной точке Xq £ bd (Х£) нормальный конус к множеству Х£ в точке xq состоит из единственного луча.

Далее изучаются свойства функции /е(х) — (fUt£)(x), которая получена в результате инфимальной конволюции выпуклых функций / и te, где

tc(x) = / -л^2 - № IWI<*.

( +оо, в остальных точках.

Надграфиком функции /е будет множество epi f£ — epi / + £5i(0n.fi).

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

X-Y= U Ш-у(д) ], деШп

дфоп

где х(д),у(д) - элементы образующих множеств X С X С С

Y С Мп, соответственно, можно считать невыпуклой разностью двух непустых выпуклых компактных множеств.

Во второй главе изучаются свойства квазидифференцируемых функций и квазидифференцируемых множеств. Понятия квазидиффе-ренцируемой функции и квазидифференциала были введены Демьяновым и Рубиновым [232] и изучены автором в работах [231,232,234, 237,238,240].

Пусть функция / определена на открытом множестве X С в каждой точке х £ X дифференцируема по любому направлению д £ Мп и при этом для ее производной по направлению справедливо разложение

/ (я, д) = lim-г-= max {v, д) + min (w, д),

А4.0 Л «€9Д®) wedf(x)

где df(x) С М», df(x) С М.п, - выпуклые компактные множества.

Функцию /, удовлетворяющую этим свойствам, будем называть квазидифференцируемой в точке х £ X. Пара множеств T>f(x) = [df(x), df(x)] называется квазидифференциалом квазидифференцируемой функции / в точке х, а множества df(x) С Мп и df(x) С Мп, соответственно, - субдифференциалом и супердифференциалом квазидифференцируемой функции / в точке х. Поскольку квазидифференциал квазидифференцируемой функции / в точке х £ Rn определен

неоднозначно, то множества и д/(х) должны рассматриваться

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

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

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