Методы прямого поиска в задачах одномерной минимизации. Метод квадратичной интерполяции

Страницы работы

18 страниц (Word-файл)

Фрагмент текста работы

1.6 Методы прямого поиска в задачах одномерной минимизации. min-? xk+1 = xk + tkSk , где Sk -направление.

Необходимо определить tk.

(t) = f(xk + tSk)- найти минимум функции одной переменной (нет анализа заданной функции). Будем искать точку локального минимума, поэтому ограничимся функциями, имеющими один минимум. Больше ничего о функции неизвестно. Можно вычислить (измерить) значения функции в точках.

1. Метод квадратичной интерполяции.

Пусть функция задана на прямой, даны при этом точки a<b<c, и f a( )  f b( ), f b( )  f c( ), точка минимума в [a, c] Через эти точки проведем параболу:

g t( )  g0 g t1 g t2

Положим:

g a( )  f a( ),

g b( )  f b( ), , т.е. имеем 3 уравнения и 3 неизвестных g0, g1, g2.

g c( )  f c( ).

Находим g0, g1, g2

g1

] *t  argmin ( )g t    ( )min

2g2 Рассмотрим два случая:

1)  a t*  b c : b b,        : t *

2)  b t*  c a: b b, : t *

Так поступаем до тех пор, пока точка t *не окажется в достаточно малой окрестности одной из трех точек a, b, c. После чего такую точку считаем точкой минимума.

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

2.  Метод дихотомии ( половинного деления.).

Если мы вычислим значения f в двух точках x1,x2 , то станет возможным исключение из рассмотрения некоторого множества точек, на котором гарантировано нет минимума, то есть имея измерения в двух точках можем сократить интервал поиска. 

Как лучше выбирать точки, чтобы процесс быстрее сходился?

1          1 

 В методе дихотомии предлагается x1          ,x2        (отрезок [0,1] ). 

2  2          2          2

    1         1  

Остается один из интервалов:0, 2  2,или2  2 ,1 . Выберем 3-й и 4-й эксперимент на -пару в середине оставшегося интервала. После n (n-четно)

n                         n

                  экспериментов min функции лежит в интервале Ln  2 2  (1 2 2 ).

Здесь каждый раз два эксперимента, но можно один, а  в качестве другого брать один из предыдущих. 

3.  Метод «золотого» сечения.

Интервал [a,b], вычислить функцию f ,в точках t t,  .

На интервале  [a,b] расположен минимум функции.

t a F b1(  a), t a F b2 ( a) , где F1 и F2 некоторые числа 0<F1<1, 0<F2<1.

Анализируем перегибы функции внутри интервала, и также, как  раньше, заменяем отрезок [a,b] на a t, или t b, . Идея метода в том чтобы после замены, необходимо было вычислить только одну точку при гарантированном уменьшении длины отрезка, т.е. b tt  a

   F2 F1 F2  1, так как b a b a

b a F b1(  a)

  1 F1 F2 .(после замены отрезок уменьшится в 1/ F2 =  b a

В новом отрезке должно быть(по правилу «золотого» сечения): t  a     2

  F2 , F1 F2 ,так как

t  a

F b1(  a)     F1

                            F2 .

F b2 (  a)    F2

F1 0382.

2                                                   2

Тогда так как F1 F2 , F1 F2  1, то F2 F1  1 .

F2     2     0618.

Таким образом, уменьшение интервала в 1/ F2 =  раз достигается с помощью вычисления функции в одной новой точке (см. процедуру выполнения). После n экспериментов имеем интервал неопределенности:

Ln      n1 ,            .

               2

В пересчете на одно измерение этот метод лучше дихотомии.

Процедура выполнения:

Рассмотрим [a,b], вычислить функцию f ,в точках t,t .

1)  f t( )  f t( )  a: t, t  t, t  a F b2(  a)

2)  f t( )  f t( )  a : t, t  t, t  a F b1(  a), b:t.

В 1) и 2) появилась только одна новая точка. И так далее, пока длина отрезка [a,b] не станет меньше заданной величины.

4 .Метод Фибоначчи.

Пусть у нас существует ограничение на количество вычисляемых точек N. Как выбирать средние точки , чтобы максимально уменьшить интервал, внутри которого лежит точка min? tk   ak FN k 2 (bk a k )

FN k

tk ak FN k 1 (bk a k ) , к- номер итерации.

FN k

Fj - числа Фибоначчи, обладающие свойством.

Fk+2 = Fk+1+ Fk

Два первых: 1;1

Как метод Фибоначчи связан с методом «золотого» сечения?

Fk2                             3   5      Fk1                              5 1

  k        ,            k         .

Fk                                        2           Fk                                   2

То есть асимптотически один метод переходит в другой. Окончательный интервал в методе «золотого» сечения всегда на 17% больше чем в методе Фибоначчи. Если количество измерений не задано, то используется метод «золотого» сечения, если задано - то Фибоначчи.

3. Условная минимизация.

2.1 Задача нелинейного программирования. min f -?, на множестве X.

Нелинейная область: X  {x Rn ,g xi ( )  0,i  1, }- m допустимое множество.

ji- некоторые функции. 

2.1.1 Ограничения типа равенства. рассмотрим X  {x R2, (g x x1, 2)  0},найти min f , f R: 2 R .

x

Ïóñòü g разрешима относительно x1, то есть x1= (x2).

Тогда min f  min f ( (x2 ), x2 )  ? 

X                    X 2

Пусть f,  - дифференцируемы. Тогда условие экстремальности:

 f   f  x1            x1 x2

                           0,  , так как

1

g  g          g  g g( (x2),x2)  0                           0                        

x1 x2 x2                                       x2 x2 x1

Тогда:

 f          g

x1 x1  0

 f           g

                 0 , из определения 

x2 x2

g x( 1,x2 )  0

Таким образом в точке минимума выполняются эти соотношения. Получить эти необходимые условия можно используя функцию Лагранжа:  F(x,)=f+g.

Тогда необходимое условие min функции f(x1,x2) при наличии ограничений может быть записано следующим образом:

F f                 g

                        0

x1 x2 x2

F f                f

                    0

x1 x1 x1

F           g x( 1,x2 )  0



2.1.2 Ограничения типа неравенств.

Пусть: область, которая разрешена ограничениями

1

точка минимума конус

Тогда -f представляется так:

-f = 1g1+2g2, где 10, 20.(1)

-f расположен в конусе, образованном g1 и g2.

(1) переписывается так:

2

f + igi  0, где i - множители Лагранжа.

i1

По рисунку i gi (x) = 0 (мы попадаем на границу). Тогда можно рассматривать

2

функцию Лагранжа f + i gi и считать стационарную точку так, будто

Похожие материалы

Информация о работе