Системы линейных неравенств. Зоркальцев В.И - 93 стр.

UptoLike

ВУЗ: 

ИГУ | Иркутск

Составители: 

Рубрика: 

93
Минимизация суммы квадратов невязок альтернативной
системы
. Рассмотрим задачу минимизации выпуклой дифференцируемой
функции при ограничениях-неравенствах на переменные
2
2
( ) ( ( )) min, 0uAu u u
ϕδ
Τ
≡
+→≥
,
где
ubu
Τ
−= 1)(
δ
.
Обозначим
u решение данной задачи. Если 0)
~
(
=
u
ϕ
, то вектор u
является решением альтернативной системы (24). Исходная система (23)
не имеет решений.
Введем дополнительные переменные, составляющие вектор
n
Ry
∈
.
Задача (25) представляется в виде
0,0 ≥=−
Τ
uuAy
, (30)
min)))(((
2
1
22
→δ+
∑
uy
j
. (31)
По теореме 5.4 эта задача равносильна следующей системе линейных
неравенств
b
Ay
δ
≥ , (32)
0,0 ≥=−
Τ
uuAy , (33)
)(u
=
. (34)
Решение задач (30), (31) и (32) – (34) составляют u
~
, )
~
(
~
u
δδ
= и некоторый
вектор y
~
, являющийся также вектором множителей Лагранжа
ограничений-равенств в задаче (30), (31).
Система (30) – (32) представляет также по теореме 5.4 необходимые
и достаточные условия задачи оптимизации:
0
≤
−
−
b
Ay
, (35)
min)(
2
1
22
→−+
∑
δδ
j
u . (36)
Вектор u состоит из множителей Лагранжа ограничений данной задачи.
Для оптимального решения
∑
=+
δδ
~
~
22
j
u . (37)
Если и только если 0
~
=y , то 0
~
=
δ
. В этом и только этом случае вектор u
является решением альтернативной системы. 
     Минимизация суммы квадратов невязок альтернативной
системы. Рассмотрим задачу минимизации выпуклой дифференцируемой
функции при ограничениях-неравенствах на переменные
                                          2
                          ϕ (u ) ≡ AΤu + (δ (u )) 2 → min, u ≥ 0 ,
где
                              δ (u ) = 1 − b Τ u .
     Обозначим u решение данной задачи. Если ϕ (u~ ) = 0 , то вектор u
является решением альтернативной системы (24). Исходная система (23)
не имеет решений.
     Введем дополнительные переменные, составляющие вектор y ∈ R n .
Задача (25) представляется в виде
                               y − AΤu = 0, u ≥ 0 ,                      (30)
                              1
                                (∑ y 2j + (δ(u )) 2 ) → min .            (31)
                              2
По теореме 5.4 эта задача равносильна следующей системе линейных
неравенств
                              Ay ≥ δb ,                                  (32)
                               y − AΤu = 0, u ≥ 0 ,                      (33)
                              δ = δ (u ) .                               (34)
                                                       ~
Решение задач (30), (31) и (32) – (34) составляют u~ , δ = δ (u~ ) и некоторый
вектор ~ y , являющийся также вектором множителей Лагранжа
ограничений-равенств в задаче (30), (31).
      Система (30) – (32) представляет также по теореме 5.4 необходимые
и достаточные условия задачи оптимизации:
                              − Ay − δb ≤ 0 ,                            (35)
                              1
                                (∑ u 2j + δ 2 ) − δ → min .              (36)
                              2
Вектор u состоит из множителей Лагранжа ограничений данной задачи.
Для оптимального решения
                                  ~     ~
                         ∑ u 2j + δ 2 = δ .                  (37)
                              ~
Если и только если ~
                   y = 0 , то δ = 0 . В этом и только этом случае вектор u
является решением альтернативной системы.


                                        93

Страницы