Задача нелинейного программирования. Условная оптимизация. Метод проекции градиента
Метод проекции градиента
Шаг 1. Выбор направления
Шаг 1. Определение длины шага
Шаг 1. Определение длины шага
Шаг 1. Координаты новой точки
Шаг 2. Выбор направления
Шаг 2. Выбор направления
Шаг 2. Определение длины шага
Шаг 2. Координаты новой точки
Шаг 3. Выбор направления
Шаг 3. Выбор направления
Шаг 3. Проверка останова
318.50K
Категория: ПрограммированиеПрограммирование

адача нелинейного программирования. Условная оптимизация. Метод проекции градиента

1. Задача нелинейного программирования. Условная оптимизация. Метод проекции градиента

2. Метод проекции градиента

max f X x x 2 x1 4 x2
max f X
x1 2 x2 2
A0 X b0
x1 x2 4
1 2
2
x 0
1 1
4
1
b0
x2 0
A0
1 0
0
0 1
0
2 x1 2
2 0
f X
H
0 2
2 x2 4
2
1
2
2

3. Шаг 1. Выбор направления

0
X0
0
2
4
A0 X 0 b0
0
Активные ограничения
0
1 0
A
0 1
1 0 2 2 <0
A f X 0
0 1 4 4 <0
2
0
K f X 0
4
Допустимо
градиентное
направление

4. Шаг 1. Определение длины шага

A0 K
0
1 2
6
1 1 2 6
1 0 4 2
0 1
4
Ограничения, которые
нарушаются при
движении в выбранном
направлении
Длина шага до нарушаемых ограничений:
0
bk ak X i
2 1 2
tk
i
0 1
0 b1 a1 X 0
ak K
t1
0
i
t2
0
2
a1K
1 2
0
4
4 1 1
0 2
b2 a2 X 0
0
3
2
a2 K
1 1
4
3

5. Шаг 1. Определение длины шага

Максимально возможная длина шага:
i
t*
0
t*
f Xi K
T
i
H Xi K
2
2 4
4
1
2 0 2 2
2 4
4
0
2
K
i T
i
Итоговая длина шага:
t
0
0 0 0
min t* , t1 , t2
1 1 2 1
min , ,
2 3 3 3

6. Шаг 1. Координаты новой точки

0
X1 X 0 t K
0
0 1 2 2 / 3
0 3 4 4 / 3

7.

3
2.5
2
1.5
1
0.5
0
-0.5
-1
-1
0
1
2
3
4
5

8. Шаг 2. Выбор направления

2 x1 2 2 / 3 2 / 3
2 / 3
f X 1
X1
2
x
4
4
/
3
4
/
3
2
4 / 3
1 2
2 0 Активные
1 1 2 / 3 4 2 ограничения
A0 X 1 b0
1 0 4 / 3 0 2 / 3
A 1 2
0 1
0 4 / 3
2 / 3
A f X 1 1 2
2
4 / 3
>0
Не допустимо
градиентное
направление

9. Шаг 2. Выбор направления

Оператор проекции:
P E A
T
AA
T
1
A
1 0 1
1
P
1 2
0 1 2
2
K
1
1
4/ 5 2/ 5
1 2
2/
5
1/
5
4 / 5 2 / 5 2 / 3 16 /15
P f X 1
2
/
5
1/
5
4
/
3
8/15

10. Шаг 2. Определение длины шага

A0 K
1
1 2
0
1 1 16 /15 24 /15 Нарушаемые
ограничения
1 0 8/15 16 /15
0 1
8/15
Длина шага
до нарушаемых
ограничений:
1
t2
Максимально возможная
длина шага:
2 / 3
4 1 1
4
/
3
5
16 /15 4
1 1
8/15
1
t
1
t*
1 1
min t* , t2
1
2
1 5 1
min ,
2 4 2

11. Шаг 2. Координаты новой точки

1
X 2 X1 t K
1
2 / 3 1 16 /15 6 / 5
4 / 3 2 8/15 8/ 5

12.

3
2.5
2
1.5
1
0.5
0
-0.5
-1
-1
0
1
2
3
4
5

13. Шаг 3. Выбор направления

2 x1 2 6 / 5 2 / 5
6 / 5
f X 2
X2
2
x
4
8/
5
4
/
5
2
8/ 5
1 2
2 0 Активные
1 1 6 / 5 4 6 / 5 ограничения
A0 X 2 b0
1 0 8/ 5 0 6 / 5
A 1 2
0 1
0 8/ 5
2 / 5
A f X 2 1 2
2 >0
4/5
Не допустимо
градиентное
направление

14. Шаг 3. Выбор направления

Оператор проекции:
1 0 1
1
P
1 2
0 1 2
2
K
2
1
4/ 5 2/ 5
1 2
2/
5
1/
5
4 / 5 2 / 5 2 / 5 0
P f X 2
2 / 5 1/ 5 4 / 5 0
Подозрение на
оптимальность

15. Шаг 3. Проверка останова

AA
T
1
A f X 2
1
1 2
2
1
2 / 5
2
<0
1 2
5
4/5
Точка
оптимальна
6 / 5
X
8/ 5
*

16.

3
2.5
2
1.5
1
0.5
0
-0.5
-1
-1
0
1
2
3
4
5
English     Русский Правила