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

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

достаточно, чтобы существовала такая окрестность







x
x
x
x
U

:
)

(
, что
0
)
(


x
f
при
)

,

(
x
x
x



и
0
)
(


x
f
при
)

,

(



x
x
x
. Если же
0
)
(


x
f
при
)

,

(
x
x
x



и
0
)
(


x
f
при
)

,

(



x
x
x
, то точка x - точка максимума функции
)
(x
f
Если найдется такое положительное

, что
)
(x
f

сохраняет неизменный знак при
)

(x
U
x


, то точка x не является точкой экстремума функции
)
(x
f
В тех случаях, когда удается вычислить в подозрительной точке производные второго и более высокого порядков, то применяют достаточное условие более общего вида. А именно, пусть известны производные
)

(x
f

,
)

(x
f

,…,
)

(
)
(
x
f
n
, причем
0
)

(
)
(

x
f
i
при
1
,...,
2
,
1

n
, а
0
)

(
)
(

x
f
n
,
1

n
Если
n
- четное число, то в случае
0
)

(
)
(

x
f
n
в точке x
реализуется локальный минимум, а в случае
0
)

(
)
(

x
f
n
- локальный максимум. Если же
n
нечетно, то при
b
x
a



в точке x
не может быть локального экстремума, при
a
x


(или
b
x


) в случае
0
)

(
)
(

x
f
n
в точке x
имеем локальный минимум (максимум), а в случае
0
)

(
)
(

x
f
n
- локальный максимум
(минимум).
Чтобы найти глобальный минимум (максимум) функции
)
(x
f
на
]
,
[ b
a
, нужно перебрать все точки локального минимума (максимума) на
]
,
[ b
a
и

среди них выбрать точку с наименьшим (наибольшим) значением функции, если таковое существует.
Поскольку применение достаточных условий требует вычисления высших производных функции
)
(x
f
, то в вычислительном плане проще сравнить значения
)
(x
f
во всех стационарных точках, не интересуясь их характером. С учетом этого можно предложить следующий алгоритм классического метода для решения задачи одномерной оптимизации (1).
Шаг 1. Найти все точки, подозрительные на экстремум, в том числе и
стационарные точки, т.е. корни уравнения
0
)
(


x
f
( 4)
Пусть это будут точки
)
;
(
,...,
1 1
b
a
x
x
k


. Положить
a
x

0
,
b
x
k

.
Шаг 2. Вычислить значения
)
(
i
x
f
функции
)
(x
f
в точках
i
x
,
k
i
,...,
0

Шаг 3. Найти
)
(
)
(
min
0
*
m
i
k
i
x
f
x
f
f




. Положить
m
x
x

*
Пример 1. Решить задачу


]
2
;
2
[
1 3
)
(
min
3





x
x
x
x
f
классическим методом.
Шаг 1. Рассматриваемая функция непрерывна внутри отрезка [-2;2], следовательно, у нас нет точек разрыва первого рода. Найдем производную этой функции:
3 3
)
(
2



x
x
f
Видно, что производная определена для любой точки отрезка, значит точек. В которых производной не существует, мы также не имеем.
Найдем стационарные точки. Для этого находим корни уравнения
0 3
3
)
(
2




x
x
f
из интервала
)
2
;
2
(

:
1 1


x
,
1 2

x
. Эти точки и будут точками, подозрительными на экстремум. Присоединим к ним точки – границы отрезка:
2 0


x
,
2 3

x
Шаг 2. Вычисляем значения
)
(x
f
в точках
i
x
,
3
,...,
0

i
:
1
)
(
0


x
f
,
3
)
(
1

x
f
,
1
)
(
2


x
f
,
3
)
(
3

x
f

Шаг 3. Находим
)
3
,
1
,
3
,
1
min(
*



f
=-1=
)
(
0
x
f
. Поэтому
2 0
*



x
x
,
1
*


f
Классический метод решения задачи (2.1) следует использовать в тех случаях, когда достаточно просто удается выявить все подозрительные точки и реализовать достаточные условия. Однако, этот метод имеет весьма ограниченное применение. Дело в том, что вычисление производной
)
(x
f

в практических задачах зачастую является непростым делом. Например, может оказаться, что значение функции
)
(x
f
определяются из наблюдений или каких-либо физических экспериментов, и получить информацию о ее производной крайне затруднительно. Но даже в тех случаях, когда производную все же удается вычислить, решение уравнения (2.6) и выявление других точек, подозрительных на экстремум, может быть связано с серьѐзными трудностями. Поэтому важно иметь также и другие методы решения задачи (1) не требующие вычисления производных, более удобные для программной реализации.
Прямые методы одномерного поиска
Для решения задачи минимизации функции
)
(x
f
на отрезке
]
;
[ b
a
на практике, как правило, применяют приближенные методы. Они позволяют найти решение этой задачи с необходимой точностью в результате определения конечного числа значений функции
)
(x
f
и ее производных в некоторых точках отрезка
]
;
[ b
a
. Методы, использующие только значения функции и не требующие вычисления ее производных, называются
прямыми методами минимизации.
Большим достоинством прямых методов является то, что от целевой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы прямых методов минимизации, это возможность определения значений
)
(x
f
в заданных точках.

Рассмотрим наиболее распространенные на практике прямые методы поиска точки минимума.
Однако все эти методы применимы лишь для тех функций, у которых каждый локальный минимум является одновременно и глобальным. Такие функции называются унимодальными.
Определение 1. Функция
)
(x
f
называется унимодальной на отрезке


 
b
a
b
x
a
x
U
;
:




, если она непрерывна на
 
b
a,
и существуют числа

, β:
b
a





такие, что
1)
)
(x
f
монотонно убывает при



x
a
(если


a
);
2)
)
(x
f
монотонно возрастает при
b
x



(если
b


);
3)
)
(
inf
)
(
x
f
f
x
f
U
x




при




x
, так что




;


U
Множество унимодальных на отрезке
]
;
[ b
a
функций мы будем обозначать через
]
;
[ b
a
Q
Отметим, что возможно вырождение в точку одного или двух отрезков из
]
;
[

a
,
]
;
[


и
]
;
[
b

. Некоторые варианты расположения и вырождения в точку отрезков монотонности и постоянства унимодальной функции показаны на рис. 2.1.
Рис. 1. Графики унимодальных функций.

Из определения 1 вытекают следующие основные свойства унимодальных функций.
1. Любая из точек локального минимума унимодальной функции является и точкой ее глобального минимума на отрезке
]
;
[ b
a
2. Функция, унимодальная на отрезке
]
;
[ b
a
, является унимодальной и на любом меньшем отрезке

]
;
[ d
c
]
;
[ b
a
3. Пусть
]
;
[
)
(
b
a
Q
x
f

и
b
x
x
a



2 1
. Тогда: если
)
(
)
(
2 1
x
f
x
f

, то
]
,
[
2
*
x
a
x

; если
)
(
)
(
2 1
x
f
x
f

, то
]
,
[
1
*
b
x
x

,
( 5) где
*
x
- одна из точек минимума
)
(x
f
на отрезке
]
;
[ b
a
Существует множество методов одномерного прямого поиска, например:
1. Метод равномерного поиска
2. Метод поразрядного поиска
3. Метод дихотомии
4. Метод золотого сечения
5. и т.д….
Метод равномерного поиска
Метод равномерного поиска является простейшим из прямых методов минимизации и состоит в следующем.
Разобьем отрезок
]
;
[ b
a
на
n
равных частей точками деления
n
i
n
a
b
i
a
x
i
,...,
0
,
)
(




. Вычислив значения
)
(x
f
в точках
i
x
, путем сравнения найдем точку
n
m
x
m


0
:
, для которой
))
(
min(
)
(
i
m
x
f
x
f

( 6)
Полагая
)
(
,
*
*
m
m
x
f
f
x
x


, получим решение задачи (1).
Пример 2. Методом перебора решить задачу


]
1
;
0
[
)
(
min
4




x
e
x
x
f
x
с точностью до
1
,
0



Функция
)
(x
f
унимодальна на отрезке
]
1
;
0
[
. Найдем число
n
отрезков разбиения:
10 1
,
0 0
1



n
, т.е. можно взять
10

n
. Вычислим значения
)
(
i
x
f
, где
10
,...,
1
,
1
,
0



i
i
x
i
и запишем их в табл. 1.
Таблица 1.
i
x
0,0 0,1 0,2 0,3 0,4
0,5
0,6 0,7 0,8 0,9 1
1 0,90 0,82 0,75 0,70 0,67 0,68 0,74 0,86 1,06 1,37
В этой таблице выделено минимальное из вычисленных значений
)
(x
f
Таким образом,
5
,
0
*

x
,
67
,
0
*

f
Метод поразрядного поиска
Рассмотрим возможности усовершенствования метода перебора с целью уменьшения количества значений
)
(x
f
, которые необходимо находить в процессе минимизации.
Во-первых, если оказывается, что
)
(
)
(
1


i
i
x
f
x
f
, то отпадает необходимость вычислять
)
(x
f
в точках
3 2
,


i
i
x
x
и т.д., как
1
*


i
x
x
Во-вторых, разумно было бы сначала определить отрезок, содержащий
*
x
, грубо, т.е. найти точку
*
x
с небольшой точностью, а затем искать ее на этом отрезке с меньшим шагом дискретизации, повышая точность.
Указанные возможности улучшения метода перебора реализованы в методе поразрядного поиска. В этом методе перебор точек отрезка происходит сначала с шагом






i
i
x
x
1
до тех пор, пока не выполнится условие
)
(
)
(
1


i
i
x
f
x
f
или пока очередная из этих точек не совпадет с концом отрезка. После этого шаг уменьшается (обычно в 4 раза), и перебор точек с новым шагом производится в противоположном направлении до тех пор, пока значения
)
(x
f
снова не перестанут уменьшаться или очередная
)
(
i
x
f

точка не совпадет с другим концом отрезка и т.д. Описанный процесс завершается, когда перебор в данном направлении закончен, а использованный при этом шаг дискретизации не превосходит

Приведем описание алгоритма метода поразрядного поиска.
Шаг 1: Выбрать начальный шаг
4
a
b



. Положить
a
x

0
, вычислить
)
(
0
x
f
Шаг2: Положить



0 1
x
x
. Вычислить
)
(
1
x
f
Шаг 3: Сравнить значения
)
(
0
x
f
и
)
(
1
x
f
. Если
)
(
0
x
f
>
)
(
1
x
f
, то перейти к шагу 4, иначе - к шагу 5.
Шаг 4: Положить
0
x
=
1
x ,
)
(
0
x
f
=
)
(
1
x
f
Проверить условие
)
;
(
0
b
a
x

Если
b
x
a


0
, то прейти к шагу 2, иначе - к шагу 5.
Шаг 5: Проверка на окончание поиска: если



, то вычисления завершить, полагая
*
x
=
0
x
,
)
(
*
x
f
=
)
(
0
x
f
, иначе - перейти к шагу 6.
Шаг 6: Изменение направления и шага поиска: положить
4




,
0
x
=
1
x ,
)
(
0
x
f
=
)
(
1
x
f
. Перейти к шагу 2.
Пример 3. Методом поразрядного поиска решить задачу:
 
}
1
,
0
|
)
(
min{
4




x
e
x
x
f
x
, с точностью до
1
,
0


Начальный шаг
25
,
0 4
/
1



. Вычисляя последовательно значения
)
(x
f
в точках дискретизации с шагом 0,25, получим:
x
0

0,25

0,50

0,75
f(x) 1,000 > 0,783 > 0,669 < 0,789
Так как
)
75
,
0
(
)
50
,
0
(
f
f

, причем



, то поиск
*
x
продолжаем из начальной точки
75
,
0 0

x
, изменив его направление и уменьшив шаг в 4 раза:
x
0,4375

0,5

0,5625

0,625

0,6875

0,75
f(x) 0,682 > 0,669 < 0,670 < 0,688 < 0,726 < 0,789

Так как




0625
,
0
, то поиск завершен и
5
,
0
*

x
,
67
,
0
*

f
Методы исключения отрезков
В методе перебора, рассмотренном выше, точки
i
x
, в которых определяются значения
)
(x
f
, выбираются заранее. Если же для выбора очередной точки вычисления (измерения)
)
(x
f
использовать информацию, содержащуюся в уже найденных значениях
)
(x
f
, то поиск точки минимума можно сделать более эффективным, т.е. сократить число определяемых для этого значений
)
(x
f
), как, например, в методе поразрядного поиска.
Один из путей такого более эффективного поиска точки
*
x
указывает свойство 3 унимодальных функций.
Пусть
b
x
x
a



2 1
. Сравнив значения
)
(x
f
в точках
1
x
и
2
x
(пробных точках), можно сократить отрезок поиска точки
*
x
, перейдя к отрезку
]
;
[
2
x
a
, если
)
(
)
(
2 1
x
f
x
f

, или к отрезку
]
,
[
1
b
x
, если
)
(
)
(
2 1
x
f
x
f

(рис. 2.7). Описанную процедуру можно повторить необходимое число раз, последовательно уменьшая отрезок, содержащий точку минимума. Когда длина последнего из найденных отрезков станет достаточно малой, следует положить
x
x

*
, где
x
- одна из точек этого отрезка, например, его середина. Методы минимизации, основанные на этом принципе, называются