Лекция_1_merged. Лекция 1. Предмет и задачи методов оптимизации

• Название: Лекция 1. Предмет и задачи методов оптимизации
• Дата: 05.02.2022
• Размер: 3.42 Mb.
• Имя файла: Лекция_1_merged.pdf
• Тип: Лекция; #352185
• страница: 3 из 9

методами исключения отрезков.
Рис. 2. Уменьшение отрезка поиска точки
минимума методами исключения отрезков

Чтобы относительное уменьшение отрезка на каждой итерации не зависело от того, какая из его частей исключается из дальнейшего рассмотрения, пробные точки следует располагать симметрично относительно середины исходного отрезка. В зависимости от способа выбора пробных точек получаются различные методы исключения отрезков. На практике используются следующие: метод дихотомии и метод золотого сечения.
Метод дихотомии (деления отрезка пополам)
Вэтом методе точки
1
x
и
2
x
располагаются близко к середине очередного отрезка
]
;
[ b
a
, т.е.
2 1




b
a
x
,
2 2




b
a
x
,
( 7)
где
0


- малое число. При этом отношение длин нового и исходного отрезков
)
(
2 2
1 2
1
a
b
a
b
a
x
a
b
x
b











близко к 1/2, этим и объясняется название метода.
Отметим, что для любых точек
1
x
и
2
x
величина
2 1


, поэтому указанный выбор пробных точек объясняется стремлением обеспечить максимально возможное относительное уменьшение отрезка на каждой итерации поиска
*
x
В конце вычислений по методу дихотомии в качестве приближенного значения
*
x
берут середину последнего из найденных отрезков
]
;
[ b
a
,
убедившись предварительно, что достигнуто неравенство



2
/
)
(
a
b
Опишем алгоритм метода деления отрезка пополам.
Шаг 1. Определить
1
x
и
2
x
по формулам (7). Вычислить
)
(
1
x
f
и
)
(
2
x
f
Шаг 2. Сравнить
)
(
1
x
f
и
)
(
2
x
f
. Если
)
(
)
(
2 1
x
f
x
f

, то перейти к отрезку
]
;
[
2
x
a
, положив
2
x
b

, иначе - к отрезку
]
;
[
1
b
x
, положив
1
x
a


Шаг 3. Найти достигнутую точность
2
a
b
n



. Если



n
, то перейти к следующей итерации, вернувшись к шагу 1. Если



n
, то завершить поиск
*
x
, перейдя к шагу 4.
Шаг 4. Положить
2
*
b
a
x
x



,
)
(
*
x
f
f


Лекция №3.
Метод золотого сечения.
Рассмотрим такое симметричное расположение точек
1
x
и
2
x
на отрезке
]
;
[ b
a
,при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка.
Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения
)
(x
f
, так как другое значение уже найдено на одной из предыдущих итераций.
Найдем точки
1
x
и
2
x
,обладающие указанным свойством.
Рассмотрим сначала отрезок
]
1
;
0
[
и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть


2
x
, тогда симметрично расположенная точка



1 1
x
(рис. 1).
Рис. 1. К определению пробных точек в методе золотого сечения
Пробная точка
1
x
отрезка
]
1
;
0
[
перейдет в пробную точку




1 2
x
нового отрезка
]
;
0
[

. Чтобы точки


2
x
и




1 2
x
делили отрезки
]
1
;
0
[
и
]
;
0
[

в одном и том же отношении, должно выполняться равенство





1 1
или




1 2
, откуда находим положительное значение
61803
,
0 2
1 5




…. Таким образом,
2 5
3 1


x
,
2 1
5 2


x
Д
ЛЯ произвольного отрезка
]
;
[ b
a
выражения для пробных точек примут вид
)
(
2 1
5
);
(
2 5
3 2
1
a
b
a
x
a
b
a
x








( 1)

Точки
1
x
и
2
x
из (1) обладают следующим свойством: каждая из них делит отрезок
]
;
[ b
a
на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньше частей отрезка. Точки с таким свойством называются точками
золотого сечения отрезка
]
;
[ b
a
.Это и объясняет название рассматриваемого метода.
На каждой итерации исключения отрезков с пробными точками (1) одна из них
x
переходит на следующий отрезок и значение
)
(x
f
в этой точке вычислять не следует. Если новым отрезком становится
]
;
[
2
x
a
, то на него переходит пробная точка
1
x
x

исходного отрезка, становясь его второй пробной точкой
1 2
x
x


(рис. 1). В случае перехода к отрезку
]
,
[
1
b
x
пробная точка
2
x
x

исходного отрезка становится первой пробной точкой отрезка
]
,
[
1
b
x
.
Легко проверить, что если осталась точка х
2
, то недостающую пробную точку х
1
можно вычислить как
2 1
x
b
a
x



, а если осталась точка х
1
, то точку х
2
можно найти как
1 2
x
b
a
x



. Поэтому на каждой итерации метода золотого сечения недостающую пробную точку нового отрезка можно найти по перешедшей на него пробной точке с помощью сложения и вычитания, не используя формул (1).
В конце вычислений по методу золотого сечения в качестве приближенного значения
*
x
можно взять середину последнего из полученных отрезков
2
b
a
x


На каждой итерации отрезок поиска точки минимума уменьшается в одном и том же отношении


2
/
1 5



, поэтому в результате
n
итераций его длина становится
)
(
a
b
n
n




. Таким образом, точность
n

, определения точки
*
x
после
n
итераций находится из равенства



a
b
n
n
n











2 1
5 2
1 2

,
( 2) а условием окончания поиска точки
*
x
с точностью е служит неравенство



n
Опишем алгоритм метода золотого сечения.
Шаг 1. Найти
1
x
и
2
x
по формулам (1). Вычислить
)
(
1
x
f
и
)
(
2
x
f
Положить


2
/
1 5



,
2
)
(
a
b
n



Шаг 2. Проверка на окончание поиска: если



n
, то перейти к шагу
3, иначе — к шагу 4.
Шаг 3. Переход к новому отрезку и новым пробным точкам. Если
)
(
)
(
2 1
x
f
x
f

, то положить
2
x
b

,
1 2
x
x

,
)
(
)
(
1 2
x
f
x
f

,
)
(
1
a
b
b
x




и вычислить
)
(
1
x
f
, иначе - пожить
1
x
a

,
2 1
x
x

,
)
(
)
(
2 1
x
f
x
f

,
)
(
2
a
b
a
x




и вычислить
)
(
2
x
f
. Положить
n
n



и перейти к шагу 2.
Шаг 4. Окончание поиска: положить
2
)
(
*
b
a
x
x



,
)
(
*
x
f
f

Замечание 1. Зная значение максимально допустимой погрешности метода

, можно определить число итераций, необходимое для достижения заданной точности. Это число можно найти из условия



n
с учетом соотношения (2):








a
b
n
n
2 1



a
b
n




2



a
b
n




2
log

 
a
b
a
b
n














2
ln
1
,
2
ln
2
ln
Замечание 2. Задав количество вычислений N функции в методе золотого сечения, можно определить достигнутую точность. Так как
N
вычислений
)
(x
f
позволяют выполнить
1

N
итераций метода золотого сечения, то достигнутая в результате этих вычислений точность определения
*
x
составляет

 


a
b
N
N
N












1 1
2 1
5 2
1


Методы, использующие производные целевой функции
Рассмотренные ранее прямые методы используются при минимальных требованиях к целевой функции
)
(x
f
- она считается унимодальной и вычислению (измерению) подлежат значения только самой функции, но не ее производных. Если усилить эти требования, предположив, что
)
(x
f
является дифференцируемой или дважды дифференцируемой выпуклой функцией, и считать, что возможно вычисление производных
)
(x
f
в произвольно выбранных точках, то эффективность процедур поиска точки минимума можно существенно повысить.
Рассмотрим методы минимизации, в которых используются значения производных целевой функции.
Напомним, что для выпуклой дифференцируемой функции равенство
0
)
(


x
f
является не только необходимым, но и достаточным условием глобального минимума. Поэтому, если известно, что
*
x
является внутренней точкой отрезка
]
,
[ b
a
, то приближенное равенство
0
)
(


x
f
или



)
(x
f
, где
0


- достаточно малое число, может служить условием остановки вычислений в рассматриваемых ниже методах
Метод средней точки
Если определение значений производной
)
(x
f

не представляет затруднений , то в процедуре исключения отрезков метода деления отрезка пополам вычисление двух значений
)
(x
f
вблизи середины очередного отрезка можно заменить вычислением одного значения
)
(x
f

в его средней точке
2
b
a
x



В самом деле, если
0
)
(


x
f
, то точка
x
лежит на участке монотонного возрастания
)
(x
f
, поэтому
x
x

*
, и точку минимума следует искать на отрезке
]
;
[
x
a
. При
0
)
(


x
f
имеем противоположную ситуацию и переходим к отрезку
]
;
[ b
x
. Равенство
0
)
(


x
f
означает, что точка минимума найдена точно:
x
x

*
(рис.2).
Такое исключение отрезков требует на каждой итерации только одного вычисления
)
(x
f

и уменьшает отрезок поиска точки
*
x
ровно вдвое.
Опишем алгоритм метода средней точки.
Шаг 1: Положить
2
b
a
x


. Вычислить
)
(x
f

Шаг 2: Проверка на окончание поиска: если



)
(x
f
, то положить
x
x

*
,
)
(
*
x
f
f

и завершить поиск, иначе – перейти к шагу 3.
Шаг 3: Сравнить
)
(x
f

с нулем. Если
0
)
(


x
f
, то продолжить поиск на отрезке
]
;
[
x
a
, положив
x
b

, иначе – перейти к отрезку
]
;
[ b
x
, положив
x
a

. Перейти к шагу 1.
Рис. 2 Исключение отрезков методом средней точки

Пример 1. Методом средней точки решить задачу
}
]
1
;
0
[
)
(
min{
4




x
e
x
x
f
x
, с точностью
02
,
0
)
(


x
f
Итерация №1.
Шаг 1: Находим
5
,
0

x
,
107
,
0
)
(



x
f
. Переходим к шагу 2.
Шаг 2: Так как
02
,
0
)
(


x
f
, переходим к шагу 3
Шаг 3: Так как
0
)
(


x
f
, полагаем
5
,
0


x
a
и переходим к следующей итерации, начиная с шага 1.
Результаты вычислений на остальных итерациях приведены в табл. 1.
Таблица 1.
№
a
b
x
)
(x
f

Знак
)
(x
f

2 0,5 1
0,750 1,215
+
3 0,5 0,750 0,625 0,441
+
4 0,5 0,625 0,563 0,142
+
5 0,5 0,563 0,531 0,012 Точность достигнута
Таким образом,
531
,
0
*

x
,
668
,
0
*

f
Метод Ньютона
Предположим, что
)
(x
f
- дважды дифференцируемая функция, причем
0
)
(


x
f
(напомним, что это гарантирует выпуклость
)
(x
f
). Тогда корень уравнения
0
)
(


x
f
можно искать приближенно, используя метод
касательных. Этот метод решения уравнения
0
)
(

x
F
состоит в построении последовательных приближений
k
x
,
,...
1
,
0

k
следующим образом.
В очередной точке
k
x
строится линейная аппроксимация функции
)
(x
F
(касательная к графику
)
(x
F
)и точка, в которой линейная аппроксимирующая функция обращается в нуль, используется в качестве следующего приближения
1

k
x
(рис. 3).
Рис. 3. Иллюстрация к методу
касательных

Уравнение касательной к графику
)
(x
F
в точке
k
x
x

имеет вид
)
)(
(
)
(
k
k
k
x
x
x
F
x
F
y




, поэтому точка
1


k
x
x
, найденная из условия
0

y
, определяется формулой
)
(
)
(
1
k
k
k
k
x
F
x
F
x
x




Положим
)
(
)
(
x
f
x
F


, тогда для решения уравнения
0
)
(


x
f
необходимо построить последовательность
,...,
1
,
0
,
)
(
)
(
1






k
x
f
x
f
x
x
k
k
k
k
( 3) где
0
x
- точка, выбранная в качестве начального приближения.
Вычисления по формуле (2.21) производят до тех пор, пока не выполнится неравенство



)
(
k
x
f
, после чего полагают
k
x
x

*
. Описанная процедура поиска точки минимума называется методом Ньютона.
Пример 2. Методом Ньютона решить задачу
)
1
ln(
2 1
)
(
)
(
2
x
x
arctg
x
x
f



с точностью
7 10
)
(



x
f
Найдем первую производную функции (для этого используем значения табличных производных
2 1
1
)
(
x
x
arctg



,
x
x
1
)
ln(


:



















2 2
2 1
1 2
2 1
)
(
1 1
1
)
1
ln(
2 1
)
(
)
(
x
x
x
arctg
x
x
x
x
arctg
x
x
f
)
(
1
)
(
1 2
2
x
arctg
x
x
x
arctg
x
x






Теперь найдем вторую производную:
2 1
1
)
(
x
x
f



Функция
)
(x
f
дважды дифференцируема, причем
0 1
1
)
(
2




x
x
f
для любого х. Выберем начальное приближение
1 0

x
и построим последовательные приближения
k
x
по формуле (2.21), записывая их в табл.
2. вместе со значениями
)
(
k
x
f


Таблица 2
k
k
x
)
(
k
x
f

0 1
0,785 1
-0,570
-0,519 2
0,117 0,116 3
-3 10 1,061
-

-3 10 1,061
-

4
-8 10 9

-8 10 9

Таким образом,
0 10 9
8
*




x