Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Башкирский Государственный Аграрный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

книги из ГПНТБ / Васильев Ф.П. Лекции по методам решения экстремальных задач

.pdf

Скачиваний:

Добавлен:

25.10.2023

Размер:

14.17 Mб

Скачать

☆

1 / 381 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

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

Лекции

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

задач

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

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, остается перебрать все точки локального ми нимума и из них выбрать точку с наименьшим значением функции, если таковая существует.

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

8 МИНИМИЗАЦИЯ ФУНКЦИИ о д н о й ПЕРЕМЕННОЙ [Гл. I

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

например, функция I{и )	задана лишь таблично или лишь извест
но, что в любой точке	значение /(«) может быть вычислено

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

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

§ 2. ЗАДАЧИ А И Б. СТРОГО КВАЗИВЫПУКЛЫЕ ФУНКЦИИ

Прежде чем переходить к изложению методов минимизации

функций	одной переменной			уточним	постановку задачи.
Пусть функция		J (и)	определена		на отрезке [а,	Ь]— { и :а ^ .
^ и ^ .Ь }	и достигает	на	[а,	Ь] своей	нижней грани,	и пусть тре

буется минимизировать ее на [а, Ь]. В зависимости от того, инте ресует ли нас только точка минимума и*, или же наряду с и* мы

интересуемся еще и значением				/ («*),		следует	различать две	по
становки задачи минимизации [56]:
Задача А:	Найти точку w *e[a,				b] и значение
	J	(и') =	inf	J	(и) =	J".
Задача Б\	Найти	точку	и *^ [а , Ь],			в которой / (ц )= /		(не
интересуясь самим значением J(u * )).
Для приближенного решения					этих	задач	обычно поступают
следующим образом:		1) вычисляют значения функции в каких-либо

специальным образом подбираемых п точках и{, и2, ..., ип из от

резка		[а, Ь]\ 2) перебором значений J (Ui)				среди точек {«i} ( i=
=	1,	..., п) выделяют точку йп, в которой J				(ип) =	min/ (иг);
		точек а, Ь, ии ..., ип					1< £ <п
3)	из		определяют точку				а„,	ближайшую	к
йп слева, и точку Ьп, ближайшую				к	ип справа;		4)	в качестве	и*
принимают какую-либо точку			ип	из отрезка [ап, Ьп]. При реше-
нии задачи А часто полагают			♦	—	(с вычисленным значением
			ип =	ип

§ 2]

Задачи А и Б.

Строго квазивыпуклые

функции

/ (« „ ));

в задаче Б

можно, например, взять

и\

~ ( ап+Ьп)

(зна

чение

J(u*n)

здесь нас не интересует).

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

случаях, когда у нас есть основание считать, что

и * е [ а п,

6„].

Од

нако нетрудно подобрать функцию (даже непрерывную),

для

ко

торой и *ф [ап, Ьп].

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

для

ко

торых всегда «*<=[«„, Ьп].

О п р е д е л е н и е

Функция / («), определенная на множестве

U = { и : а ^ .и ^ .Ь },

называется строго

квазивыпуклой

на

если

существуют

числа

а,

Р,

а ^ а ^ р ^ б ,

такие, что: 1)

J (и)

строго

монотонно убывает

при

a^ .u<Z а

(если а < а ^ р ^ & ) ;

2) J (и)

строго

монотонно

возрастает при

р < и ^ 6

*(если а ^ а ^ р с б ) ;

3) J (и) = / * = jnf/(u)

при а < « < р

(если й ^ а < р ^ й ) ; 4) в точ-

и€(/

ках и = а	и и = р выполняются у с л о в и я : / ( а ) п р и а = а ^ р ^ 6						;
J (а — 0) — lim J (и) > J			(а) > J*	при	а С а С Р ^ б ;	J (b )^ tJ * при
	и-за—О		lim J (и) > J		ф) > J* при
й ^ а ^ Р = 6 ; / ( Р		+ 0) =				а ^ а < р < 6 ;	и
наконец,	в случае	а < а = р < 6		: / * ^ / ( а ) < ;т а х {/ ( а — 0), 7 ( а + 0			}

(эквивалентное и более изящное определение см. ниже в упраж

нении 3)	[135].
Множество всех строго		квазивыпуклых функций на отрезке
а ^ .и ^ .Ь	обозначим через	Q[a, Ь]. Вот примеры таких функций:

h (и) — u2<=Q[a, Ь] при любых a, b\ J 2(u) — |w | + «+ sign (u )eQ [a, 6]

при любых a, b\	J 3( u ) = j ^	’	принадлежит Q[a, 6] при
	l	1» й ^	0 1
любых a, b. Функция
/ 4(й) =	{\|“ 1, “ J o } e Q [ o .		i], но m i - i , 1].
Очевидно, строго квазивыпуклая			функция на U локальных ми

нимумов не имеет, или, точнее говоря, любая точка локального минимума такой функции одновременно является точкой ее (абсо лютного) минимума на U. Если а < Р , то нижняя грань J (и) на U всегда достигается; если а = р , то нижняя грань может и не до стигаться. Множество всех тех функций из Q[a, b], которые до стигают своей нижней грани на [а, Ь], хотя бы в одной точке и*, обозначим через Q*[ct, Ь].

Задачи А и Б мы будем рассматривать на классе функций Q*(a, b], 0 < 6 — а < о о . Для функций этого класса, очевидно, спра

ведливо утверждение: если /(«„) s^m in{/(an), Ц Ь п)}, ап< й п< .Ьп,

то на	отрезке	[а„, Ъп] существует хотя бы одна точка минимума
J (и)	на [а, Ь].	Поэтому намеченная выше схема поиска минимума
оправдана.

1 / 381 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 > Следующая >>>

Соседние файлы в папке книги из ГПНТБ