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

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

Замечание 1. Исследования метода Ньютона показывают, что для функции
)
(x
f
удовлетворяющей определенным требованиям, и начального приближения
0
x
, достаточно близкого к
*
x
, гарантируется высокая скорость сходимости последовательности
 
k
x
из (3) к точке минимума
*
x
Замечание 2. Если начальное приближение
0
x
выбрано не достаточно близким к точке
*
x
, то последовательность (3) метода Ньютона может расходиться. Так, положив при решении примера 2.12 3
0

x
, получим последовательность
5
,
9 1


x
,
124 2

x
,
9
,
23905 3


x
,
8 4
10 97
,
8


x
,
18 5
10 27
,
1



x
,..., расходимость которой не вызывает сомнений.
В подобных случаях необходимо найти лучшее начальное приближение
0
x
, например, с помощью нескольких итераций метода золотого сечения.

Лекция №4.
Задачи многомерной оптимизации.
Исследование задач многомерной оптимизации сводится к поиску точек минимума функции многих переменных на всем пространстве соответствующей размерности. Такая задача сложнее задачи минимизации функции одной переменной, так как с ростом размерности пространства переменных возрастают объем вычислений и сложность алгоритмов, затрудняется анализ поведения целевой функции
Постановка задачи многомерной оптимизации
Будем рассматривать функции многих переменных
)
,...,
,
(
)
(
2 1
n
x
x
x
f
X
f

как функции, заданные в точках
X
n
-мерного евклидова пространства
)
(
:
X
f
f
E
n

. Точки
n
E
X

представляются векторами-столбцами координат:


)
,
,
(
1
n
x
x
X

, где символ «

» - знак транспонирования. В дальнейшем, там, где это не приводит к недоразумениям, символ «Т», будем опускать.
Точка
n
E
X

*
называется точкой глобального минимума функции
)
( X
f
, если для всех
n
E
X

выполняется неравенство
)
(
)
(
*
X
f
X
f

Значение
*
*
)
(
min
)
(
f
X
f
X
f
n
E


называется
минимумом
функции.
Множество всех точек глобального минимума функции
)
( X
f
будем обозначать через
*
U
Замечание. Если



U
, то вместо минимума функции
)
( X
f
иногда рассматривают ее точную нижнюю грань
)
(
inf
*
X
f
f
n
E

Точка
X
называется точкой локального минимума функции
)
( X
f
, если существует

-окрестность точки
X

:








)

,
(
:
)

(
X
X
E
X
X
U
n
такая, что для всех
)
(

X
U
X


выполняется неравенство
)
(
)

(
X
f
X
f


Здесь
)

,
(
X
X

- расстояния между векторами
X
и
X

(точками пространства
n
E ):


2 1
1 2


)
,
(












n
j
j
j
x
x
X
X
Y
X

Теперь сформулируем постановку задачи безусловной оптимизации.
Дана целевая функция
n
переменных
)
( X
f
, определенная не всем пространстве
n
E . Требуется определить минимум этой функции на
n
E и точки
n
E
X

*
в которых он достигается.
Условимся для обозначения данной задачи использовать следующую краткую стандартную запись:


n
E
X
X
f

)
(
min
( 1) или эквивалентную ей :
(max)
min
)
(

X
f
,
n
E
X

Классический метод решения задачи безусловной оптимизации
Под классическим методом решения поставленной задачи (1) понимается подход к поиску минимума функции, который основан на дифференциальном исчислении функций многих переменных.
Напомним некоторые понятия и факты, известные из курса математического анализа.
Вектор













n
x
X
f
x
X
f
X
f
)
(
,...,
)
(
)
(
0 1
0 0
называется
градиентом
функции
)
( X
f
в точке
0
X . В малой окрестности точки
0
X градиент указывает направление наискорейшего возрастания функции
)
( X
f
, а его норма характеризует скорость этого возрастания. Градиент в точке
0
X

перпендикулярен линии (поверхности) уровня
c
X
f

)
(
, проходящей через эту точку.
Условие 1: Если в точке
n
E
X

0
функция
)
( X
f
дифференцируема и достигает локального минимума, то
0
)
(
0


X
f
или
n
j
x
X
f
j
,...,
1
,
0
)
(
0




( 2)
(необходимое условие минимума). Точки, в которых выполнено условие
(2), называются
стационарными
точками
дифференцируемой функции
)
( X
f
Если функция
)
( X
f
дважды дифференцируема в точке
n
E
X

0
, то существует матрица вторых производных (матрица Гессе, гессиан)
n
n
j
i
x
x
X
f
X
f














)
(
)
(
0 2
0
Из курса линейной алгебры известен критерий Сильвестра: матрица
)
(
ij
a
A

называется положительно определенной, если все ее угловые миноры положительны:
0 11 1



a
;
0 22 21 12 11 2



a
a
a
a
;…;
nn
n
n
n
a
a
a
a




1 1
11


. ( 3)
Здесь знак |

| означает определитель матрицы.
Соответственно: матрица
)
(
ij
a
A

называется отрицательно определенной, если знаки ее угловых миноров чередуются, начиная с минуса:
0 11 1



a
;
0 22 21 12 11 2



a
a
a
a
;…;
nn
n
n
n
a
a
a
a




1 1
11


. ( 4)
Условие 2: Если в стационарной точке
n
E
X

0
функция
)
( X
f
дважды дифференцируема и матрица ее вторых производных
)
( X
f


(Гессиан) положительно определена, то
0
X есть точка локального минимума
)
( X
f
(достаточное
условие
минимума).
Условия 1 и 2 лежат в основе классического метода минимизации функций, дифференцируемых во всем пространстве
n
E . Приведем алгоритм этого метода.
Шаг 1. Решив систему уравнений (2), найти все стационарные точки функции
)
( X
f
Шаг 2. Используя достаточные условия минимума, среди стационарных точек функции
)
( X
f
найти точки локального минимума и, сравнивая значения функции в них, определить точки глобального минимума.
Пример 1. Классическим методом решить задачу
}
2
)
(
min{
3 3
2 3
1 2
3 2
2 2
1
E
X
x
x
x
x
x
x
x
X
f







Шаг 1. Запишем систему (3.12):
0 1
2 1
1





x
x
f
;
0 2
3 2
2





x
x
x
f
;
0 2
2 2
3 3






x
x
x
f
Решив ее, получим стационарную точку







3 4
,
3 2
,
2 1
0
X
Шаг 2. Находим гессиан














2 1
0 1
2 0
0 0
2
)
(
0
X
f
Проверяем ее по критерию Сильвестра:

0 2
11 1




a
;
0 4
2 0
0 2
22 21 12 11 2





a
a
a
a
;
0 6
2 1
0 1
2 0
0 0
2 3






Согласно критерию Сильвестра, эта матрица положительно определена, заключаем, что
0
X является точкой минимума функции
)
( X
f
Минимальное значение
12 19
)
(
0
*



X
f
f
Замечание. Классический метод минимизации функций многих переменных имеет ограниченное практическое применение в основном из-за трудностей в аналитическом решении системы уравнений (3.12). Кроме того, на практике часто аналитическое задание функции неизвестно, а ее значения получаются в результате измерений. Все это вынуждает заняться разработкой других методов решения задачи (3.7) более удобных для компьютерной реализации.
Численные методы многомерной минимизации.
Численные методы многомерной оптимизации можно разделить на: прямые (без использовании информации о производной функции), и градиентные (с использованием значений производной).
Прямые методы безусловной оптимизации
Рассмотрим конкретнее вычислительные алгоритмы решения задачи безусловной минимизации, которые опираются только на вычисление значений функции
)
( X
f
, т.е. прямые методы минимизации. Важно отметить, что для их применения не требуется не только дифференцируемость целевой функции, но даже аналитическое ее задание. Нужно лишь иметь возможность вычислять или измерять значения
)
( X
f
в произвольных точках. Такие ситуации часто встречаются в практически важных задачах оптимизации.
Поиск по правильному симплексу
Определение 1. Правильным симплексом в пространстве
n
E называется множество из
1

n
равноудаленных друг от друга точек (вершин

симплекса). Отрезок, соединяющий две вершины называется ребром
симплекса.
В пространстве
2
E правильным симплексом является совокупность вершин равностороннего треугольника, в
3
E - правильного тетраэдра.
Из аналитической геометрии известно, что если
0
X - одна из вершин правильного симплекса в
n
E , то координаты остальных
n
вершин
n
X
X ,...,
1
находятся по формулам:









,
,
,
,
2 0
1 0
j
i
d
x
j
i
d
x
x
i
i
j
i
( 5) где


1 1
2 1




n
n
n
t
d
,


1 1
2 2



n
n
t
d
,
t - длина ребра. Вершину
0
X симплекса, построенного по формулам (5), будем называть базовой.
В алгоритме симплексного метода используется следующее важное свойство правильного симплекса. По известному симплексу можно построить новый симплекс путем отражения какой-либо вершины, например
k
X , симметрично относительно центра тяжести
c
X остальных вершин симплекса. Новая и старая вершины
k
X и
k
X связаны соотношением
c
k
k
X
X
X


2
, где












n
j
k
j
c
X
X
n
X
0 1
. В результате получается новый правильный симплекс с тем же ребром и вершинами
k
c
k
X
X
X


2
,
j
X ,
k
j
n
j


,
,...,
0
На рис. 1 представлена иллюстрация этого свойства симплекса в пространстве
2
E .

Рис. 1. Построение нового симплекса в
2
E
отражением точки
2
X
:
а

начальный симплекс
2 1
0
,
,
X
X
X
; б

новый симплекс
1 0
, X
X
;
центр отражения

точка
2
/
)
(
1 0
X
X
X
c


.
Поиск точки минимума функции
)
( X
f
с помощью правильных симплексов производится следующим образом. На каждой итерации поиска сравниваются значения функции
)
( X
f
в вершинах симплекса и выполняется описанная выше процедура отражения для той вершины, в которой
)
( X
f
принимает наибольшее значение. Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. Иначе выполняют ещѐ одну попытку отражения для вершины со следующим по величине значением
)
( X
f
. Если и она не приводит к уменьшению функции, то сокращают длину ребра и строят новый симплекс с этим ребром. При этом в качестве базовой выбирают ту вершину
0
X старого симплекса, в которой функция принимает наименьшее значение. Поиск точки минимума
*
X заканчивают, когда либо ребро симплекса, либо разность между значениями функции в вершинах симплекса становятся достаточно малыми. Опишем один из вариантов алгоритма этого метода.
Шаг 0. Задать параметр точности

, выбрать базовую точку
0
X и длину ребра t , построить по формулам (5) начальный симплекс и вычислить
)
(
0
X
f
Шаг 1. Вычислить значения функции
)
( X
f
в вершинах симплекса
n
X
X ,...,
1
Шаг 2. Упорядочить вершины симплекса
n
X
X ,...,
0
так, чтобы
)
(
)
(
)
(
1 0
n
X
f
X
f
X
f




Шаг 3. Проверить условие достижения точности






n
j
j
X
f
X
f
n
1 2
2 0
)
(
)
(
1

.
( 6)
Если оно выполняется, то перейти к шагу 7, иначе – к шагу 4.
Шаг 4. Найти по формуле центр тяжести
c
X вершин
1 1
,...,

n
X
X
и выполнить отражение вершины
n
X :
n
c
n
X
X
X


2
. Если
)
(
)
(
n
n
X
f
X
f

, то положить
n
n
X
X

и перейти к шагу 2, иначе - к шагу 5.
Шаг 5. Найти центр тяжести
c
X вершин
n
n
X
X
X
,
,...,
2 1

и выполнить отражение вершины
1

n
X
:
1 1
2




n
c
n
X
X
X
. Если
)
(
)
(
1 1



n
n
X
f
X
f
, то положить
1 1



n
n
X
X
и перейти к шагу 2, иначе – к шагу 6
Шаг 6. Построить новый правильный симплекс с вдвое меньшим ребром, считая базовой вершину
0
X , а остальные
n
вершин находя по формуле
2
/
)
(
0
X
X
X
j
j


n
j
,...,
1

и перейти к шагу 1.
Шаг 7. Завершить вычисления, положив
)
(
,
0
*
0
*
X
f
f
X
X


Геометрическая иллюстрация работы алгоритма в пространстве
2
E показана на рис. 2, где точки
2 1
0
,
,
X
X
X
- вершины начального симплекса, а пунктиром указаны операции отражения.
Рис. 2. Поиск точки минимума функции
)
( X
f
с помощью
правильных симплексов в пространстве
2
E
.