Введение к работе
Актуальность томи.
Задами на окстромум при налігши ограничений - больаой класс
зодач с которыми приходится встречаться как п собствоіаю
математических провломах. так и в экономике, тохнико, практике
планировании и организации проиоподстпа. СущоствошшЯ вклад в
создпнио теории и мотодоп решении условна)? экстромзльних эздач
шіосли А.С.Аіі7йішіі, С.А.АШшюп, 8.ІІ.Булатов, Ф.П.Васильев,
Р.ГаОасои, А.И.Голиков, Б.Г.ГольатоЯн, А.М.Гунал». О.М.Данидкй,
В.Ф.Домьянов, Р,Г.Евтушенко» И.И.Еремин, П.М,Ермолов, В.Г.Жадан,
Я,И.Заботил, С.К.Заприоп, В.И.Зорквдьцоо, В.Г.Карманов,
А.А.Каплэн, Ф.М.Кириллова, Л.СКрпеноцоков. В.Н.Мэлозомов,
В.С.Михалевич, А.СНомирсвский, К.А.Нурминский, В.М.Панин,
Б.Т,Поляк, А.И.Пропой, Б.Н.Пшоничішй, Н.И.Родковский,
А.М.Рубинор, А.Г.Сухаров, А.К,Тихонов, А.А.Третьяков,
Н.В.Тротьлков, В.В.Фодоров, Н.З.Шор, Л.Б.Юдин.
Хорошо известны работа заруОояшх учоких Р.БроЯдена, К.Ботсариса, . Ф.Вулфа, П.Гклла, К.Гроссмана, Д.Гольдїарба, Г.Зойтондор.ка» В.Зангвилла.К.Кшзиела.Г.Клейіімихеля, К.Ломаропшя, Л.Майна, В.Мюрро*, Р. Мифішина, Д.Ди Пилло, Д.Паллашке, Е.Полака, Д.Розеиз, Ы.Райт, Э.Сподикато, Р.Флатчора, К.-Г.Эльстора.
Многие проблеми в коночном счато сводятся к задаче
rain (f0(x)| ;х ( о с е»), о .- at л пг (і) О,* (X * E*| fj(X) , Ог- (x Ьп| Гл(х)-0. 3J2) , Выделим три основных подхода к рошетш этой задачи.
Первый подход основан на решении той системы уравнений и неравенств, к которой сводятся необходимые условия оптимальности рассматриваемой задачи. Второй подход к решению задачи состоит в тем, чтобы сконструировать Функцию, безусловішй минимум которой совпадает с решением исходной задачи х0 или связан с ней определенным образом. Тогда к х, можно прийти, решто одну или несколько подзадач безусловной оптимизации. В основа третьего подхода легат идея итеративного спуска, не выводящего за пределы допустимого множества. При выборе направления фбтН9 решаете/! вспомогательная экстремальная задача лілейного йля квадреуячного
прогрсмштровашя. Не выводящий из области шаг выбирается из условия достаточного убивания целевой функции. Существуют такие варианты методов атой группы, в которых экстремальная задача выбора направления рошаотся явным образом. При атом используется операция приведения или проектирования градиента.
Обратимся теперь к методам спроектированного лагранжиана, в
которых используются идеи вышензложошшх подходов. При выборе
очередного приближения н о обходимо также рошать подзадачу
квадратичного программирования для определения направления
движения, длину шага в получившемся направлении подбирают так,
чтобы обоспочить убывание некоторой функции, являющейся сродством
оценивания качества приближений. В роли этой функции
использовались квадратичная штрафная фуішция, точная штрафная Функция, барьерная функция и модифицированная функция Лагранжа.
Каждый из вышеприведенных подходов имеет свои достоинства и недостатки и хорош для соответствующего класса задач.
Неоднократно предпринимались попытки выделить общую основу различных методов, чтобы осуществлять единообразно их анализ.
В частности, В.Г.Жаданом разработана единая теория методов нелинейного программирования, в которой затрагивается большая часть численных методов. При атом главное внимание уделяется принципиальным вариантам методов и не обсуждаются их многочисленные модификации и частные реализации.
Следует отметить, что весьма актуален вопрос единого построения вычислительных процессов различных методов, но только дающего возможность единообразного их анализа, но позволяющего также создавать гибридные алгоритмы, соединяющие в себе достоинства различных методов, и эффективно организовывать их nporpavMHj-ю реализации со всевозможными модификациями.
Цель настоящей работы заключается в единообразном построении, исследовании и программной реализации методов различных групп и порядков для решения нелинейных условных экстремальных задач.
Методика исследований базируется на результатах линейной алгебры, выпуклого анализа и теории численных методов нелинейной оптимизации.
научная новизна работы состоит в следу $tf:':
Для мотодоо решения зпдочи нолиноЯноЯ условной "бптамизациі' развит одюшЯ принцип построения направления-'в" п'арамЗтрическсй*" видо, на его основе разработаны новііо^ алгоритми^ методов" линеаризации и возможных направлошіЯ. В каче-ства наїграплонкя з * иторпциошіоЯ точко используются моли'Эицкровзгашо нрщіод9шікЯ" градиент и ортогональная проекция градиента в переменной метрике.
Построены новые алгоритму этих методов с ускоренной сходимость», которая достигается примененном КрКЕОЛИНЭЙНЫХ траекторий па основа квадратичной аппроксимации функция задачи. Предложжи гибридные алгоритмы, сочетающие в собэ методы первого и второго порядков.
Построен новий мэтод спроектироватюго лагранжиана с использованной квадраточноЯ штрэфноЯ функции, кспользукхвдй,. в-отличмо от известных , в качестве направления в итерационное точке модифщировазпшо приведошша градиент и ортогональную нроекш» градиента <,
Предложены новые варианта рогуляризованкых мотсїЗв-'' линеаризации и воэаойшх ' направлений" б; использование^' спроектированного градиента для задач виг.узілогЗ;- прогремміірЬваїшя с погрешностями а исходных денних.
Разраоота.'ш метода спрооктирезагаюгй обобщенного градиента для задачи негладкой оптимизации о ограшиеииями.
Прикладное значение На основе единой схеїяі построений' ёэ'тодов программно реализована ка ПЭВМ IBM PC оптамкзацкотга^ діалоговая система СДИС решо;шя нолинвйких условных экстремальных* з'Йдач г в рамках которой когут прийняться алгоритмы различных r'jTynii' дЪя- решения-разнообразных экономических и технических зада*'!1.- 1 tfeW/ ногут Сить cif/ипоноьош гиСрядіше алгоритмы, исгіо#ьзуйко Ш начальном и конечном этапах итерационного процесса* кётодн- первого» я второго порядков. На базе система ОДиС разработан програмйно-мэтодическиЯ комплекс изучения вышеуказанных методов оптимизаций-
Апробация работа. Результаты, вошедшие в диссертации,- в> 1979-19Э2Г. докладывались автором на семинарах кефэдрн прикладной
- і -
математики МарГУ. кафодри экономической кибернетики КГУ .(рух.-проф. Заботин Я.И.), кафедри математической физики МГУ (ііроф. Васильєв Ф.П.),кафедри исследования операций МГУ (академик РАН Краснощекое П.С.), кафедри теории управления СПГУ (проф. Доньянов В.О.), ИЫМ УрО РАН (чл.-корр. РАН Еремин И.И.), ВЦ РАН (чл.-корр. РАН Евтушенко Ю.Г.), Института Проблем Кибернетики РАН (проф. Карманов В.Г., Фодоров В.В.), ЦЭМИ РАН (і:роф. Гольштойн Е.Г.), Института Кибернетики АНУ (академик Украшш Б.Н.ПшоничішЯ), Технического Университета Дроздона (проф. D-ыдт И., Гроссман К.), Лейпцигского (проф. Фокке И.) и Берлинского (ироФ.Гуддат Ю.) университетов, университета Карлсруэ (проф. Паллзико Д.).
Результати работы докладивались на следующих собраниях : конференции "Динамическое управление", Свердловск 1979, второй сколе-семинаре по оптимизации и ео приложениям в экономике, Ашхпбад 1984, пятой конференции "Управление в механических системах", Казаш 1985, конференции "Проблемы теоретической кибернетики", Иркутск 1985, Горький 1988, конференциях "Математическое программирование и приложения", 1985, 1987, 1989, 1931. 19ЭЗ, Байкальских школах - семинарах "Методы оптимизации и приложения" 1978, 1980, 1986, ІХ-ХІІ Симпозиумах-школах "Системи программного обеспечения решения задач оптимального планирования", Минск 1986, Нарва-Иыэссуу 1988, 1992, Кострома 1990, Межгосударствешюй конференции "Экстремальные задачи и их приложения " Нижний Новгород 1992, Международной вколе-семинаре по оптимизации и приложениям, Иркутск 1989.
Сделаны также доклады на Международных собраниях'.конференции
"Математическое программирование" Зеллин 1983, XI конгрессе по
применении математики в инженерных науках, Веймар 1984,
конференциях по теории математического программирования н
приложениям, Айзенах 1987, 1989, 1990. 33 научном коллоквиуме,
Ильмонау 1988, 8 конференции "Математические и компьютерные
проблемы экономики", Кё'тен IS83, 17 симпозиуме по исследованию
операций. Гамбург 1Э92 в Германии, конференции по
математическому программированию", Галятето 1990 в Венгрии, XV .ИФЙП конференции по системному моделированию и оптимизации, Ц»ркх 1991 в Щвойцарии.
Структура и обьем работа. Диссортоция состоит из зводекия, трех глав, заключения, списка литературы и приложения. ооілД обьем диссертации - 2 20 страниц.
Публикации. По теме диссертации опубликовано 5G почаїїшх работ,основные результати отражены и публикациях прииодонного списка литературы.