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

UptoLike

ВУЗ: 

ИГУ | Иркутск

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

Рубрика: 

51
решением данной задачи, необходимо и достаточно выполнения
равенства
()
f
xAu
Τ
∇=
при некотором
m
uR
∈
.
Данный вектор
u
называется вектором множителей Лагранжа
ограничений задачи (10).
Оптимизация на линейном многообразии. Приведенные выше
теоремы непосредственно обобщаются на задачу минимизации выпуклой
функции
f
от векторов
n
R
на линейном многообразии
n
L
R
∈
:
() min
f
x → ,
x
∈
. (11)
Линейное подпространство является линейным многообразием.
Поэтому задача (11) может рассматриваться как обобщение задачи (8).
Вместе с тем для задачи (11) действуют те же критерии оптимальности.
Считаем, что
S
– линейное подпространство, параллельное
.
Справедливы следующие теоремы, обобщающие теоремы 1 и 2.
Теорема 1а. Для того чтобы вектор
x
∈
был оптимальным
решением задачи (11), необходимо и достаточно равенства нулю
производных функции
f
в точке
x
по любому направлению из
S
, т. е. для
всех
S
s
∈ должно выполняться равенство
0)),(( =∇ sxf .
Теорема 2а. Для того чтобы вектор
x
∈
был оптимальным
решением задачи (11), необходимо и достаточно выполнения
соотношения
⊥
∈∇ Sxf )(.
Задание 4. Опираясь на теоремы 1, 2 и определение линейного
многообразия как сдвига на заданный вектор линейного подпространства,
доказать теоремы 1а, 2а.
Любое линейное многообразие можно определить как множество
решений некоторой системы линейных уравнений, т.е. задачу (11) можно
представить в такой форме
b
Ax
x
f
=
→ min,)( (12)
при заданной матрице
A
размерности nm
×
и заданном векторе b . В
общем случае, в том числе при 0
≠
b , обобщением теоремы 3 будет
следующая формулировка условия оптимальности Лагранжа.
Теорема 3а. Для того чтобы вектор
x
, удовлетворяющий
ограничениям задачи (12), был оптимальным решением данной задачи, 
решением данной     задачи,     необходимо          и   достаточно   выполнения
равенства
                          ∇f ( x ) = AΤu
при некотором u ∈ R m .
    Данный вектор u называется вектором множителей Лагранжа
ограничений задачи (10).
      Оптимизация на линейном многообразии. Приведенные выше
теоремы непосредственно обобщаются на задачу минимизации выпуклой
функции f от векторов R n на линейном многообразии L ∈ R n :
                              f ( x) → min , x ∈ L .                      (11)
     Линейное подпространство является линейным многообразием.
Поэтому задача (11) может рассматриваться как обобщение задачи (8).
Вместе с тем для задачи (11) действуют те же критерии оптимальности.
Считаем, что S – линейное подпространство, параллельное L .
Справедливы следующие теоремы, обобщающие теоремы 1 и 2.
     Теорема 1а. Для того чтобы вектор x ∈ L был оптимальным
решением задачи (11), необходимо и достаточно равенства нулю
производных функции f в точке x по любому направлению из S , т. е. для
всех s ∈ S должно выполняться равенство
                              (∇f ( x), s ) = 0 .
    Теорема 2а. Для того чтобы вектор x ∈ L был оптимальным
решением задачи (11), необходимо и достаточно выполнения
соотношения
                              ∇f ( x ) ∈ S ⊥ .
    Задание 4. Опираясь на теоремы 1, 2 и определение линейного
многообразия как сдвига на заданный вектор линейного подпространства,
доказать теоремы 1а, 2а.
    Любое линейное многообразие можно определить как множество
решений некоторой системы линейных уравнений, т.е. задачу (11) можно
представить в такой форме
                              f ( x) → min, Ax = b                        (12)
при заданной матрице A размерности m × n и заданном векторе b . В
общем случае, в том числе при b ≠ 0 , обобщением теоремы 3 будет
следующая формулировка условия оптимальности Лагранжа.
     Теорема 3а. Для того чтобы вектор x , удовлетворяющий
ограничениям задачи (12), был оптимальным решением данной задачи,


                                       51

Страницы