Линейные задачи оптимизации. Ч.1. Линейное программирование. Лутманов С.В. - 35 стр.

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

1. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА
35
Доказательство. Необходимость. Пусть
**
ÎUu . Для всех
(
]
,0,1
uU
a
ÎÎ
имеем
()
()
()
()
()
(
)
01()()',.
o
IuuIuIuuuIuIuuu
a
aaaa
a
*******
£+--=---=-+
(3)
Последнее неравенство разделим на число
0
a
>
и устремим его к нулю. В
пределе получим неравенство (2). Пусть теперь
Uu intÎ
*
. Тогда для любого
вектора 1, =Î eRe
n
найдется число 0
0
>
e
, что
[
]
00
,,
eeee
-Î"Î+=
*
Ueuu . В
неравенстве (3) полагаем euu
e
+=
*
. Тогда
(
)
0,' ³
*
euI
e
. В силу произвольности
1, =Î eRe
n
из последнего неравенства выводим, что
(
)
0' =
*
uI . Необходимость
доказана.
Заметим, что при доказательстве необходимости выпуклость функции
I
не использовалась. Для граничной точки
*
u , равенство
(
)
0' =
*
uI может
выполняться, а может и не выполняться. Например, пусть
(
)
(
)
uuIuuIRu 2',
21
=Þ=Î . Тогда:
1)
[
]
01,0 =Þ=
·
uU - равенство
(
)
0' =
*
uI выполняется;
2)
[
]
12,1 =Þ=
·
uU - равенство
(
)
0' =
*
uI не выполняется.
Достаточность. Пусть функция
I
выпукла на множестве
U
и для
некоторой точки
Uu Î
*
выполнено условие (2). Тогда в силу первого критерия
выпуклости выполнено
(
)
UuuIuIuuuIuIuI Î"³Þ-+³
****
),()(,')()( ,
что и доказывает достаточность. Теорема доказана.
Из доказанной теоремы следует, что для выпуклых функций равенство
(
)
0' =
*
uI
влечет за собой
**
ÎUu
.
1.13. Проекция точки на множество
Определение 27. Пусть
n
RU Ì . Проекцией точки
n
Rv Î на множество
U
называется точка UvPw
U
Î= )( , удовлетворяющая условию 
1. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА


      Доказательство. Необходимость. Пусть u* ÎU * . Для всех u Î U , a Î (0,1]
имеем

                                                                           é                     o (a) ù
    0 £ I (au + (1 - a) u* ) - I (u* ) = I (u* - a (u - u* ))- I (u* ) = a ê I ' (u* ), u - u* +       ú . (3)
                                                                           ê                       a   ú
                                                                           ë                           û

      Последнее неравенство разделим на число a > 0 и устремим его к нулю. В
пределе получим неравенство (2). Пусть теперь u* Î int U . Тогда для любого
вектора e Î R n , e = 1 найдется число e 0 > 0 , что u = u* + e e ÎU , "e Î [- e 0 , e 0 ]. В

неравенстве (3) полагаем u = u* + e e . Тогда e I ' (u* ), e ³ 0 . В силу произвольности

e Î R n , e = 1 из последнего неравенства выводим, что I ' (u * ) = 0 . Необходимость

доказана.

        Заметим, что при доказательстве необходимости выпуклость функции I
не использовалась. Для граничной точки u* , равенство I ' (u* ) = 0 может
выполняться,           а      может          и       не        выполняться.               Например,    пусть
u Î R 1 , I (u ) = u 2 Þ I ' (u ) = 2u . Тогда:

        1) U = [0, 1] Þ u · = 0 - равенство I ' (u* ) = 0 выполняется;

        2) U = [1, 2] Þ u· = 1 - равенство I ' (u* ) = 0 не выполняется.

      Достаточность. Пусть функция I выпукла на множестве U и для
некоторой точки u* Î U выполнено условие (2). Тогда в силу первого критерия
выпуклости выполнено

                            I (u ) ³ I (u * ) + I ' (u * ), u - u * Þ I (u ) ³ I (u * ), "u Î U ,

что и доказывает достаточность. Теорема доказана.

       Из доказанной теоремы следует, что для выпуклых функций равенство
I ' (u * ) = 0 влечет за собой u * ÎU * .

      1.13. Проекция точки на множество

      Определение 27. Пусть U Ì R n . Проекцией точки v Î R n на множество U
называется точка w = PU (v) Î U , удовлетворяющая условию

                                                         35

Страницы