Некоторые задачи негладкой оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

%

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

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

АБАНЬКИН Александр Евгеньевич

НЕКОТОРЫЕ ЗАДАЧИ НЕГЛАДКОЙ ОПТИМИЗАЦИИ

Специальность: 01.01.09. "Математическая кибернетика"

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

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

Турсве1 Ьу Л/и^-ТеХ

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

Научный руководитель -

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

Демьянов В.Ф.

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

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

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

Даугавет В.А.

Ведущая организация: Вычислительный Центр РАН, Москва.

Защита диссертации состоится ЛИЗА?? 199 Сг- в пИ£п часов на заседании диссертациоиного совета К-063.57.16 по защитам диссертаций на соискание ученой степени кандидата физико-математических наук в Санкт-Петербургском Госуниверситете по адресу: 198904, Петродворец, Библиотечная пл. 2, факультет Прикладной математики - Процессов Управления.

С диссертацией можно ознакомиться в научной библиотеке им. А.М.Горького Санкт-Петербургского Государственного Университета

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

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

Ученый секретарь

диссертационного совета,

д.ф.м.н.

Горьковой В.Ф.

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

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

В хорошо известной работе А.Д. Александрова (1949) ставился ряд задач в рамках теории внутренней геометрии выпуклых поверхностей. Одну из этих задач можно сформулировать как задачу отыскания минимальной пары двух выпуклых компактных множеств в классе эквивалентности, который определяет эта пара. Различными авторами предпринимались неоднократные попытки решить эту задачу и предложить алгоритм построения минимальной пары. Вероятно, первой в этом направленнии была работа В.А. Залгал-лера (1963). В ней был дан алгоритм построения минимальной пары в пространстве М2 для произвольных выпуклых компактов, но приемлемым для вычислений он оказался только в случае многогранных множеств. С развитием теории квазидифференцируемых функций встал вопрос о нахождении минимального квазидифферен-пиала, что в свою очередь усилило актуальность задачи поиска решения обсуждаемой задачи. Для нахождения минимального квазидифференциала М. Хандшутом был предложен алгоритм в случае многогранных множеств в пространстве К2 (1989). Позднее, в ряде работ немецкой школы математиков ( Д. Паллашке, С. Шолтес, Р. Урбанский ) было конкретизировано понятие минимальной пары и

в соответствии с ним доказало, что в К2 такая пара единственна с точностью до сдвига. Там же было показало, что в пространстве размерности 3 и выше минимальная пара неединственна и, более того, множество минимальных пар в одном классе эквивалентности имеет мощность континуума. Заметим также, что в этих работах не были указаны эффективные алгоритмы построения минимальных пар, пригодных для практических вычислений. Конструктивный алгоритм построения минимальной пары в пространстве К2 для произвольных множеств был представлен Демьяновым В.Ф. на международной симпозиуме "Многозначные отображения и негладкий анализ-95" в Санкт-Петербурге. На данном этапе актуальными задачами являлись обоснование алгоритма и создание программного обеспечения.

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

Цель и задачи исследования. Цель работы заключалась в решении ряда теоретических и практических вопросов в области негладкого анализа. Перед диссертантом были поставлены следующие задачи:

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

2. Разработать конструктивные численные методы решения квазилинейных и колинейных систем,

3. Построить алгоритм для нахождения минимальной пары двух выпуклых компактов в их классе эквивалентности (в случае пространства И2), доказать единственность минимальной пары с точностью до сдвига в пространстве К2,

4. Создать пакеты программ, реализующих разработанные алгоритмы, провести численные экперименты.

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

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

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

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

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

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

Апробация работы. Основные результаты были представлены на семинарах кафедры Математической Теории Моделирования Систем Управления факультета Прикладной Математики - Процессов Управления СПбГУ(1992-1995), на семинаре кафедры Исследования Операций Математико-Механического факультета (1995), в Вычислительном Пентре РАН (1995), на Международном симпозиуме "Set-valued Mapping and Nonsmooth Analysis-95" (СПбИМ им. Стеклова, 1995).

Публикации. По материалам диссертации опубликовано 2 печатные работы.

Объем и структура работы. Диссертация состоит из введения с аналитическим обзором литературы, главы с предварительными сведениями, трех глав, содержащих основные результаты, и приложения с программным обеспечением. Работа изложена на 108 страницах, содержит 5 рисунков; список цитируемой литературы включает 58 наименований.

s

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

Пусть X С R" - выпуклое открытое множество. Функция / : X —> R называется квазидиффсренцируемой в точке х £ S, если она дифференцируема в этой точке по всем направлениям и если существуют выпуклые компакты dj(x) С R", д/(х) С R", такие, что

f'{x,g):=]im-[f(x+ag)-f(x)] = max (v,g)+ min (w,g).

«10 a v€ö/(i) wB8f(x)

Множества д/(х) и df(x) называются соответственно субдифференциалом и супердифференциалом функции / в точке х. Пара множеств Vf(x) = [df{x),df(x)] называется квазидифференциалом функции / в точке х. Очевидно, что квазидифференциал определяется неоднозначно.

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

необходимое условие минимума на R"

~df{x') С №*), необходимое условие максимума

-№") с д/(х**),

достаточное условие строгого локального минимума

-df(x*) С mtdj(x"),

достаточное условие строгого локального максимума

-äf{x") С midj(x").

Будем говорить, что функция /, заданная и конечная на X, кодиф-ференцируема в точке х, если существуют такие выпуклые компакты df(x) С Rn+1 и df(x) С что

f(x + Д) = f(x) + Фх(Д) + ох( Д),

где

Ф*(А) = [..3SSkJa + + ьА/+{щх}]'

о УД € R».

а

Здесь a,b £ R;v,w 6 R". Естественно, здесь предполагается, что со{х,я + Д} С X.

Пара множеств Dj(x) — [dj(x), df(x)} называется кодифферепци-алом функции / в точке х, множество df(x) называется гиподиффе-ренциалом, множество dj(x) - гипер дифференциал ом.

Пусть f(x),ip{x) : R" —* R лишпицевые функции, <р(х) > 0 Vx £ R". Положим

П = {хе Rn\ч>{х) = 0}. Предположим, что множество П непусто. Требуется найти

min f(x). xen

Описанная задача назьшается задачей условной минимизации. В ряде случаев с помощью функции (называемой штрафной)

Fa (х) = f{x) + Аф),

где А € R - константа, исходная задача условной минимизации может быть сведена к задаче безусловной минимизации функции Fa{x), т. е. к задаче нахождения

min Fa{x).

Будем говорить, что функция Ра(х) есть точная штрафная функция, если существует конечное число А* > 0 ,такое, что для любого А > А* выполняются следующие свойства:

(р1) всякий глобальный минимум функции ^(х) есть глобальный минимум функции /(х) на П, и наоборот;

(р2) всякий локальный минимум функции /л (г) есть локальный минимум функции /(х) на П.

Лемма. Если точка условного минимума х' Е Я не является стационарной тонкой функции /(х) каН", то не существует гладкой точной штрафной функции. Предположим, что

¡М /(х) = Г > -оо. г£Я„

Так как функция <р(х) лшшшцева, то ее нижняя производная Дини в точке х по направлению д

4>\}{х,д) = ИтЫ ~[(р{х + ад) - <р(г)] »10 о:

ограличена снизу константой Липшица. Положим

<рЬ(х>9),

Ы\=1

Фп(х) = limsup d(x'). х'—х,х'еп

Функция фа{х) определепа только для граничных точек множества Я (которое обозначим через По) и для любого х 0 П.

Достаточное условие существования точной штрафной функции: если для некоторого е > 0 множество Пе = {я € Rn\<p(x) < f} ограничено и

Vxefto, (1)

то Fa(x) есть точная штрафная функция, т.е. найдется конечное число А* > 0, такое, что VA > А* свойства (pl) и (р2) вьшолняются.

Рассмотрим теперь общую задачу нелинейного программирования. Пусть /, 0;(г € 1: m), hj(j € 1 : р): R" —► R. Требуется найти

min f(x)

при условии

&■(*) <0, Vi € 1 : гг; hj(x) = О, Vi € 1 : р.

В такой формулировке множество П есть

п = {ж е ЯпЫх) <0,^(х) = 0,Н;(х) = 0,1 € 1 :т,; € 1 :р). В качестве функции <р(х) часто выбирают норму в пространстве £ч:

г т Р 1

4=1 ; = 1

где 1 < 9 < +оо.

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

П р и м е р 1. Пусть множество

А={х€ #2| < 0,й(г) < 0,дг(х) < 0},

где

ду(х) - 2x1 - х2, д2 (ж) = 2х2 - хг, 9з{х) = (х, - 0.5)2 + (®2 " 0.5)2 - 0.5. П р и м е р 2. Пусть множество

П = {х 6 Я?Ых) < 0,д2{х) < 0,д3{х) < 0>,

где

дг(х) = хз, 91{х) - хг\х-1\- ахч, 9з{х) -х\- 0х2, О < а < 1, 0 < /3 < 1, а + 0<1. ПримерЗ. Пусть множество

П={хеДп|31(1)<0,52(х)<0},

где

51 С®) = 1 — ах2,

02(»=^ + (Z2 + 1)2-1, 0 < а < 1.

Из приведенных примеров следует, что в одних случаях достаточное условие (1) выполняется для функции <р\(х), а для i/j«, не выполняется, в других случаях - наоборот, а и третьих достаточное условие (1) выполняется только для <рд(х) и не выполнено ни для <Pl(x), НИ ДЛЯ <Роо(х).

Пусть х € R". Квазилинейной системой будем называть систему

max(t>,:r) + min (w,x) = с,, Vi € 1 : n, (2)

w£AJ w€Bi

где Л[, В\ С Rn - выпуклые компактные множества, с, € R. Решить квазилинейную систему - это значит найти х, удовлетворяющее (2).

Колинейной системой будем называть систему

max [а+(«,х)]+ min [6 + (tt>,x)] = с;, Vi € 1 : n,

где Ai,Bi С К."41 - выпуклые компактные множества, Ci € R.

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

тш /(*),

/(я) = тах<р(а:,у) + иЛпф{х,г),

у€А z£B

где А С Rm и В CR' выпуклые компактные множества, функции же ц>{х,у) и ф{х,г) гладкие по совокупности аргументов. Для ее решения предлагается применить метод покоординатного спуска по переменным (а:, z) к функции

h(x, z) = тах[^(г, у) + ф(х, z)\

для поиска

min h(x,z). (i,*)€R пхВ

Опишем метод.

Выберем произвольное zo £ В. Пусть уже найдено zt £ В, тогда ищем

min hfx.Zk). (3)

В качестве х* возьмем решение задачи (3) и далее найдем

min h(xk,z). х€В

Обозначим через Q(xk) множество

Q{xk) = {z\z = aigmmh(xk,z)}.

х€В

Бели окажется, что zt € Q(zt), то останавливаем процесс, если же Zk ф Q(xk), то продолжаем.

В результате получаем последовательность {(xt,Zfc)}, которая может быть конечной или бесконечной. Предположим теперь, что множество

D(x0) = {x\f(x) < f(x0)}

ограничено, тогда верна следующая

Теорема. Если последовательность {(st,zjt)} конечна, то х, взятое из последнего члена последовательности, является стационарной точкой функции h(x,z).

Рассмотрим колинейную систему

шах [а + (г,х)] + min [b -f- (ш,х)] = Cj, » 6 1 : n, [fl,o]6Aj \b,w]eBi

где Ai,Bi С - заданные многогранники, x € R". Введем функции

tpi(x) = max [a + (t»,a;)]+ min [6 + - Ci,i e 1 : n.

[a, v] € Ai [6, w] £ Bi

Тогда невязку N(x) системы (4) можно определить через одну из норм

п

= N,(x) = У>;(х)|, N2(x) = Nm(x) = тах{|^(*)|}.

f 1 S£1:A

i = l

Теперь исходную задачу (4) заменяем задачей поиска

min N(x),

предварительно представив N(x) в виде

N(x) = max [а + (t>,x)] + min [Ь+(ги,г)]. (5)

[о,и]£А [Ь,и>]еВ

Следствие. Для функции N(x) описанный метод приводит к стационарной точке за конечное число шагов.

На практике, при решении колинейных систем, метод хорошо себя зарекомендовал. Хотя множества Л и В из (5) содержат в итоге большое количество векторов, из которых, кстати, не все вершины, тем не менее предлагаемый метод обеспечил достаточно быструю сходимость.

Пусть дана пара выпуклых компактных множеств U, KcR2h

t/ = clco{X1(6)|ö€ [0,2тг]}, (6)

К = с1со{Х2(б)|0€ [0,2тг]}, (7)

О = в0 < в, < • • • < 0N = 2тг,

где

в

Хк(в) = Хк(Ъ) + Vti + J v>k(<*)da W € [0; Д+i),

9i

Vi,' = (Pki COs{6i),Pki sin(0,)), Pki > 0,

4>k = (Pk{a) cos(a),pk{a) sin(a)), pk{a) > 0,

JTfc(0) = JCjfeo, Xk(2x) = Xi(0), ke 1:2, i € 0 : N - 1.

Лемма. Сумма Минковского двух выпуклых компактных множеств U и V представима следующим образом:

U +V = clcoiX^e) + Хг(в)\в <Е [0,2тг]}.

Лемма. Пусть для представлений (6) и (7) множеств U и V выполнены условия

?1(а)>Р2(а) Уа€[0,2тг1

ы

Pii >P2i V* € О : N - 1,

тогда

U — V = с1со{х(0)|0 € [0,2тг]},

где

в

X(fl) = Х(9>) + V¡+J<p{a)da V0 € [Mi+i), вi

Vi = ((Pi¡ - P2i) eos(0¡), (Pu - p2i) sin^)), Pu - p2i > 0,

V = ((Pi(a) - Рг(а» cos(a), (Pl(a) - p2{a)) sin (a)), pi(a) - p2(<*) > 0,

X(0) = X0, Х(2тг) = X(0), i € 0 : N - 1.

Пусть Di = [A\,B\\ и £)2 = [^2,-62] будут парами выпуклых компактных множеств в R".

Будем говорить,что пары Dа и Z)2 эквивалентны, если

таx(v,g) + min (w,g) = max(w,p) + min (w,g) Vg, v€Ai W€B2

или, что тоже самое,

А! - В2 = Ai - Вг.

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

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

Пусть дана вара выпуклых компактных множеств [А, В], А, В С К2 и множества заданы следующим образом

А = clco{Xi(6)|0 € [0,2тг]},

-Я = с1со{Х2(0)||?е[О,27г]}, о = в0 < 0] < • • • < 6N = 27г,

где

в

Хк(в) = Xk{0i) + Vki + J4>k{a)da V0 € [Mi+i),

Si

Vki = (pki COs(ffj),Pki sîn(0;)), pki > 0, <Pk = ÍPk{o) cos(a),pt(o;) sin(a)), pk(a) > 0,

**(0) = Xko, Xh{2n) = X¿(0), ¿£1:2, i e 0 : JV - 1. Составляем следующие функции

q(a) = mm{pi(a),p2(a)}, q¡ = miü{pi¡,pl2}.

Далее находим

N-i 2;

V" = ]T(çi cos(âi),qjsm(âi)) + (q(a)cos(a),q(a)sïn(a))da = i=o {

= (ucos(0),t>sm(0)), PfcH = Pk{a) - ç(a), >0 pl¡= pki - qit pli > 0.

Теперь положим

Vk ~ (PÎ(Q)cos(a),pî(û)sin(a)), Vk¡ = {ph cos(ffi),P« 8т(в0).

Тогда минимальная пара ¡А', В*} определяется так

а* = с1со е [0,ё)}у{у* + х;(в)\8 е [0,2*)}

-В* = с1со{{*2*(0)|0 € [0+ € [0,2тг)}

где

е

Х№ = Х№) + + I

Х2(0)=ЛГ*о, ¿€0:(ЛГ-1).

При этом имеют место теоремы.

Теорема. Пара выпуклых компактных множеств [Л*, 5*] обладает свойством

р1(а)р'2(а) = 0 Чсхфви г € 0 : (Ы - 1);

РиР*а =0 V» е 0 : (ЛГ - 1).

Доказательство. Вытекает из построения. Теперь можно ввести определение минимальной пары. Пару [А, В\ будем называть минимальной, если для нее выполнено свойство, указанное в теореме 1.

Теорема. Минимальная пара единственна с точностью до сдвига. Теорема. Пара [А, В] £ 2 тогда и только тогда, когда существует некоторое выпуклое компактное множество такое, что

А + С2~А' Л-Сг,

-В + С2 =-В* + Сь

где Сг = со{0, V*}.

ВЫВОДЫ

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

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

3. Представлен аналитический способ вычисления разности — и суммы Минковского двух выпуклых множеств в пространстве И2. Дано понятие минимального квазидифференциала. Доказано, что минимальный квазидифференциал в М2 единственен в своем классе эквивалентности. Получено представление произвольного квазидифференциала через минимальный.

4. Все представленные численные методы и алгоритмы снабжены хорошо разработанным программным обеспечением.

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

По теме диссертации автором опубликованы следующие работы:

1. Абанькин А.Б. О точных штрафных функциях. Вестник СПбГУ,

1995, Серия N 1, Вып. N 3, стр. 4-13.

2. Абанькин А.Б. Численный метод решения квазилинейных систем.

В кн. "Математические вопросы анализа негладких моделей",

под ред. В.Ф.Демьянова, Изд-во СПбГУ,1995, стр. 39-43.