close

Вход

Забыли?

вход по аккаунту

?

Презентация

код для вставкиСкачать
Методы вычислительного
эксперимента
Оптимизация
5. Нелинейное программирование.
5.1. Постановка задачи
Bx;
T
x ( x1 , x 2 ,..., x n ) ;
T
( 1 , 2 ,..., m ) ;
*
x D;
( , ,..., ) ;
*
*
*
x x : min F *
1
*
2
*
m
T
F F ( ). Если B - детерминир ованный оператор,
F F ( x ).
5. Нелинейное программирование.
5.2. Однокритериальные задачи
K
K K (x, f )
f
ср
f min f f max
f
5. Нелинейное программирование.
5.2. Однокритериальные задачи
*
*
x x : f f0 , K ( x, f0 ) K
*
f min f f max
f max
F f min
*
F K ( x, f0 ) K
2
*
K ( x , f ) K ( f ) df
2
5. Нелинейное программирование.
5.2. Однокритериальные задачи
K
f ср
f
5. Нелинейное программирование.
5.2. Однокритериальные задачи
F max
f min f f max
*
K (x, f ) K ( f )
2
min F ( x ), x ( x1 , x 2 ,..., x n )
xD
i
i
x x i x ; i 1, 2 ,..., n
j
g k 0;
j j ; j 1, 2 ,..., m
k 1, 2 ,..., 2 n 2 m
g 0
5. Нелинейное программирование.
5.2. Однокритериальные задачи
g g ( x ) g ( x , ( x ))
j
g j j ; j 1, 2 ,..., m ;
g m j j
j ; j 1, 2 ,..., m
j
g 2 m j x j x ; j 1, 2 ,..., n
j
g 2 m n j x x j ; j 1, 2 ,..., n
5. Нелинейное программирование.
5.2. Однокритериальные задачи
T
T
B x ; x ( x1 , x 2 ,..., x n ) ; ( 1 , 2 ,..., m ) ;
x D;
*
*
x x : min F ( x )
g(x) 0
T
x ( x1 , x 2 ,..., x n ) ;
T
g ( g 1 , g 2 ,..., g p ) ;
5. Нелинейное программирование.
5.3. Многокритериальные задачи
T
T
B x ; x ( x1 , x 2 ,..., x n ) ; ( 1 , 2 ,..., m ) ;
x D;
*
*
x x : F1 ( 1 x )
1 x 1
F
(
x
)
x
2
2
2
2
5. Нелинейное программирование.
5.3. Многокритериальные задачи
F
F1
F2
область
компромиссов
области согласия
x
5. Нелинейное программирование.
5.3. Многокритериальные задачи
F2
область
решений,
оптимальных
по Парето
F1
5. Нелинейное программирование.
5.3. Многокритериальные задачи
Поиск оптимального решения
Определить область компромиссов
Задать критерий, позволяющий выбрать
из множества эффективных точек ту,
которую мы будем считать оптимальной.
Найти решение, оптимальное в
соответствии с заданным критерием
5. Нелинейное программирование.
5.3. Многокритериальные задачи
( x )
F ( x ) F1 ( x ), F2 ( x ), x ' ' ( x )
U ( ( x )) U ( x )
x" " ( x" )
' " U ( x ' ) U ( x" )
T
5. Нелинейное программирование.
5.3. Многокритериальные задачи
U (x) m
jFj (x)
j 1
U ( x ) max j F j ( x )
j
U ( x ) Fl ( x );
j 1, 2 ... m ; j l
Fj (x) Fj ,
5. Нелинейное программирование.
5.3. Многокритериальные задачи
min F ( x )
g(x) 0
T
x ( x1 , x 2 ,..., x n ) ;
T
g ( g 1 , g 2 ,..., g p ) ;
5. Нелинейное программирование.
5.4. Классификация задач
По числу варьируемых параметров
По наличию (отсутствию ограничений)
Задачи условной минимизации
Задачи безусловной минимизациии
В зависимости от количества экстремумов в области
допустимых значений вектора варьируемых параметров
Задачи одномерной минимизации
Задачи многомерной минимизации
Задачи минимизации одноэкстремальной (унимодальной)
целевой функции
Задачи минимизации многоэкстремальной целевой функции
В зависимости от структуры целевой функции и
ограничений
Задачи линейного программирования
Задачи квадратичного программирования, выпуклого
программирования и т.д.
5. Нелинейное программирование.
5.4. Классификация задач
Локальный и глобальный минимум в
многоэкстремальных задачах
Локальный минимум:
*
x , если r 0 , F x F x x :
Глобальный минимум:
*
x , если
F x F x x :
xD
xx r
5. Нелинейное программирование.
5.4. Классификация задач
x1
D
x2
5. Нелинейное программирование.
5.5. Условия оптимальности для некоторых классов задач
Безусловная минимизация функций одной
переменной
min F ( x );
x R
dF ( x )
0
dx
2
d F (x) 0
2
dx
5. Нелинейное программирование.
5.5. Условия оптимальности для некоторых классов задач
Безусловная минимизация функций n переменных
min F ( x );
n
xR
F ( x )
0
x
i
2
F
(
x
)
H П.О.
ij
xi x j
5. Нелинейное программирование.
5.5. Условия оптимальности для некоторых классов задач
Условная минимизация функций n переменных:
m
условия Куна-Таккера
min F ( x );
g(x) 0
L F (x) L ( x )
0
;
x
i
g j 0;
j
g j 0;
j 0 ;
jg j (x)
j 1
i 1, 2 ,..., n ;
j 1, 2 ,..., m ;
5. Нелинейное программирование.
5.6. Безусловная минимизация функций одной переменной.
Метод Ньютона
min F ( x ); x R
dF ( x )
( x) 0
dx
F
0
x
x
x k 1
xk
x
5. Нелинейное программирование.
5.6. Безусловная минимизация функций одной переменной.
Метод Ньютона
F
0
x
x
x k 1
tg d ( xk )
dx
( xk )
x k x k 1
xk
x
x k 1 x k ( xk )
( x k )
5. Нелинейное программирование.
5.6. Безусловная минимизация функций одной переменной.
Метод Ньютона
x 0 , задать , 0, положить
1 . Выбрать
k 0
3 . : 2 3 . Пока | F ( x k ) | , выполнить
x k 1 : x k 4 . Положить
x xk M
2m
F ( x k )
F ( x k )
; : | x k 1 x k |
x x k 1 . Завершить
*
( x k x k 1 )
2
M max ' ( x )
x[ a , b ]
работу .
m 1 min ' ( x )
x[ a , b ]
5. Нелинейное программирование.
5.7. Безусловная минимизация функций одной переменной.
Метод золотого сечения
x1 x 3 x 2 ;
F0
F ( x 3 ) F ( x1 );
F ( x 3 ) F ( x 2 );
x1
x3
x2
x
5. Нелинейное программирование.
5.7. Безусловная минимизация функций одной переменной.
Метод золотого сечения
F
x1 x 3 x 2 ;
F ( x 3 ) F ( x1 );
F ( x 3 ) F ( x 2 );
x1
x3
x2
x
5. Нелинейное программирование.
5.7. Безусловная минимизация функций одной переменной.
Метод золотого сечения
Алгоритм локализации минимума
1. Выбрать произвольное xa, h > 0, 1 < < 2.
2. xc = xa + h
3. Если F(xc) > F(xa) то h = – h, xc = xa + h
4. h = h
5. xb = xa + h
6. Если F(xb) < F(xc), то xc = xb и перейти к шагу 4.
7. x3 = xc.
8. Если xa < xb, то x1 = xa, x2 = xb, иначе x1 = xb, x2 = xa
5. Нелинейное программирование.
5.7. Безусловная минимизация функций одной переменной.
Метод золотого сечения
x 2 x1
x 3 x1
5. Нелинейное программирование.
5.7. Безусловная минимизация функций одной переменной.
Метод золотого сечения
Алгоритм метода золотого сечения
1. Взять точки x1, x2, x3, такие что
x1 < x3 < x2, F (x3) < F(x1) и F(x3) < F(x2).
Задать точность нахождения минимума .
2. Положить δ=2
3. Пока δ> выполнить
3.1. Выбрать следующую точку симметрично x3
относительно середины интервала (x1, x2):
x4 – x1 = x2 – x3,
x4 = x1 + x2 – x3.
5. Нелинейное программирование.
5.7. Безусловная минимизация функций одной переменной.
Метод золотого сечения
Алгоритм метода золотого сечения
F0
x1 < x4 < x3 < x2
F(x4) < F(x3) F(x4) < F(x1)
x1
x4
x3
x2
x
5. Нелинейное программирование.
5.7. Безусловная минимизация функций одной переменной.
Метод золотого сечения
Алгоритм метода золотого сечения
F0
x1 < x4 < x3 < x2
F(x4) > F(x3) F(x3) < F(x2)
x1
x4
x3
x2
x
5. Нелинейное программирование.
5.7. Безусловная минимизация функций одной переменной.
Метод золотого сечения
Алгоритм метода золотого сечения
x 1 < x3 < x4 < x2
F0
F(x4) > F(x3) F(x3) < F(x1)
x1
x3
x4
x2
x
5. Нелинейное программирование.
5.7. Безусловная минимизация функций одной переменной.
Метод золотого сечения
Алгоритм метода золотого сечения
x1 < x3 < x4 < x2
F0
F(x4) < F(x3) F(x4) < F(x2)
x1
x3
x4
x2
x
5. Нелинейное программирование.
5.7. Безусловная минимизация функций одной переменной.
Метод золотого сечения
Алгоритм метода золотого сечения
3.2. Если x4 < x3, то
если F(x4) < F(x3), то x2 = x3, x3 = x4
иначе x1 = x4
иначе
если F(x4) < F(x3), то x1 = x3, x3 = x4
иначе x2 = x4
3.3. δ =x2 – x1.
4. x = (x2 + x1)/2.
5. Завершить работу.
5. Нелинейное программирование.
5.7. Безусловная минимизация функций одной переменной.
Метод золотого сечения
Алгоритм метода золотого сечения
x 2 x1
x 3 x1
x 3 x1
x 2 x3
x 2 x1
x 2 x1 x 2 x1
1
1
1 0 1, 618 ...
2
5. Нелинейное программирование.
5.8. Безусловная минимизация функций одной переменной.
Метод квадратичной аппроксимации
F
0
x * x x1 x2 x3
x
5. Нелинейное программирование.
5.8. Безусловная минимизация функций одной переменной.
Метод квадратичной аппроксимации
ax bx 1 c F ( x1 )
2
0
ax 2 bx 2 c F ( x 2 )
2
0
ax
bx
c
F
(
x
)
3
3
3
2
1
~
x b / 2a
0
5. Нелинейное программирование.
5.8. Безусловная минимизация функций одной переменной.
Метод квадратичной аппроксимации
F
0
x1
x*
x x3
x2
x
5. Нелинейное программирование.
5.8. Безусловная минимизация функций одной переменной.
Метод квадратичной аппроксимации
1 . Выбрать
x1 , x 2 , x 3 , локализующ
ие min F ( x ), задать 2 . 2
3 . Пока выполнить
Найти a , b , c ;
Положить
x4 b / 2a;
Положить
M , j 1;
Для всех
j от 1 до 3 выполнить
Найти k : F ( x k ) F ( x i ), i 1 .. 4 , i k , i M ;
M M k;
Если
x i , i 1 .. 4 , i k локализуют
Исключить
min F ( x ), выйти из цикла ;
x k , перенумеро вать оставшиеся
x i от 1 до 3;
| x1 x 2 |
4 . Положить
x ( x1 x 2 ) / 2 . Завершить
*
работу .
5. Нелинейное программирование.
5.9. Безусловная минимизация функций n переменных.
Метод покоординатного спуска
x2
e2
x0
e1
x1
5. Нелинейное программирование.
5.9. Безусловная минимизация функций n переменных.
Метод покоординатного спуска
x 0 , задать 1 . Выбрать
2 . x b x 0 ; : 2 ;
3 . Пока выполнить
Для всех i от 1 до n выполнить
x s xb ;
*
Найти : min F ( x s e i );
Положить x s x s e i ;
Положить | x b x s |; x b x s
* 4 . Положить x x s Завершить
работу .
5. Нелинейное программирование.
5.9. Безусловная минимизация функций n переменных.
Метод покоординатного спуска
x2
x1
5. Нелинейное программирование.
5.9. Безусловная минимизация функций n переменных.
Метод покоординатного спуска
x2
x1
5. Нелинейное программирование.
5.10. Безусловная минимизация функций n переменных.
Метод локальных вариаций
x2
e2
x0
e1
h
x1
5. Нелинейное программирование.
5.10. Безусловная минимизация функций n переменных.
Метод локальных вариаций
1 . Выбрать x 0 , задать h , ;
2 . x b x 0 ; : | h |;
3 . Пока выполнить
Покоордина тный поиск
из x b с шагом h и результато м x s
Если x s x b , то x b x s
иначе h h / 10 ; / 10 ;
* 4 . Положить x x s ; Завершить
работу .
5. Нелинейное программирование.
5.10. Безусловная минимизация функций n переменных.
Метод локальных вариаций
Покоордина
1 . x s xb ;
тный поиск из x b x s c шагом h
2 . Для всех i от 1 до n с шагом
x r x s hi e i ;
Если F( x r ) F( x s ), т,
Если F( x r ) F( x s ), т,
4 . Возврат из
ппроцедур
1 выполнить
x r x s hi e i ;
xs xr ;
5. Нелинейное программирование.
5.11. Безусловная минимизация функций n переменных.
Метод Хука-Дживса
1 . Выбрать x 0 , задать h , ;
2 . x b x 0 ; : | h |;
из x b с шагом h x s
3 . Покоордина тный поиск
4. Если x s x b , то h h / 10 ; / 10 ;
* 5. Если , то x x s ; Завершить
работу ;
Иначе перейти к шагу 3;
6. x p x b ( x s x b ); ~ 2,3 - 2,5; x b x s
7. Покоордина тный поиск из x p с шагом h x q ;
8. Если F ( x q ) F ( x s ), то x s x q , перейти к шагу 6
иначе перейти к шагу 3 .
5. Нелинейное программирование.
5.11. Безусловная минимизация функций n переменных.
Метод Хука-Дживса
xb
x2
xs
xp
xq
x1
5. Нелинейное программирование.
5.12. Безусловная минимизация функций n переменных.
Симплекс-метод
x2
2
6
4
5
1
3
x1
5. Нелинейное программирование.
5.13. Безусловная минимизация функций n переменных.
Метод наискорейшего спуска
x 0 , задать , ;
1 . Выбрать
2 . xb x 0 ; 2 ;
3 . Пока выполнить
4. g F ( x ) x x ; h g ; | g |;
b
*
5. min F ( x b h ) ;
*
6. x s x b h ;
7. x b x s ;
* 8. x x s ; Завершить
работу ;
5. Нелинейное программирование.
5.13. Безусловная минимизация функций n переменных.
Метод наискорейшего спуска
x2
x0 g
x1
5. Нелинейное программирование.
5.14. Безусловная минимизация функций n переменных.
Метод градиентного спуска с ускорением
1 . Выбрать
x 0 , задать , ; x b x 0 ; 2 ;
2 . Пока выполнить
4. g F ( x ) x x ; h g ;
b
* *
5. min F ( x b h ) ; x s x b h ;
7. g F ( x ) x x ; h g ;
s
* *
8. min F ( x s h ) ; x p x s h ;
9. h x p x b ; max{| g |, | h |};
* *
10. min F ( x p h ) ; x b x p h ;
* 11. x x b ; Завершить
работу ;
5. Нелинейное программирование.
5.14. Безусловная минимизация функций n переменных.
Метод градиентного спуска с ускорением
x2
xp
e2
xs
xb
e1
x1
5. Нелинейное программирование.
5.15. Безусловная минимизация функций n переменных.
Развитие градиентных методов
Ax b
T
( A x b )( A x b ) F ( x )
F (x) ax F
2
G ij xi x j
1
2
T x Gx
1 h G g
5. Нелинейное программирование.
5.15. Безусловная минимизация функций n переменных.
Развитие градиентных методов
F
2
H ij 0
xi x j
T x1 H x 2 0
1 h H g
Документ
Категория
Презентации по информатике
Просмотров
47
Размер файла
840 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа