Максимин функции разности аргументов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

о

йс с:

со

ГО ^

МОСКОВСКИМ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В.ЛОМОНОСОВА ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

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

УДК 519.853

Дудов Сергей Ипанооич МАКСИМИН ФУНКЦИИ РАЗНОСТИ АРГУМЕНТОВ

01.01.09 - математическая кибернетика

Автореферат

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

Москва - 1997

Работа выполнена на кафедре дифференциальных уравнений и прикладной математики механико-математического факультета Саратовского государственного университета им. Н.Г.Чернышевского

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

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

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

доктор физико-математических наук, профессор Е.С.Половинкин

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

Защита состоится (О 1997 г. в 11 часов

на заседании Диссертационного Совета Д 053.05.38 по математике в Московском государственном университете им. М.В.Ломоносова по адресу: 119899, ГСП-3, Москва, Воробьевы горы, МГУ, факультет ВМиК, ауд.685.

Автореферат разослан О С&ссГкЛ^^ 1997г.

Ученый секретарь Диссертационного Совета профессор

Н.П.Трифонов

Общая характеристика работы

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

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

^(.r) = min/(.г - ;j) max, (1)

ycQ sei)

где V. и D некоторые замкнутые множества пз конечномерного пространен ва R''. а /(•) функция, определённая на открытом множестве S, которое содержит множество D — Q = {г — у £ Rp / .г £ Д у £ i}}.

Выяснилось, что некоторые задачи наглядного геометрического характера (например, задачи о внутренней и внешней оценке множества шаром произвольной нормы) также сводятся к задаче вида (1). Частным случаем функции ^(.г) в задаче (1) является функция расстояния (ФР) от точки до множества в некоторой норме п(-) :

ро(.с) - min n(.r - у). (2)

у ей

Хорошо известна ее важная роль в негладком анализе, теории приближений и других разделах математики.

Задача отыскания максимина функции разности аргументов (1) и ФР (2) являются главными объектами исследования диссертации.

Многие успехи в решении минимаксных задач связаны с исследованием маргинальных функций (функций максимума и минимума), сначала с распадающимися, а затем со связанными неременными. Дифференциальные свойства таких функций изучались б работах В.Ф.Демьянова1, Б.Н.Пшеничного2, Дж.Данскина, А.М.Рубинова, М.С.Никольского, Л.И.Минченко, 11.Т.11осаГе11аг, ИЛашп, .Шатчи, Р.ВиЬеаи, Л.-В.Шпаг1--игпиу и др. Другой подход к решению минимаксных задач, известный по работам В.В.Федорова3, основан на применении метода штрафов. К решению минимаксных задач применялся также метод линеаризации Б.Н.Пшеничного4 и его модификации. Полученные результаты, касающиеся как необходимых и достаточных условий решения, так и алгоритмов решения, опирались на довольно жёсткие предположения.

Часто в задачах параметрической оптимизации проектируемых технических устройств, которые сводятся к задаче вида (1), функция j(x), а также функции, которыми задаются множества П и £>, сами являются маргинальными функциями или функциями, от которых нельзя требовать более, чем дифференцируемость по направлениям. В этой ситуации обычно становится невозможным перенесение известных ранее результатов для минимаксной задачи общего вида на случай задачи (1) из-за невыполнения предположений, при которых эти результаты были получены.

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

'См.напр.: В.Ф.Демьянов. Мшпшакс: дифференцируемость по направлениям. П.: изд. Ленпнгр. ун-та, 1974.

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

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

4См.: Б.II.Пшеничный. Метод линеаризации. М.: Наука, 1983.

5См.напр.: В.С.Балаганский, Л.П.Власов. Проблема выпуклости чебышевских множеств // Успехи матем. наук. 1996. Т.51г N6. С.125-188.

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

Цель работы заключалась в

а) нолучешт необходимых и достаточных условий решения задачи (1) при основном предположении о дифференцируемости по направлениям функции /(•) и функций, лебеговыми множествами которых являются il и D; конкретизации этих результатов для случая квазидифференцируемых функций 6;

б) исследовании свойств ФР с произвольной нормой, а именно, требовалось:

- установить необходимые и достаточные условия дифференцируемости ФР по направлениям в фиксированной точке, а также получить соответствующие условия субдифференцируемости и супер-дифференцируемости ФР (в определении В. Ф. Де.и ья нов а-А .М. Ру-бинова6);

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

- установить случаи непустоты и формулы субдифференциала и супердифференциала Пено'ФР;

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

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

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

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

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

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

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

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

При изучении дифференциальных свойств ФР во многом использовалась техника и некоторые идеи геометрического характера, наработанные в трудах В.Ф.Демьянова" • и Б.Н.Пшеничного по исследованию функций маргинального вида. Главные результаты базировались на получении формулы нижней производной Дини ФР по направлению и оценки сверху для верхней производной Дини ФР по направлению, а также на рассмотрении случаев выпуклости и вогнутости ФР.

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

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

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

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

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

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

Практическая значимость. Задача отыскания максимина функции разности аргументов может иметь приложения в задачах наглядного геометрического и технического содержания. Примеры таких приложений, задачи о внутренней и внешней оценке множества шаром произвольной нормы, а также некоторые задачи параметрической оптимизации проектируемых устройств, даны непосредственно в диссертации. При сотрудничестве с разработчиками радиотехнических устройств, результаты диссертации были использованы соискателем при расчёте номиналов и допусков на параметры для ряда СВЧ-устройств ([1]-[3]).Отметим также, что максимин нормы разности аргументов задействован в определении расстояния Хаусдорфа между множествами и, следовательно, результаты исследования задачи (1) могут быть полезными при решении задач по равномерной оценке сложных множеств множествами простой геометрической структуры.

ФР широко применяется в математике, как инструмент исследований. Установленные в диссертации новые свойства ФР могут увеличить круг ее приложений.

Апробация работы. Результаты диссертации докладывались на Саратовских зимних школах по теории функций и приближений (1986, 1988,1990,1992,1994,1996 гг.), Воронежских весенних школах 4Понтря-

гинские чтения" (1993, 1994 гг.), международной конференции "Функциональные пространства, теория приближений, нелинейный анализ", посвященной 90-летию академика С.М.Никольского (Москва, апрель-май 1995г.), международной конференции "Негладкий анализ и многозначные отображения1' (С.-Петербург, май-июнь 1995г.), международной конференции "Современные проблемы математики и механики", посвященной 175-летию со дня рождения П. Л. Чебышева (май 1996), конференции "Алгебра и анализ" (Казань, июнь 1997г.), а также докладывались и обсуждались на семинарах кафедры математической теории моделирования систем управления С.-ПбГУ,кафедры оптимального управления МГУ, Вычислительного центра РАН, Института высокопроизводительных вычислительных систем РАН, кафедры дифференциальных уравнений и прикладной математики СГУ.

Публикации. Основные результаты диссертации опубликованы в [4]-[16]. Их приложения к задачам параметрической оптимизации некоторых радиотехнических устройств отражены в [1]~[3], а также в книге В.П.Мещанова, А.Л.Фельдштейна8 (глава 10 "Вопросы расчёта допусков" написана вместе с В.П.Мещановым) и в книге В.П.Мещанова и др.9 (глава 6 "Оптимизация допусков" написана вместе с В.П.Мещановым).

Структура и объем работы. Диссертация состоит из введения, четырех глав, списка литературы (содержащего наименования), списка обозначений и изложена на 274 стр. машинописного текста.

Основное содержание работы

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

Первая глава посвящена получению необходимых и достаточных условий решения задачи (1). Основные требования к объектам, опреде-

8См.:В.П.Мещанов, АЛ.Фельдштешг. Автоматизированное проектирование на-

правленных ответвителей СВЧ. М,: Связь, 1980.

эСм.: Б.М.Кац, В.П.Мещанов, АЛ.Фсльдштейн. Оптимальный синтез устройств

СВЧ с Т-волнами. М.: Радио и связь,. 1034.

ляющим задачу, таковы. Предполагается, что множества i2 и D заданы в виде

Q-{xeRp/ h{x) < 0}, D = {x eRp / Ла (x) < 0},

где функции h(x),h1(x), а также f(x) - непрерывны и дифференцируемы по любому направлению всюду на RP. Получаемые результаты выражаются через свойства производных по направлению этих функций:

h'(x,g) + - Л(ж)], h\{x,g), f{x,g),

а также через конусы вида

ъ(х) = {g€Rp / h'(x,g) < 0}, = {д G Rp / h'(x,g) < 0}.

Многие успехи в получении необходимых и достаточных условий решения максгшинных задач связаны с исследованием дифференциальных свойств маргинальных функций. Наличие дифференцируемости по направлениям целевой функции в экстремальной задаче позволяет использовать известные схемы получения необходимых и достаточных условий решения. Однако, условия, гарантирующие дифференцируемость по направлениям функции <р(х) в задаче (1), если применить к ней известные результаты (например, В.Ф.Демьянова7''*, Б.Н.Пшеничного2, А.М.Рубинова*), являются довольно жесткими. Трудности того же характера возникают и при попытке получения оценок для верхней и нижней производных Дшш функции (р{х) по направлениям, которые также могли бы быть использованы при получении условий оптимальности''.

Подход, использованный в диссертации к получению условий оптимальности в задаче (1), не связан с изучением дифференциальных свойств функции <р(х). Он изложен в §1 и опирается на использование оценок конуса Булигана лебеговых множеств функции <р(х), а также допустимого множества D. Его суть раскрывается в следующих двух теоремах.

Теорема 1.1. Для того, чтобы точка Хо € D была точкой максимума функции <р(х) на множестве D, необходимо, а в случае, если D - выпуклое множество и ¡р(х) - вогнутая на открытом выпуклом

множестве S Э D функция, имеющая точку непрерывность. Х\ 6 D, то и достаточно, чтобы

T(xo,D)cT(xo,G(xo)). (3)

Здесь G(xо) = {х G S / ц>(х) < ¥>(х0)}, а

Г(х, А) = {g G Rp/3o(a) £ Я", {afc} | 0, jfe оо :

х + akg + о(ак) е А, с*~1о(а) 0, а 4- 0} - конус Булигана множества А в точке х.

Теорема 1.2. Если для точки х0 € D имеет место соотношение

r(xQ,f)nr(xo,Gc(xo)) = {0}, (4)

где Gc(x0) — {х Е S / <f(x) > ip(a'o)}, то она является точкой строгого локального максимума функции <р(х) на множестве D.

Как следует из теорем 1.1 и 1.2, условия оптимальности в экстремальной задаче можно получать через оценку конусов Г(жо,£>), Г(го, С(х'о)) и Г(х-(|,Сс(жо). Поясним, как это осуществлялось по отношению к задаче (1).

Для конуса Г(х'о, D) нужны оценки снизу и сверху (то есть, внутренняя и внешняя, по включению). При нашем предположении о том, что D - лебегово множества функции hi(x), первая оценка, при hi(x0) — 0, очевидна

cl-y^ixo) С r(ar0,D).

В качестве оценки сверху, при дополнительном предположении липши-цевости функции h\(x) в окрестности точки Хо, использовалось включение

Г(х0, D) С ЪмЫ)-

Если же /¿i(a'o) < 0, то, в силу непрерывности h\[x), очевидно, T(x0,D)=R"

Основную сложность представляет оценка конуса Г(ги, G(x0)). Идея ее получения заключается в представлении множества С(а'0) в виде (теорема 1.3):

G{xq) = W(x0) +х0,

где И'(х0) = {]) £ Лр//(.го —у)< <р(хо)}. Это дало повод для изучения в §2 локальной аппроксимации алгебраической разности пересекающихся множеств конусом Булигана. Проведенные исследования, в частности, показали, что при определенных условиях справедливо включение

Г(г„,6'Ы) С и {Г(г,П)-Г(г,Щ*0))},

*еС!(,х о)

где = {г € П//(х0 — г) = 1р(х0)}. Следовательно, принимая во

внимание приведенные выше соображения по оценке конуса Г(х0,О), при некоторых условиях будет иметь место оценка

Г(жо,С(*о)) С и {71,а(2)+71,/(*о-2)}

г6<3(г0)

которая использовалась далее для получения необходимого условия решения задачи (1). Отметим, что данная оценка справедлива не всегда (пример 2.1).

По аналогичным соображениям, реализация соотношения (4), или, что то же самое, включения

Г(г0,О) С {/АГОго,0'сЫ)}1К°}

для получения достаточного условия строгого локального максимума функции <р{х) на О л задаче (1), осуществлялась на основе оценки (лемма 4.4)

и Ы*)+7/(*0-*)},

¿е<2Ы

справедливой при условии линшицевости функции /(ж) в окрестности точек х0 — г для г 6 С^(х0).

Основные результаты главы содержатся в §§3-4. Сформулируем две главные теоремы, используя, кроме уже введенных, обозначения: с1А -замыкание множества Л, В(х,6) = {у Е ВР / Цж — у\\ <

<?(*)= II {7Ф)+7/(®-г)}и{0},

гес?(г)

^Я(х)

Теорема 3.5. Пусть х$ € О и е каждой точке г € <3(ж) выполняется /г(г) = 0, а также хотя бы одно из условий:

1) функции f(x) и h(x) липшицевы соответственно в окрестности точек Xq — z и z и выполняется соотношение

71^(2) n{-7li/(:i:e-*)} = {0},

2) функции f(x) и h(x) липшицевы и квазивыпуклы в окрестности точек Хо — z и z соответственно,

3) хотя бы одна из функций h'(x,g) и f'(x,g) полунепрерывна снизу по совокупности переменных соответственно в точках (2,5) € Я2р и (х0 - z,g) € R2p для любого g G RP,

4) функция /(;г) или h(x) липшицева и квазивогнута соответственно о окрестности точки Хо — z или z,

5) функция f(x) или h(x) липшицева и квазивыпукла соответственно в окрестности точки хв — z или z, причем

Кр\ъ,}{хо - z) С -7/(^о - z) или fipVyu(z) С -7л(2)-

Тогда для того, чтобы функция <р{х) достигала в точке наибольшего на D значения, необходимо, чтобы

С\{ха) = Rp, если k\(xn) < 0,

cl 7/,j (х0) С Ci(x0), если кг(ха) — 0.

Теорема 4.4. Пусть х0 £ D, функция h\(x) липшицева в окрестности точки хо, а функция f(x) в окрестности точек xq — z для всех z 6 Q{x0). Тогда, если

С(ха) = Rp, при hi(xo) < 0,

7i,fciOco) С С{хо), при hx(x0) = О,

то х"о - точка строгого локального максимума функции (р(х) на множестве D, причем сущестщют е > 0, <5 > 0, такие что

¡р(х) < <р(х0) - е|[ж - аг0||, Vx Е DC\B(x0,5).

Теоремы 3.5 и 4.4, как и другие, доказанные в § § 3 - 4, сформулированы на языке свойств функций f'{x,g), h'(x,g),h'1(x,g) и конусов

вида 7(-) и 71(-). Это позволяет использовать их для различных классов функций, в том числе недифферендируемых, с определенными свойствами и формой производной по направлению. В §5 условия и выводы доказанных в §§3-4 теорем переведены на язык квазидифференцируемых, в определении В.Ф.Демьянова -А.М.Рубинова6, функций.

Вторая глава диссертации посвящена изучению дифференциальных свойств ФР (2). Кроме того, что ФР является важным частным случаем функции ^(х) в задаче (1), она, во многом, представляет самостоятельный интерес. Исследованием ее свойств занимались известные специалисты негладкого анализа' ,£,и теории приближений5" .

Давно известно, что если О - выпуклое множество, то ФР является выпуклой на IV. Б.Н.Пшеничным2, получена формула её субдифференциала. Им же для произвольного множества О, но уже для евклидовой нормы, приведены условия на выпуклую положительно однородную функцию, при которых она является верхней выпуклой аппроксимацией ФР. В.Ф.Демьяновым6 получены условия дифферецируемости ФР по направлениям и соответствующая формула производной по направлениям, когда О - лебегово множество квазидифференцируемой функции, а п(-) - евклидова норма. В известной монографии Ф.Кларка10 приведены сведения об обобщённом градиенте ФР для произвольного множества П и евклидовой нормы. В более широкой трактовке определения, ФР использовалась в работах Л.И.Минченко11 для изучения дифференциальных свойств маргинальных функций и многозначных отображений.

Обратим внимание на два обстоятельства, которые отражают трудности исследования ФР. Для произвольного множества Я и произвольной нормы п(-) не гарантируется дифференцируемость ФР по направлениям. В.Ф.Демьяновым приведен пример, когда ФР не дифференцируема по направлению в граничной точке множества 12. Пример 7.1 из §7 диссертации указывает на то, что ФР может не быть дифференцируемой по направлению также и в точке х П. Отметим, что этот пример связан со случаем негладкой нормы. В случае же, когда гс(*) - гладкая норма, как и для евклидовой3,6, нетрудно установить дифференцируе-

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

11 См. напр.: Л.И.Минченко, О.Ф.Борисенко, С.П.Грицай. Многозначный анализ и возмущенные задачи нелинейного программирования. Минск.: Навука 1 тэхнща, 1993.

мость ФР по всем направлениям в точках х (jL Q.

Второе обстоятельство заключается в следующем. ФР является примером маргинальной функции и может рассматриваться с этой позиции. Оказывается, что даже если ФР в данной точке обладает дифферснци-руемостью по направлению, то подсчет ее производной по направлению может не вписываться в рамки известных формул производной по направлениям для маргинальных функций^'2'^. Эту ситуацию иллюстрирует пример 7.2 из §7.

Приведем основные результаты §§6-8. Обозначим через

W{x) = {у € Rp / п{х -у)< ра(х)},

Q{x) = {z G и [ п(х - z) - pi2(r)},

Фр - множество функций ф(-), определённых на некотором отрезке [0,а^], принимающих значения в Rp и обладающих свойством а~1ф{а) О ПРИ а I О-

К(х,А) = {д е RPJ3 Ф{-) G Фр,ай > 0 :х + ад + ф{а) £ A, a G (0,аг)}

- конус касательных направлений множества А в точке х. Введем в рассмотрение множества:

Эу(а)€П, z(a)eW(x), ф(-) £ Фр, ГД-г, г) = { 9 е R" / {а,.} J. О,* оо : y(ak) -> z, J , (5)

- л(а^) = акд + ф{ак)

3 у(а) е О, г(а) € И^г), G ФР, Л'р(х,г) = { 5 € Rp / & > 0, {afc} J. О, А оо : у(ак) (б)

у(а) - г(а) = ад + ф(а), a G [О,/?,])

Г , 3 б а, г(а) € И^а), ^ (■) € Фр, ]

= / & > 0 : у(а)г, ^ 0, . (7)

[ Г у (о) - г(аг) = + ^(о), а £ [0, /?г] ]

Эти конусы являются некоторыми совместными характеристиками множества П и нормы п(-). Они не пустые только для г 6 (¿(х), причем, как следует из (5)-(6),

Г(0,п-^(г))= и К{о,а-ш(х))= и кр(х,г).

гвЭО) 2б(ЗИ

А если (¿{х) состоит из единственного элемента, С)(х) = {г}, то

ГР(х,г) = Г(0,П— IV{х)), Кр{х,г) = Ьр(х,г)=К(0,П-\У(х)). Нам также потребуются множества.

Ш» = и {2+Тр(х,2)}, Ш{х)= и {2 + Кр(х,г)}, (8)

геСЦх)

ПЬ(х) = и {г+1„{х,г)}. (9)

^ед(х)

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

Поскольку основные результаты главы формулируются с помощью введенных множеств (5)-(9), то важным является вопрос об их вычислимости, который обсуждается в §6. К настоящему времени накопился некоторый опыт подсчета локальных аппроксимаций множества в точке, в том числе конуса касательных направлений и конуса Булига-В §6 получен ряд условий на й и п(-), при выполнении каждого из которых множества (5)-(9) можно вычислить через подсчет конусов касательных направлений или конусов Булигана множеств О и \¥(х) в точках г € (5(х'). Так в лемме 6.5 приведены условия, при которых имеет место формула

ГДа:,г) = С/(Г(г,П)-Г(г,И'(а:))). (10)

Принципиально важный результат главы - это получение в §7 формулы нижней производной Дшш ФР по направлению (теорема 7.1):

Рп{х>9) = Ит ^а~1[рп(х + ад) - рп(х)] =

афО

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

производной Дини ФР по направлению получена оценка сверху (теорема 7.2):

= ^ ыра'^р^х + ад)-рп{х)]<

^ МьЛ 9-о- (12)

Соотношения (11)-(12) использованы в §8 для получения необходимых и достаточных условий дифференцируемости ФР по всем направлениям в заданной точке.

Теорема 8.2. Для тпого, чтобы ФР была дифференцируемой б точке х по любому направлению, необходимо, чтобы

пг(г) = шах), (13)

и достаточно, чтобы

Ш» = Ш(х). (14)

Если ФР дифференцируема с точке х по направлению д, то

9) = М М п'(х -г,д- £). (15)

Приведенные в §8 примеры 8.1 и 8.2 соответственно показывают, что равенство (13) может не быть достаточным, а равенство (14) необходимым для дифференцируемости ФР по всем направлениям. В то же время, если (¿(х) = {г}, то есть, проекция точки х на множество П. состоит из единственного элемента, то выполняется равенство 0,К{х) = Г2Ь{х) и тогда соотношения (13) и (14) совпадают. Необходимым и достаточным условием дифференцируемости ФР по всем направлениям, при С}{х) = {г}, является равенство

Г(0, а - IV(х)) = К (О, п - Ш(х)),

эквивалентное, в этом случае, и (13) и (14).

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

= Ы п'(х-г,д-£), (16)

где 7(с, О) = {д £ Лр/3 а,>0:г + адё!!,а£ (0, а,,)}. Если в каждой точке г € Я{х) выполняется равенство (10) и = с1у(г,Г1), то,

учитывая, что = К+(дп(х — г)), нетрудно видеть, что фор-

мулы (15) и (16) становятся эквивалентными. Однако, как показывает пример 7.2, равенство (10), а вместе с ним и формула (16), справедливы не всегда.

Далее в §8, с помощью результатов §6, касающихся вычисления конусов (5) -(7), получены достаточные условия дифференцируемости ФР по направлениям конструктивного вида. То есть, в них: требования на О и п(-) выражаются раздельно. Отдельно рассмотрен случай, когда -лебегово множество липшицевой и дифференцируемой по направлениям функции.

В §9 рассматриваются случаи выпуклости и вогнутости ФР. В §9 п.1 установлено (теорема 9.1), что выпуклость множества А является не только достаточным, но и необходимым условием как выпуклости, так и квазивыпуклостн ФР на всем пространстве Пр. Формула субдиф-

Л

фереициала ФР, полученная Б.II.Пшеничным , преобразована к следующему виду

др^(х) = Эп(х - л) П -К+{г, О), V 2 £ <3(х).

Здесь К+ - сопряжение конуса К, дп(-) - субдифференциал нормы. В §9 п.2 получены необходимые п достаточные условия вогнутости ФР на выпуклом множестве (теорема 9.2). Получена соответствующая формула супердифференциала ФР для случая, когда множество О = выпукло (теорема 9.3):

дра(:г) = со{дп{х - г) П Г+(г, В)\г € <2(а:)}, х £ О.

Здесь со А - выпуклая оболочка множества А.

В работах Е.С.Полошшкина12 многие факты из выпуклого анализа перенесены, с соответствующим усилением, на случай сильно выпуклых множеств. В §9 п.З рассматриваются случаи, когда О или ЛР\И являются сильно выпуклыми множествами. Выявлены некоторые особенности

!2См. напр.: Е.С.Половнякин. Сильно выпуклый анализ // Матем. сборник. 1906. Т.187, N2. С.102-130

поведения ФР до таких множеств (случаи сильной выпуклости лебеговых множеств ФР, сильной выпуклости или вогнутости ФР на отрезках, соединяющих равноудаленные от О точки).

В §10 получены условия субдифференцируемости ФР в заданной точке. То есть, это те условия на норму гг(-) и множество Q, при которых ФР дифференцируема в точке т. по любому направлению и существует выпуклый компакт дрр(х) такой, что

Ра 9) = max (v, g), Vg € Rp.

vedpn(x)

Выпуклый компакт дрп(х) называется субдифференциалом ФР в точке х.

Теорема 10.1. Для того, чтобы ФР была еубдифференцируемой в точке х £ U и выпуклый компакт А С Rp был ее субдифференциалом, необходимо и достаточно, чтобы выполнялись соотношения

А = со |{0} |J{v G A/n*(v) = 1}} , где п*(-) — max (v, -).

п(к)<1

Теорема 10.2. Для того, чтобы ФР была субдифферещируема в точке х ^ П и выпуклый компакт А С BP был ее субдифференциалом, необходимо, а если выполняется (Ц), то и достаточно, чтобы

А = {v е А / n(v) — 1},

ПГ(ж) = Ш{х) = {у е Rp / max(v,y- х) + pQ(x) < 0}.

Выяснилось, что если только ФР субдифференцируема в данной точке х, то для ее субдифференциала справедлива следующая формула (теоремы 10.3-10.4)

я и_ i 5п(0)П-Г+(х,П),

- { дп(х - z) п —Q - W(x)), X £ П, 2 е W(x) П ПГ(аг).

В §10 п.З, при использовании результатов §6, получены достаточные условия субдифференцируемости ФР конструктивного вида. В §10 п.4

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

В §11 получены соответствующие условия супердифференцируемо-сти ФР в заданной точке. В §12 выясняются особенности геометрической структуры субдифференциала и супердифференциала ФР, указываются способы построения ФР, обладающей в точке заданным субдифференциалом или супердифференциалом.

§§13-15 посвящены верхним выпуклым аппроксимациям2, (в.в.а.) и нижним вогнутым аппроксимациям7 (н.в.а.) ФР. Учитывая липшице-вость ФР, далее, под се в.в.а. в точке х понимаем выпуклую замкнутую положительно однородную по д 6 В? функцию hf (х, д), для которой выполняется неравенство

1гНх,д)>ргп(х,д), Vg€Rp.

По аналогии, под н.в.а. ФР в точке х будем понимать вогнутую положительно однородную по д функцию h^(x,g), для которой выполняется неравенство

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

В §13 указаны простые способы построения в.в.а. и н.в.а. ФР в заданной точке.

Теорема 13.1. Пусть z - любая точка из Q{x), а Г - выпуклый конус такой, что Г С Lfl(x,z). Тогда выпуклых1. компакт

Б1 = дп(х - z) П -Г+, как субдиффереициал, порождает в.в.а. ФР в точке х, то есть КЦх,д) = max(i>,5) > p¡j{x,g), V<7 € Rp.

v 6BT

Поскольку с очевидностью из (7) следует, что K(z,Q) С Lp{x,z), то теорема 13.1 обобщает соотвествующий результат Б.Н.Пшеничного2, на

случай произвольной нормы п(-).

Теорема 13.2. Пусть для каждой точки г € Q(x) выпуклые конусы Г(г) ф Rp обладают свойством

К+{дп(х - г)) С T{z) С с/(Я"\Г,(г,г)).

Тогда выпуклый компакт

В1 = co{w € Г+(г) / ге Q(x),n*{w) = 1},

как супердифференциал, порождает н.в.а. ФР в точке х, то есть

hl[x,g) = min{w,g) < /&(*,$), Vg 6 Rp.

w йВ*

В §13 п.З показано, что компакт

С = сй{дп( х - г) П N(z, П)/г£ Q(x)},

где Л7(г, П) - нормальный конус Ф.Кларка множества Q в точке г, обладает свойством (теорема 13.3)

>,g) < Pa(x,g) < p¡i{x,g) < max(v,g), Уд € Rp.

uifcO t>fcC

То есть, в соответствии с определением В.Ф.Демьянова13, компакт С является конвексификатором для верхней и нижней производной Дини ФР по направлениям. В случае, когда fi или D ~ Rp\í2 является выпуклым множеством, компакт С является минимальным, по включению, конвексификатором и единственным, в качестве минимального. Одновременно, в этих случаях, он является субдифференциалом Ф.Кларка ФР в точке х.

В §14 при дополнительном требовании выполнения равенств ri(x,z)=d(r(z,fi)-r(ziw(x))), Y(z,ü) = K(z,Q), z € Q(x),

13 См.: V.P.Demyanov. Convexificatioa and concavification of a positively homogeneous function by the same family of linear function // Universita de Pisa. Dipartimento di matcmatica. Gruppo di optimizzazione e ricerca operativa. 3.208.802. Giugno. 1994.

которые влекут дифференцируемость ФР по любому направлению в точке х (ем.(11)-(12)), указаны способы построения исчерпывающих семейств в.в.а. <;)}, Л е Л1 и и.в.а. {к^(х,д)}, А 6 Л2. То есть, это те семейства, для которых выполняется

Р'п{х,9) = № = яир к{{х,д), Уд £ Ш.

Ограничимся тем, что приведем способ построения исчерпывающего семейства в.в.а. ФР в заданной точке.

Пусть А : Ер —> 2Н? - многозначное отображение, сопоставляющее каждому элементу г € С^{х) множество А{г) С Ш так, что

и РМ,

абА(з)

где Р(~,а) - выпуклый конус при каждом а £ А{г). Обозначим через Ах = {Л = (г, а) I гв Я{х), а £ А{г)}, В1 = дп{х- г)П-Р+(г,а).

Теорема 14.1. Семейство выпуклых компактов £ Л1 по-

рождает исчерпывающее семейство в.в.а. ФР в точке х, то есть

Рп^^д) = »1/ тЫь,д), \/у £ Яр. леД1 г(ЕВт

Заметим, что, с точки зрения характеризации решения эктремаль-ной задачи, валено одновременно располагать как семейством в.в.а., так и семейством н.в.а. целевой функции. Наличие семейства в.в.а. позволяет сформулировать необходимое условие минимума данной функции на заданном множестве^". Если же построено также семейство н.в.а., то, как показано в §14 п.З, нетрудно сформулировать и достаточное условие строгого локального минимума. При этом, чем ближе будут построенные семейства к исчерпывающим, тем меньше будут отличаться достаточные условия от необходимых.

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

н.в.а. Пользуясь ими в конкретной ситуации (иллюстрируется на примере 15.1), можно построить все в.в.а. и н.в.а., в том числе и главные

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

Пусть ФР дифференцируема в точке х по любому направлению. Под субдифферснциапом Пено в точке х будем понимать множество

д^ра(х) = Rp/{v,g) < (/a(x,g)^g G R"} Супердифференциалом Пено ФР в точке х называется множество д*ря(х) = {ш € Rpl{w,g) > р'ъ(х,д)Уд € iF}.

Теорема 16.1. Если х € Q, то 3~pq(x) ф 0, причем д^рп{х)=дп{0)Г\-Т+{х, О).

Теорема 16.2. Пусть х ^ О. Для того, чтобы д-рп(х) ф 0, необходимо и достаточно, чтобы

M = соПГ(х) ф W, ри{х) = ра(х). Если дъра(х) ф 0, то имеет место формула

д < рп{х) = дп(х - z) П —K+(z,M),Vz 6 M П W(x).

Соответственно также получены условия непустоты и оценка снизу для супердифференциала Пено ФР в заданной точке.

Оценки и аппроксимации множеств достаточно сложной природы множествами простой геометрической структуры имеют обширные приложения. Можно указать на многочисленные работы, связанные с внешними и внутренними эллипсоидальными оценками множеств и многозначных отображений14. М.С.Никольским и Д.Б.Силиным15 рассматривалась равномерная оценка (в метрике Хаусдорфа) выпуклого компакта

иСм. напр.: Ф.Л.Черноусько. Оценивание фазового состояния динамических систем: Метод эллипсоидов. М.: Наука, 1988

15См.: М.С.Ннколъский, Д.Б.Силин. О наилучшем приближении выпуклого компакта элементами аддиала // Труды матем. ин-та им. В.А.Стсклова. 1995. Т.211. С.338-354

линейными комбинациями фиксированного набора выпуклых компактов. Е.С.Половинкиным рассматривались внутренние и внешние многогранные аппроксимации сильно выпуклых множеств.

В третьей главе рассматривается задача о внутренней оценке телесного компакта шаром некоторой нормы «(■), то есть, задача о вложении в заданное множество шара с наибольшим радиусом. Эту задачу можно записать в виде

ри(х) — тнт(а; — ?/)—> шах, (17)

где И С Яр - компакт, подлежащий оценке шаром нормы п(-), а П = с1(Яр\0). Таким образом, задача (17) является частным случаем задачи (1).

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

В §18 рассматривается случай, когда О является многогранником. Показано, что в этом случае задача (17) сводится к линейной максимин-ной, а затем, известным приемом С.И.Зуховицкого16, к задаче линейного программирования.

В §19 предлагается простой в реализации алгоритм приближенного решения задачи для оценки выпуклого телесного компакта. Основные вычисления на каждом его шаге связаны с отысканием проекции точки очередного приближения задачи на множество О, построением опорной гиперплоскости к множеству О в найденной точке проекции и решением задачи вида (17) для ограниченного многогранника, образованном опорными к О гиперплоскостями (то есть, как показано в §18, задачи линейного программирования).

В §20 дается обоснование сходимости алгоритма, обсуждается приложение задачи (17) к задаче расчета номинальных значений параметров проектируемого технического устройства, обладающих оптимальными допусками, при их априорно заданном соотношении. Отметим,

"'См.: С.И.Зуховицкий, Л.И.Лвдеева. Линейное и выпуклое программирование. М: Наука, 1964.

что некоторые модификации предложенного алгоритма использовались в процессе проектирования ряда СВЧ-устройств (см. также [1]—[3]).

Заключительная четвертая глава диссертации посвящена приложению задачи (1) к одной из задач параметрической оптимизации проектируемых технических устройств. А именно, рассматривается задача расчета номинальных значений параметров устройства, изготовление по которым, в пределах точностных возможностей используемого оборудования, обеспечивает получение устройства с наилучшей качественной характеристикой (задача фиксированных допусков). В §21 приводится формализация задачи в виде

<р(х) = min f(x - у) max, (18)

у€П z£Rp

где функция /(■) задает зависимость качественной характеристики от параметров устройства, а компакт Q отражает точностные возможности используемого для изготовления устройства оборудования. Результаты главы I используются в §22 для получения необходимых и достаточных условий решения задачи.

В §23, при основном предположении непрерывности и квазивогнутости функции /(•), а также выпуклости, телесности компакта Q и О £ тШ, строится алгоритм приближенного решения задачи (18). Основные этапы реализации его шага состоят в

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

- отыскания точки минимума функции Минковского множества П на дополнении некоторого выпуклого множества до всего пространства R1',

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

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

Список работ, опубликованных по диссертации

1. Дудов С.И., Мещанов В.П. Оптимизация гарантированного запаса качества в задачах синтеза радиотехнических систем // Радиотехника и электроника. 1981. Т.26, N б. С. 1161-1165.

2. Дудов С.И., Мещанов В.П. Параметрическая оптимизация проектируемых устройств по критериям стоимости и качества // Обзоры по электротехн. Сер. 1. Электроника СВЧ. М.: ЦНИИ "Электроника', 1990. Вып. 1(1512), 40с.

3. Дудов С.И., Попова Н.Ф. Расчет параметров коаксиальных рези-стивных рассогласованных нагрузок с оптимальными допусками // Электронная техника. Сер. 8. Управление качеством, стандартизация, метрология, испытания. 1991. Вып. 2(144). С. 39-42.

4. Дудов С.И. Необходимые условия максимина функции разности аргументов // Теор. функ. и прибл. Труды III Сарат. зимней школы. Ч.Н. Сарат. ун-т. 1988. С. 52-54.

5. Дудов С.И. О дифференцируемости по направлениям функции максимума // Сарат. ун-т. Саратов. 1989. Юс. Деп. в ВИНИТИ 05.07.1989. N 4470-В89.

6. Дудов С.И. К дифференцируемости по направлениям функции максимума // Теор. функ. и прибл. Труды IV Сарат. зимней школы. Ч.П. Сарат. ун-т. 1990. С. 88-90.

7. Дудов С.И. О некоторых приложениях задачи отыскания максимина функции разности аргументов // Математика и ее приложения. Межвуз. сб. научн. трудов. Изд-во СГУ. 1991, вып. 2. С. 52-54.

8. Дудов С.И. Достаточные условия локального максимина функции разности аргументов. // Теор. функ. и прибл. Труды V Сарат. зимней школы. Ч.П. Сарат. ун-т. 1992. С. 56-58.

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

И). Дудов С.И. Критерий дифференцируемости по направлениям функции расстояния // Теор. функ. и прибл. Труды VII Сарат. зимней школы. 4.1. Сарат. ун-т. 1995. С. 130-130.

11. Дудов С.И. Дифференцпруемость по направлениям функции расстояния // Матем. сборник. 1995. Т. 180. К 3. С. 29-52.

12. Дудов С.И. Внутренняя оценка выпуклого мнолеества телом нормы // Ж. вычиел. матем. и матем. фнз. 1990. Т.36. N 5. С. 153-159.

13. Дудов С.И. К решению задачи фиксированных допусков // Материалы иеждунар. конференции "'Современные проблемы математики и механики", поев. 175-летию со дня рождения П.Л.Чебышева. М.: пзд-во механпко-матсм. ф-та. МГУ. 1996. Т.1. С. 156-159.

I I. Дудов С.И. Субдпфференцируемость и супердифференцируемость функции расстояния // Матем. заметки. 1997. Т. 61, N 4. С. 530 ' 542.

15. Дудов С.И. Некоторые свойства функции расстояния // Тез. докл. конф. "Алгебра п анализ". 1997. Казань. С. 74 77.

16. Дудов С.И. О задаче фиксированных допусков // Ж. вычиел. матем. п матем. фпз. 1997. Т. 37. N 8. С. 937-944.