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

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

88
Обозначим решение
x
. Если вектор невязок для оптимального решения
задачи (4)
x
A
bu
−
=
(5)
ненулевой, то исходная система (1) не имеет решения. Если
0=u , то
очевидно
x
есть решение системы (1).
Из условия оптимальности
0)( =∇ xf
следует, что вектор
x
может быть получен как решение системы
уравнений
b
A
A
x
A
Τ
Τ
=
(6)
с симметричной, неотрицательно определенной матрицей
A
A
Τ
.
Задачу (4), введя вектор дополнительных переменных
m
R
u ∈ , можем
представить в виде
∑
→ min
2
1
2
i
u , (7)
bu
Ax
=
+
. (8)
Ее решение составляют векторы
x
и u .
Воспользуемся теоремой 3а главы 3 для задачи (7), (8). Вектор
множителей Лагранжа ограничений (8) совпадает с вектором
u . Получаем,
что векторы
x
, u будут оптимальными решениями задачи (7), (8) в том и
только том случае, если они составляют решение системы линейных
уравнений
bu
Ax
=
+
, (9)
0
=
Τ
u
A
. (10)
Здесь ограничение (9) – условие допустимости решения для задачи (7), (8),
ограничение (10) – дополнительное условие, обеспечивающее
оптимальность.
Систему уравнений (9), (10) можно также рассматривать как
необходимое и достаточное условие оптимальности по той же теореме 3а
другой задачи оптимизации, в которой ограничение (10) является условием
допустимости:
min
2
1
2
→−
∑
Τ
ubu
i
, (11)
0
=
Τ
u
A
. (12)
Оптимальным решением данной задачи будет вектор
u (решение у этой 
Обозначим решение x . Если вектор невязок для оптимального решения
задачи (4)
                            u = b − Ax                              (5)
ненулевой, то исходная система (1) не имеет решения. Если u = 0 , то
очевидно x есть решение системы (1).
     Из условия оптимальности
                            ∇f ( x ) = 0
следует, что вектор x может быть получен как решение системы
уравнений
                            AΤ Ax = AΤb                             (6)
с симметричной, неотрицательно определенной матрицей AΤ A .
     Задачу (4), введя вектор дополнительных переменных u ∈ R m , можем
представить в виде
                            1
                            2
                              ∑ ui2 → min ,                         (7)

                            Ax + u = b .                            (8)
Ее решение составляют векторы x и u .
      Воспользуемся теоремой 3а главы 3 для задачи (7), (8). Вектор
множителей Лагранжа ограничений (8) совпадает с вектором u . Получаем,
что векторы x , u будут оптимальными решениями задачи (7), (8) в том и
только том случае, если они составляют решение системы линейных
уравнений
                            Ax + u = b ,                            (9)
                            AΤu = 0 .                               (10)
Здесь ограничение (9) – условие допустимости решения для задачи (7), (8),
ограничение (10) – дополнительное условие, обеспечивающее
оптимальность.
      Систему уравнений (9), (10) можно также рассматривать как
необходимое и достаточное условие оптимальности по той же теореме 3а
другой задачи оптимизации, в которой ограничение (10) является условием
допустимости:
                            1
                            2
                              ∑ ui2 − bΤu → min ,                   (11)

                            AΤu = 0 .                               (12)
Оптимальным решением данной задачи будет вектор u (решение у этой


                                     88

Страницы