Ф.П. Васильев - Методы оптимизации (1125241), страница 2
Текст из файла (страница 2)
Поэтому автор, стремясь сделать книгу доступной широкому кругу читателей, впервые знакомящихся с теорией и методами решения экстремальных задач, разделил ее на две части, В части ! излагаются методы минимизации функций конечного числа переменных (главы 1 — 5), а также рассматриваются задачи оптимального управления процессами, описываемыми системами обыкновенных дифференциальных уравнений (главы 6, 7). Этот материал для своего понимания требует лишь знания основ математического анализа, линейной алгебры, теории обыкновенных дифференциальных уравнений в объеме стандартных ку сов технических вузов. части П книги рассматриваются задачи оптимизации на множествах из бесконечномерных функциональных пространств, и посвящена задачам оптимального управления процессами, описываемыми как обыкновенными дифференциальными уравнениями, так и уравнениями с частными производными (глава 8), методам решения неустончивых задач оптимизации (глава 9), проблемами аппроксимации бесконечномерных задач оптимизации (глава 10).
Для понимания содержания части П желательно знание элементов функционального анализа в объеме программ, обычно изучаемых в университетах и технических вузах с повышенной математической подготовкои. Однако следует оговориться, что отсутствие знаний по функциональному анализу не будет мешать пониманию и усвоению излагаемых в книге основ методов и приложений к конкретным классам экстремальных задач, если читатель будет готов принять некоторые приводимые в книге утверждения не в самой общей их форме. Настоящу>о книгу можно считать очередным изданием сразу двух предыдущих книг автора «Численные методы решения экстремальных. задач» (М.; Наука, 1980 г.
— 1-е издание, 1988 г. — 2-е издание) и «Методы решения экстремальных задач» (М,; Наука, 1981 г.), причем часть 1 ранее излагалась в первой из названных книг, часть П вЂ” во второй книге. В„предлагаемом переиздании указанных книг сохранена прежняя их структура, но содержание существенно переработано и дополнено.
Заново написаны главы 2, 9, добавлены новые параграфы: Я 6, 11, 16 в главе 5, $4 в главе 6, Я 10, 11 в главе 8, Я 2, 7, 13 в главе 9, $ 7 в главе 10, существенно обновлено содержание $ 5 главы 3, $ 13 главы 5, Я 2, 3 главы 8, улучшено изложение материала во многих других параграфах, исправлены замеченные ошибки, неточности, опечатки. В $2 главы 2 впервые в учебной литературе изложены новые необходимые условия экстремума второго порядка, принадлежащие А.
В. Арутюнову. В главе 3 дано простое обоснование антициклина ($3), теория двоиственности в линейном программировании изложена, опираясь лишь на симплекс- метод ($5). Приведено элементарное доказательство принципа максимума ПРЕДИСЛОВИЕ Понтрягина для весьма общей задачи оптимального управления, включая задачи с фазовыми ограничениями (9 $3, 4 главы 6).
Часть текста, которая содержит материал, дополняющий и расширяющий основное содержание книги, напечатана петитом и при первом чтении может быть опущена. По рассматриваемым в книге проблемам оптимизации имеется обширная библиография, насчитывающая много тысяч названий. Список литературы, приведенный в конце книги, содержит лишь некоторые работы, в основном, российских математиков, а также переведенные на русский язьпс книги и монографии зарубежных авторов, которые были или непосредственно использованы в книге или близко примыкают к ней, дополняя и расширяя ее содержание. Нумерация формул, теорем, лемм, определений, упражнений в каждом параграфе самостоятельная'; ссылки на материалы, расположенные в пределах данного параграфа, нумеруются одним числом, вне данного параграфа,' но в пределах данной главы — двумя числами, вне данной главы' — тремя числами.
Так, например, теорема 3 из $2 главы 4 в пределах этого параграфа именуется просто теоремой 3, в других параграфах 4-й главы— теоремой 2.3, в других главах — теоремой 4.2.3. Аналогично параграфы при ссылках на ннх в пределах данной главы нумеруются одним числом, а вне этой главы — двумя, числами: первое число означает номер главы, второе— номер параграфа, Работа по подготовке настоящей книги к изданию не могла бы быть выполнена без помощи многих моих коллег и читателей. Автор глубоко признателен А. С. Антипину, А. В.
Арутюнов, Е. Г. Бедо сову, Н. А. Бобылеву, Н. Л. Григоренко, М, И. Зеликину,' Л. Ф. Зеликиной, А; Ф. Измаилову, А. С, Ильинскому, Х. Д. Икрамову, А,'3. Ишмухаметову,'М. Йовановнчу, А. С. Леонову, А. Недич, М. С. Нйкольскому, О.' Обрадовичу,' Н, М. Попову, М, М. Потапову, А, В. Разгулину,' В, А,.
Срочко, А. А. Станевичюсу, М. Ф. Сухинину, А, В. Тимохову, В. В. Федорову', А. А. Шананину, В. Янковичу, В. Ячимовичу, М. Ячимовичу, которые свойми советами,'предложениями, замечаниями способствовали улучшению содержания кнйги. Особенно благодарен А. В. Арутюнову, без помощи которого автор не смог бы написать Ц 2.4, 6.16, 6,4 в их настоящем виде, А, 3. Ишмухаметову за помощь при написании 9 10,7. В столь бурно развивающейся области, как теория 'и методы решения экстремальных задач, очень трудно создать учебное.
пособие, которое обладало бы определенной завершенностью н было бы свободным от недостатков, и поэтому автор будет признателен читателям за критические замечания по содержанию книги. Ф., П. Васильев ГЛАВА 1 Методы минимизации функций одной переменной С задачами минимизации функций одной переменной мы впервые сталкиваемся при изучении начальных глав математического аналива и решаем их методами дифференциального исчисления. Может показаться, что эти аадачи относятся к достаточно простым и методы их решения хорошо разработаны и изучены.
Однако это не совсем так. Методы дифференциального исчисления исходят ограниченное применение и далеко не всегда удобны для реализации на современных ЭВМ. Хотя в последние десвтилетия появились другие методы, более удобные для испольаования иа ЭВМ, требующие меньшего объема вычислительного труда, но тем не менее эту область экстремальных вадач нельзя считать завершенной, Работы, посвященные новым методам минимизации функций одной переменной, продолжают появляться иа страгшцах математических книг и журналов. Мы здесь остановимся на некоторых наиболее известных методах, достаточно хорошо проявивших себя на практике.
Другие методы минимизации функ. ций одной переменной читатель найдет, например, в [76; 148; 193; 214; 257; 5901 662; 671; 681; 684; 709; 738; 7551. В 1. Постановка задачи Пусть К = (х: — со < х < со) — числовая ось, Х вЂ” некоторое множество из К, /(х) — функция, определенная на множестве Х и принимающая во всех точках х Е Х конечные значения; Примерами множеств из К являются: отрезок [а, Ь) =(х е К: а< х < Ь), интервал (а, Ь) = (х Е К: а< х < Ь), полуинтервалы 1а, Ь) = (х Е К: а< х < Ь), (а, Ь] = (х Е К: а < х < Ь), где а, Ь вЂ” заданные числа. Будем рассматривать задачу минимизации функции /(х) на множестве Х. Начнем с того, что уточним постановку этой задачи.
Для этого сначала напомним некоторые определения из классического математического анализа. О п 0 е д е л е н и е 1. Точку х, Е Х называют точкой минимума функции /(х) на множестве Х, если /(х„) < /(х) для всех х е Х; величину /(х,) называют наименьшим или минимальным значением /(х) на Х и обозначают ш1п /(х) = /(х,). Множество всех точек минимума 7(х) на Х будем еех обозначать через Х„.
В зависимости от свойств множества Х и функции /(х) множество Х, может содержать одну, несколько или даже бесконечно много точек, а также возможны случаи, когда Х, пусто. П р и мер 1. Пусть /(х)=з(п'(я/х) при хр10 и /(0)=0. На множестве Х = (х: 1 < х < 2) минимальное значение /(х) равно нулю, множество Х, состоит из единственной точки х, = 1.
Если Х = 1х: 1/3 < х < Ц, то Х, содержит три точки: 1/3, 1/2, 1; если Х ='.(х: 0 < х < 17, то Х„ = (х; х= 1/тз, тз =1, 2,...1 — счетное мьгожество. В случае Х = (х: 2 < х < со), 10 Гл, 1. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ З 1. ПОСТАНОВКА ЗАДАЧИ :функция Т(х) не имеет наименьшего значения на Х. В самом деле, какую бы точку х е Х ни взять, найдется точка ь е Х (например, ь = й при достаточно большом к) такая, что Т(х) > Т(ь).
Это значит, что Х, пусто. Пример 2. Функция Т(х) = !х!+ !х — 1! — 1 на Х =(х: !х! < Ц принимает свое наименьшее значение, равное нулю, во всех точках отрезка Х. = (х: О < х < 1). Если Х = (х: 1 < х < 2), то Х„содержит одну точку х, = 1; если Х = (х: 1 < х < 2), то Х„= О. Пример 3. Пусть Т(х) = х при х ~ 0 и Т(0)=1. На множествах Х=(х: О< х<1) или Х=(х: 0<х<1) эта функция не имеет наименьшего значения, т. е. Х„=(д.
Пример 4. Пусть |(х) =1пх, Х =(х: 0< х < 1). Здесь Х,=0, так как во всех точках из Х функция принимает конечные значения, а для последовательности х„=1/к (к = 1, 2...) имеем 1пп Т(х„) = — со. Определение 2. Функция Т(х) называется ограниченной снизу на множестве Х, если существует такое число М, что Т(х) > М для всех х е Х. Функция 1(х) не ограничена снизу на Х, если существует последовательность (х„) е Х, для которой !Пп Т(х„) = — со. ь со В примерах 1-3 функции ограничены снизу на рассматриваемых множествах, а в примере 4 функция не ограничена. В тех случаях, когда Х, = О, естественным обобщением понятия наименьшего значения функции является понятие нижней грани функции, Определение 3.
Пусть функция Т(х) ограничена снизу на множестве Х. Тогда число 1; называют нижней гранью Т(х) на Х, если: 1) 1; < Т(х) при всех х е Х; 2) для любою сколь угодно малого числа е > 0 найдется точка х, Е Х, для которой г(х,) < Ть+.е. Если функция г(х) не ограничена снизу на Х, то в качестве нижней грани 1(х) на Х принимается Т. = — со.
Нижнюю грань |(х) на Х обозначают через !п1 Т(х) = ('„. гх В примерах 1-3 Т, = О, а в примере 4 ~, = — со. Если Х, фо, то, очевидно, нижняя грань Т(х) на Х совпадает с наименьшим значением этой функции на Х, т. е. 1и! Т(х) = ппп Т(х). В этом жеХ жьХ случае говорят, что функция Т(х) на Х достигает своей нижней грани. Подчеркнем, что !п1 г" (х) = Т„всегда существует, а пип Т(х), как мы видели из жеХ * *ьх примеров 1-4, не всегда имеет смысл. Введем еще два определения. О яр едел ение 4. Последовательность (((х„)) е Х называется минимизирующей для функции Т(х) на множестве Х, если 1!ш,Т(х,) = !п(,г(х) = Т,.
Из определения и существования нижней грани следует, что минимизиру1ощая последовательность всегда существует. О яр вдел ение 5. Скажем, что последовательность (х ) сходится к непустому множеству Х, если !!гп р(х„, Х) = О, где р(х„, Х ) = !и! ~х— й О0 — х~ — расстояние от точки х„до множества Х. Заметим, что если Х, ф О, то всегда существует минимизирующая последовательность, сходящаяся к Х,; например, можно взять стационарную последовательность х = х, (к = 1, 2,...), где х„— какая-либо точка из Х,. Однако не следует думать, что при Х, ф О любая минимизирующая последовательность будет сходиться к Х,. 3 Пример 5. Пусть Т(х)=,, Х =И. Очевидно, здесь Т,=О и 1-Ь х~ множество Х, состоит из единственной точки х, = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
