Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

Скачать файл (13,51Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.04.2024

Просмотров: 178

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Ф . П . Васильев

Лекции

по методам решения экстремальных

задач

Издательство М осковского университета

1 9 7 4

' у

у д к

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

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

Печатается по постановлению Редакционно-издательского совета Московского университета

Рецензенты:

Кандидаты физ.-матем. наук В. Г.	К а р м а н о в ,
М. С. Н и к о л ь с к и й , II. X.	Р о з о в

(С) Издательство Московского 7пиверситета, 1974 г.

О Г Л А В Л Е Н И Е

П р е д и с л о в и е .................................................................................................................											5
Г л а в а	1.	Минимизация функций одной переменной						...............................			7
§	1.	Постановка	з а д а ч и .....................................................................							7
§	2.	Задачи А и Б. Строго квазивыпуклые функции							. .	. .	8
§	3.	Оптимальный пассивный поиск в задачах А и Б							.	.. .	11
§	4.	Последовательный			п о и с к ...........................................................					16
§	5. Метод деления отрезка пополам................................................									18
§	6.	Оптимальный последовательный поиск для задачи А									20
§	7.	Оптимальный последовательный поиск для задачи Б								.	27
§	8.	Метод золотого . с е ч е н и я ...........................................................								32
§	9.	Метод л о м а н ы х ......................................................									35
§	10.	Выпуклые функции. Метод к а с а т е л ь н ы х ................................................									38
§	11.	М е т о д 'п а р а б о л ......................................................................................................									44
§	12.	О некоторых		других методах		м и н и м и зац и и .......................................					47
Г л а в а	2.	Минимизация		функций многих		п е р е м е н н ы х ........................................					51
§	1.	Постановка	задачи.		Обозначения. Вспомогательные сведения						51
§	2.	Градиентный	м е т о д ..........................................................................							65
§	3.	Метод проекции г р а д и е н т а .........................................................								72
§	4.	Метод возможных направлений					.......................................		: • .		77
§	5.	Метод проекции опорных ф у н к ц и й ..........................................								84
§	6.	Метод условного г р а д и е н т а .........................................................								96	101
§	7.	Метод сопряженных градиентов					...........................................................				101
§	8.	Метод Н ь ю т о н а			..............................................................................					107
§	9.	Метод штрафных ф у н к ц и й .........................................................								117
§	10. Теорема Куна			— Т а к к е р а .............................................................................							121
§	11.	Элементы линейного п р о гр ам м и р о ван и я .............................................									131
§	12. О методе случайного поиска и некоторых других								методах .		148
Г л а в а	3. Принцип максимума Л. С. П о н ..............................................т р я г и н а										155
§	1.	Постановка задачи			оптимального ..................		у п р а в л е н и я			155
§	2.	Формулировка принципа максимума Л. С. Понтрягина								. .	159
§	3.	Приближенное		решение краевой			задачи принципа		максимума		168
§ 4.		Связь между принципом максимума ..и классическим вариаци
		онным и с ч и с л е н и е м ....................................................................								177
Г л а в а	4.	Динамическое		программирование.			Проблема	синтеза .			181
§	1. Схема Р. Веллмана. Проблема синтеза для дискретных									систем	181
§	2.	Схема Н. Н.	М о и с е е в а .....................................................................................								191
§	3.	Дифференциальное			уравнение Р.		Веллмана	. . .		' . .	198
§	4.	Проблема синтеза для систем с непрерывным временем. Оцен
		ка п о г р е ш н о с т и ...........................................................................								203
Г л а в а	5. Достаточные			условия оптимальности .............................................							213
§	1.	Достаточные условия оптимальности для задач с закрепленным
		временем.................................................................................................								213
§	2.	Достаточные условия оптимальности для задач с незакреплен									222
		ным в р е м е н е м ..............................................................................				.......				.	222
§	3.	Достаточные условия оптимальности для дискретных управляе
		мых систем. Оценка п огр еш н ости .........................................								227
Г л а в а	6. Методы минимизации в функциональных пространствах									. .	232
'§	1.	Вспомогательные с в е д е н и я .............................................................................									233
§	2.	Некоторые методы минимизации					функционалов .		.	. .	247
§	3.	Задача оптимального управления со свободным правым концом									257

Градиент функционала, связанного с

дискретной

управляемой

системой. Условия оп ти м альн ости

.........................................

273'

Минимизация квадратичного

функционала.

Примеры .

284

Оптимальное управление процессом нагрева

стержня .

294

Оптимальное

управление

процессом

колебания струны

300'

Г л а в а

Методы решения

задач

б ы ст р о д е й ст в и я .................................

308

Постановка

з а д а ч и ........................................................................

308-

Вспомогательный

аппарат.

Критерии

управляемости и

опти

314

мальности

.............................................................................................................

р-метод..............................................................................................................

321

П р и лож ен и я.........................................................................................

327'

Г л а в а 8.

Регуляризация некорректно поставленныхэкстремальных

задач

337

О некорректно

поставленных задачах минимизации .

337

Метод регуляризации А. Н. Тихонова

.............................................

339

Регуляризация при вычислении с погрешностями

. .

349

Регуляризация с помощью аппроксимации множества

351

Усиленная регуляризация

. ' ..................................................

353-

Г л а в а

9. Разностные

аппроксимации

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

35S

Разностная

аппроксимация

для одной

задачи

минимизации

квадратичного

ф у н к ц и о н а л а ..................................................

355-

Разностная

аппроксимация

задачи

об

оптимальном нагреве

с т е р ж н я ..................................................................................................

361

Л и т е р а т у р а ...........................................................................................................

364

П р е д и с л о в а е

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

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

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

В математической постановке задачи сводятся к отысканию экстре мума (максимума или минимума) некоторой функции или функционала J(u ), выражающего собой качество (цену) управления и из заданного множества U некоторого пространства. Требование принадлежности управления и некоторому множеству U выражает собой ограничения, обычно вытекающие из ограниченности наличных ресурсов, возможностей технической реализации управления, нежелательности каких-либо запре щенных (аварийных) состояний и т. п. Задачи отыскания экстремума функционала J (и) на множестве U принято называть экстремальными за дачами. Заметим, что задача максимизации функционала J(u) на множе стве U эквивалентна задаче минимизации функционала —J (и) на том же множестве U, поэтому можно ограничиться рассмотрением задач мини мизации.

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

В основу настоящей книги положен курс лекций по численным мето дам решения экстремальных задач, который автор в течение ряда лет чи тает студентам 3—4-го курса факультета вычислительной математики и кибернетики Московского университета. В книге изложены основы наи более часто используемых на практике методов’ приближенного решения экстремальных задач, теоретическое обоснование и краткая характеристи ка этих методов. Содержание книги можно разделить на две части. К первой относятся две первые главы, где рассматриваются методы мини-, мизации функций конечного числа переменных, во второй части — методы минимизации функционалов, заданных на множествах из функциональных (в основном гильбертовых) пространств н связанных с процессами, опи сываемыми системами обыкновенных дифференциальных уравнений или уравнениями с частными производными.

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

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

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

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

Нумерация формул, теорем, лемм, определений, упражнений в каж дом параграфе самостоятельная; ссылки на материалы, расположенные в

пределах данного	параграфа,	имеют	вид (А), вне	данного	параграфа,	но
в пределах данной	главы —	(В, А)	вне данной	главы —	(С. В. А),	где

С — номер главы, В — номер параграфа, в котором находится упоми наемая формула, теорема или другой материал с номером А. Так, напри мер, теорема 3 из § 1 главы 2 в пределах данного § 1 именуется просто теоремой 3, в других параграфах 2-й главы — теоремой 1.3, в других главах — теоремой 2.1.3. Аналогично, при. ссылках на § В главы С в пределах главы С этот параграф будет именоваться просто § В, вне гла вы С — § С. А. Значок А в тексте означает окончание доказательства теорем, лемм.

Автор выражает глубокую благодарность академику А. Н. Тихонову

за внимание	и поддержку при	написании книги,	В. Г. Карманову,
М. С. Никольскому, Н. X. Розову, прочитавшим книгу			в рукописи и сде
лавшим ряд	ценных замечаний,	И. С. Березину, взявшему на себя труд

по научному редактированию книги и своими советами способствовавшему улучшению содержания книги, устранившему многочисленные погрешности изложения. Автор весьма признателен В. Г. Курилову, В. И. Селиверсто

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

Г л а в а 1

Минимизация функций одной переменной

1. ПОСТАНОВКА ЗАДАЧИ

Пусть на

множестве

U— {и : а ^ .и ^ .Ь }

числовой оси,

где а

b — заданные

числа,

— о о ^ а < & ^ )-(-о о ,

определена

функция

/(и). Под задачей минимизации функции /(и)

на

множестве

будем понимать следующее:

1) найти </* =

inf J

(и);

если на

u£U

u *^ U ,

нижняя

грань достигается,

то

найти точку

которой

J ( u * ) = J * ; 3)

если нижняя грань не достигается на

U, то указать

последовательность и0, щ,

...,

uk,

u ^ U

(k — 0, il,

...)

такую, что

lim J (uk) = J*.

Точку

со свойством J (и*) =

называют точ-

&—*oo

кой минимума J (и) на U, а последовательность

{uh} ^ U

со свой

ством:

lim J (uk) = J" называют

минимизирующей последователь-

k-*oo

на U.

ностью для функции J (и)

Что нам известно из классического математического анализа о методах решения этой задачи? Допустим, что /(и) кусочно-непре рывная и кусочно-гладкая функция на U. Тогда, как известно [126], минимум J (и) на U может достигаться лишь в тех точках ы е!7, в которых или J ' { u ) = 0, или J'(u) не-существует, или J (и) терпит разрыв, или же, в точках, являющихся граничными для множества U. Такие .точки принято называть точками, подозрительными на минимум. Если точки, подозрительные на минимум, найдены, то среди них нужно выбрать те, в которых в самом деле достигается минимум. Для этого обычно исследуется знак производной J'(u ) в окрестности подозрительной точки или знак второй производной J " (и) в этой точке, если J"(u) существует. В результате такого отбора определяются точки, в которых достигается, вообще говоря, лишь локальный минимум J (и) на U. Чтобы найти абсолютный минимум /(и) на U, остается перебрать все точки локального ми нимума и из них выбрать точку с наименьшим значением функции, если таковая существует.

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

Смотрите также файлы

Курсовая работа тепловой расчет спирального теплообменника для конденсации насыщенного пара бензола (.docx

Контрольная работа По курсу История хореографического искусства.docx

Жк тасымалдау дегеніміз.docx

9, 11ші сыныпоушыларынорытындыаттестаттауадайындаужмысыныжоспарынбекітутуралы Білім туралы.docx

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

Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

Смотрите также файлы

Информация

Списки файлов

Дополнительно