Одномерная минимизация. Горячев Л.В. - 10 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

Составители: 

Рубрика: 

10
оптимума параболы на этом отрезке может служить оценкой точки оптимума нашей функции на
этом отрезке
x
min
=
b
2a
=
x
2
+ x
1
2
−
b
0
2a
0
Аппроксимирующий квадратичный полином также является унимодальной функцией.
Рассмотрим одну схему метода квадратичной аппроксимации [4]
Пусть x
1
-начальная точка, x-выбранная величина шага по оси x
Шаг 1. Находим x
2
= x
1
+ x
Шаг 2. Вычислить f(x
1
) и f(x
2
)
Шаг 3. Если f(x
1
) >f(x
2
), то находим x
3
= x
1
+2x и переход к 4, если f(x
1
) <f(x
2
), находим
x
3
= x
1
−x к4
Шаг 4. Вычисление f(x
3
), находим F
min
= minf(x
1
),f(x
2
),f(x
3
),
фиксируем точку x
min
, на которой достигается F
min
Шаг 5. По известным трем точкам аппроксимируем функцию и находим точку x
min
Шаг 6. Проверка на окончание процесса:
а) Является ли разность |x
min
− x
min
| достаточно малой?
Если оба условия выполняются, закончить процесс, в противном случае переход к 7.
Шаг 7. Выбираем “лучшую” из точек x
min
и x
min
и две точки по обе стороны. Переход к шагу 4.
Замечание: На шаге можно применять одно из проверочных условий.
МЕТОД КАСАТЕЛЬНЫХ
В заключение данной темы рассмотрим весьма простой метод отыскания минимума выпуклой
дифференцируемой функции. Напомним, что функция f(x) называется выпуклой на отрезке [a, b],
если для произвольных x
1
и x
2
(a x
1
<x
2
b),всякогоα (0 α 1) справедливо неравенство
f(αx
1
+(1− α)x
2
) αf(x
1
)+(1− α)f(x
2
)
Если функция f(x) имеет на отрезке [a, b] непрерывную вторую производную f

(x), то для того,
чтобы функция была выпуклой на этом отрезке, достаточно, чтобы f

(x) 0, ∀x ∈ (a, b).
Этот критерий удобно применять на практике.
Пусть дана выпуклая функция f(x), определенная на отрезке [a, b]. Проведем в точках (a, f(a)) и
(b, f(b)) касательные к кривой y = f (x):
y −f (a)=f
(a)(x − a));
y −f (b)=f
(b)(x − b)).
Касательные пересекаются в точке с абсциссой
c =
f(b) − f (a)+f
(a)a − f
(b)b
f
(a) − f
(b)
Из выпуклости следует:
если f
(c) > 0,тоx
∗
∈ (a, c);
если f
(c) < 0,тоx
∗
∈ (c, b);
если f
(c)=0,тоc является точкой минимума.
Процесс вычислений заканчивается, когда в очередной точке c выполняется условие |f
(c)| <ε,где
ε>0 задано. За приближенное значение точки минимума принимается значение c,т.е.x
∗
≈ c.
Схема метода касательных
1. Проверить выпуклость функции f(x) на отрезке [a, b].
2. Найти c по известной формуле.
3. Найти f
(c), если |f
(c)| ε,тоx
∗
≈ c;
10

оптимума параболы на этом отрезке может служить оценкой точки оптимума нашей функции на
этом отрезке
                                        b   x2 + x1    b0
                                xmin =    =         −
                                       2a      2      2a0

Аппроксимирующий квадратичный полином также является унимодальной функцией.
Рассмотрим одну схему метода квадратичной аппроксимации [4]
Пусть x1 -начальная точка, x-выбранная величина шага по оси x
Шаг 1. Находим x2 = x1 + x
Шаг 2. Вычислить f (x1 ) и f (x2 )
Шаг 3. Если f (x1 ) > f (x2 ), то находим x3 = x1 + 2 x и переход к 4, если f (x1 ) < f (x2 ), находим
x3 = x1 − x к 4
Шаг 4. Вычисление f (x3 ), находим Fmin = minf (x1 ), f (x2 ), f (x3 ),
фиксируем точку xmin , на которой достигается Fmin
Шаг 5. По известным трем точкам аппроксимируем функцию и находим точку xmin
Шаг 6. Проверка на окончание процесса:
а) Является ли разность |xmin − xmin | достаточно малой?
   Если оба условия выполняются, закончить процесс, в противном случае переход к 7.
Шаг 7. Выбираем “лучшую” из точек xmin и xmin и две точки по обе стороны. Переход к шагу 4.
Замечание: На шаге можно применять одно из проверочных условий.

     МЕТОД КАСАТЕЛЬНЫХ

   В заключение данной темы рассмотрим весьма простой метод отыскания минимума выпуклой
дифференцируемой функции. Напомним, что функция f (x) называется выпуклой на отрезке [a, b],
если для произвольных x1 и x2 (a  x1 < x2  b), всякого α (0  α  1) справедливо неравенство

                             f (αx1 + (1 − α)x2 )  αf (x1 ) + (1 − α)f (x2 )


Если функция f (x) имеет на отрезке [a, b] непрерывную вторую производную f  (x), то для того,
чтобы функция была выпуклой на этом отрезке, достаточно, чтобы f  (x)  0, ∀x ∈ (a, b).
Этот критерий удобно применять на практике.
Пусть дана выпуклая функция f (x), определенная на отрезке [a, b]. Проведем в точках (a, f (a)) и
(b, f (b)) касательные к кривой y = f (x):

                                        y − f (a) = f  (a)(x − a));
                                        y − f (b) = f  (b)(x − b)).

Касательные пересекаются в точке с абсциссой

                                        f (b) − f (a) + f  (a)a − f  (b)b
                                   c=
                                                 f  (a) − f  (b)

Из выпуклости следует:
если f  (c) > 0, то x∗ ∈ (a, c);
если f  (c) < 0, то x∗ ∈ (c, b);
если f  (c) = 0, то c является точкой минимума.
Процесс вычислений заканчивается, когда в очередной точке c выполняется условие |f  (c)| < ε, где
ε > 0 задано. За приближенное значение точки минимума принимается значение c, т.е. x∗ ≈ c.

                                     Схема метода касательных

   1. Проверить выпуклость функции f (x) на отрезке [a, b].
2. Найти c по известной формуле.
3. Найти f  (c), если |f  (c)|  ε, то x∗ ≈ c;

Страницы