Методы оптимизации. Конспект лекций (Буряков) (2003) (1125388)
Текст из файла
Московский Государственный Университетимени М. В. Ломоносовафакультет Вычислительной Математики иКибернетикиМетоды оптимизации.Конспект лекций(V-VI семестр)лектор — доцент М. М. Потаповсоставитель — М. Л. Буряков <mib431@mail.ru>v. 0.064β — 14.06.2003Москва 2003Содержание1 Теоремы существованияМетрический вариант теоремы Вейерштрасса . . . . .
. . . . . . . . . . . . . . .Слабый вариант теоремы Вейерштрасса . . . . . . . . . . . . . . . . . . . . . . .4592 Элементы дифференциального исчисленияв нормированных пространствах11Производная Фреше . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . 11Формулы конечных приращений . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 Задачи управления линейной динамической системой144 Элементы выпуклого анализаТеорема о локальном минимуме выпуклой функции . . . . . . . .Сильно выпуклый вариант теоремы Вейерштрасса . . . . . . . . .Критерий выпуклости для дифференцируемых функций . . . . .Критерий сильной выпуклости для дифференцируемых функцийУсловия оптимальности в форме вариационного неравенства .
. .Метрическая проекция . . . . . . . . . . . . . . . . . . . . . . . . .Существование и единственность проекции и её свойства . . . . .Проекционная форма критерия оптимальности . . . . . . . . . . .................................................................1818192123242627305 Итерационные методы минимизацииМетод скорейшего спуска . .
. . . . . . . . . . . .Непрерывный аналог метода скорейшего спуска .Метод проекции градиента . . . . . . . . . . . . .Метод условного градиента . . . . . . . . . . . . .Метод Ньютона . . . . . . . . . . . . . . . . . . .Метод сопряжённых направлений (градиентов) .Метод покоординатного спуска . . . . .
. . . . .Задачи линейного программирования . . . . . . .Симплекс-метод . . . . . . . . . . . . . . . . . . .........................................................................30303334353740434547....5050525662...........................6 Методы снятия ограниченийМетод штрафов . . . .
. . . . . . . . . . . . . . . . . .Правило множителей Лагранжа для выпуклых задачПравило множителей Лагранжа для гладких задач . .Двойственные экстремальные задачи . . . . . . . . . ........................................................................................................................7 Простейшая задача оптимального управления.Принцип максимума Понтрягина65Постановка задачи . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65Функция Гамильтона-Понтрягина. Принцип максимума . . . . . . . . . . . . . . 65Линеаризованный принцип максимума. Градиент функционала . . . . . . . . . 7028 Регуляризация некорректно поставленныхэкстремальных задач по Тихонову71A Программа курса 2002/2003 учебного года75Список литературы7831Теоремы существованияОпределение. Множество M называется метрическим, если на нём задано отображение ρ : M × M → R1+ , называемое метрикой и удовлетворяющее трём аксиомам:1) ρ(u, v) = ρ(v, u) ∀u, v ∈ M (симметричность);2) ρ(u + v, w) 6 ρ(u, w) + ρ(v, w) ∀u, v, w ∈ M (неравенство треугольника);3) ρ(u, v) > 0 ∀u, v ∈ M, ρ(u, v) = 0 ⇔ u = v (неотрицательность).Упражнение 1 (3). Привести примеры функций, не достигающих inf на замкнутом,но не ограниченном множестве и ограниченном, но незамкнутом множестве.ρОпределение. Последовательность {uk } сходится по метрике ρ (uk → u) в метрическом пространстве M, если ρ(uk , u) → 0 при k → ∞.ρВ дальнейшем в метрических пространствах если uk → u, то будем говорить, чтопоследовательность {uk } сходится к u, а u будем называть пределом {uk }.Определение.
Последовательность {uk } называется фундаментальной, еслиρ(ui , uj ) → 0 при i, j → ∞.Определение. Метрическое пространство M называется полным, если любая фундаментальная последовательность в этом пространстве сходится к элементу из M.Примеры полных пространств:1. M = Rn — метрическое пространство с метрикойvu nuXρ(u, v) = ku − vkRn = t (ui − vi )2 ;i=12. M = C[a, b] — множество непрерывных на [a, b] функций — метрическое пространство с метрикойρ(f, g) = max |f (x) − g(x)|.a6x6bОпределение.
Функция J(u) называется непрерывной [полунепрерывной снизу] (полунепрерывной сверху) в точке u0 , если для любой сходящейся к u0 последовательности элементов {uk } из U существует предел lim J(uk ) = J(u0 )k→∞lim J(uk ) 6 J(u0 ) (см. рис. 1.)lim J(uk ) > J(u0 )k→∞k→∞Определение.
Множество U называется компактным (ρ-компактом) в M, если улюбой последовательности {uk } из U существует сходящаяся к элементу из U подпоследовательность {ukm }.Замечание. В конечномерном пространстве (Rn ) множество U компактно тогда итолько тогда, когда оно замкнуто и ограничено.4J(u)J(u)66qu0-u0uнепрерывность-uполунепрерывность снизуJ(u)J(u)66qu0q-uu0полунепрерывность сверху-uнепрерывности нетРис. 1: к определению видов непрерывности.Введём ряд обозначений:sup J(u) = J ∗ ;inf J(u) = J∗ ,u∈Uu∈UU∗ = {v ∈ U|J(v) = J∗ };u∗ = argmin J(u) ∈ U∗ .u∈UТеорема 1 (метрический вариант теоремы Вейерштрасса).
Пусть M — метрическое пространство, множество U ⊆ M — компакт, функция J(u) полунепрерывнаснизу на U. Тогда:1) J∗ > −∞;2) U∗ 6= ∅;3) из того, чтоJ(uk ) → J∗ при k → ∞,следует, что ρ(uk , U∗ ) → 0.uk ∈ UДоказательство.По определению точной нижней грани J∗ (которая в общем случае может равнятьсяи −∞) существует последовательность {uk } ⊆ U такая, что J(uk ) → J∗ при k → ∞.Так как U — компакт, то у этой последовательности существует подпоследовательность{ukm } такая, что ukm → u ∈ U при m → ∞. Тогда из полунепрерывности J(u) снизу вэтой точке u следует, что−∞ < J(u) 6 lim J(ukm ) = {т.к.
{ukm } п/п-ть {uk }} = lim J(uk ) = J∗ .k→∞m→∞Таким образом, J∗ конечно (J∗ > −∞).5Из того, что u ∈ U и J(u) 6 J∗ следует, что u ∈ U∗ 6= ∅. Следовательно U∗ 6= ∅.Докажем теперь третье утверждение от противного. Предположим, что существуетподпоследовательность {ukm } такая, что ρ(ukm , U∗ ) > ρ0 > 0. Так как U — компакт, то уэтой подпоследовательности существует “подподпоследовательность” {ukml } такая, чтоl→∞ρ(ukml , u) → 0 для некоторого u (u ∈ U). Отсюда, с учётом полунепрерывности J(u)снизу, имеем:J(u) 6 lim J(ukml ) = lim J(uk ) = J∗ .k→∞l→∞То есть для точки u ∈ U∗ρ(ukml , U∗ ) = inf ρ(ukml , u∗ ) 6 ρ(ukml , u) → 0 при l → ∞.u∗ ∈U∗Полученное противоречие (подпоследовательность сходится к нулю, тогда как сама последовательность отделена от нуля положительным ρ0 ) завершает доказательствотретьего утверждения.
Теорема полностью доказана.Определение. Задачи, удовлетворяющие условиям (выводам) Теоремы 1 называюткорректно поставленными в метрическом пространстве M.Упражнение 2 (3). Доказать, что в C[a, b] единичный шар U = {kf kC 6 1} является замкнутым и ограниченным множеством, но при этом компактом не является.(Напомним, что метрика k·kC для отрезка [a, b] определяется как kf (x)kC = max |f (x)|.)x∈[a,b]Пример. (когда множество U не компакт и Теорема 1 не применима)M = C[−1, 1], ρ(f, g) = max |f (t) − g(t)| = kf − gkC , U = {kf kC 6 1},−16t61Z0Z1f (t) dt −J(f ) =−1f (t) dt.0U ограничено и замкнуто, но не является компактом (см. Упражнение 2); J(u) — непрерывен:Z0Z1|J(f ) − J(g)| 6 |f (t) − g(t)| dt + |f (t) − g(t)| dt 6 2·kf − gkC−10(то есть даже Липшиц-непрерывен с константой 2). Но в тоже время минимум функционала J(u) равен J∗ = −2 = J(u∗ ) и, как легко видеть, достигается на функции(см.
рис. 2):−1, −1 6 t < 0u∗ (t) =1 06t61которая, очевидно, не принадлежит классу C[−1, 1], то есть множество U∗ пусто.Пример. (когда множество U не компакт, но inf достигается)R1Возьмём в предыдущем примере в качестве функционала J(f ) =f (t) dt. Тогда−1J∗ = −2, U∗ = {u∗ } =6 ∅, u∗ = u∗ (t) ≡ −1 ∈ U.Определение. Линейное пространство L называется нормированным, если существует такая функция kuk : L → R1 , называемая нормой, что:661−101t−1Рис.
2: u∗ (t)1) kαuk = |α|·kuk ∀u ∈ L, ∀α ∈ R (неотрицательная однородность);2) ku + vk 6 kuk + kvk ∀u, v ∈ L (неравенство треугольника);3) kuk > 0 ∀u ∈ L, kuk = 0 ⇔ u = 0 (неотрицательность).Если в пункте 3) выполнено лишь условие u = 0 ⇒ kuk = 0, то kuk называют полунормой.Определение. Множество U называется ограниченным в M, если существуетu0 ∈ M и R < 0 такие, что для всех u из U выполняется условие ρ(u, u0 ) 6 R.Определение. Нормированное линейное пространство L, полное относительно метрики ρ(u, v) = ku − vk, называется ба́наховым.Определение. Линейное пространство L называется евклидовым, если на нём заданоскалярное произведение hu, vi : L × L → R1 :1) hu, vi = hv, ui∀u, v ∈ L (симметричность);2) hu + v, wi = hu, wi + hv, wi3) hαu, vi = α hu, vi∀u, v, w ∈ L (линейная аддитивность);∀u, v ∈ L, ∀α ∈ R (линейная однородность);4) hu, ui > 0, hu, ui = 0 ⇔ u = 0 (неотрицательность).pВ любом евклидовом пространстве kuk = hu, ui является нормой (евклидовой нормой),а ρ(u, v) = ku − vk — метрикой.Определение.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
