lecture-khlebnikov
.pdf
'
Допустимая область
• Допустимая область äëÿ LMI:
Dfeas = {x Rℓ : F (x) 4 0}
Dfeas выпуклая область (возможно неограниченная, возможно пустая)
2.5
2
1.5
1
• Задача допустимости (feasibility)
0.5
отыскание некоторой точки x Dfeas
0
−0.5
−2 |
−1.5 |
−1 |
−0.5 |
0 |
0.5 |
1 |
1.5 |
2 |
2.5 |
&
11/29
'
Примеры допустимых областей
Простейший случай: |
|
|
|
|
(Dfeas R2) |
|
|
|
|
|
|
|
|
|||||||
|
0 |
−1 |
|
|
ℓ = 2, n = 2 |
|
|
{| |
|
|
|
|
} |
|||||||
|
|
|
0 |
0 |
|
0 |
1 |
|
D |
|
|
| |
|
|
||||||
F1 |
(x) = −1 |
0 |
+ x1 |
0 |
0 + x2 |
−1 |
0 |
4 |
0 = |
|
feas = |
|
x2 |
|
6 |
1 |
|
|||
|
0 |
−1 |
|
0 |
1 |
1 |
0 |
|
|
D |
|
{ |
|
|
|
|
|
} |
||
F2 |
(x) = −1 |
0 +x1 |
−1 |
0 +x2 |
0 |
1 |
4 0 = |
feas = |
x12 +x22 |
6 |
1 |
|||||||||
F3 |
(x) = 0 |
−1 |
+ x1 |
1 |
0 + x2 |
0 |
0 |
4 0 |
|
|
|
|
|
|
|
|
|
|||
|
−1 |
0 |
|
|
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
= Dfeas внутренность отрицательной ветви гиперболы x1x2 = 1 |
|
|
|
|||||||||||||||||
& |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12/29
'
Задача полуопределенного программирования
Задача полуопределенного программирования (Semi-De nite Programming, SDP):
c x −→ min при ограничении F (x) 4 0
Сведение задачи допустимости к SDP:
LMI F (x) 4 0 разрешимо |
задача SDP |
γ −→ min |
при ограничении F (x) 4 γI |
относительно переменных γ R è x Rℓ имеет решение γb, xb такое, что
γb 6 0
Ïðè ýòîì xb является допустимой точкой
&
13/29
' |
|
|
|
|
|
Лемма Шура |
|
|
|
|
|
|
|
||
Рассмотрим блочную матрицу |
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
M = M11 |
M12 |
|
|
|
|
|
|||
ãäå M11 = M11, |
M22 = M22, |
M12 |
M22 |
|
|
|
|
|
|
||||||
M12 матрицы соответствующих размерностей |
|||||||||||||||
Лемма Шура. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
M |
|
0 |
|
M |
0, M |
|
M |
12 |
M−1M |
|
0 |
|
||
|
|
|
22 |
|
11 − |
|
22 12 |
|
|
||||||
Матрица M |
11 − |
M |
|
M−1M |
называется дополнением по Шуру к блоку |
M |
|||||||||
|
|
12 |
22 12 |
|
|
|
|
|
|
|
|
|
22 |
||
Лемма Шура для нестрогого неравенства.
Пусть M22 = M22 невырожденная матрица. Тогда
M |
4 |
0 |
|
M |
0, M |
M |
12 |
M−1M |
4 |
0 |
& |
|
22 |
11 − |
|
22 12 |
|
||||
|
|
|
|
|
|
|
|
|
|
14/29
' |
|
|
Сведение некоторых задач к LMI |
|
|
|
|
|
||||||||||||||
Пусть |
|
|
|
|
|
|
|
F11(x) |
|
F12(x) |
|
|
|
|
|
|
||||||
|
|
|
|
F (x) = |
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
F12(x) |
|
F22(x) |
|
|
|
|
|
|
||||||
ãäå Fij(x) аффинны по x = (x1, . . . , xℓ) , |
|
F11(x) = F |
(x), |
F22(x) = F |
(x) |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
|
|
|
|
22 |
|
F (x) |
|
0 |
|
F |
22 |
(x) |
|
0, F |
11 |
(x) |
− |
F |
12 |
(x)F −1(x)F |
(x) |
|
0 |
|
||||
|
|
|
|
|
|
|
|
22 |
|
12 |
|
|
|
|||||||||
Поскольку F (x) 0 выпукло, то и второе неравенство выпукло!
Пример. Матричное неравенство Риккати относительно матрицы P = P :
A P + P A + P BR−1B P + Q |
|
0, R |
|
0 |
|||
|
|
|
|
|
|
||
По лемме Шура (в обратную сторону ) оно эквивалентно LMI |
|||||||
A P + P A + Q P B |
|
0 |
|
|
|||
|
B P |
−R |
|
|
|
||
&= множество решений неравенства Риккати выпукло (что неочевидно!)
15/29
'
Сведение некоторых задач к LMI (продолжение)
• Ограничение на норму. Пусть F (x) аффинная матричная функция от x.
Рассмотрим нелинейное неравенство |
|
|
|
|
|
|||||
|
|
|
|
|
F (x) 2 6 1 |
|
|
|
||
|
|
F (x) |
2 6 1 |
|
F (x)F (x) 4 I |
|
I |
F (x) |
< 0 |
|
|
|
|
|
|
F (x) |
I |
|
|||
|
• Взаимно-обратные матрицы. Пусть F (x), G(x) 0 симметричные аф- |
|||||||||
финные матричные функции от x. |
|
|
|
|
|
|||||
Неравенство |
|
|
F (x) 4 G−1(x) |
|
|
|
||||
|
|
|
|
|
|
|
|
|||
по лемме Шура эквивалентно LMI |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F (x) |
I |
4 0 |
|
|
|
& |
|
|
|
I |
G(x) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
16/29
'
Матричное описание эллипсоидов
Эллипсоид с центром в точке xc и матрицей P : |
|
|
|
||
E(xc, P ) = {x Rn : |
(x − xc) P −1(x − xc) 6 1}, P 0 |
||||
LMI-форма записи: |
(x − xc) < 0, |
|
|
|
|
1 |
P |
|
0 |
||
x − xc |
P |
|
|
|
|
Критерии минимальности эллипсоида:
• Сумма квадратов полуосей: tr P (след матрицы линейная функция)
√
• Большая полуось: P 2 (2-норма матрицы сводится к линейной)
√
• Объем: cl det P (нелинейна, однако − log det X выпукла для X 0)
&
17/29
'
Вложенность эллипсоидов
• Пусть
E(0, P ) =
Условие
гарантирует, что
• Обобщение:
E(0, P1) =
E(0, P2) =
Условие
эквивалентно вложенности
{x Rn : x P −1x 6 1}, P 0
P < δI
B(0, δ1/2) E(0, P )
n |
|
1 |
|
{x Rn |
: |
x P1−1x 6 1}, P1 |
0 |
{x R |
: |
x P2− x 6 1}, P2 0 |
|
P1 4 P2
& |
E(0, P1) E(0, P2) |
|
18/29
'
Задача 1
Найти эллипсоид, минимальный по критерию следа, содержащий точки
x1, . . . , xℓ Rn
Приходим к задаче SDP
tr P −→ min
при ограничениях |
|
(xi − xc) |
|
|
|
1 |
< 0, i = 1, . . . , ℓ |
||
xi − xc |
P |
|
|
|
по матричной переменной P = P Rn×n и векторной переменной xc Rn.
• Если центр эллипсоида фиксирован (например начало координат), полагаем
xc = const
&
19/29
'
Задача 2
Найти эллипсоид, минимальный по критерию объема, содержащий точки
|
|
x1, . . . , xℓ Rn |
|
|
||
1. Центр xc эллипсоида фиксирован. |
|
|
|
|
||
Рассмотрим эллипсоид |
|
|
|
|
||
|
|
E = {x Rn : (x − xc) Q(x − xc) 6 1}, |
Q 0 |
|||
С учетом Q = P −1 имеем log det P = |
− |
log det Q = приходим к задаче |
||||
выпуклой оптимизации: |
|
|
|
|||
|
|
|
|
|||
|
|
− log det Q −→ min |
|
|
||
при линейных ограничениях |
|
|
|
|
||
|
|
(xi − xc) Q(xi − xc) 6 1, i = 1, . . . , ℓ, |
Q 0 |
|||
относительно матричной переменной Q = Q Rn×n. |
b |
|||||
• |
|
b |
|
|
b |
|
|
Решение Q определяет матрицу эллипсоида |
P = Q−1 |
||||
& |
|
|
|
|
|
|
20/29