шпоры методы оптимизации. Задача матго программирования (змп) заключ в нахождении min фии f ( X ), если. (1) Под реш змп понимают
 Скачать 1.38 Mb.
|
|
Опр. Говорят, что ф-ция уд.усл. Липшица на [a;b], если , что . (2) Геометрическое усл.Липшица означает, что угловой коэф-т хорд, кот соединяют две произвольные точки графика ф-ций y=f(x) не превосходит константы L. Если ф-я уд.усл. Липшица на [a;b] то она явл-ся непрерывной на [a;b]. Т1: Пусть f(x)-определена и непрерывна на [a;b] и на каждом [ai;ai+1], где а=a1 Д-во: выберем произвольные x,y из отрезка [a,b]. Предположим, что т-ка . Рассм.модуль разности Т2: Пусть f(x)–дифер на [a;b] и её производная огр-на на [a;b], тогда эта ф-ция уд. усл. Лип с конст. L=sup|f’(x)| Д-во: т.к. ф-ция f(x) диф-ма, то по формуле конечных приращений приращение ф-ции Отсюда и из ограниченности производной следует утв. теоремы. Пусть ф-я f(x) удовлетворяет на [a;b] условию Липш (2) с константой L. Зафиксируем некоторую точку y из [a;b] и построим ф-цию , , g(y,y)=f(y) . Ф-ция g явл. кусочно-линейной ф-цией, ее график есть ломаная с углами наклона L (до y) и –L (после y) и в т-ке y g(y,y)=f(y). Рассмотрим нерав-вот.е. , . 35. Алгоритм и условия сходимости метода ломаных решения задачи одномерной минимизации. Пример. Описание метода ломаных Выбирем некот т-ку . Построим ф-ю и определим из усл. . Очевидно, что x1=a или x1=b. Пусть в результате выполнения нескольких шагов определены т-ки х1,х2,…,хn, n. Построим ф-цию g(x,xn)=f(xn)-L|x- xn |. Строим ф-цию Следующее приближение Процесс вычисл. продолж. до тех пор, пока не будет выполнено нерав-во , где - заданная точность. В кач-ве решения задачи выбирается т-ка . Зам.Метод ломаных сходится при любом начальном при любом начальном приближении. Зам. Для всех х справедливо соотнош. т.е. ф-ции рn(х) приближают ф-цию f(x) снизу, оставаясь каждый раз не выше графика ф-ции f(x). Зам, Недостаток – с ростом числа шагов растет требуемый объем памяти вычисл машины. Зам. Для применения метода надо знать константу Липшица. Теорема. Пусть ф-я уд. усл. Липшица на [a;b], тогда посл-ть полученная методом ломанных такая, что: 1) (1), причем (2) 2) (3) Док-во. Рассмотрим (4) (5), (6) , где . Из (4)-(6) получаем т.е. послед-ность явл. возрастающей и ограничена сверху, поэтому . Кроме того, из (4)-(6) следует оценка (2). Покажем, что . Т.к. ограничена, то из нее можно выделить сходящуюся подпослед-ность . Пусть - некотор. т-ка послед-ности . Послед-ность сходится к т-ке при n1 Пример. f(x)=|x2-1|, x [-2,3]. На отр. [-2,3] ф-ция уд. усл. Липшица с константой L1=4, на отр. [-1,1] L2=2, на отр. [1,2] L3=6. На всем отр. L=6. Строим ф-цию g(x,0)=1-6|x|. При x<0, g(x,0)=1+6x, g(-1,0)=-5, x>0, g(x,0)=1-6x, g(1,0)=-5. Т-ка x1. g(x,3)=8-6|x-3|, g(x,3)=8+6x-18. Следующ. т-ка x2 определ. как min g(x,-2)=3-6|x+2|, g(x,-2)=3-6x-12 36.Алгоритм метода скорейшего спуска решения ЗММ. Пусть выбрано некот нач-е приближение и на некоторой итерации построено очередное приближение и вычислены значения , . Рассм.луч, проходящий ч/з т в направлении антиградиента .В этом луче рассм. ф-ю, зависящую от альфа . Рассм. вспомогательную задачу одномерной минимизации (*). И пусть решение этой задачи достигается в т : , тогда след. приближение вычисляется по ф-ле . Итерационный процесс продолжается до тех пор, пока не будет выполнен критерий окончания счета. В качестве критерия окончания счета могут использоваться нерав-ва: ; ; , где,,–заданные числа, характеризующие точность счета Если на некоторой итерации выполняется рав-во, то в т-ке хk выполн. необход. усл. Оптимальности и итерационный процесс заканчивается. Если , то сущ.такое неотрицат. , что . Если значения явл. решением задачи (*), то в этой т-ке должно быть выполнено необходимое усл. оптимальности, т.е. Вычислим эту производную в т-ке Получаем, что градиенты, вычисл. в соседних приближениях, постоенных методом скорейшего спуска ортогональны. Зам. Величину можно выбирать из условия , в этом случае метод наз градиентным. 37.Алгоритмы метода условного градиента и метода проекции градиента решения задачи многомерной условной минимизации. 1)алгоритм метода условного градиента. Пусть задано начальное приближение и методом условного градиента вычислено Строим ф-цию и решаем задачу (1) Пусть есть решение задачи. Заметим, что . Если , то уд. необходимому усл. и вычислительный процесс заканчивается. Если , то строим отрезок (2) на этом отрезке рассматриваем ф-цию и решаем задачу (3). Тогда след.приближение находится по формуле где есть решение задачи (3). Практическим критерием окончания счета выбираются нер-ва где согласованные числа, характеризующие точность счета. Замеч1. Метод условного градиента эффективен когда вспомогат. задача (1) допускает простое решение. Замеч2.Часто на практике задают некоторое значение , н/р, равное 1, проверяют усл.. Если оно не выполняется, то уменьшают, например, в два раза и т.д. 2)алгоритм метода проекции градиента. Пусть задано нач. приближение и методом проекции градиента вычислено . След.приближение ищется по формуле(4) В зависимости от выбора строятся различные варианты метода проекции градиента. Например, может находиться как решение задачи од номерной минимизации (5), где (6) В этом случае при метод проекции градиента превращается в метод скорейшего спуска. Часто при практическом исп. метода (4) находят такое , что выполняется условие релаксационности При его нарушении полагают равным снова проверяют условие ре лаксационности и т. д. В качестве критерия окончания счета выбираются неравенства , где — числа, характеризующие точность счета. Замеч4. Главная сложность реализации метода проекции градиента заключается в решении задачи проектирования. 38.Алгоритм метода покоординатного спуска решения задачи многомерной минимизации. Геометрическая иллюстрация. Рассм. задачу . Пусть выбрано некоторое начальное приближение. И методом покоординатного спуска было получено приближение . Ч/з , , обозначим координатные вектора (1 на j-ом месте). Положим и для , где определяется из условия . И след. приближение , если для некоторого , то процесс вычисления заканчивают, А т считают приближением к точке минимума. Данный метод хорошо подходит для задач с параллепипедными ограничениями, , . В этом случае при решении вспомагательной задачи минимизации, . на альфа накладываются ограничения, не позволяющие точкам х выходить за пределы мн-ва Х 39.Сходимость метода скорейшего спуска. Рассм. задачу (1). Пусть в (1) ф-ция f(x) непрерывно дифференцируема, ограничена снизу на мн-ве , ее градиент уд.векторному усл. Липшица с константой L, то есть для всex Тогда при любом начальном приближении итерационный процесс метода скорейшего спуска является релаксационным,то есть уд.нер-ву обладает св-вом Если дополнительно предположить, что мн-во ограничено, то посл-ность {xk} сходится к непустому мн-ву S*стационарных точек ф-ции f(x) Если кроме того, f(x) выпукла на то посл-ность {xk} явл. минимизирующей и сходится к непустому мн-ву X* решений задачи. 40.Постановка простейшей задачи вариационного исчисления. Примеры. Говорят, что на некотором классе ф-ций задан функционал, если каждой ф-ции x=x(t) из этого класса, поставлено в соотв. число . Если кажд. Ф-цию x(t) рассматривать, как элемент некоторого пр-ва L, н/р пр-во непрерывных ф-кций, непрерывно дифференцируемых ф-кций, то ,где В пр-ве L можно рассматривать некоторые мн-ва XL, н/р мн-во Тогда можно рассматривать задачу оптимизации в функциональном пр-ве, кот.формально может быть записана в той же форме, что и задача мат. прогр: Найти такое , что. (1) Задача (1) понимается в глобальном смысле, если необходимо найти ф-цию, доставляющую линейному функционалу J(x) по всем xXи понимаемом в лок смысле, если,, где Сформулируем зад.вариационного исчисления: Пусть на отрезке T= определена непрерывно дифференцируемая ф-ция x(t), принимающая на концах отрезка заданные значения: Определим мн-во: (2) И на этом мн-ве определена ф-ция:(3) Где ф-ция определена и непрерывна по всем своим аргументам вместе с частными производными по x,,tдо 2-го порядка. Требуется найти ф-цию , такую что (4) Ф-ции из мн-ва (2)наз. допустимыми,а ф-кия наз. минималью Зад. (2)-(4) обычно понимается в локальном смысле, т.е. минимум ищется по ф-циям
то говорят о сильном локальном минимуме
то говорят о слабом локальном минимуме Замечание.Если на некоторой кривойдостигается сильный локальный минимум, то на ней достигается и слабый локальный минимум, но не наоборот. Поэтому необходимые усл. слабого локального минимума будут явл. и необходимыми усл. сильного локального минимума, но не наоборот. Пример: (зад.о бахистохроне – кривая наискорейшего времени ) На плоскости заданы 2-е точки А и B. Введем декартовую систему координат: т. А попадает в начало координат, а т.B имеет координаты .Из А в B скатывается тяжелая материальная точка. Найти кривую x(t) по которой перемещение из А в B произойдет за минимальное время. Начальная скорость . Точка скатывается под воздействием силы тяжести; сопротивление не учитывается, поэтому скорость точки зависит только от положения точки и не зависит от формы кривой. По закону Галия: , где g- ускорение свободного падения. С другой стороны, скорость в каждый момент времени вычисляется, как отношение , где ds- дифференциал дуги, которая будет пройденна точкой за время dt. Известно, что Т.о. . Тогда время, которое необходимо точке для перехода из А в B определяется как . Т.о. получаем следующую задачу вариационного исчисления: 41. Метод вариаций Лагранжа Пусть в задаче , где и Пусть на кривой дости-тся минимум, тогда все допустимые кривые x(t), из мн-ва X можно представить в виде: Тогда рассм. приращение функционала: =/ в силу дифференцируемости ф-ции F/= = (т.кминимально), где бесконечно малая велич. Первый интеграл наз. 1-вой вариацией функционала. В таком разложении приращения функционала, кривые имеют произвольную природу, что влечет за собой сложность исследования. Представим кривые в виде однопараметрического семейства ф-ций: Для таких приращений функций рассмотрим приращение функционала: где наз. первой вариацией функционала. Т.к ( на кривой подозрительной на минимум) Замечание:Необходимое условие оптимальности в силу произвольности ф-ций является неудобным для использования на практике. 42. Уравнение Эйлера Лемма Дюбуа-Реймона.Если рав-вовыполнено для некоторой непрерывной ф-иии всех непрерывных ф-ий, уд.условию, то=с на . Док-во. Пусть. Для ф-ии, кот.уд.условиям леммы, рассм..(1). Вместо в (1) подставим . Тогда, т.к.-непрерывная ф-ия. Следствие.Если -непрерывная ф-ия, то . Теорема. Пусть кривая явл. минималью в простейшей ЗВИ, то на ней выполнено ДУ Эйлера (2) с краевыми условиями (3). Док-во. Пусть кривая явл минималью ПЗВИ, то ,где, Рассмотрим Тогда Используя следствие к лемме получим (4). Ур-ние (4) наз. интегр.уравн.Эйлера, его решение называется экстремалью. Перепишем (4) так . В правойчасти стоит ф-я диф. по t, значит и в левой части стоит ф-я диф. по t, 43. Случаи интегрируемости ур-ния Эйлера. Примеры. 1-й сл. . , , т.к. задача явл. вырожденной, тогда В задаче о кратчайшем расстоянии между 2мя точками плоскасти функционал имеет вид 2й сл. . В этом сл.ур-е Э-ра ,. Для того, чтобы найти ур-я (1) рассмотрим: Если ф-я x(t) явл решением ур-я (1), то Отсюда получим, что первый ур Эйлера в этом случае имеет вид: . 3й сл. . Тогда ур-е Эйлера им. вид: 4й сл. . , Если рав-во (3) не явл тождеством, то оно определяет некоторую линию x=x(t), кот-я удовл-ет граничным условиям лишь в исключит-ых случаях. Если же ур-е (3) явл тождеством, то подинтегральное выраж-е представляет собой полный дифф-л некоторой ф-и, тогда значение интеграла Значение интеграла не зависит от вида кривой, соединяющей граничные точки. Пример. Исследовать на extr функционал 0=0 явл тождеством, значит ф-я подъинтегральная явл полным дифф-м, т.е. , , тогда 44.Задача вариационного исчисления с незакрепленными концами и фиксированным отрезком интегрирования. Отрезок задан, значения не закреплены, т.е. рассматривается задача поиска минимума функционала (1) где ф-ция . Теор1. Пусть функция = доставляет слабый локальный минимум (1). Тогда эта ф-ция уд. ур-нию Эйлера. и краевым усл. Док-во. Рассм вариации Лагранжа , где . И необходимое усл. минимума , где . И образуем 1-ую вариацию функционала: (2) Т.о. доказали теор 1. Замеч: Если левый или правый конец траектории закреплён, то первое или второе из условий (2) заменяется или . 45.Задача вариационного исчисления с незакрепленными концами и нефиксированным отрезком интегрирования Рассм. задачу (1) где определена и непрерывна со всеми частными производными до 2-ого порядка включительно.Ищем (1) при усл. когда отрезок [] не фиксирован. Значение ф-ии на концах отрезка не заданы. Пустьявл решением рассм.задачи.Тогда найдётся такие,что кривая уд. уравн Эйлера и краевым усл., (2). Определим усл. для значений . Рассм где - произвольные приращения интервала, . И предположим продолжимость решения на отрезок [], если это необходимо. Рассмотрим- (3) В (4) рассм, разделим на и. ,тогда(4) ,. (5) (4) должно выполняться для . Значит (4) и (5) должны выполняться одновременно. Значит: (6) В (7) произвольны и независимы друг от друга, поэтому (7) Т.о. справедлива теор 2. Теорема 2. Если доставляет слабый минимум функционалу (1) в задаче с незакреплёнными концами, то кривая удовл ДУ Эйлера (2) и усл. (6) и (7). 46. Задача вариационного исчисления с движущимся по кривой концом. Рассм. задачу где ,значение задано, левый конец траектории зафиксирован , правый конец траектории явл. подвижным, то есть лежит на заданной кривой Таким обр, необходимо найти точку и функцию , определяется на отрезке , для которых функционал достигает минимальное значение при условиях |