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

г V) н

О МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ' ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В.ЛОМОНОСОВА

Факультет вычислительной математики и кибернетики

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

СТРЖАЛОВСКИЙ Александр Сергеевич

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

01.01.09 - цате!£атаческая кибернетика

АВТОРЕФЕРАТ

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

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЩИИ И ОРДЕНА ТРУДОВОГО КРАСНОГО ШАМЕНИ ' ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В.ЛОМОНОСОВА

Факультет вычислительной математики и кибернетики

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

СТРЕКАЛОВСКИЙ Александр Сергеевич

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

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

АВТОРЕФЕРАТ

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

Работа выполнена на кафедре методов оптимизации Иркутского государственного университета

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

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

доктор физико-математических наук, профессор Стронгин Р.Г.,

дохтор $изико-математических наук, вед.н.с. Антипин А.С.

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

ggmHTa диссертации состоится "/?$" QKTJlSjc-f 1993 г. в "// " часов на заседании специализированного совета при факультете вычислительной математики и кибернетики Московского государственного университета им. М.В.Ломоносова по адресу: 119899, ГСП, Москва, Ленинские горы; МГУ, факультет Вычислительной математики и кибернетики, ауд.

С диссертацией можно ознакомиться в библиотеке факультета ШиК MI7

Автореферат разослан •¿f' tehfs^ 1993 Г.

Ученый секретарь специализированного совета, и

профессор ^fiS^x^ Н.П.Трифонов

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

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

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

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

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

1) выпуклая максимизация (ила вогнутая минимизация) на допустимом мнояестве;

2) оптимизация на дополнениях выпуклых мнонеств (обратно-выпуклое программирование);

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

4) минимизация липшициевых функций.

Известные-численные метода глобальной оптимизас:-:. тзкте, например, как метода отсечений, внешней и — ут мации, вегвей и границ, характеризуются ¡частотой геометрических построений с одной стороны, ~ другой, отсутствием аналитических эквивалентов очевидна: неметрических построений, а такие отсутствием связей с пленной теорией экстремума и классическими методами ог~.■ ;.зации, -

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

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

б) решение является точкой Куна-Таккера;

в) значение двойственной задачи является нижней оценкой для исходной задачи.

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

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

Для этого необходимы:

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

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

3. Новые методы исследования глобальной сходности, а также сравнительной эффективности построенных алгоритмов.

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

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

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

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

1. Развит аппарат выпуклого анализа (например, дано описание элементов поляры множества Лебега выпуклой функции, даны различные аналитические эквиваленты включения некоторого мно-кества в другое выпуклое множество).

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

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

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

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

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

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

Реализация. Метода, разработанные в диссертации, использовались:

1. При разработке пакета программ глобальной оптимизации на ВЦ Иркутского университета.

2. При разработке пакета прикладных программ для решения задач энергетики в Сибирском энергетическом институте СО РАН. Работа выполнена в рамках НИР "Теория и методы оптимизации управляемых процессов" по постановлению СФТМН Президиума АН СССР $ ПОО-494-1216 от 05.12.85 г. £ госрегистрации 01870004239, а также проекта "Методы линейно-квадратичных аппроксимаций и их программное обеспечение для решения задач оптимального управления", получившем гранд Министерства науки, высшей школы и технической политики РФ на 1992-1993 гг.

Результаты, изложенные в диссертации, являются частью спецкурса "Дополнительные главы методов оптимизации", читаемого на математическом факультете Иркутского университета.

Апробация работы. Результаты диссертации докладывалась на международном семинаре "Функциональный анализ и его отклонения

(Константин, Алжир, 1987 г.), на УП-й Всесоюзной конференции по проблемам теоретической кибернетики (Горький-Н.Новгород, 1988 г.) международной школе-семинаре по методам оптимизации и их приложениям (Иркутск, Байкал, 1989 г.), всесоюзной конференции по дифференциальным уравнениям и оптимальному управлению (Ашхабад, 1990 г.), международном семинаре по негладким и разрывным задачам оптимизации и управления (Владивосток,

1991 г.), школе-семинаре "Разрывные динамические системы" (Ужгород, 1991 г.), на 15-й конференции 1Р1Р по моделированию систем и оптимизации (Цюрих, Швейцария), на Ш-ем мевдународ-ном семинаре по глобальной оптимизации (Иркутск, Байкал,

1992 г.).

Материалы диссертации неоднократно докладывались и обсуждались на следующих семинарах:

- в отделе вычислительных методов и оптимизации Института кибернетики АН Украины (Киев);

- по недифференцируемой оптимизации Института вычислительной математики-процессов управления при факультете ПМ-ПУ Санкт-Петербургского университета;

- по метода;.! оптимизации кафедры вычислительной математики ФВМК Московского университета им. М.В.Ломоносова;

- по методам оптимизации в отделе прикладной математики ШТК РАН (Москва);

- по оптимальному управлению Института математики АН Бело-руси (Минск);

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

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

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

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

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

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

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

Как известно, метод Дубовицкого-Милзотина для общей вкст-. ремальной задачи

f (#} — тасс} xez£>i} ¿=/,...,/га ; •■ (D

основан на аппроксимации допустимых мнокеств; i- , Ь -и множества возрастания в точке 2 е В = П D^

ВГ{Х/{(Х)> {U)} локальными в точке ¡2 выпуклыми коническими аппроксимациями

X., ¿ = о, /,..., т .

Тогда из того, что Z является локальным максимумом в задаче (I), вытекает геометрическое условие:

Л Оъ. = 0 . (2)

i*ß I

Аналитическим эквивалентом геометрического условия (2) является, как известно, уравнение Эйлера-Лагранжа, из которого вытекают различные варианты правила множителей Лагранжа.

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

f(X)-—maJC, x^D, (Р)

( -f - выпукла, Jc^ ) и обратно-выпуклое программирование

- min, д(х) ^ о, сге^, (РЯ)

( ^ - выпукла, 5 с: X , (f - непрерывна) геометрия (2) не является естественной для характеризацпк глобального решения, поскольку локальные конические аппроксимации для этих задач не могут претендовать быть достаточно широкими, и тем более исчерпывающими.

Как было замечено специалистами, для выпукло-вогнутых за-

дач оптимизации необходимо применить другую геометрию - "геометрию включений". Например, для задачи (I) или для задачи (Р) она имеет вид:

в й п 3,с С , (3)

где С — X \ Л0 - дополнение множества возрастания Ъ0 ■ Однако для описания различного типа включений аппарат выпуклого анализа был разработан недостаточно. Поэтому превде всего было предпринято следующее развитие аппарата выпуклого анализа. Пусть

лебегово множество выпуклой функции

на

В - пространстве X

Предложение I. 1.1. Пусть ) - слабо компактно,

и'Е. X* 11 существует ЦЕ. 5 £ )

' < у*, и - г> ^ о .

Тогда для того, чтобы 2)- 2 ]° , необходимо и г

достаточно, чтобы существовшга крайняя в 5(/, 2) точка ЫЦФ1, )] ) , И число X =» о такие, что'''

/•ф = f(Z), Хч'е д{(у),

- г > = у*, х-г>/х(=5(£ 2 /,

где с^; - субдкфгазренциал функции в точке

С помощью этого результата получен следующий критерий включения некоторого множества А с X в лебегово мнопест-

во5слг; .

Предлоаение 1.1.2. Пусть выполнены условия предыдущего предлонения. Тогда для тогб, чтобы

А с.{д;е X • {(Х)^ f(Z)} ,

необходимо, а в случае выполнения условия и достаточно, чтобы

где Л/(2/А)={я*е XV <Х*СС~2>^0}. # Обобщение этого результата на случай, когда множество Лебега

не обязательно компактно, дают следующие предложения. Предложение 1.2.1. Пусть С - выпуклое замкнутое, а!?-произвольное множество из X , причем С ПВ^ 0 . а Х~ рефлексивно.

Тогда включение Ъ с С имеет место в том и только в том случае, когда

А/(г//С С, (6)

гае {% С - грашща С .

Предложение 1.2.2. Пусть А ,В , С - непустые выпуклые подмножества из X » причем, В % С открыты и.

А П В <= 0,

Тогда, если справедливо

(АПВ)а С, (?)

то верны включения

ы(р с)<= n{^1а пв) {ъс . (8)

Если же, кроме того,

С) п Ы(у/А )= {о) /гс, о)

то из (8) будет следовать (7). ££

На основе полученного развития аппарата выпуклого анализа исследуются задачи выпуклой максимизации (задача (Р )) и обратно-выпуклого программирования (задача (PR)). Так, в § 1.4 рассмотрена задача выпуклой максимизации.

Теорема 1.4. 1(2). Если Т) является глобальным максимумом в задаче (Р) (2 £Р)), то

¿ели же, кроме того, выполнено предложение (/■?), то условие {и) становится и достаточным для того,

чтобы 2 е Агд тсюс(/, Ъ).

В случае, если'множество Лебега^С/, 2 ) слабо компатно, то необходимо рассматривать в условии (Е ) только те ^ '■ f(íj} = i( 2), которые являются крайними точками •

Далее выясняется существенность предположений теоремы и уста-

возливается связь условия глобальной оптимальности (Е ) с классическими результатами. Так, легко видеть, что в гладком случае условие (Е ) при ^= 2 обращается в известное условие локального максимума в задаче (Р):

< /'(2 ), х-г > г= о Чх^Ъ, (Ш

доказываемое обычно для выпуклого В ..

Однако в (Е ) не предполагается выпуклость множества Б . Аналогичное замечание верно и в негладком случае для условия Рокафеллара:

д/(Н)с= А/С 2/5) (£Ш

вытекающего из (Е ) при ^ — 2 .

С целью обеспечить применение условия (Е ) ему можно придать экстремальную форму.

Теорема 1.4.3. В условиях теоремы 1.4.2 для того, чтобы точка £ являлась глобальным решением задачи (Р ), необходимо, а в случае справедливости (Н ) и достаточно, чтобы

любая максимизирующая последовательность]X г линеаризованной задачи:

< у*, х > —^ тах, х^д (Р£)

удовлетворяла условию:

¿ът < ^ 0. #

Поскольку решение задачи (Р£, ) легче, чем (Р ) (в случае выпуклости О задача (РА ) оказывается выпуклой), то и' больше шансов решить (Р ) с использованием известннх численных методов. С другой стороны, рассмотрение задач(Р1-)\[у> д{ (Ц) процесс довольно трудоемкий. Однако, чтобы убедиться, что 2 не является глобальным максимумом в задаче (Р), достаточно найти единственный набор

= , прикотором

< у*, а-у>>о .

Это позволяет значительно упростить процесс отбраковки локальных Maiici5.ryi.ioB в задаче (Р ), как показывают примеры, представленные в главе I и главе П.

Далее, в § 1.5 рассмотрена следующая задача:

f0(x) — max, f{ fx0, i=f,...,tn, (I0) Лх= S , лев A ,

где f0 , jf - выпуклые функции, A CI X, A ~

линейный оператор из X в JQ пространство Р .

При некоторых предположениях регулярности удается из условия ( Е ) для задачи (10) при (j — Z получить аналог правила множителей Лагранжа. Это в свою очередь позволяет установить взаимосвязь между предложенным в теоремах 1.4.1-3 подходом и классическими условиями оптимальности типа правила множителей.

Параграфы 1.6-7 посвящены исследованию задач на дополнениях Выпуклых множеств. Так, в § 6 изучается задача:

f(iг) — min, эс<= д, (id

где множество D обладает непустым выпуклым дополнением С, С й X \ Д z е (D П ci С )cft В , а / может быть, в частности, непрерывным.

Основным результатом в § 6 является Теорема I.6.I. Ь У Для того, чтобы Z G ■fzD была глобальным минимумом в задаче (II), необходимо, а в случае справедливости условия

ЗГс X : /(1Г)< f(2) , СЮ

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

vyefic, VfsN(f/C), 1 цз) VX:f(X)s.f(Z)\

il) В частности, из (13) при ^ = Z следует

NU/С) с cone df**(z), (м)

где -f - биполяра функционала / • #

Как известно, традиционные условия оптимальности для задачи (II) дают лишь

дс /(z) П л/(г/ %)Ф Ф , as)

где ^ - некоторая локальная в точке 2 , коническая аппроксимация множества J) , а дг{(.' ) - скажем, суЗдкфференциал

Кларка. Условие ке (13) принципиально отличается от (15), поскольку работает с дополнением С допустимого множества Ъ • Если условие (13) представить в виде

А/(^/С)с VyefzC, аз1)

то разница с (15) становится совсем очевидной. Например, при дифференцируемой f (' ) из (14) следует

</'(z), 0c-z > < 0 vxglc. (I41)

По форма это условие вроде бы известно (правда, с противоположным знаком неравенства!), но учитывая, что в этом неравенстве участвуют не элементы допустимого множества 1) , а его дополнения С= X \ В , то можно сделать заключение о действительной нетрадиционности .условия (14), которое, как следует из теоремы, является только частным случаем (при Ц= Z ) более информативного ( \/i/€T /7, С ) условия оптимальности (13). . '

С другой стороны, j^z с и n(ff с) рас-

смотрим вспомогательную задачу:

< f, х >max, -f(x)^/ (z). (16)

"Тогда из (13) следует, что для всякой максимизирующей последовательности | хк } задачи (16) должно выполняться условие:

Ш < f, хк- ч > •« О

Если ке найдется хотя бы один набор (U, U , it )'•

при котором < tL- Ц 0 , то точка Z не иявляется точкой глобального минимума в задаче. (II), что и демонстрируют примеры.

Далее, в § 7 рассматривается следущая задача обратно-выпуклого программирования:

■f0(X>) —tnin, h {X О, Ь »/,..., т,

Ах = 6, А ,

где все данные задачи выпуклы, а оператор А : X Р линеен.

Для этой задачи при обычных предположениях регулярности

доказано основное необходимое условие оптимальности в задаче (17).

Теорема 1.7.1. С ) Если допустимая точка 2 , й(Е}— 0 . является решением задачи (17) а^кЪйШП (17)), то

ц-уч^0' „ ]

< \/Х€= СйА: Кх-Ь,' > (18)

Ь I ) Если функция О {• ) имеет слабо компактное множество Лебега

5(^,2 ) = {х<ЕХ/р(Х)< 0 = ,

то в (18) нужно рассматривать только те , (у) = 0 , которые являются крайними точками в <2, 2 ) " • Ц I ) При выполнении следувдего аналога условия Слейтера в задаче (17):

Э^е А •• }< (2), Ау=5, Д ()0 , ь= /,..., т ;

а также условий: Л(Х)= Р, ЬПЬА - АУХ^ О,

то из (18) при 2 вытекает, что

да (г),

Эр*е: 7>* такие; что Г* ^ +1|/>*||л>0,.

Л* Д(Н> 0, ¿- яг,

ЛцХ1 + р*оА, ЧхеАЬ

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

вило множителей (19) и, вообще говоря, с различными множителями Лагранжа ( Л0 ,..., Д т , р ).

К тому же ати условия только частный случай (при 2 ) более общего условия (18).

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

1.(19)

Итак, доказательство условий глобальной оптимальности в главе I существенно используют сложный аппарат выпуклого анализа и его развитие, полученное в предложениях 1.1.1-2 и 1.2.1-2.

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

Учитывая это, в главе П предложены прямые доказательства теорем 1.4.1-2, 1.6.1-2, 1.7.1-3. При этом удалось распространить построенную в главе I теорию на более общие задачи математического программирования. В таких задачах лишь часть данных удовлетворяет условиям выпуклости, поэтому задачи называются частично выпукло-вогнутыми. Далее, методика доказательств условий оптимальности для этих задач отличается, как уже отмечалось, от геометрических подходов главы I, эти доказательства более коротки, педагогичны для незнакомых с выпуклым анализом.

Так, в §§ 1-2 главы П обобщены результаты главы I для задач (Р) и (10) для случая, когда ограничения в (10) заданы локально липшициевыми функциями в присутствии ограничения типа равенства 0 , задаваемого нелинейным оператором

Р-

В § 11.3 исследуется задача:

, /(Я) —ШЛ, 0, .лге 5, (РП)

где <2(») - выпуклая, а / ) - полунепрерывная сверху функ-

Х,5 = X • ' .

Задача (Р/с ) оказывается-значительно более трудной для исследования, нежели задача выпуклой максимизации (Р ).

Так, как было видно уже из теорем 1.6.1-2, 1.7.1-3, здесь условия глобальной оптимальности расслаиваются на необходимые и достаточные: необходимые условия доказаны при одних предположениях, достаточные при других. Так, если предположить, что

В задаче ) не существует точки .^глобального минимума, такой, что (20)

то имеет место следующий результат Теорема П.3.1. . i ) Пусть выполнено предположение (20). Тогда если 2 является точкой глобального минимума в задаче (.pr) ( 2 €

AzgminiPR )). то

vy.w>-o, Vfe da(V 1

11 ) Если f{- ) дифференцируема по Кларку, то из (21) при Ц-Ъ следует, что V (2) 3JU , Л» 0, JU+ 0,

jufeXdcf(z)+Nc{z/S). #

Все комментарии к теореме I.7II остаются в силе, с учетом того только, что f (• ) - не обязательно выпукла. Важно, что. в случае задачи (pfí ) получены более простые, чем в теореме 1.7.3, достаточные условия глобальной оптимальности. Т е'о рема П.3.2. Пусть в задаче (PR )

Ítlf(f,X)^ .f(Z)= 0, (22)

и, кроме того,

ЗА= A(y,f)e c¿coS-.<f, b-y>>o]

Тогда следующее усиление условия (21)

О, toe cScoS, f{X)^f{i),\

становится и достаточным для того, чтобы Z явилось глобальным решением задачи (PR ).

Затем теорема П.3.2 в § П.4 обобщена на случай присутствия нескольких обратно-выпуклых ограничений:

/(£)-— trtitl, F(X)= О, Xej?,

г= i.....т\ (25)

о, ¿=

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

Д являются локально липшициевыми в окрестности Н , а : X Р - нелинейный оператор. В третьей главе диссертации рассмотрены невыпуклые задачи оптимального управления (ОУ) обыкновенными системами. Как правило, принцип максимума Л.С.Понтрягина для невыпуклых задач ОУ является локальной характеристикой и не дает возможности отыскать глобальное решение или хотя бы "выскочить из локальной ямы" в многоэкстремальных задачах ОУ. Известны также вычислительные трудности применения метода динамического программирования, а также условий типа Кротова. Поэтому в главе Ш предлагается использовать результаты двух первых глав для получения необходимых и достаточных условий глобальной оптимальности в таких задачах ОУ, как максимизация выпуклого терминального функционала, и в задачах ОУ с обратно-выпуклыми терминальными ограничениями.

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

'/(я и,))— тах,

где t^[t01t1]й Т . t0 , - фиксированы,

е: ¡¡^ % , остальные ограничения стандартны, л, наконец, функция 7 : /\?/г—^ $ - выпукла я дифференцируема,

и а ¡¡¡>1 . Пусть Х(*,и) ~ решение задачи Коши (27), соответствующее допустимому управлению (¿(' )€Е 21.

Теорема Ш.1.1. Для того, чтобы управление было глобально оптимально в задаче (26)-(28), необходимо, а в случае выполнения условия

Зрет*: 7(р) < /(2(2, ))< +

(где х(1, уу ) ) и достаточно, чтобы & •

/({/)— J (2 () ) выполнялось неравенство:

(26)

(27)

(28)

У О, {ЕОУ)

(где СОд{')= Х0{'¿Л0{Ц]) - решение системы (27), соответствующее управлению (¿0{' , ^ » УД°влетворянщему принципу максимума: ...

У1Ге и ^еГ;, :

с функцией (р (• )= , у) , которая является решением сле-дущей системы:

А^)Ф(^), # ос)

15з этой теореш при 2 ( ) , где £(• ) — Х(* , УТ ) ? вытекает, что глобально оптимальное управление ^

удовлетворяет принципу максимума Понтрягина.

Работоспособность условий оптимальности проверяется на примерах. ' ' ' •

Тагам образом, из теоремы Ш.1.1, а также остальных теорем . главы Ш следует, что для того, чтобы управление ЬО"(•) было глобально оптимальных в задачах подобных (26)-(28), необходимо , а при дополнительных предположениях■и достаточно, чтобы -

= «7(2(¿г» (вде Ж-)-¿СС-, IV)

является решением соответствующей задачи Коши) имело место неравенство (ЕОУ), где . Х^ (' ) - состояние, полученное в результате своего принципа максимума типа (29)-(30). Иначе говоря, имеет место целое семейство принципов максимума (вместо одного классического) и неравенство (ЕОУ).

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

В § 4 главы Ш рассмотрена задача 0У линейной по состоянию системой с терминальными обратно-выпуклыми ограничениями.

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

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

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

1) доказательство условий оптимальности;

2) обобщение этих условий оптимальности на максйшзирую-щие или минимизирующие последовательности;

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

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

5) тестирование алгоритмов на ранее решенных другими ме- • тодами задачах;

6) решение этими алгоритмами практическлх задач;

7) анализ численных экспериментов.

Именно этим моментам в решении задачи выпуклой максимизации и посвящена 1У-ая глава. Так,'в § 1У.1 доказаны необходимые и достаточные условия того, что последовательность^?*]-С В была максимизирующей в задаче (Р ). Для этого вводится следующая функция (р ( Е ) =

х~ ч>/х* т ^дп^

Тогд'а условие оптимальности ( Е ) принимает вид: СР(2) = 0 , а для максимизирующих последовательностей соответствующее условие выглядит так:.

йт о. (31)

/с—

В § 1У.2 предлагается теоретический метод решения задачи (г ) с использованием условия (31), основное правило которого имеет вид:

где к-а,...

£ £,< -*- 00 •

о

При этом последовательность 12 } • генерируемая этим методом является максимизирующей в задаче (Р ).

В § 1У.З предлагается алгоритм максимизации квадратичной функции:

У <Сх\ X > , (33)

гдсХ€Е ¡к , С~ _ матрица положительно определена и

симметрична. ( С ^ 0, С ~ Сг ) .

Для построения алгоритмов гладкой выпуклой максимизации, основанных на условии (31), предлагается использовать следующие предположения

(ЯМ-. УгеБ, V1r•.f(1r)=f(г),

можно найти точку ((е ]) , такую, что

< /,'(1Г)Л>^ шр{<{'{V),X >/хе в }-е;

О*

{ни.) : 0

есть возможность отыскать точку f )— f (И ),

</'(«0," а-иг> + е

Предположение (НЫ довольно естественно и говорит о возможности приближенного решения линеаризованной по целевому функционалу задачи (Р ):

< /V), X >— /ТММ:,' ЯеВ; )

которая в случае выпуклости I) оказывается выпуклой.

Предположение же ) вытекает из природы условия оптимальности (£ ) или (31), где используется поверхность уровня функции / (• ) и предполагает возможность приближенного решения связанной с условием оптимальности (Е ) "задачи уровня":

и,-1Г>-~тах, f(1r)=f(Z). (Ри)

Оказывается, что для квадратичной функции /(•) вида (33) эта задача решается аналитически.

Лемма 1У.3.1. Пусть для $ {' ) , заданной в (33), {{И)>0 , йе^ „ . Тогда для

/Ш, /¿=( Щ/{(и))'/г, (34)

справедливо равенство </'(£(/*), Ц~ 1С > ~

V

Естественно,, что построение алгоритма, основанного на условии (31), не может быть осуществлено с использованием всей поверхности уровняу? | I отвечающей точке 2 . Нужно на этой поверхности уровня выбрать некоторое конечное семейство точек {^(У"1)-), А/, и, используя эти точки, осуществить если это возможно, в;код из уровня на более высокий. С этой целью вводится следующее

Определение 1У.3.1. Пусть заданы точка 2€Е 2), число 8 О и» кроме того, ( 1= 7 N )

Набор !Я, (2 , £ ) назовем (2,6) - разрешающим, если из того, что 2 не является 8 - решением задачи (Р ), то есть •

$и,р )-г, (35)

следует справедливость двух неравенств:

И2)4 тсис </Ы£;, о, (36>

£( 2) 5= # '<37)

Далее, наряду с предположениями íЯ¿ ) и (#£/) рассматривается условие:

(НЯ ): УЕ 0 , и для всякой 8 -стационарной точки можно построить (с,в ) - разрешающий набор Пусть справедливы предположения (///, ) и (НЯ)- Тогда для успения задачи (Р ) предлагается алгоритм, называемый да;:еэ Л -алгооитмем. •

Пусть заданы точка X £ В и последовательность^8 к }", 0 , к = 0,1,2.....£.к + 0(к~°°). Опишем алгоритм по шага:.:. к

1) 2 Б является -стационарной точкой, полученной, исходя из 30К каким-нибудь известнш алгоритмом локального подъема:

К

П) Для Е строится - разрешающий набор:

= 1.1". Мк , строятся точки а1, (= В :

IV) М .строятся точки ОГ^ ^{ИХ 5

V) Вычисляется величина

VI) Если ^ > 0 , то полагаем

хкн \ = к: = к + / , •

и переходим на шаг I..

УЩ Если ^^ 0 «то полагаем '

и переходам на шаг I. -//Замечания. I) При численной реализации -алгоритма, при £„ достаточно малом на шаге У11 при $ О

** /С 'л

производится останов процесса счета, и £ пр- -ется за

приближенное решение задачи (Р ), поскольку из г зления . разрешающего набора имеем

2) Нетрудно видеть, что последовательность { 2*} , генерируемая -алгоритмом, является последовательностью £ -стационарных то^ек..

3) Если Ь > 0 , то

/и^'з-Л2*)^о.

Поэтому в случае ^ ^ 0 , V К = 0,1,2,..., (Ц - алгоритм оказывается строго релаксационным.-

Далее показано, что в случае конечного числа областей приближенной стационарности (К> -алгоритм обладает конечной сходимостью.

На 1-ом и Ш-ем шагах % -алгоритма предполагается использование ачгоритмов локального подъема. Это свойство 01 - алгоритма позволяет использовать стандартные алгоритмы и программы локальной оптимизации. Таким образом, (Л -алгоритм представляет собой комбинацию известных алгоритмов локальной оптимизации и некоторых вычислительных процедур, вытекающих из условия оптимальности. ,

После этого доказывается глобальная сходимость ¡Я -алгоритма.

Теорема 1У.3.1. Пусть в задаче (Р ) с ) , заданной в (33), множество V ограничено, и выполнены предположения (Н1и М), а также

гк>0, к=о, 1,2,... > £ + оо .

Тогда последовательность| 2 к } , генерируемая Щ -алгоритмом, является максимизирующей в задаче ( р ).

В § 1У.4 приводятся конкретные примеры построения разрешайте: наборов в простейших задачах оптимизации, а з § 5 главы 1У представлены результаты численного тестировашш ¡К> -алгоритма на задачах, где решение можно найти аналитически. Затем сложность рассматриваемых задач начинает увеличиваться.

Так, в § 6 приведено численное решение задачи ммаксимиза-цки недифференцированной выпуклой функции на некотором симплексе. При этом оказалось, что для зтой задачи $Ь -алгоритм обладает рядом прекмуцеств перед известными методами. Это касается прежде всего нечувствительности Ж -алгоритма к возрастанию размерности задачи.

Далее, з § 17.? приведены результаты численных экспериментов по квадратичной шкоикизашк на многограннике:

M = {xe Rn/ Ах^ ß } .

Наконец, в 1У.8 представлено численное решение задачи планиро-вакля трассировки и структуры трубопроводных систем, постановка которой была предложена в Сибирском энергетическом институте СО РАН. Эта задача имеет следующую форму:

f(x)ü-iiccl\xifi — min,

' хе^Х^хеКЧАх-бьХЧьО},} С39> тае сС->- 0 , 0 ^ ßi < 1 , Ь =/,...,«■ .

Хотя сепарабельная функция f ) из (39) не является квадратичной, оказалось, тем не менее, что для решения этой задачи можно применять Ж -алгоритм. При этом удалось преодолеть некоторые нерегулярности задачи, связанные .с-недифференцируемостью целевой функции и невозможностью применить лемму 1У.3.1. Татг.е был предложен способ построения разрешающего набора, от-рана:~и;ий специфику задачи (39).

Во всех тестовых и практических постановках задачи (39) численный эксперимент свидетельствует об эффективности. (Я -алгоритма, несмотря на возрастание размерности задачи.

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

Глава У посвящена распространению идеологии решения задачи невыпуклой оптимизации, развитой в главе 1У для- задачи выпуклой максимизации, на задачу обратно-выпуклого программирования:

f(x)-~miü,x<=:S,<j(x)^0, (ря)

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

и пусть, кроме того, - совокупность всех минимизирующих в задаче (г??) последовательностей.

Теорема У. 1.1. Пусть выполнено следуадее предполо-

Не существует {; 0и I , для которой] - .

$ (х* )=><?. /

Тогда, если{2*}е Щ,, то

В отличие от задачи ( Р ) необходимые условия для минимизирующих последовательностей в задаче (Я/? ) значительно отличаются от достаточных. .

Теорема У.1.2. Пусть в задаче (Р/? ) функционал ) полунепрерывен сверху на X и выполнено предположение: ;'

Пусть, кроме того, для некоторю": ; -следовательности }сг $) удовлетворяющей предположению

выполняются следующие услсвк.'г.

шп,а(гк)=0 (41)

где У « . „

Тогда { 2 К } является минимизирующей в задаче

Далее, в §§ 2 и 3 предложены два варианта теоретического метода, которые генерируют минимизирующие последовательности г задаче (Р/?). При этом здесь вновь отчетливо проясняется значительно большая сложность задачи (Р/? ) по сравнению с задачей ( Р ). Так, построение вышеупомянутых методов оказывается возможным при дополнительных предположениях типа ( 0" / ). Основное правило методов выражается неравенством:

где

(43)

3 § У.4 предложен алгоритм глобальной оптимизации для задачи (Р/? \ с квадратичным ограничением:

¡¡(х)й у < Сх, х> - (44)

гдо С-(ИХ П) -матрица. С>0, С~СТ, 0.

Пусть множество St (£,} обозначает совокупность Е -стационарнцх точек в задаче (РЯ ).

Рассмотрим два следующих предположения, использующие понятие Б -стационарности в задаче ( Р/? ):

3\>>0' Уе>0, гнетах Л Vе Улетев); \

можно найти точку

(ЯЯ)

z<EiSt(d£), геЯ, <}(*)> - 6,

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

) ■=£ 0 с некоторой точностью. Сшсл же условия (Я5 ) состоит в том, что для всякой точки, допустимой, но не являющейся стационарной в задаче (РР ), можно найти приближенно

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

Далее, также, как в § 3 главы 1У, вводится понятие разрешающего набора на поверхности уровня Z) СИ 0 » позволяющего выйти из приближенно стационарной точки в точку с меньшим значением целевого функционала, если это возможно.

Для обоснования -алгоритма'необходило использовать два предположения, одно из которых (НЯ ) заключается в возможности построения разрешающего набора во всякой приближенно стационарной'точке, а второе (НL ) - в возможности приближенного реиения задачи:

<y'(V),x> — тасс, x^s, f(oc)^f{i).

В этих условиях для задачи ( PR ) предлагается следующий алгоритм, называемый,как и в главе 1У, $1 -алгоритмом.

Пусть заданы ХК<Е S , 0.{ХК)^0, К =0,1,2,... и последовательности - "

£к>0,: О, 0, K=0,f,2y...

1)Н*е£QU*)^ ))d£K является Геостационарной точкой, полученной, исходя из £ К • согласно (HL) (стандартным алгоритмом легального спуска).

П) Для £к строится (£ , ) - разрешающий набор:

ПО Vi =1,..., ÑK , па: л-.тся точки

«¡'(1Т1), é> +

17) Vi/ = I,.-., N к . строятся точки' iü't/ , такие, что ИТЬсеЕ*: д(ф ) = ^U),

= тр{< f'iirj, и,1-tr>'/(¡m = fi) Ь

по формулам .

где + Г = -к<С2К,2*> .

У) Вычисляется величина: .

У1 Если , то полагаем

Я*4': = -к: = 'К + 1, .

и переходим на шаг I.

УП) Если 0 , то полагаем

= Ък, К- = К+и

ж переходим на шаг I.

При численной реализации $ -алгоритма для достаточно мапого 8 /с на шаге УП при 0 производится останов

процесса счета и принимается за приближенное решение за-

дачи (РЯ ), поскольку из определения разрешающего набора вытекает

ек ,

где

<}{Х)> 0}.

Условия глобалыюй сходимости $ -алгоритма даются следующей теоремой.

Теорема У.4,1. Пусть в задаче (Р/? ) с функцией заданной в (44), выполнены предположения (.Нв), ((?&), (НЬ ) и (), а также

(и)

Пусть, кроме того, числовые последовательности { Е^ } , {8К} и { ®к } таковы, что

а для точки 5 выполнено соотношение

Б^сть наконец для последовательности | Ж * } , генерируемой «Д -алгоритмом, справедлив о^еравенство ■ ,

где .

Тогда последовательность /2 к V является шнимизирующей в задаче (Р£). # 1 '

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

Отметил, что на 1-ом и И-ем шагах % -алгоритма предполагается использование неких классических алгоритмов локального (а в случае шага Ш глобально?, .^дъема линейной функции) спуска, что представляется весьма выигрышным,'поскольку позволяет использовать стандартные алгоритмы и программы локальной оптимизации.

ОСНОВНЫЕ ,., ТМ РАБОИ

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

2. Для следующих невыпуклых задач оптгошзйцкя:

.а) выпуклая максимизация на допустимом икожс-стае;

в) минимизация на дополнениях выпуклых мноеюств (обратно-

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

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

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

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

. ПУБЛИКАЦИИ ПО TEffi ДИССЕРТАЦИИ

Основные результаты диссертации опубликованы в следующих статьях.

1. Стрекаловский А.С. К проблеме глобального экстремума// Доклады АН СССР,' 1987, т 292,' Щ 5, с. I0G2-I066.

2. Стрекаловский А.С. К проблемам глобального экстремума

в невыпуклых задачах оптимизации//. Известия ВУЗов, Серия "Математика", 1990, MS 8, с. 74-80.

3. Стрекаловский. А.С. Об условиях глобального экстремума в одной невыпуклой задаче минимизации// Известия ВУЗов, серия "математика", 1991, гё 2, с. 94-98.

4. Strokalovaky A.S. Global optimization. Theory and algorithms// Abstracts of 15th IJ4P Conference on System Modelling and Optimization. Zurich, Switzerland, 1991, part I, p.186-187.

5. Стрекаловский А.С. Об экстремальных задачах на дополнениях выпуклых множеств// Кибернетика и системный анализ, 1993, Ш I, с. II3-I26.

6. Стрекаловский А.С. К проблемам глобально.'' 'я

б невыпуклых экстремальных задачах // Вопросы кибернетики. Анализ больших систем.- М.: Научный совет РАН по комплексной проблеме "Кибернетика™, 1992, с. 178-197.

7. Стрекаловския А.С. "О невыпуклых задачах оптимального управления // Вестник Московского университета, серия "Вычислительная .математика, и кибернетика 1993, 1, с. 9-13.

8. Стрекаловския А.С. О поиске глобального максимума выпуклого функционала на допустимом множестве // Журнал вычислительной математики и математической физики, 1993, т.33, 3, с. 349-363.

9. Strekalovsky Д., Clobal optimization algorithms corresponding global optiraality conditions // 16th IFIP Conference on SYSTE1 MODELLING AMD OPTIMIZATION, July 5-9 , 1993, Compiegne (France), Collection of Abstracts, volume II, p.825-828.

Подписано к печати 20.09.93. Закал 08.1993 г. Объем 2.0 Формат'60x90. 1/Тб. Т'/"^ ТОО

Подразделение оперативной пол:;гт.. Иркутского государственного университета. 664003.г.Иркутск, 5.Гагарина, 36. .