ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2021
Просмотров: 693
Скачиваний: 1
16
.
0
)
(
,...,
0
)
(
,
0
)
(
0
0
2
0
1
P
u
J
P
u
J
P
u
J
n
Определение
.
Точки
,
в
которых
обращаются
в
нуль
все
частные
производные
первого
порядка
функции
)
(
u
J
,
называются
стационарными
точками
этой
функции
.
МЕТОД
ГРАДИЕНТНОГО
СПУСКА
Метод
градиентного
спуска
использует
условие
дифференцируемости
функции
)
(
u
J
в
n
R
.
В
качестве
критерия
остановки
этого
метода
,
как
правило
,
выбирается
условие
||
)
(
||
k
u
J
grad
.
В
качкестве
направления
движения
для
нахождения
минимума
в
метода
градиентного
спуска
на
каждом
шаге
выбирается
вектор
-
антиградиент
)
(
k
k
u
J
grad
v
,
так
как
в
малой
окрестности
точки
k
u
антиградиент
обеспечивает
наискорейшее
убывание
функции
.
Рассмотрим
два
варианта
метода
,
отличающиеся
способом
нахождения
величины
.
Замечание
.
Если
)
,...,
,
(
)
(
2
1
n
u
u
u
J
u
J
,
то
n
u
J
u
J
u
J
u
J
grad
,...,
,
)
(
2
1
,
а
2
2
2
2
1
...
||
)
(
||
n
u
J
u
J
u
J
u
J
grad
.
Точка
*
u
-
точка
минимума
функции
)
(
u
J
,
а
)
(
*
u
J
-
значение
функции
в
точке
минимума
.
АЛГОРИТМ
(
метод
дробления
шага
)
Шаг
1
.
Задать
0
-
требуемую
точность
,
начальный
шаг
0
.
Выбрать
n
R
u
0
и
вычислить
)
(
0
u
J
.
Шаг
2
.
Найти
)
(
0
u
J
grad
и
проверить
критерий
остановки
метода
||
)
(
||
0
u
J
grad
.
Если
он
выполнен
,
то
вычисления
завершаются
.
Полагаем
0
*
u
u
,
)
(
0
*
u
J
J
.
Шаг
3
.
Положить
)
(
0
0
1
u
J
grad
u
u
.
Вычислить
)
(
1
u
J
.
Если
)
(
)
(
0
1
u
J
u
J
,
то
положить
1
0
u
u
и
)
(
)
(
1
0
u
J
u
J
.
Перейти
к
шагу
2
.
Шаг
4
.
Положить
2
/
и
перейти
к
шагу
3
.
АЛГОРИТМ
(
метод
наискорейшего
спуска
)
Шаг
1
.
Задать
0
-
требуемую
точность
.
Выбрать
n
R
u
0
.
Шаг
2
.
Найти
)
(
0
u
J
grad
и
проверить
критерий
остановки
метода
||
)
(
||
0
u
J
grad
.
Если
он
выполнен
,
то
вычисления
завершаются
.
Полагаем
0
*
u
u
,
)
(
0
*
u
J
J
.
17
Шаг
3
.
Решить
задачу
одномерной
оптимизации
min
))
(
(
)
(
0
0
u
J
grad
u
J
,
при
0
,
т
.
е
.
найти
*
.
Положить
)
(
0
*
0
0
u
J
grad
u
u
.
Перейти
к
шагу
2
.
Замечание
.
Кроме
рассмотренных
методов
выбора
шага
на
практике
часто
применяют
методы
с
изначально
заданным
шагом
,
например
,
)
1
/(
1
k
k
,
где
k
-
номер
итерации
.
МЕТОД
НЬЮТОНА
МНОГОМЕРНОЙ
МИНИМИЗАЦИИ
Итерационный
метод
вида
1
*
1
)
(
H
u
J
grad
u
u
k
k
k
носит
название
метода
Ньютона
.
В
этой
формуле
1
H
-
это
обратная
матрица
к
матрице
вторых
частных
производных
.
...
...
...
...
...
...
...
2
2
2
2
1
2
1
2
1
2
2
2
1
2
n
n
n
n
u
J
u
u
J
u
u
J
u
u
J
u
u
J
u
J
H
Для
квадратичной
функции
с
положительно
определённой
матрицей
Гессе
применение
метода
Ньютона
с
шагом
1
обеспечивает
получение
точки
глобального
минимума
ровно
за
одну
итерацию
,
независимо
от
выбора
начальной
точки
.
Для
выпуклой
квадратичной
функции
применение
этого
метода
обеспечивает
,
как
правило
,
быструю
сходимость
.
Однако
,
если
точка
n
R
u
0
выбрана
недостаточно
близко
к
оптимальному
решению
,
то
последовательность
n
k
R
u
может
расходиться
(
как
и
в
одномерном
случае
).
Существенным
недостатком
метода
Ньютона
является
необходимость
вычисления
и
обращения
матрицы
Гессе
на
каждой
итерации
.
АЛГОРИТМ
Шаг
1
.
Задать
начальную
точку
n
R
u
0
,
0
-
требуемую
точность
,
вычислить
)
(
0
u
J
.
Шаг
2
.
Найти
)
(
0
u
J
grad
и
проверить
критерий
остановки
метода
||
)
(
||
0
u
J
grad
.
Если
он
выполнен
,
то
вычисления
завершаются
.
Полагаем
0
*
u
u
,
)
(
0
*
u
J
J
.
Шаг
3
.
Положить
1
0
0
0
)
(
H
u
J
grad
u
u
.
Вычислить
)
(
0
u
J
.
Перейти
к
шагу
2
.
18
МЕТОД
ШТРАФНЫХ
ФУНКЦИЙ
Основная
идея
метода
штрафных
функций
состоит
в
преобразовании
задачи
минимизации
функции
с
соответствующими
ограничениями
в
задачу
поиска
минимума
функции
без
ограничений
.
Преимущество
,
которое
получаем
в
результате
такого
перехода
к
новой
функции
,
достигается
за
счет
применения
более
простых
алгоритмов
.
Постановка
задачи
.
Требуется
найти
минимум
функции
)
,...,
(
1
n
u
u
J
при
ограничениях
m
i
u
u
g
n
i
,...,
2
,
1
,
0
)
,...,
(
1
или
inf,
)
,...,
(
1
n
u
u
J
m
i
u
g
i
,...,
2
,
1
,
0
)
(
.
Введём
функцию
)
,...,
(
)
,...,
(
)
,...,
(
1
1
1
n
n
n
u
u
P
u
u
J
u
u
F
.
Здесь
)
,...,
(
1
n
u
u
P
выступает
в
роли
штрафа
.
Штраф
можно
выбрать
в
виде
m
i
n
i
n
u
u
g
r
u
u
P
1
1
1
|
)
,...,
(
/
1
|
)
,...,
(
или
в
виде
m
i
n
i
n
u
u
g
r
u
u
P
1
1
2
1
)
,...,
(
)
,...,
(
,
где
-
некоторый
положительный
параметр
.
ПРИМЕРЫ
1.
Один
из
вариантов
выбора
штрафной
функции
таков
.
Пусть
дана
функция
2
2
1
2
1
)
1
(
)
,
(
u
u
u
u
J
при
ограничениях
0
,
2
2
1
u
u
.
Выберем
штраф
|
/
1
)
2
/(
1
|
)
,
(
2
1
2
1
u
u
r
u
u
P
.
В
результате
минимизируем
функцию
|
/
1
)
2
/(
1
|
)
1
(
)
,
,
(
2
1
2
2
1
2
1
u
u
r
u
u
r
u
u
F
.
19
2.
Ещё
один
из
вариантов
выбора
штрафной
функции
.
Требуется
минимизировать
функцию
2
2
2
1
2
1
)
2
(
)
3
(
)
,
(
u
u
u
u
J
,
при
ограничении
0
4
2
1
u
u
.
Прибавим
к
целевой
функции
значение
)
,
(
2
1
2
u
u
rg
,
тогда
получим
функцию
без
ограничений
2
2
1
2
2
2
1
2
1
)
4
(
)
2
(
)
3
(
)
,
,
(
u
u
r
u
u
r
u
u
F
Таким
образом
,
методы
штрафных
функций
определяются
как
выбором
вида
штрафа
,
так
и
выбором
параметра
r
.
3.
Рассмотрим
теперь
один
из
параметрических
методов
(
метод
внутренней
точки
).
Пусть
требуется
минимизировать
функцию
2
2
2
1
2
1
2
1
9
6
)
,
(
u
u
u
u
u
u
J
при
ограничениях
.
2
,
1
,
0
i
u
i
Исходная
точка
поиска
)
5
,
0
;
1
(
0
A
.
1.
Строим
функцию
без
ограничений
,
используя
штраф
2
1
)
(
1
)
(
)
,
(
i
i
u
g
r
u
J
r
u
P
,
)
/
1
/
1
(
9
6
)
,
,
(
2
1
2
2
2
1
2
1
2
1
u
u
r
u
u
u
u
r
u
u
P
2.
Пусть
1
0
r
.
Найдем
минимум
функции
)
,
,
(
0
2
1
r
u
u
P
любым
методом
безусловной
оптимизации
,
например
,
градиентным
7
1
6
1
2
)
/
1
6
2
(
0
0
2
1
1
1
A
A
u
u
u
P
;
6
25
,
0
/
1
9
5
,
0
2
)
/
1
9
2
(
0
0
2
2
2
2
A
A
u
u
u
P
;
05
,
0
0
0
1
2
2
2
2
1
2
0
u
P
u
P
;
20
55
,
0
7
05
,
0
1
0
1
0
0
1
1
1
A
u
P
u
u
;
2
,
0
6
05
,
0
5
,
0
0
2
0
0
2
1
2
A
u
P
u
u
;
018
,
0
;
6
,
15
;
7
,
3
1
2
1
0
0
A
A
u
P
u
P
;
483
,
0
1
1
1
1
1
2
1
A
u
P
u
u
;
48
,
0
1
2
1
1
2
2
2
A
u
P
u
u
;
)
48
,
0
;
483
,
0
(
1
A
.
И
так
далее
.
Получим
16
,
11
)
(
);
325
,
0
;
38
,
0
(
)
(
0
0
r
P
r
A
Опт
Опт
.
3.
Уменьшаем
r
.
Полагаем
1
,
/
0
1
C
C
r
r
.
Пусть
10
C
.
Минимизируем
)
,
,
(
1
2
1
r
u
u
P
тем
же
градиентным
методом
,
теперь
за
исходную
точку
принимаем
)
325
,
0
;
38
,
0
(
0
A
.
07
,
6
)
/
1
,
0
6
2
(
0
0
2
1
1
1
A
A
u
u
u
P
;
7
,
8
)
/
1
,
0
9
2
(
0
0
2
2
2
2
A
A
u
u
u
P
;
02
,
0
0
;
26
,
0
07
,
6
02
,
0
38
,
0
0
1
0
0
1
1
1
A
u
P
u
u
;
26
,
0
07
,
6
02
,
0
38
,
0
0
2
0
0
2
1
2
A
u
P
u
u
;
И
так
далее
.
Получим
47
,
3
)
(
);
106
,
0
;
127
,
0
(
)
(
1
1
r
P
r
A
Опт
Опт
.
4.
Вновь
уменьшаем
r
.
Полагаем
C
r
r
/
1
2
и
т
.
д
.