Курс лекци Русакова по методам оптимизации (1083216), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

Будем искать точку локальногоминимума,поэтомуограничимсяунимодальнымифункциями,т.е.имеющими один минимум. Больше ничего о функции неизвестно. Толькоможно вычислить (измерить) значения функции в точках.Пусть функция задана на прямой, даны при этом точки a<b<c, иf ( a ) ≥ f (b), f (b) ≤ f (c ) , точка минимума в [a, c]Через эти точки проведем параболу:g (t ) = g 0 + g1t + g 2 t 287Положим: g ( a ) = f ( a ), g (b) = f (b), , т.е. имеем 3 уравнения и 3 неизвестных g0, g1, g2. g ( c) = f ( c ).Находим g0, g1, g2t* = arg min g (t ) ⇒− g1→(•) min2g2Рассмотрим два случая:a ≤ t* ≤ b ⇒ c:= b,b:= t *b ≤ t* ≤ c ⇒ a:= b,b:= t *Так поступаем до тех пор, пока точка t * не окажется в достаточномалой окрестности одной из трех точек a, b, c.

После чего такую точкусчитаем точкой минимума.Метод можно обобщить на случай кубических и т.д. функций, нопотребуется вычислять большее количество точек.2.15 Метод дихотомии (половинного деления)Точки x1 , x2 выбираются на расстоянии δ < ε от середины отрезка:x1 = ( ai + bi − δ ) / 2,x2 = ( ai + bi + δ ) / 2(1)За одну итерацию интервал неопределенности уменьшается примерно вдва раза (рис. 1). За n итераций длина интервала будет примерно равнаln((b0 − a0 ) ε )(b0 − a0 ).

Для достижения точности ε потребуется n ≥nln 22итераций. На каждой итерации минимизируемая функция вычисляетсядважды.88Рис. 1. Метод дихотомииАлгоритмНайти W(x) на отрезке [a,b].Шаг 1. xm=(a+b)/2; L=b-a; вычислить W(xm).Шаг 2. x1=a+L/4; x2=b-L/4; вычислить W(x1) и W(x2).Шаг 3.Если W(x1)<W(xm), то исключить (xm,b], т.е. b=xm, xm=x1.

Перейти кшагу 5.Если W(x1) W(xm), то перейти к шагу 4.Шаг 4.Если W(x2)<W(xm), то исключить [a,xm), т.е. a=xm, xm=x2. Перейти кшагу 5.Если W(x2) W(xm), то исключить [a,x1) и (x2,b], т.е. a=x1, b=x2.Перейти к шагу 5.89Шаг 5. L=b-a. Если | L| <e , то закончить поиск. В противном случаевернуться к шагу 2.2.16 Метод «золотого» сечения.Точки x1 , x2 находятся симметрично относительно середины отрезка[a0 , b0 ] и делят его в пропорции золотого сечения, когда длина всего отрезкаотносится к длине большей его части также, как длина большей частиотносится к длине меньшей части:b0 − a0 b0 − x1b − a0 x2 − a0=и 0=.b0 − x1 x1 − a0x2 − a0 b0 − x2Отсюда(3 − 5)(bi − ai ) ≈ ai + 0.381966011 × (bi − ai ),2( 5 − 1)x2 = ai +(bi − ai ) ≈ ai + 0.618003399 × (bi − ai ) =2= bi − 0.381966011 × (bi − ai ).x1 = ai +(2)За одну итерацию интервал неопределенности уменьшается в5 +1= 1.618...

раз, но на следующей итерации мы будем вычислять2функцию только один раз, так как по свойству золотого сеченияx2 − x1b − x2= 0.381... и= 0.618... . (рис. 2). Для достижения точности εb − x1b − x1потребуется n ≥90ln((b0 − a0 ) ε )итераций.5 −1ln2Неточное задание величины5 на ЭВМ уже при достаточнонебольшом количестве итераций может приводить к погрешностям и потереточки минимума, так как она выпадает из интервала неопределенности.Поэтому, вообще говоря, при реализации алгоритма возможность такойситуации должна быть предусмотрена.Рис. 2. Метод золотого сеченияАлгоритмНайти W(x) на отрезке [a, b].Шаг 1.

Вычисляем коэффициент дробления отрезка [a, b] k=(- 1)/2.Шаг 2. x1=a+(1-k)(b-a), вычислить W(x1).Шаг 3. x2=a+k(b-a), вычислить W(x2).Шаг 4.Если | x2-x1| < e, где e - заданная погрешность, то xm = (x1+x2)/2,вычислить W(xm) и закончить поиск.Если | x2-x1| >e, то перейти к шагу 5.91Шаг 5.Если W(x1)>W(x2), то исключить a=x1, x1=x2 и W(x1)=W(x2). Перейти кшагу 3, затем к шагу 4.Если W(x1) <W(x2), то b=x2, x2=x1 и W(x1)=W(x2). Перейти к шагу 2 и 4.2.17 Метод ФибоначчиПусть у нас существует ограничение на количество вычисляемых точекN. Как выбирать средние точки, чтобы максимально уменьшить интервал,внутри которого лежит точка min?tk ′ = a k +FN −k −2(bk −a k )FN −ktk ″ = a k +FN −k −1(bk − a k ) , к- номер итерации.FN −kFj - числа Фибоначчи, обладающие свойством.Fk+2 = Fk+1+ FkДва первых: 1;1{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,4181, 6765, 10946,…}Как метод Фибоначчи связан с методом «золотого» сечения?Fk −23 − 5 Fk −15 −1k→,k→.→∞→∞Fk2Fk2Тоестьасимптотическиодинметодпереходитвдругой.Окончательный интервал в методе «золотого» сечения всего на 17% больше92чем в методе Фибоначчи.

Если количество измерений не задано, тоиспользуется метод «золотого» сечения, если задано - то Фибоначчи.Числа Фибоначчи определяются соотношениями:Fn+ 2 = Fn+1 + Fn , n = 1, 2,3..., F1 = F2 =1.С помощью индукции можно показать, что n -е число Фибоначчипредставимо в виде (формула Бинэ):nnFn =  (1 + 5) / 2 − (1 − 5) / 2  / 5, n = 1,2,...(Изэтой()) (формулы)видно,чтоприбольшихn:nFn ≈ (1 + 5) / 2 / 5, так что числа Фибоначчи с увеличением n растуточень быстро.На начальном интервале вычисляют точкиx1 = a0 +Fn(b0 − a0 ),Fn +2Fx2 = a0 + n+1 (b0 − a0 ),Fn+ 2(3)где n выбирается исходя из точности и начальной длины интервала(см.

ниже соотношение (5)).Наk -м шаге метода будет получена тройка чиселлокализирующая минимум f ( x) , такая, что∆ k = bk − ak = (b0 − a0 )Fn−k +3, 1 ≤ k ≤ n, a1 = a0 , b1 = b0 ,Fn+ 2а точка xk , ak < xk < bk , с вычисленным значениемf ( xk ) = min f ( xi ) ,1≤i ≤ k93ak , bk , xk ,совпадает с одной из точекx1 = ak +Fn − k +1F(bk − ak ) = ak + n − k +1 (b0 − a0 ),Fn − k + 3Fn + 2FFx2 = ak + n − k + 2 (bk − ak ) = ak + n − k + 2 (b0 − a0 ),Fn − k + 3Fn + 2расположенных на отрезке[ ak , bk ](4)симметрично относительно егосередины (рис.

3). При k = n процесс заканчивается. В этом случае длинаотрезка∆ n = bn − a n = (b0 − a 0 ) / Fn +2 ,а точкиx1 = an +F1(b0 − a0 ),Fn + 2x2 = an +F2(b0 − a0 )Fn + 2совпадают и делят отрезок пополам.Рис. 3. Метод Фибоначчи94Следовательноbn − an b0 − a0=<ε.2Fn + 2Отсюда можно выбрать n из условияb0 − a0< Fn + 2 .ε(5)С ростом n , из-за того, что Fn / Fn+ 2 – бесконечная десятичная дробь,происходит искажение метода. Поэтому на очередном шаге в качестве новойточки берут из (4) наиболее удалённую от xk −1 на предыдущем шаге.Глава 3 Условная оптимизация3.01 Задача нелинейного программированияРешается задача минимизации функции f на множестве X, заданномнабором ограничений g.Множество X = {x ∈ R n , g i ( x ) ≤ 0, i = 1, m} — называется допустимыммножеством.gi- некоторые гладкие функции.Ограничения типа равенства.Рассмотрим следующий пример:min f , f : R 2 → R .x95X = {x ∈ R 2 , g ( x1 , x 2 ) = 0},найтиПусть g разрешима относительно x1, то есть g(x1,x2)=0⇔ x1= γ(x2),∀x1,x2.Тогда min f = min f (γ ( x 2 ),x 2 )Xx2Функции f, γ - дифференцируемы.

Запишем условие экстремальности:∂ f ∂γ∂ f+= 0, (∗) . Так как∂ x1∂ x 2 ∂ x 2∂ g ∂γ∂g∂γ∂gg (γ ( x2 ), x2 ) ≡ 0 ⇒⋅+=0⇒=−∂ x1 ∂ x2 ∂ x2∂ x2∂ x2(∗) ⇒ − ∂ f ⋅ ∂ g∂ x1 ∂ x2∂g  ∂ x1 −1+∂g ∂x 1−1∂f=0∂ x2Обозначим∂ f ∂g −∂ x1  ∂ x1 −1=λx1* , x2*Тогда:∂g∂ f∂ x + λ ∂ x = 02 2∂g∂ f+λ= 0 , из определения λ∂x∂x1 1 g ( x1 , x2 ) = 0Таким образом, в точке минимума выполняются эти соотношения.Получить эти необходимые условия можно, используя функцию Лагранжа:F(x,λ)=f+λg.Тогда необходимое условие min функции f(x1,x2) при наличииограничений может быть записано следующим образом:96∂ F ∂ f∂g∂ x = ∂ x + λ ∂ x = 022 1∂ F ∂ f∂f=+λ=0∂x∂x∂x11 1∂ F= g ( x1 , x2 ) = 0∂ λТаким образом, задача условной минимизации сведена к задачебезусловнойминимизации.Длярешенияпоследнейзадачиможноиспользовать ранее описанные методы.Ограничения типа неравенств.Не формальное введение.Решаем задачу: X = {x ∈ R n , g i ( x ) ≤ 0, i = 1,2} найти min f , f : R 2 → R .xПусть:область, которая разрешена ограничениямиg1(x)=0g2(x)=0∇fточка минимумаf = const (линия уровня)∇g1∇g2-∇fконус97Пусть x* точка минимума, тогда из рисунка видно, что -∇fпредставляется так:-∇f = λ1∇g1+λ2∇g2, где λ1≥0, λ2≥0.(1)-∇f расположен в конусе, образованном ∇g1 и ∇g2.(1) переписывается так:2∇f +∑ λ i ∇g i= 0 , где λi - множители Лагранжа.i =1По рисунку λi gi (x) = 0 (мы попадаем на границу).

Тогда можно2рассматривать функцию Лагранжа f +∑ λ i giи считать стационарную точкуi =1так, будто нет ограничений. Переход от равенств к неравенствамнакладывает ограничения на λi (λi ≥0). Пусть ∇fнаправлен иначе (-∇fнаходится не в конусе), тогда иллюстрация принимает вид:Иллюстрация:Sg2(x) = 0g1(x) = 0-∇f∇g198конус∇g2В этом случае есть вектор S, который составляет острый угол с -∇f итупой с ∇g1 и∇g2.То есть, для векторов x(α)=x* + αS, (при малых α) наши ограничениябудут выполняться (в тоже время функция будет убывать), и точка x* небудет точкой локального минимума.Таким образом, чтобы точка была экстремальной, антиградиентдолжен лежать в выпуклом конусе, определенном векторами ∇g1 и∇g2.Рассмотрим другую точку на g2(x) = 0.∇f1g2(x) = 0∇g2Если ∇f1 направлен так, как показано на рисунке, то точка x* будетподозрительной на точку локального минимума.

Необходимое условиезаписывается также, но в этом случае λ1=0 (то есть не рассматривается g1).Таким образом, наша цель получить необходимые условия экстремумафункции в допустимой точке.Пусть x*- экстремальная точка, свяжем с x* множество индексовактивных ограничений : I ( x * ) = {i: g i ( x*) = 0; i ∈ {1...m}}Лемма:99Пусть ∃s ∈ R n - некоторый вектор, удовлетворяющий следующимсвойствам:(∇g i ( x*), S ) < 0(*) (∗) ,тогда точка x* - не экстремальная. ∀i ∈ I(x*)(∇f(x*),S)<0Доказательство:Идея:Показать, что на луче с вершиной x* и направлением S будут лежатьвблизи вершины некоторые точки, которые будут допустимыми и в нихцелевая функция строго меньше чем в точке x*Пусть ε>0(1) g i ( x * +ε S ) = g i ( x*) + ε (∇g i ( x*), S ) + o(ε 2 )f ( x * +ε S ) = f ( x*) + ε (∇f ( x*), S ) + o(ε 2 ) (разложениевполиномТейлора)]i ∈ I ( x*), тогда g i ( x*) = 0 (см.

Характеристики

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