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

• Аббасов Меджид Эльхан оглы
• доктор наук
• 2019

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

Оглавление

ВВЕДЕНИЕ

1 Экзостеры

1.1 Исчерпывающие семейства верхних выпуклых и нижних вогну-

тых аппроксимаций. Экзостеры

1.2 Основные формулы исчисления экзостеров

1.3 Производные по направлению в смысле Дини и Адамара

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

1.4.1 Описание условий экстремума без ограничений с помощью

производных по направлению

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

экзостеров

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

ных экзостеров

1.4.4 Квазидифференцируемые функции. Сравнение практиче-

ского применения экзостеров и квазидифференциалов

1.4.5 Примеры

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

1.5.1 Условия экстремума с ограничениями в терминах произ-

водных по направлению

1.5.2 Условия экстремума с ограничениями в терминах собствен-

ных экзостеров

1.5.3 Условия экстремума с ограничениями в терминах несоб-

ственных экзостеров

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

ции на экзостерном множестве

1.6 Конвертирование экзостеров

3

1.6.1 Конверторы

1.6.2 Модифицированные конверторы

1.7 Минимальность экзостеров

1.7.1 Определение минимальности

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

1.7.3 Достаточные условия минимальности экзостеров

1.7.4 Сокращение экзостеров

1.7.5 Геометрические условия минимальности

1.8 Сравнение класса квазидифференцируемых функций с классом

функций, имеющих экзостеры

1.9 Обобщенные экзостеры. Существование. Построение. Условия оп-

тимальности

1.9.1 Определение обобщенных экзостеров

1.9.2 Теорема существования

1.9.3 Условия оптимальности

1.9.4 Примеры

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

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

2.1 Определение и построение коэкзостеров

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

2.3 Исчисление коэкзостеров

2.4 Конвертирование коэкзостеров

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

2.5.1 Условия экстремума кусочно-аффинных функций

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

нах собственных коэкзостеров

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

нах

несобственных коэкзостеров

2.5.4 Примеры

2.6 Метод коэкзостерного спуска

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

2.7.1 Условия экстремума с ограничениями для неоднородных

аппроксимаций приращения функции

4

2.7.2 Условия экстремума с ограничениями в терминах собствен-

ных и несобственных коэкзостеров

2.8 Сокращение и минимальность коэкзостеров

2.8.1 Определение минимальности

2.8.2 Минимальность по включению

2.8.3 Минимальность по форме

2.8.4 Примеры

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

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

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

2.9.3 Конвертор второго порядка

2.10 Оптимизационный алгоритм

3 Вспомогательные проблемы

3.1 Эвристические вероятностные алгоритмы ортогонального проек-

тирования точки на множество

3.1.1 Базовый алгоритм

3.1.2 Алгоритм с половинным делением

3.1.3 Алгоритм с обучением

3.1.4 Численные эксперименты

3.1.5 Выводы

3.2 Метод заряженных шариков

3.2.1 Ортогональная проекция точки на выпуклое множество с

гладкой границей

3.2.2 Минимальное расстояние между двумя выпуклыми мно-

жествами с гладкой границей

3.2.3 Минимальное расстояние между двумя гладкими кривыми

в трехмерном евклидовом пространстве

Заключение

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

Приложения

5

A Листинг программ, реализующих эвристические вероятностные

алгоритмы

A.1 Базовый алгоритм

A.2 Алгоритм с дихотомией

A.3 Алгоритм с обучением

B Листинг программ, реализующих метод заряженного шарика

B.1 Ортогональная проекция точки на выпуклое множество с глад-

кой границей. Метод второго порядка с автоматическим выбором

шага

B.2 Ортогональная проекция точки на выпуклое множество с гладкой

границей. Метод первого порядка

B.3 Минимальное расстояния между двумя выпуклыми множествами

с гладкой границей. Метод второго порядка

B.4 Минимальное расстояния между двумя выпуклыми множествами

с гладкой границей. Метод первого порядка

B.5 Минимальное расстояние между двумя плоскими

гладкими кривыми в трехмерном евклидовом пространстве

6

Введение диссертации (часть автореферата) на тему «Экзостеры и коэкзостеры в недифференцируемой оптимизации»

ВВЕДЕНИЕ

С момента появления дифференциального исчисления большую часть истории

математики исследователи предпочитали работать с гладкими функциями, и ес-

ли приходилось сталкиваться с функциями, не имеющими производной в «клас-

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

есть аппроксимация негладких функции с некоторой степенью точности глад-

кими. Довольно скоро пришло понимание того, что этот путь не подходит для

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

ких, как, например, нахождение нескольких направлений наискорейшего спуска

или подъема [1]), хотя и дает возможность приближенно находить точки экс-

тремума. Поэтому сглаживание в данном случае можно рассматривать лишь

как некий суррогатный подход. Этот факт дал толчок развитию научного на-

правление «негладкий анализ», сформировавшегося в середине XX века как

продолжение идей классического гладкого анализа, хотя первые существенно

негладкие задачи были поставлены и решены еще П.Л.Чебышевым [2, 3].

Оказалось, что одним из центральных понятий нового направления явля-

ется понятие производных по направлению (в смысле Дини и Адамара). Они

являются положительно однородными (п.о.) функциями, как функции направ-

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

го направления в данной точке. Последнее связано с тем, что производные по

направлению являются, по сути, аппроксимацией приращения рассматривае-

мой функции в окрестности исследуемой точки. Если скорость неотрицательна

(функция не убывает) вдоль любого направления, это означает, что в точке вы-

полнено необходимое условие минимума. Если же найдется направление, вдоль

которого производная отрицательна (функция убывает), то это направление

спуска. Направление, соответствующее максимальной скорости убывания, на-

зывается направлением наискорейшего спуска (н.н.с.). Аналогично обстоит си-

туация с точкой максимума, скоростью и направлением наискорейшего подъема

 7

(н.н.п.). Очевидно, что описанные в терминах производных по направлению

условия оптимальности не являются конструктивными, так как невозможно

проверить скорость изменения функции вдоль всех направлений. Это, однако,

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

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

ведения градиента на соответствующее направление. Используя это представ-

ление, можно переформулировать условия экстремума в более конструктивной

форме, а именно, в терминах градиента. К сожалению, этот подход неприме-

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

негладкую функцию в окрестности рассматриваемой точки некоторой линейной

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

для производных по направлению.

Первыми классами недифференцируемых функций для которых удалось это

сделать, явились выпуклые функции и функции максимума (см. работы [4–15]).

Было показано, что они являются дифференцируемыми по направлениям, а их

производные по направлениям, могут быть представлены с помощью некото-

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

объекта были описаны конструктивные условия экстремума и процедуры поис-

ка направлений спуска и подъема. Оказалось, что необходимое условие миниму-

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

направленный к нулю от ближайшей к началу координат точки, этого мно-

жества. Было построено исчисление, с помощью которого можно достаточно

просто находить субдифференциалы. Это дало возможность построения новых

оптимизационных алгоритмов [5,6,16–21], что повлияло на развитие математи-

ческого программирования [18,21–33]. Эти исследования привели к зарождению

теории минимакса и выпуклого анализа [4–7, 12, 16, 20, 34]. Отметим, что изуче-

нию субдифференциалов в абстрактных пространствах посвящена работа [35].

Успехи в выпуклом анализе заставили задуматься о подходах к решению невы-

пуклых проблем.

Один из путей, по которому пошли многие исследователи, заключался в ухо-

де от производных по направлению и введении новых специальных конструк-

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

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

попыток в этом направлении — субдифференциал Шора [36] и являющийся его

 8

выпуклой оболочкой субдифференциал Кларка [13, 37], позволившие изучать

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

ренциал Мордуховича [38–41], субдифференциал Мишеля-Пено [42], прибли-

женные и геометрические субдифференциалы Иоффе [43, 44], контейнеры Вар-

ги [45]. Подробный анализ различных подходов к этой проблеме приведен в [46].

Нужно отметить, что само построение этих объектов вызывает трудности, что

является недостатком по сравнению с конструктивностью теории в выпуклом

случае.

Другой путь состоял в поиске компромисса между простотой построения

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

функций и мощностью класса функций, которые этот объект обслуживает. Так

в 1980-х было предложено понятие квазидифференциала [16,47,48]. Квазидиф-

ференциал — это пара выпуклых компактов, позволяющих представить произ-

водную по направлению в виде суммы максимума и минимума некоторых ли-

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

циалов, руководствуясь которым можно строить эти пары для широкого класса

функций. Этот класс был назван классом квазидифференцируемых функций.

Условия экстремума в терминах этих объектов были получены В.Ф. Демьяно-

вым и Л.Н. Поляковой в [49]. Было показано, как находить н.н.с. и н.н.п. тогда,

когда эти условия не выполнены. Это позволило строить новые оптимизацион-

ные алгоритмы. Из-за своей конструктивности и эффективности при решении

негладких задач, квазидифференциалы стали предметом многочисленных ис-

следований [5, 50–57].

Для расширения класса исследуемых функций в 2000-х В.Ф. Демьяновым

было введено определение экзостеров [58, 59] (любая квазидифференцируемая

функция имеет экзостеры, обратное же, вообще говоря, неверно). Эти инстру-

менты являются естественным продолжением идей Б.Н. Пшеничного, который

ввел понятие верхних выпуклых аппроксимации (в.в.а.) [6], и А.М. Рубинова, на

основе в.в.а. предложившего понятия исчерпывающих семейств в.в.а. и нижних

вогнутых аппроксимации (н.в.а.) [60–62].

Экзостеры — семейства выпуклых компактов, с помощью которых произ-

водную по направлению можно представить в виде максимина либо минимакса

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

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

 9

В работах В.Ф. Демьянова, В.А. Рощиной, М.Э. Аббасова (см. [58,59,63–70]) бы-

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

терминах. Эти объекты изучались во многих работах [71–76]. Связь экзостеров

с различными обобщенными субдифференциалами обсуждается в работе [77].

Так как квазидифференциальное отображение не является непрерывным

в метрике Хаусдорфа, могут возникать трудности со сходимостью численных

методов, построенных на его базе. Для преодоления этой проблемы, были вве-

дены кодифференциалы [57, 62], позволившие получать локальные аппрокси-

мации исследуемой функции в виде суммы максимума и минимума аффинных

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

сти. Можно выделить класс непрерывно кодифференцируемых функций (чье

кодифференциальное отображение непрерывно в метрике Хаусдорфа), что поз-

волило строить более совершенные численные методы. Отметим, что множество

кодифференцируемых функций совпадает с множеством квазидифференциру-

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

дифференциалы.

Дальнейшим развитием этого подхода стало появление коэкзостеров — се-

мейств выпуклых компактов, позволяющих представлять аппроксимацию при-

ращения исследуемой функции в виде минимакса или максимина аффинных

функций [63,78], а также коэкзостеров второго порядка [68], позволяющих пред-

ставлять аппроксимацию приращения в виде минимакса или максимина квад-

ратичных функций. Условия экстремума в терминах этих объектов, методика

поиска направлений спуска и подъема, а также сопутствующие вопросы, воз-

никающие при использовании коэкзостеров, описаны в работах [63, 68, 79–85].

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

явное выражение для локальных аппроксимаций исследуемых функций. Оба

этих понятия могут быть использованы для решения задач недифференциру-

емой оптимизации. Но экзостерное отображение, так же, как и квазидиффе-

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

кодифференциалами, можно выделить класс функций с непрерывным коэкзо-

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

ких задач оптимизации видится использование коэкзостеров. Это, однако, не

означает, что исследование в области теории экзостеров следует прекратить.

Дело в том, что коэкзостеры можно рассматривать как экзостеры, заданные

 10

на некотором конусе. Поэтому весь ценный объем результатов, накопленный по

экзостерам, можно с легкостью обобщить на случай коэкзостеров.

Целью диссертации является развитие современных подходов негладкого

анализа, изложение новых, полученных автором результатов по данной тема-

тике, а также систематическое изложение теории экзостеров и коэкзостеров.

Несмотря на большое количество публикаций по данному направлению, до на-

стоящего времени не существует единого источника, к которому мог бы обра-

титься специалист, желающий ознакомиться с данным направлением. Настоя-

щая работа является попыткой восполнить образовавшийся пробел.

Теоретическая значимость работы состоит в том, что в ней развивается

теория экзостеров и коэкзостеров, уже успевшая выделиться в отдельную ветвь

негладкого анализа. Также в последней главе получены результаты, важные

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

зации — ортогонального проектирования точки на множество. Теоретическая

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

торых является соискатель, со стороны экспертов

• Российского Научного Фонда (РНФ) (проект №18-71-00006 «Построение

и исследование методов решения актуальных задач негладкого анализа и

дифференциальных включений»),

• Российского Фонда Фундаментальных Исследований (РФФИ) (проект №

18-31-00014 «Разработка современных методов недифференцируемой оп-

тимизации и их приложения»).

Практическая значимость работы определяется тем, что полученные в

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

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

кающих при их решении. В частности, метод заряженных шариков позволяет

эффективно находить ортогональную проекцию точки на выпуклый компакт

с гладкой границей, а, кроме того, дает возможность эффективно решать и

некоторые другие более сложные задачи вычислительной геометрии.

Основные результаты, полученные в диссертации и выносимые на защи-

ту:

• получены условия экстремума в терминах обобщенных экзостеров, дока-

зана теорема существования обобщенных экзостеров,

 11

• проведен сравнительный анализ применения экзостеров и квазидиффе-

ренциалов для решения задач недифференцируемой оптимизации,

• описаны новые условия минимальности экзостеров и коэкзостеров, а так-

же техника сокращения этих семейств,

• получены новые условия экстремума в терминах экзостеров и коэкзосте-

ров,

• разработано исчисление коэкзостеров второго порядка; для подкласса

функций максимума разработан метод минимизации второго порядка, ос-

нованный на коэкзостерах второго порядка,

• разработан Метод Заряженных Шариков, для решения вспомогательных

задач, возникающих в недифференцируемой оптимизации, а также важ-

ных проблем вычислительной геометрии, таких как поиск минимального

расстояния между двумя множествами с гладкой границей, поиск мини-

мального расстояния между двумя гладкими кривыми в трехмерном про-

странстве.

• предложены новые эвристические, вероятностные алгоритмы решения

важной подзадачи, возникающей в недифференцируемой оптимизации,

а именно задачи поиска ортогональной проекции точки на множество.

Указанные алгоритмы могут быть применены и для поиска начального

приближения при применении Метод Заряженных Шариков.

Апробация работы. Результаты, изложенные в диссертации, докладыва-

лись и обсуждались на следующих конференциях и семинарах:

• XXXVIII, XXXIX, XL, XLI конференции «Процессы управления и устой-

чивость», Факультет Прикладной Математики – Процессов Управления

СПбГУ, г. Санкт-Петербург (Россия), апрель 2007 г., апрель 2008 г., ап-

рель 2009 г., апрель 2010 г.;

• II Международная конференция «Control and Optimization with Industrial

Applications», г. Баку (Азербайджан), 2–4 июня 2008 г.;

 12

• Всероссийская конференция «Устойчивость и процессы управления», по-

священная 80-летию В.И. Зубова, г. Санкт-Петербург (Россия), 1–2 июля

2010 г.;

• XIV-я Всероссийская конференция «Математическое программирование

и приложения», Институт математики и механики им. Н.Н. Красовского

УрО РАН, г. Екатеринбург (Россия), 28 февраля–2 марта 2011 г.;

• The 8th International Congress of the International Society for Analysis, its

Applications and Computation (ISAAC 2011), г. Москва (Россия), 2011;

• Международная конференция «Конструктивный негладкий анализ и смеж-

ные вопросы», г. Санкт-Петербург (Россия), 18–23 июня 2012 г.;

• Международная конференция «Математика, экономика, менеджмент: 100

лет со дня рождения Л.В. Канторовича», г. Санкт-Петербург (Россия), 7–9

февраля 2012 г.;

• VI Международная конференция «Динамические системы: устойчивость,

управление, оптимизация» (DSSCO13), посвященная 95-летию со дня рож-

дения Е.А. Барбашина, г. Минск (Беларусь), 1–5 октября 2013 г.;

• 8th Australia New Zealand Mathematics Convention, г. Мельбурн (Австра-

лия), 8–12 декабря 2014 г.;

• Applied Mathematics Seminars, Swinburne University of Technology, Faculty

of Science, Engineering and Technology, г. Мельбурн (Австралия) 2014 г.;

• The 5th International Conference on Control and Optimization with Industrial

Applications (COIA 2015), г. Баку (Азербайджан), 27—29 августа 2015 г.;

• Международная конференция «Устойчивость и процессы управления»,

посвященная 85-летию со дня рождения проф., чл.-корр. РАН В.И. Зу-

бова (SCP 2015), г. Санкт-Петербург (Россия), 5–9 октября 2015;

• XV Всероссийская конференция «Математическое программирование и

приложения», Институт математики и механики им. Н.Н. Красовского

УрО РАН, г. Екатеринбург, 2–6 марта 2015 г.;

 13

• 10th Workshop on Theory of Randomized Search Heuristics, г. Люнгбю (Да-

ния), 18–19 марта 2016 г.;

• VIII Московская международная конференция по исследованию операций

(ORM 2016), г. Москва (Россия), 17–22 октября 2016 г.;

• Семинар лаборатории 7 ИПУ РАН, г. Москва (Россия), 6 декабря 2016 г.;

• Global Optimization Conference (GOC-2017), Техасский Университет A&M,

Техас (США), 30 марта–01 апреля 2017г.;

• Международная конференция «Конструктивный негладкий анализ и смеж-

ные вопросы» (CNSA-2017), посвященная памяти профессора В.Ф. Демья-

нова, Международный математический институт им. Леонарда Эйлера, г.

Санкт-Петербург (Россия), 22–27 мая 2017 г.;

• Семинар ВЦ РАН, г. Москва (Россия), 13 декабря 2017 г.;

• Семинар кафедры высшей математики МФТИ, г. Москва (Россия), 14

декабря 2017 г.;

• The 6th International Conference on Control and Optimization with Industrial

Applications (COIA-2018), г. Баку (Азербайджан), 11—13 июля 2018 г.;

• Международная научная конференция «Динамические системы: устойчи-

вость, управление, оптимизация» (DSSCO18) к 100-летию со дня рожде-

ния Е.А. Барбашина, г. Минск (Беларусь), 24–29 сентября 2018 г.;

• IX International Conference Optimization and Applications (OPTIMA-2018),

г. Петровац (Черногория), 1–5 октября 2018г.;

• Семинар лаборатории Ц-2 «Распределенные вычислительные системы»

Института проблем передачи информации РАН, г. Москва (Россия), 22

ноября 2018 г.

Кроме того, все результаты, полученные в данной работе, докладывались и

обсуждались на семинаре по конструктивному негладкому анализу и недиффе-

ренцируемой оптимизации (CNSA & NDO), который проходил на кафедре мате-

матической теории моделирования систем управления факультета Прикладной

 14

Математики – Процессов Управления Санкт-Петербургского Государственного

Университета.

По результатам исследований опубликовано 39 печатных работ [68–70,79,81–

115], 7 из которых [68,83,85,90,95,97,100] в изданиях, рекомендуемых ВАК, 13 в

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

в наукометрических базах Web of Science/Scopus [68–70,79,81–83,85,92,100,108,

114, 115].

Диссертация состоит из введения, трех глав, заключения, списка обозначе-

ний, списка литературы и приложений. Определения, утверждения, теоремы,

примеры, замечания нумеруются в соответствии с главой, параграфом, в кото-

рых они находятся. Следствия нумеруются в соответствии с теоремами, к кото-

рым они относятся. Объем работы составляет 281 страница, список литературы

включает 163 наименования, в работе 50 рисунков, 14 таблиц, 2 приложения.

Благодарности. Автор выражает глубочайшую признательность своему

учителю и научному консультанту д.ф.-.м.н., проф. В. Ф. Демьянову , идеями

которого он во многом руководствовался, и под руководством которого была

написана большая часть данной работы.

Автор считает своим долгом поблагодарить д.ф.-м.н., проф. В. Н. Малоземо-

ва, д.ф.-м.н., проф. Е. С. Половинкина, д.ф.-м.н., проф. С. И. Дудова, д.ф.-м.н.,

проф., чл.-корр. НАН Беларуси В. В. Гороховика за ценные замечания, д.т.н.,

проф. Б. Т. Поляка за полезные обсуждения, позволившие получить новые тео-

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

тета Прикладной Математики – Процессов Управления Санкт-Петербургского

Государственного Университета д.ф.-м.н., проф. Л. А. Петросяна за поддержку,

оказанную в ходе написания данной работы.

 15

ГЛАВА 1

Экзостеры

1.1 Исчерпывающие семейства верхних выпуклых и ниж-

них вогнутых аппроксимаций. Экзостеры

Успехи в выпуклом анализе подтолкнули исследователей к попыткам распро-

странения полученных результатов на невыпуклые функции. Поэтому есте-

ственным представляется введение понятий верхних выпуклых аппроксимаций

(в.в.а.) предложенных Б.Н. Пшеничным [6].

Пусть задана п.о. функция h : K Ñ R, где K Ă Rn –конус. Выпуклая п.о.

функция h : Rn Ñ R называется верхней выпуклой аппроксимацией функции

h на K, если

hpgq ď hpgq @g P K.

Аналогично вводится понятие нижних вогнутых аппроксимаций (н.в.а.). Во-

гнутая п.о. функция h : Rn Ñ R называется нижней вогнутой аппроксимацией

функции h на K, если

hpgq ě hpgq @g P K.

А.М. Рубинов ввел понятия исчерпывающих семейств аппроксимаций [60].

Множество Λ˚ верхних выпуклых аппроксимаций функции h на K называ-

ется исчерпывающим, если

hpgq “ inf hpgq @g P K. (1.1)

hPΛ˚

Множество Λ˚ нижних вогнутых аппроксимаций функции h на K называ-

 16

ется исчерпывающим, если

hpgq “ sup hpgq @g P K. (1.2)

hPΛ˚

Им же установлены условия существования исчерпывающих семейств [60,

62].

Теорема 1.1.1 (Рубинова (см. [59])) Пусть п.о. функция hpgq задана на

замкнутом конусе K, ограничена сверху на B1K т.е.

sup hpgq ă `8,

gPB1K

где B1K “ tg P K | }g} ď 1u. Тогда, если h полунепрерывна сверху на K, то су-

ществует исчерпывающие семейство верхних выпуклых аппроксимаций функ-

ции h на K.

Если h полунепрерывна снизу на K, ограничена снизу на B1K т.е.

inf hpgq ą ´8,

gPB1K

то существует исчерпывающие семейство нижних вогнутых аппроксимаций

функции h на K.

Каждая выпуклая п.о. функция h может быть единственным образом пред-

ставлена (см. [4]) в виде

hpgq “ max xv, gy @g P Rn , (1.3)

vPCphq

где Cphq — выпуклый компакт.

Поэтому (1.1) можем переписать так:

hpgq “ inf˚ maxxv, gy @g P K, (1.4)

CPE vPC

␣ (

где E ˚ “ C Ă Rn | C “ Cphq, h P Λ˚ . Множество E ˚ называют верхним

экзостером функции h по отношению к K.

Аналогично, так как каждая н.в.а. h может быть единственным образом

 17

представлена (см. [4]) в виде

hpgq “ min xv, gy @g P Rn , (1.5)

vPCphq

где Cphq — выпуклый компакт, то (1.2) можем переписать так:

hpgq “ sup minxv, gy @g P K, (1.6)

CPE˚ vPC

где E˚ “ tC Ă Rn | C “ Cphq, h P Λ˚ u . Множество E˚ называют нижним эк-

зостером функции h по отношению к K.

В [73] было показано, что если hpgq — п.о. липшицевая функция, то она

может быть записана как в виде

hpgq “ h1 pgq “ min˚ maxxv, gy, (1.7)

CPE vPC

так и в виде

hpgq “ h2 pgq “ max minxv, gy, (1.8)

CPE˚ vPC

где семейства множеств E ˚ , E˚ ограничены в совокупности (то есть найдется

такое r ą 0, что C Ă Br p0q для всех C P E ˚ (E˚ ), где Br p0q P Rn — шар ради-

уса r с центром в нуле). Пару семейств rE˚ , E ˚ s будем называть биэкзостером

функции h. Впервые понятие экзостеров появилось в работах [58, 59].

Мы, как правило, будем рассматривать случай K “ Rn и работать с пред-

ставлениями (1.7), (1.8). Поведение функции f в окрестности изучаемой точки

x определяется поведением аппроксимации приращения h в окрестности нуля.

С помощью экзостеров, при выполнении соответствующих условий, гаранти-

рующих их существование, можно получить минимаксное либо максиминное

представление для этого члена:

f px ` gq “ f pxq ` min maxxv, gy ` ox pgq, (1.9)

CPE pxq vPC

˚

f px ` gq “ f pxq ` max minxv, gy ` ox pgq. (1.10)

CPE˚ pxq vPC

В этом случае при дополнительных условиях на ox pgq (см. пункт 1.3), аппрок-

симация приращения совпадает с производной по направлению функции f в

точке x.

 18

Отметим, что экзостер функции f в точке x совпадает с экзостером функции

h в нуле. Поэтому везде в дальнейшем под экзостером h понимается экзостер

этой функции в нуле.

Отметим также, что в дальнейшем мы будем работать с семействами мно-

жеств. Изучению непосредственно исчерпывающих семейств верхних выпуклых

или нижних вогнутых аппроксимаций, посвящены, например, работы [116–119].

Существует широкий класс негладких функций [57, 59], допускающих раз-

ложения (1.9), (1.10). В него входят входят гладкие, выпуклые, вогнутые функ-

ции, функции максимума и минимума.

Теорема 1.1.2 Пусть функция f pxq дифференцируема в точке x0 . Тогда су-

ществуют верхний и нижний экзостеры, состоящие из одного одноточечного

множества каждый

E ˚ px0 q “ t∇f px0 qu ,

E˚ px0 q “ t∇f px0 qu ,

где ∇f px0 q — градиент функции f в точке x0 .

1.2 Основные формулы исчисления экзостеров

Рассмотрим основные свойства [59], которым удовлетворяют функции, имею-

щие экзостеры. Пусть дана функция h : Rn Ñ R имеющая биэкзостер E “

rE˚ , E ˚ s, где E˚ , E ˚ — семейство выпуклых компактов из Rn . Непосредственно

из определения экзостеров следует, что для произвольного λ P R выполнено

$

&rλE , λE ˚ s , λ ě 0,

˚

λE “

%rλE ˚ , λE˚ s , λ ă 0.

Если E1 “ rE1˚ , E1˚ s, E2 “ rE2˚ , E2˚ s, где Ei˚ , Ei˚ при i “ 1, 2 — семейство

выпуклых компактов из Rn , тогда

E1 ` E2 “ rE1˚ ` E2˚ , E1˚ ` E2˚ s .

Теперь можем перейти непосредственно к исчислению экзостеров.

 19

Теорема 1.2.1 Пусть для п.о. функций h1 , h2 существуют биэкзостеры

Eph1 q “ rE1˚ , E1˚ s и Eph2 q “ rE2˚ , E2˚ s соответственно. Тогда при произволь-

ных λ1 , λ2 P R пара Ephq “ λ1 Eph1 q`λ2 Eph2 q является биэкзостером функции

h “ λ1 h1 ` λ2 h2 .

Теорема 1.2.2 Пусть функции f1 pxq, f2 pxq дифференцируемы по направле-

ниям в точке x0 P X, где X Ă Rn – открытое множество, предположим

также, что существуют биэкзостеры E1 “ Eph1 q и E2 “ Eph2 q функций

h1 pgq “ f11 px0 , gq и h2 pgq “ f21 px0 , gq соответственно. Тогда функции F1 pxq “

f1 pxq ¨ f2 pxq и F2 pxq “ f1 pxq{f2 pxq (в последнем случае если f2 px0 q ‰ 0) явля-

ются дифференцируемыми по направлениям в точке x0 и существует биэк-

зостеры функций H1 pgq “ F11 px0 , gq и H2 pgq “ F21 px0 , gq вида

1

EpH1 q “ f2 px0 qE1 ` f1 px0 qE2 , EpH2 q “ rf2 px0 qE1 ´ f1 px0 qE2 s .

f22 px0 q

Теорема 1.2.3 Пусть функции f1 pxq, . . . , fm pxq : Rn Ñ R дифференцируемы

по направлениям в точке x0 , функция F pyq “ F py1 , . . . , ym q : Rm Ñ R —

непрерывно дифференцируема в точке y0 “ pf1 px0 q, . . . , fm px0 qq и пусть Ei

являются биэкзостерами функций hi pgq “ fi1 px0 , gq. Тогда функция f pxq “

F pf1 pxq, . . . , fm pxqq также являются дифференцируемыми по направлениям в

точке x0 и существует биэкзостер функции Hpgq “ f 1 px0 , gq вида

m

ÿ BF py0 q

EpHq “ Ei .

i“1

Byi

Теорема 1.2.4 Пусть функции fi pxq, i P I “ 1 : N дифференцируемы по на-

правлениям в точке x0 , и пусть Ei являются биэкзостерами функций hi pgq “

fi1 px0 , gq. Тогда функций F1 pxq “ max fi pxq и F2 pxq “ min fi pxq также являют-

iPI iPI

ся дифференцируемыми по направлениям в точке x0 . Кроме того существует

Список литературы диссертационного исследования доктор наук Аббасов Меджид Эльхан оглы, 2019 год

B -

´1 0 1

´1

Рис. 1.3: Квазидифференциал в примере 1.4.2.

В точке x0 производная по направлению функции f принимает вид

f 1 px0 , gq “ hpgq “ min xv, gy ` max xv, gy.

vPBf px0 q vPBf px0 q

С помощью квазидифференциала строим (см. теорему 1.4.24) верхний эк-

зостер функции f в точке x0 (см. рис 1.4a).

␣

E ˚ “ tC “ w ` Bf px0 q | w P Bf px0 qu “ p0, 1q ` cotp´1, 0q, p1, 0qu,

(

p0, ´1q ` cotp´1, 0q, p1, 0qu “ tC1 , C2 u,

где C1 “ cotp´1, 1q, p1, 1qu, C2 “ cotp´1, ´1q, p1, ´1qu.

 45

Аналогично, используя теорему 1.4.24, строим нижний экзостер функции

f в точке x0 (см. рис 1.4б):

␣

E˚ “ tC “ v ` Bf px0 q | v P Bf px0 qu “ p´1, 0q ` cotp0, 1q, p0, ´1qu,

(

p1, 0q ` cotp0, 1q, p0, ´1qu “ tC3 , C4 u,

где C3 “ cotp´1, 1q, p´1, ´1qu, C4 “ cotp1, 1q, p1, ´1qu.

а б

Рис. 1.4: Верхний а) и нижний б) экзостеры в примере 1.4.2.

Исследуем вначале точку x0 на минимум. Верхний экзостер E ˚ является

собственным для задачи на минимум. Из рис. 1.4 a) видно, что 0 R C1 и

0 R C2 , т.е. (см. теорему 1.4.6) точка x0 не удовлетворяет необходимому

условию минимума (1.20). Найдем

min ||z|| “ ||z1 || “ ||p0, 1q|| “ 1, min ||z|| “ ||z2 || “ ||p0, ´1q|| “ 1.

zPC1 zPC2

Так как ||z1 || “ ||z2 || “ 1, то max t||z1 ||, ||z2 ||u “ 1, и отсюда следует, что

скорость наискорейшего спуска равна ´1 и существует 2 направления наи-

скорейшего спуска g1 “ p0, ´1q, g2 “ p0, 1q.

Теперь используем нижний экзостер E˚ , который является несобствен-

ным для задачи на минимум. Из рис. 1.4б видно, что необходимое условие

минимума (см. теорему 1.4.12 и следствие 1.4.12.1) не выполнено: например,

для направления g1 “ p0, 1q соответствующая ему гиперплоскость (в дан-

␣ (

ном случае прямая) Lpg1 q “ x P R2 | xx, g1 y “ 0 не является отделяющей

от нуля ни для одного из множеств C1 и C2 . Более того, как легко видеть,

␣ (

эта прямая (наряду с прямой Lpg2 q “ x P R2 | xx, g2 y “ 0 , где g2 “ p0, ´1q)

 46

является «наиболее» неотделяющей. В данном случае прямые Lpg1 q и Lpg2 q

совпали, но они задаются разными направляющими векторами. Для направ-

ления g1 имеем minxw, g1 y “ ´1, minxw, g1 y “ ´1, отсюда

wPC1 wPC2

hpg1 q “ max minxw, g1 y “ ´1 ă 0.

CPE˚ wPC

Аналогично для направления g2 будет minxw, g2 y “ ´1, minxw, g2 y “ ´1, от-

wPC1 wPC2

сюда

hpg2 q “ max minxw, g2 y “ ´1 ă 0.

CPE˚ wPC

Нетрудно видеть, что для любого другого единичного направления g будет

hpgq ą ´1. Поэтому существует два направления наискорейшего спуска: g1 “

p0, 1q и g2 “ p0, ´1q. Скорость наискорейшего спуска равна -1.

Таким образом, с помощью верхнего и нижнего экзостеров удалось уста-

новить, что точка x0 не является точкой минимума и найти направления

и скорость наискорейшего спуска.

Теперь исследуем точку x0 на максимум. Нижний экзостер E˚ является

собственным для задачи на максимум. Из рис. 1.4 б) видно, что 0 R C3 и

0 P C4 , т.е. (см. теорему 1.4.8) точка x0 не удовлетворяет необходимому

условию максимума (1.28). Найдем

min ||z|| “ ||z3 || “ ||p1, 0q|| “ 1, min ||z|| “ ||z4 || “ ||p´1, 0q|| “ 1.

zPC3 zPC4

Так как ||z3 || “ ||z4 || “ 1, то maxt||z3 ||, ||z4 ||u “ 1, и отсюда следует, что

скорость наискорейшего подъема равна 1 и существует 2 направления наи-

скорейшего подъема g3 “ p1, 0q, g4 “ p´1, 0q.

Теперь используем верхний экзостер E ˚ , который является несобствен-

ным для задачи на максимум. Из рис. 1.4 a) видно, что необходимое условие

максимума (см. теорему 1.4.14 и следствие 1.4.14.1) не выполнено: например,

для направления g3 “ p1, 0q соответствующая ему гиперплоскость (в данном

␣ (

случае прямая) Lpg3 q “ x P R2 | xx, g3 y “ 0 не является отделяющей от ну-

ля ни для одного из множеств C3 и C4 . Более того, как легко видеть, эта

␣ (

прямая (наряду с прямой Lpg4 q “ x P R2 | xx, g4 y “ 0 , где g4 “ p´1, 0q), яв-

ляется «наиболее» неотделяющей. В данном случае прямые Lpg3 q и Lpg4 q сов-

пали, но они задаются разными направляющими векторами. Для направления

 47

g3 имеем maxxw, g3 y “ 1, maxxw, g3 y “ 1, отсюда

wPC3 wPC4

hpg1 q “ min˚ maxxw, g3 y “ 1 ą 0.

CPE wPC

Аналогично для направления g4 будет maxxw, g4 y “ 1, maxxw, g4 y “ 1, отсюда

wPC3 wPC4

hpg1 q “ min˚ maxxw, g4 y “ 1 ą 0.

CPE wPC

Нетрудно видеть, что для любого другого единичного направления g будет

hpgq ă 1. Поэтому существует два направления наискорейшего подъема: g3 “

p1, 0q и g4 “ p´1, 0q. Скорость наискорейшего подъема равна 1.

Таким образом, с помощью верхнего и нижнего экзостеров удалось уста-

новить, что точка x0 не является точкой максимума, и найти направления

и скорость наискорейшего подъема.

Пример 1.4.3 Пусть задана функция f : R2 Ñ R вида

f px1 , x2 q “ | |x1 | ´ |x2 | |.

Эта функция является квазидифференцируемой (см. [16]). Рассмотрим снова

точку x0 “ 0 “ p0, 0q. В точке x0 квазидифференциал функции f (см. рис. 1.5)

определяется как Df px0 q “ Bf px0 q, Bf px0 q , где

“ ‰

Bf px0 q “ cotp2, 0q, p0, 2q, p´2, 0q, p0, ´2qu,

Bf px0 q “ cotp1, 1q, p´1, 1q, p´1, ´1q, p1, ´1qu.

 48

Рис. 1.5: Квазидифференциал в примере 1.4.3.

По теореме 1.4.24 построим верхний экзостер функции f в точке x0 (см.

рис. 1.6 a).

E ˚ “ tC “ w ` Bf px0 q | w P Bf pxqu “

␣

“ p1, 1q ` cotp2, 0q, p0, 2q, p´2, 0q, p0, ´2qu,

p´1, 1q ` cotp2, 0q, p0, 2q, p´2, 0q, p0, ´2qu,

p´1, ´1q ` cotp2, 0q, p0, 2q, p´2, 0q, p0, ´2qu,

(

p1, ´1q ` cotp2, 0q, p0, 2q, p´2, 0q, p0, ´2qu “

“ tC1 , C2 , C3 , C4 u,

где $

’

’

’ C1 “ cotp1, 3q, p3, 1q, p0, ´1q, p´1, 1qu,

’

’

’

&C

2 “ cotp´1, 3q, p1, 1q, p´1, ´1q, p´3, 1qu,

’

’

’ C3 “ cotp´1, 1q, p1, ´1q, p´1, ´3q, p´3, ´1qu,

’

’

%C4

’

“ cotp1, 1q, p3, ´1q, p1, ´3q, p´1, ´1qu.

Аналогично, используя теорему 1.4.24, строим нижний экзостер функции

 49

f в точке x0 (см. рис. 1.6 б).

E˚ “ tC “ v ` Bf px0 q | v P Bf pxqu “

␣

“ p2, 0q ` cotp1, 1q, p´1, 1q, p´1, ´1q, p1, ´1qu,

p0, 2q ` cotp1, 1q, p´1, 1q, p´1, ´1q, p1, ´1qu,

p´2, 0q ` cotp1, 1q, p´1, 1q, p´1, ´1q, p1, ´1qu,

(

p0, ´2q ` cotp1, 1q, p´1, 1q, p´1, ´1q, p1, ´1qu “

“ tC5 , C6 , C7 , C8 u,

где $

’

’

’ C5 “ cotp3, 1q, p3, ´1q, p1, ´1q, p1, 1qu,

’

’

’

&C

6 “ cotp1, 3q, p´1, 3q, p´1, 1q, p1, 1qu,

’

’

’ C7 “ cotp´3, 1q, p´3, ´1q, p´1, 1q, p´1, ´1qu,

’

’

%C8

’

“ cotp1, ´1q, p´1, ´3q, p1, ´3q, p´1, ´1qu.

а б

Рис. 1.6: Верхний а) и нижний б) экзостеры в примере 1.4.3.

Исследуем вначале точку x0 на минимум. Верхний экзостер E ˚ является

собственным для задачи на минимум. Из рис. 1.6 a) видно, что 0 P Ci для

всех i P 1 : 4, т.е. (см. теорему 1.4.6) точка x0 удовлетворяет необходимому

условию минимума (1.20) и потому является inf-стационарной.

Теперь используем нижний экзостер E˚ , который является несобствен-

ным для задачи на минимум. Из рис. 1.6 б) видно, что необходимое условие

 50

минимума (см. теорему 1.4.12 и следствие 1.4.12.1) выполнено: для любого на-

правления g соответствующая ему гиперплоскость (в данном случае прямая)

Lpgq “ tx P R2 | xx, gy “ 0u является отделяющей от нуля хотя бы для одного

из множеств Ci , i P 1 : 4, т.е. точка x0 удовлетворяет необходимому усло-

вию минимума (см. теорему 1.4.12) и потому является inf-стационарной.

Таким образом, с помощью верхнего и нижнего экзостеров удалось уста-

новить, что точка x0 является стационарной точкой.

Теперь исследуем точку x0 на максимум. Нижний экзостер E˚ является

собственным для задачи на максимум. Из рис. 1.6 б) видно, что 0 R Ci , при

любых i P 5 : 8, т.е. (см. теорему 1.4.8) точка x0 не удовлетворяет необхо-

димому условию максимума (1.28). Найдем

min ||z|| “ ||z5 || “ ||p1, 0q|| “ 1, min ||z|| “ ||z6 || “ ||p0, 1q|| “ 1,

zPC5 zPC6

min ||z|| “ ||z7 || “ ||p´1, 0q|| “ 1, min ||z|| “ ||z8 || “ ||p0, ´1q|| “ 1.

zPC7 zPC8

Так как ||zi || “ 1 для всех i P 5 : 8, то max ||zi || “ 1, и отсюда следует,

iP5:8

что скорость наискорейшего подъема равна 1 и существует 4 направления

наискорейшего подъема g5 “ p1, 0q, g6 “ p0, 1q, g7 “ p´1, 0q, g8 “ p0, ´1q.

Теперь используем верхний экзостер E ˚ , который является несобствен-

ным для задачи на максимум. Из рис. 1.6 a) видно, что необходимое условие

максимума (см. теорему 1.4.14 и следствие 1.4.14.1) не выполнено: для любого

единичного направления, кроме направлений

ˆ ˙ ˆ ˙ ˆ ˙ ˆ ˙

1 1 1 ´1 ´1 ´1 ´1 1

g5˚ “ ? , ? , g6˚ “ ? , ? , g7˚ “ ? , ? , g8˚ “ ? , ? ,

2 2 2 2 2 2 2 2

соответствующая ему гиперплоскость (в данном случае прямая) Lpgq “ tx P

R2 | xx, gy “ 0u не является отделяющей от нуля ни для одного из множеств

Ci , i P 5 : 8. Нетрудно видеть, что «наиболее» неотделяющими являются

направления g5 “ p1, 0q, g6 “ p0, 1q, g7 “ p´1, 0q, g8 “ p0, ´1q.

Для любого направления gi , i P 5 : 8 имеем maxxw, gi y “ 1 @k P 5 : 8,

wPCk

отсюда

hpgi q “ min maxxw, gi y “ 1 ą 0.

CPE˚ wPC

Нетрудно видеть, что для любого другого единичного направления g будет

 51

hpgq ă 1. Поэтому существует 4 направления наискорейшего подъема: g5 “

p1, 0q, g6 “ p0, 1q, g7 “ p´1, 0q, g8 “ p0, ´1q. Скорость наискорейшего подъема

равна 1.

Таким образом, с помощью верхнего и нижнего экзостеров удалось уста-

новить, что точка x0 не является точкой максимума, и найти направления

и скорость наискорейшего подъема.

Пример 1.4.4 Пусть f pxq “ |x1 | ` |x2 |, x0 “ p0, 0q. Исследуем вначале f на

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

задачи, имеет вид (рис. 1.7 a)

E ˚ “ tcotp´1, ´1q, p´1, 1q, p1, ´1q, p1, 1quu .

а б

Рис. 1.7: Верхний а) и нижний б) экзостеры в примере 1.4.4.

Ясно, что выполнено необходимое и достаточное условие строгого локаль-

ного минимума (см. теорему 1.4.7).

Нижний экзостер, являющийся несобственным для данной задачи, имеет

вид (рис. 1.7 б)

E˚ “ tp´1, ´1q; p´1, 1q; p1, ´1q; p1, 1qu .

Как видим, E˚ удовлетворяет условиям теоремы 1.4.13.

Проверим теперь f на максимум в точке x0 с помощью нижнего экзосте-

ра, являющегося собственным для данной задачи. Из рисунка 1.7 б) видно, что

точка x0 не удовлетворяет необходимому условию максимума (см. теорему

 52

1.4.8). Имеем

?

max min }z} “ 2.

CPE˚ zPC

Значит скорость наискорейшего подъема равна 1 и существует 4 направления

наискорейшего подъема

ˆ ? ? ˙ ˆ ? ? ˙

2 2 2 2

g1 “ ´ , ´ , g2 “ ´ , ,

2 2 2 2

ˆ? ? ˙ ˆ? ? ˙

2 2 2 2

g3 “ ,´ , g4 “ , .

2 2 2 2

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

стера, являющегося несобственным для данной задачи (см. теорему 1.4.14),

причем видно, что «наиболее» неотделяющими являются две гиперплоско-

сти, представляющие собой биссектрисы I, III и II, IV квадрантов соответ-

ственно. Этим прямым соответствуют те же направления g1 , g2 , g3 , g4 .

Менее тривиальным является

Пример 1.4.5 Рассмотрим в точке x0 “ p1, 1q приводившуюся в [124] функ-

цию

f pxq “ max tfi pxqu ` min tfi pxqu,

i“1,2,3 i“4,5,6

где

f1 pxq “ x41 ` x22 , f2 pxq “ p2 ´ x1 q2 ` p2 ´ x2 q2 , f3 pxq “ 2e´x1 `x2 ,

f4 pxq “ x21 ´ 2x1 ` x22 ´ 4x2 ` 4, f5 pxq “ 2x21 ´ 5x1 ` x22 ´ 2x2 ` 4,

f6 pxq “ x21 ` 2x22 ´ 4x2 ` 1.

Можно записать

f pxq “ max min tfi pxq ` fj pxqu “ min max tfj pxq ` fi pxqu.

i“1,2,3 j“4,5,6 j“4,5,6 i“1,2,3

Поэтому для аппроксимации приращения hpgq функции f pxq справедливо как

максиминное, так и минимаксное представление. Верхний экзостер здесь име-

ет вид (рис. 1.8 a)

E ˚ “ tC1 , C2 , C3 u ,

 53

где

C1 “ cotp4, 0q; p´2, ´4q; p´2, 0qu,

C2 “ cotp3, 2q; p´3, ´2q; p´3, 2qu,

C3 “ cotp6, 2q; p0, ´2q; p0, 2qu.

Очевидно, что в терминах собственного экзостера в точке x0 выполняется

условие нестрогого локального минимума. Нижний экзостер имеет вид (рис.

а б

Рис. 1.8: Верхний а) и нижний б) экзостеры в примере 1.4.5.

1.8 б)

E˚ “ tC4 , C5 , C6 u ,

где

C4 “ cotp4, 0q; p3, 2q; p6, 2qu,

C5 “ cotp´2, ´4q; p´3, ´2q; p0, ´2qu,

C6 “ cotp´2, 0q; p´3, 2q; p0, 2qu.

Из рис. 1.8 б) видно, что произвольная плоскость, проходящая через начало

координат, вообще говоря, нестрого разделяет какие-то два множества из

E˚ , а значит, выполнено условие теоремы 1.4.12.

 54

1.5 Условия экстремума с ограничениями в терминах эк-

зостеров

1.5.1 Условия экстремума с ограничениями в терминах производ-

ных по направлению

Вначале приведем вспомогательные результаты из [60].

Пусть нужно найти минимум или максимум функции f : X Ñ R на множе-

стве Ω Ă X, где X — открытое множество. Прежде всего определим конусы,

аппроксимирующие множество Ω в окрестности рассматриваемой точки x.

Направление g ‰ 0 называется возможным направлением множества Ω в

точке x, если найдутся последовательности tgk u, tαk u, что