close

Вход

Забыли?

вход по аккаунту

?

Необходимые условия апироксимационного условного минимума.

код для вставкиСкачать
НЕОБХОДИМЫЕ УСЛОВИЯ
АППРОКСИМАЦИОННОГО УСЛОВНОГО МИНИМУМА
В. Е. Рольщиков
В статье доказывается существование точек условного аппроксимационного и обобщенного минимума [2] и исследуются свойства множества точек
условного аппроксимационного минимума выпуклой функции при выпуклых ограничениях. Условия гладкости при этом не накладываются.
Ключевые слова:
аппроксимационный градиент, условный мини-
мум, множетели Лагранжа.
Работа посвящена получению необходимых условий минимума для
негладких функций на основе понятия аппроксимационного градиента [1].
Исследуется соотношение точек условного аппроксимационного минимума
и аппроксимационных седловых точек. Работа продолжает исследования [3;
8; 9 ].
1.
Свойства точек условного аппроксимационного минимума
N = f1; 2; 3; :::g - множество нату2 Rjx > 0g - множество положительных чисел;
W - множество собственных выпуклых функций f : Rn ! R; n 2 N,
с непустой внутренностью эффективной области [5] int(domf ) =
6 ;. Далее
8f : Rn ! R 8c 2 R обозначим M (f; c) = fx 2 Rnj f (x) cg - множество Лебега функции f . Для любого множества Q Rn символом Q
Введем следующие обозначения:
ральных чисел;
R+ = fx
обозначим его замыкание, а символом
волом
N (Q; x) = fy
(Q)
- границу множества
2 Rnj 8z 2 Q < z x; y > 0g
Q.
Сим-
обозначим конус
Q в точке x. Для любых x 2 Rn ; r 2 R+
обозначим Vr (x) = fy 2
jjx yjj < rg - открытый шар радиуса r,
Br (x) = Vr (x); Br = Br (0); G - множество функций p : R+ Rn ! [0; 1)
внешних нормалей к множеству
Rn j
таких, что
p(r; s) = 0; 8s 62 Br ;
Таким образом,
s 7! p(r; s)
Z
Br
p(r; s)ds = 1; p(r; s) = p (r; jjsjj):
- функция, симметричная относительно любой
гиперплоскости, проходящей через начало координат. Для любой функции
p(1; ) 2 G обозначим
G0 (p) = fp 2 Gj p(r; s) =
1
s
p(1; )g; 8f 2 W 8x 2 int(domf ):
n
r
r
Необходимые условия аппроксимации условного минимума
159
Обозначим @f (x) - субдифференциал [5] функции f в точке x. Символом
a(x; r; p; f ) = (a1 (x; r; p; f ); :::; an (x; r; p; f )) обозначим вектор аппроксимационного градиента [2] функции f .
Далее будем рассматривать следующую задачу:
f0 (x) ! min x 2 Q Rn ; f0 : Rn ! R;
Q=
m
\
i=1
Qi ; qi = fx 2 Rnj fi(x) 0g; fi : Rn ! R; i = 1; m :
(1)
Приведем некоторые определения и обозначения из [2], которые нам
понадобятся в дальнейшем.
Назовем точку x 2 Rn точкой аппроксимационного
минимума функции f : Rn ! R при выбранных r > 0; p 2 G, если существует число " > 0 такое, что для любых точек x 2 B"(x ) выполнялось
неравенство
Определение 1.
< a(x; r; p; f ); x x > 0:
(2)
D0 (r; p; f ) множество всех точек аппроксимационного минимума. Отметим, что в силу непрерывности отображения x 7! a(x; r; p; f )
[5] для любого x 2 D 0 (r; p; f ) справедливо равенство
Обозначим
a(x ; r; p; f ) = 0:
Назовем точку xc 2 Q точкой условного аппроксимационного минимума функции f : Rn ! R при ограничениях Q Rn и
фиксированных r >T0; p 2 G, если существует " > 0 такое, что для
любой точки x 2 Q B"(xc) будет выполняться неравенство (2).
Определение 2.
xc из определения 2 обозначим CD(r; p; Q; f0 ).
CD(r; p; Q; f0 ), где Q определено
в (1) при условии, что fi 2 W; i = 0; m; int(Q) 6= ;; Q int(domf0 ).
Множество всех точек
Отметим некоторые свойства множества
Предложение 1.
Доказательство.
Множество CD(r; p; Q; f ) выпукло и замкнуто.
0
Докажем замкнутость множества
CD(r; p; Q; f0 ).
Пусть
x j . Нужно показать, что x 2
8j 2 N x j 2 CD(r; p; Q; f ) и 9x = jlim
!1
CD(r; p; Q; f ). Доказывать будем от противного. Предположим, что x 62
CD(r; p; Q; f ), тогда существует x 2 Q и Ж > 0 такие, что
( )
0
( )
0
0
< a(x ; r; p; f0 ); x x >= Ж < 0:
160
В. Е. Рольщиков
! x и непрерывности функции z 7!< a(z; r; p;
f ); x z > существует n 2 N такое, что для любых j n выполняется
В силу сходимости
x(j )
0
неравенство
j < a(x; r; p; f ); x x j > j 2Ж :
0
Тогда для любых
j n
( )
выполняется неравенство
Ж
;
2
< a(x; r; p; f0 ); x x(j ) >
x(j ) .
Покажем выпуклость множества CD (r; p; Q; f0 ). Пусть, следовательно, x(i) 2 CD (r; p; Q; f0 ), i = 1; 2. Покажем, что [x(1) ; x(2) ] CD (r; p; Q; f0 ).
Зафиксируем две произвольные точки x 2 Q и x(0) 2 [x(1) ; x(2) ]. Точке x(0)
соответствует число (0) 2 [0; 1] такое, что
что противоречит определению точки
x(0) = x(1) + (0) (x(2)
В силу выполнения неравенства (2) для
x(1) ):
x = x(i) ; i = 1; 2, имеем
0 (1 (0) ) < a(x; r; p; f0 ); x x(1) > +
+(0) < a(x; r; p; f0 ); x x(2) >=< a(x; r; p; f0 ); x x(0) > :
Так как точки x 2 Q и x(0) 2 [x(1) ; x(2) ] были произвольными, то из послед-
него соотношения следует требуемое утверждение.
Пусть f : Rn ! R измеримая по Лебегу, ограниченная на любом ограниченном множестве функция. Пусть зафиксированы
произвольные p 2 G; r > 0. Тогда отображение (x; r) 7! a(x; r; p; f ) является непрерывным на Rn (0; r ] при p 2 G (p).
Доказательство. Пусть ri > 0 8i 2 N и x i ! x; ri ! r при i ! 1. Для
Предложение 2.
1
0
0
1
( )
доказательства утверждения покажем, что
выполняется неравенство
8" > 0 9n(") 2 N : 8i n(")
ka(x i ; ri ; p; f ) a(x ; r; p; f )k " :
(3)
В силу условий утверждения существует компакт K Rn ; int(K ) 6= ; и
число n 2 N такие, что для любого i n Br (x i ) int(K ) и Br (x ) ( )
1
1
i
( )
int(K ). Как следует из [6; 10 ], для любого Ж > 0 существует непрерывная
n
Ж : R ! R, которая совпадает с f на компакте KЖ , при этом
мера Лебега множества K n KЖ меньше Ж
функция
(K n KЖ ) < Ж:
(4)
Необходимые условия аппроксимации условного минимума
161
Для оценки левой части в неравенстве (3) перейдем к интегрированию
по шару радиуса 1. Используя соотношения
p(r; s) =
1
s
1
p
1;
;d =
d;
rn
r r rn 3 1
получим
A = ka(x(i) ; ri ; p; f ) a(x ; r ; p; f )k =
Z
h f (x(i) + r z )
1 f (x + r z ) i
i
= z
p(1; z )(dz ) =
d1 B1
ri
r
Z
h (x(i) + r z )
i
1 i
Ж (x + r z )
z Ж
p(1; z )(dz )+
= T
d1 B1 KЖ (x )
ri
r
Z
h f (x(i) + r z )
1
f (x + r z ) i
i
+
z
p(1; z )(dz ) :
d1 B1 nKЖ (x )
ri
r
Здесь KЖ (x ) = KЖ
x . Так как выполняется (4), а функция f ограничена
на K и ri сходятся к r > 0, то для любого " > 0 существует Ж1 (") > 0 и
n2 (") 2 N такие, что при igeqn2 (") Ж 2 (0; Ж1 (")] выполняется неравенство
Z
f (x + r z ) i
"
p
(1;
z
)
(
dz
)
:
ri
r
2
B1 nKЖ (x )
В силу непрерывности функции Ж и сходимости ri к r > 0 существует n3 (") 2 N такое, что для любого i n3 (") первое слагаемое в вы"
ражении для A не будет превосходить 2 . Выберем Ж = Ж1 ("); n (") =
maxfn1 ("); n2 ("); n3 (")g, тогда будет выполняться требуемое соотношение
1 d1 z
h f (x(i) + r
iz)
(3). Утверждение доказано.
Пусть зафиксированы fi 2 W;
тогда многозначное отображение
Предложение 3.
i = 0; m
и p(1; ) 2 G,
r 7! CD(r; p; Q; f0 )
(5)
при p 2 G (p(1; )) полунепрерывно сверху по включению на (0; r ], где
r > 0 выбрано из условия Q + Br int(domf ).
Доказательство. Пусть последовательности frigi2N ; fx i gi2N таковы, что
0
0
( )
ri 2 R+ ;
2 CD(r; p; Q; f0 ) 8i 2 N и ri ! r; x(i) ! x при i ! 1. Для
доказательства утверждения нужно показать, что x 2 CD (r ; p; Q; f0 ). Доказывать будем от противного. Предположим, что x 62 CD (r ; p; Q; f0 ), тогда существует x0 2 Q :< a(x0 ; r ; p; f0 ) >< 0. Из монотонного неубывания
xi
( )
функции [5]
(t) =< a(x + t`; r ; p; f0 ); ` >
8` 2 Rn : k`k = 1 :
(6)
162
В. Е. Рольщиков
получаем, что для любого
x 2 [x0 ; x ] выполняется неравенство
< a(x; r ; p; f0 ); x0
(7)
2 CD(ri; p; Q; f0 )
x 2 [x ; x ] справедливо неравенство
С другой стороны, из включения
любого
x > < 0:
0
x(i)
следует, что для
< a(x; ri ; p; f0 ); x0 x(i) > 0 :
Так как точка
x
и число
переходя к пределу при
r
(8)
удовлетворяют условиям утверждения 2, то,
i ! 1 в (8), получаем
< a(x; r ; p; f0 ); x0
x > 0;
что противоречит неравенству (7). Полученное противоречие доказывает
утверждение 3.
В дальнейшем нам понадобится следующее вспомогательное утверждение.
Предложение 4.
Пусть f 2 W; P int(domf ) - компакт, int(P ) 6= ; и
c = inf f (x) > inf f (x) :
x2P
(9)
x2domf
Тогда существует число r > 0 такое, что для любых r 2 (0; r ]; p 2
G; x 2 P вектор a(x; r; p; f ) не принадлежит конусу внешних нормалей
к множеству Лебега M (f; f (x)) в точке x, т.е.
0
0
a(x; r; p; f ) 62 N (M (f; f (x)); x) :
Доказательство.
(10)
Как известно [5], многозначное отображение
полунепрерывно сверху по включению на
int(domf ), т.е.
8" > 0 8x 2 int(domf ) 9Ж (x ; ") > 0 : 8x 2 BЖ
1
@f (x) (@f (x ) + B" :
В силу (11), компактности
1 > 0 такое, что
P
x ;") (x
1(
x 7! @f (x)
)
(11)
и неравенства (9) существует число
'
'
min min < 1 ; 2 >
x2P '1 ;'2 2@f (x) k'1 k k'2 k
1 + 1 :
Необходимые условия аппроксимации условного минимума
163
Действительно, в противном случае из (10) следует, что существует точка
x 2 P , в которой выполняется равенство
'
'
< 1 ; 2 >= 1 :
k'1 k k'2 k
Но это равенство означает, что 0 2 @f (x) и, следовательно, x - точка минимума выпуклой функции f , что невозможно в силу неравенства (9).
Обозначим через
2 = min min
x2P '2@f (x)
Выберем
"() > 0 таким
k'k; = minf ; g > 0 :
1
малым, что для любого
неравенство
'
'
min
min
< 1 ; 2 >
x2P '1 ;'2 2(@f (x)+B" ) k'1 k k'2 k
Из того, что расстояние между точкой
мится к нулю при
r
соотношения
!0
2
" 2 [0; "()]
1+
:
2
(12)
выполнялось
(13)
a(x; r; p; f ) и множеством @f (x) стре-
[2; 3 ] и выполнения (11), следует выполнение
8" > 0 8x 2 P 9Ж (x; ") > 0 : 8y 2 BЖ x;" (x) 8r 2 (0; Ж (x; ")] 8p 2 G
a(y; r; p; f ) 2 (@f (x) + B" ) :
Пусть для каждого x 2 P число Ж (x; ) > 0 выбрано из условий
Ж (x; ) = minfЖ (x; "()); Ж (x; "())g; "() = minf"(); g :
2
2
2(
1
Тогда компакт
P
2
)
2
будет покрыт бесконечной системой открытых шаров
fVЖ x; (x) j x 2 P g, в каждом из которых выполняются соотношения (11)(13) и при этом 8r 2 (0; Ж (x; )] 8p 2 G выполняется неравенство
ka(x; r; p; f )k 2 :
(
)
2
x(j ) ; j = 1; k - центры шаров конечного подпокрытия. Выберем
величину r > 0 из соотношения
Пусть
r = min Ж (x(j ) ; ):
j 21;k
r 2 (0; r ]; p 2 G справедливо неравенство
' a(x; r; p; f )
min min <
;
> > 1+ :
x2P '2@f (x) k'k ka(x; r; p; f )k
2
Тогда для любых
(14)
164
В. Е. Рольщиков
Так как для любых c: inf f; x 2
N (M (f; c); x) совпадает с конусом
(M (f; c))
конус внешних нормалей
K (@f (x)) = fy 2 Rn j 9 0 9' 2 @f (x) : y = 'g;
то соотношение (14) гарантирует выполнение требуемого условия (10).
Пусть функции fi 2 W , i 2 0; m таковы, что int(Q) 6=
; и Q int(domf ), существует c 2 R такое, что множество
Предложение 5.
0
1
Kc1 = M (f0 ; c1 )
\
Q
имеет непустую внутренность (int(Kc ) 6= ;) и ограничено. Тогда существует r > 0 такое, что для любых r 2 (0; r ]; p 2 G множество
CD(r; p; Q; f ) не пусто и ограничено.
Доказательство. Рассмотрим четыре возможных случая
0
^
^
1) (9c0 = inf f0 (x)g)( (M (f0 ; c0 ) 6= ;) (M (f0 ; c0 ) int(Q));
x2domf0
^
2) (9c0 = inf f0 (x)) (Kc0 = ;)
x2domf0
(при этом возможен случай, когда M (f0 ; c0 ) = ;);
3) inf f0 (x) = 1;
x2domf0
^
^
4) (9c0 = inf f0 (x)) (Kc0 6= ;) (M (f0 ; c0 ) 6 int(Q)) :
x2dom(f0 )
В случае 1) справедливость утверждения следует из существования
r > 0 [3] такого, что
8r 2 (0; r] 8p 2 G D (r; p; f ) 6= ;; D (r; p; f ) int(Q) :
тогда точки аппроксимационного минимума xr 2 D (r; p; f )
0
Но
0
0
0
0
0
явля-
ются и точками условного аппроксимационного минимума, то есть xr 2
CD(r; p; Q; f0 ). Так как множество CD(r; p; Q; f0 ) Kc1 , то оно ограничено.
В случае 2) в силу условий утверждения множество Kc1 не пусто и
ограничено. Тогда существует r1 > 0 такое, что для любых p 2 G; r 2 (0; r1 ]
будет выполняться соотношение (10) при P = Kc1 . В силу непрерывности
f0 на int(domf0 ) существует c 2 (c0 ; c1 ) такое, что Kc (Q) и Kc 6= ;,
т.е.
c = min f0 (x) = min f0 (x) :
x2Kc1
x2Q
Необходимые условия аппроксимации условного минимума
Отметим, что в рассматриваемых условиях существует
r 2 (0; r2 ] p 2 G и x 2 Kc1
для любых
r2 > 0
такое, что
выполняется соотношение
a(x; r; p; f0 ) 6= 0 :
Пусть
ниями
где
c 2 (c ; c1 ]. Определим
165
отображение
(15)
c : Kc
! Kc соотноше-
c (x) = npKc (Ar (x)); Ar (x) = x a(x; r; p; f0 );
8y 2 Rn
npKc (y) =
y;
y 2 Kc
y 2 Kc : minz2Kc ky z k = ky yk; y 62 Kc :
c (x) непрерывна и переводит выпуклый компакт Kc в Kc ,
xr 2 Kc этой функции. В силу выполнения (15) xr 62 int(Kc ) при r 2 (0; r2 ]. Так как r1
выбрано из условия выполнения (10) при P = Kc1 , и Kc Kc1 , то
T
xr 62 (M (f0 ; c)) int(Q) при любых r 2 (0; r1 ] и c 2 (c ; c1 ]. Так как
int(Kc ) 6= ;, множество Kc выпуклое и ограниченное, то можно показать,
что для любого c 2 (c ; c1 ] можно выбрать "(c) > 0 таким малым, чтобы
T
для любого x 2 (M (f0 ; c))
(Q) выполнялось равенство
Функция
следовательно, [7] существует неподвижная точка
N"(c) (Q; x)
а конус
N"(c) (M (f0 ; c); x)
\
( N"(c) (M (f0 ; c); x)) = f0g ;
(16)
не содержал противоположно направленных век-
торов. Здесь
N"(c) (P; x) = fz 2 Rn j (z = 0)
_
(9x 2 N (P; x) : kz
xk0kz k ")g :
Докажем (16) от противного. Допустим, что соотношение (16) не
" > 0 существует точка x" 2 (M (f ;
2 N" (Q; x") T( N" c (M (f ; c); x)); ky"k = 1. Выберем
последовательность "i ! 0 при i ! 1; "i > 0 8i 2 N. Из соответствую-
выполняется, тогда для любого
c))
T
(Q)
и
0
y"
( )
щих последовательностей
0
x(i) = x"i ; y(i) = y"i выберем сходящиеся, оставив
за ними ту же нумерацию. Это можно сделать, так как последовательность
x(i) содержится в компакте Kc , а последовательность y(i) - в компакте B1 . В
силу полунепрерывности сверху по включению многозначных отображений
x 7! N (Q; x); x 7! N (M (f0 ; c); x)
будет справедливо включение
\
y 2 N (Q; x ) ( N (M (f0 ; c); x ));
166
В. Е. Рольщиков
где
\
y = lim y(i) ; x = lim x(i) ; x 2 (Q)
(M (f0 ; c)) :
i!1
i!1
S
N (Kc ; x ) = N (Q; x ) N (M (f0 ; c); x ), то y 2 N (Q; x ) N (Kc ; x ) и y 2 N (M (f0 ; c); x ) 2 N (Kc ; x ). Но в этом случае выпуклое множество Kc содержится в гиперплоскости, перпендикулярной вектору y , что противоречит условию int(Kc ) 6= ;. Аналогично доказывается,
что существует " > 0, для которого конус N" (M (f0 ; c); x) не содержит
Так как
противоположно направленных векторов.
Пусть
a(x; r; p; f )
r3 = minfr1 ; r2 g, тогда r3 > 0, а в силу сходимости вектора
r ! 0 к множеству @f (x) (f 2 W; x 2 int(domf )) [2, 3]
при
выполняется соотношение
9r 2 (0; r ] : 8p 2 G 8r 2 (0; r ] 8x 2 (M (f ; c))
4
3
4
\
0
(Q);
где
a(x; r; p; f0 ) 2 N" (M (f0 ; c); x) & 8i 2 1; m a(x; r; p; fi ) 2 N" (Q; x) :
r неподвижнаяTточка xr отображения c не
(M (f0 ; c))
(Q). Действительно, если
бы это было не так, то вектор a(xr ; r; p; f0 ) должен был бы принадлежать
S
конусу co(N (Q; x)
N (M (f0 ; c); x)), что невозможно в силу (16). Итак,
Следовательно, для этих
может принадлежать множеству
\
8p 2 G 8r 2 (0; r ] xr 2 (Q) int(M (f ; c)) :
a(xr ; r; p; f ) 2 N (Q; xr ) и по определению конуса внешних нормалей
4
Тогда
8x 2 Q
0
0
< a(xr ; r; p; f0 ); x xr > 0 :
В силу монотонного неубывания функции (t) (6) для любого x 2 Q будет
выполняться неравенство (2), следовательно, xr 2 CD (r; p; Q; f0 ) и утвер-
ждение в случае 2) доказано.
Доказательство утверждения в случае 3) полностью аналогично доказательству в случае 2).
Рассмотрим последний случай 4). Если для некоторого
T
r > 0 D0 (r;
p; f0 ) Q 6=T;, то этот случай сводится к случаю 1). Пусть, следовательно,
D0 (r; p; f0 ) Q = ;. В этом случае выбираем c 2 (c ; c ]. Так же, как и в
случае 2) для любых x 2 Kc , r 2 (0; r4 ], p 2 G будет выполняться (15). Тогда
T
для некоторых r 2 (0; minfr4 ; r g] будет выполняться либо D 0 (r; p; f0 )
Q 6=
;, либо (15). Доказательство справедливости утверждения для первых r
аналогично случаю 1), а для вторых - случаю 2).
Необходимые условия аппроксимации условного минимума
167
Из доказательства утверждения 5 легко получить, что множество
CD(r; p; Q; f0 ) сходится при r ! 0 к множеству точек условного минимума
Kc в полуметрике (т.е. по включению).
Замечание 1.
Пусть выполняются условия утверждения 5 и зафиксиро-
вано произвольное
p 2 G, тогда при p 2 G0 (p ) выполняется равенство
lim (
max
( min kx yk)) = 0 :
(17)
r!0 y2CD(r;p;Q;f0 ) x2Kc
Доказательство.
c
! 1.
fcj gj2N; cj 2 (c ; c ], cj !
1
cj по доказательству утверждения 5
существует свое rj > 0 : 8r 2 (0; rj ] CD (r; p; Q; f0 ) Kcj . Учитывая сходимость Kcj к Kc и последнее включение, получаем требуемое равенство
при
j
Выберем последовательность
Тогда для каждого
(17).
В дальнейшем будет использоваться следующее понятие обобщенного
в широком смысле условного минимума из [8].
Точку x 2 Q назовем точкой условного обобщенного
в широком смысле минимума функции f , если существуют последовательности frj gj2N , fpj gj2N , fxj gj2N такие, что для любого j 2 N rj > 0,
pj 2 G, xj 2 CD(rj ; pj ; Q; f ) и rj ! 0, xj ! x при j ! 1.
Определение 3.
0
0
0
0
Kc состоит из единственной точки, то она
является точкой условного обобщенного минимума функции f0 .
Замечание 2.
Если множество
Пусть f 2 W , x 2 int(domf ) и пусть последовательности frj gj2N, fpj gj2N, fxj gj2N таковы, что 8j 2 N rj > 0, pj 2 G и
rj ! 0, xj ! x , a(xj ; rj ; pj ; f ) ! a при j ! 1. Тогда
Предложение 6.
a 2 @f (x ) :
Доказательство.
Справедливость этого утверждения следует из полуне-
прерывности сверху по включению многозначного отображения
и сходимости вектора
a(x; r; p; f ) при r ! 0 к множеству @f (x).
x 7! @f (x)
Для предложения 5 справедливо обратное утверждение.
Пусть для fi 2 W , i 2 0; m выполняются следующие
условия: int(Q) 6= ;, Q int(domf ), точка x 2 Q является точкой
условного обобщенного в широком смысле минимума функции f . Тогда
x точка условного минимума, т.е. x 2 Kc .
Предложение 7.
0
0
168
В. Е. Рольщиков
Доказательство.
Из условий утверждения и по определению 3 существу-
frj gj2N, fpj gj2N, fxj gj2N такие, что для любого
8j 2 N rj > 0, pj 2 G и rj ! 0, xj ! x , при j ! 1. Из ограниченности
сходящейся последовательности fxj gj 2N следует ограниченность последовательности fa(xj ; rj ; pj ; f )gj 2N . Выберем из последней сходящуюся под-
ют последовательности
0
последовательность, оставив за ней ту же нумерацию. Из утверждения 6
следует, что вектор
a = lim a(xj ; rj ; pj ; f0 )
j !1
@f0 (x) и при этом из выполнения неравенства (2)
a(xj ; rj ; pj ; f0 ) при любом j 2 N получаем, что вектор = a принадлежит конусу N (Q; x ). В то же время a 2 N (M (f0 ; c); x ), где c = f0 (x ).
Следовательно, выпуклые множества Q и M (f0 ; c) касаются в точке x ,
а это означает, что точка x является точкой условного минимума, что и
принадлежит множеству
для
требовалось доказать.
2.
Аппраксимационные седловые точки
m+1 = f 2 Rm+1 ji 0; i = 0; mg. Как известно (смот[4]), точка (x ; ) 2 Q m+1 является седловой точкой
Обозначим
ри, например
функции
L(x; ) =
тогда и только тогда, когда
m
X
i=0
i fi (x)
(18)
x является точкой минимума функции
)
(x) = L(x; и выполняются условия дополняющей нежесткости
i fi (x ) = 0; i = 0; m:
Основываясь на этом утверждении, приведем следующее определение, аналогичное данному в [2].
. Точку (xr ; (r)) 2 Qm назовем аппроксимационной
седловой точкой функции L (18) при фиксированных r > 0, p 2 G, если
существует число " > 0 такое, что для любого x 2 B"(xr ) выполняются
соотношения
+1
Определение 4.
< a(x; r; p;
(r) ); x
xr > 0 ;
(r)i fi (xr ) = 0; i = 1; m :
(19)
Необходимые условия аппроксимации условного минимума
Обозначим
седловых точек
D0 (r; p;
(r) )
169
SP (r; p; L) Q m+1 множество аппроксимационных
функции L. Таким образом, (x; ) 2 SP (r; p; L), если x 2
и выполняются условия дополняющей нежесткости (19).
. Точку (x ; ) 2 Q m назовем обобщенной седловой точкой функции L, если существует r > 0 такое, что для любых
r 2 (0; r ] p 2 G существует (xr ; (r)) 2 SP (r; p; L) и имеет место сходимость xr ! x, (r) ! при r ! 0.
+1
Определение 5.
Отметим, что множества
SP (r; p; L) и CD(r; p; Q; f0 ) могут не совпаf0 (x; y) = (x 1)2 + (y 1)2 ,
дать и даже не пересекаться. Так, в случае
f1(x; y) = x2 + y4 1 эти множества являются одноточечными и не совпадают. Однако в пределе при r ! 0 соотношение между ними становится более
естественным.
Предложение 8.
и при этом > 0.
0
Доказательство.
Пусть (x ; ) - обобщенная седловая точка функции L
Тогда x является точкой условного минимума.
По
определению
5
существуют
последовательности
f j gj2N , fx j gj2N, frj gj2N, fpj gj2N такие, что для любого j 2 N rj >
0; pj 2 G, (x j ; j ) 2 SP (rj ; pj ; L) и x j ! x ; j ! ; rj ! 0 при j !
1. Выберем из ограниченных последовательностей fa(x j ; rj ; pj ; fi)gj2N ,
( )
( )
( )
( )
( )
( )
( )
i = 0; m сходящиеся,
оставив за ними ту же нумерацию. В силу утвержде-
ния 6 справедливы включения
a(i) 2 @fi (x ); a(i) = lim a(x(j ) ; rj ; pj ; fi ); i = 1; m :
j !1
a(i) 2 N (M (fi ; fi (x )); x ). Для любого 2 m+1 обозначим I () = fi 2 1; mj i > 0g. В силу сходимости j ! существует число
n 2 N такое, что для любых i 2 I ( ) и j n будет выполняться нераj
венство i > 0. Так как для (x(j ) ; (j ) ) выполняется (18), то для i 2 I ( ) в
силу непрерывности функций fi (x) будет выполняться равенство fi (x ) = 0.
Следовательно, в точке (x ; ) выполняются условия дополняющей нежестЭто означает, что
кости (18). Из соотношения (17) имеем
< a(x(j ) ; rj ; pj ;
(j ) ); x
Поэтому
j
j
a(x ; rj ; pj ; f0 ) =
( )
0
( )
m
X
i=1
x(j ) ) >= 0 :
ji a(x(j ) ; rj ; pj ; fi ) :
Переходя в последнем неравенстве к пределу при
0 a(0) =
X
i2I ( )
i a(i) :
j ! 1, получаем
170
В. Е. Рольщиков
0 и включений
Из этого равенства, неравенства
a(i) 2 @fi (x ); i 2 0; m;
для вектора
= a(0)
[
i2
I ( )
N (M (fi ; fi (x )); x ) N (Q; x )
следует справедливость включения
Следовательно, выпуклые множества
x , а это означает, что x
M (f0 ; f0 (x ))
и
Q
2 N (Q; x ).
касаются в точке
- точка условного минимума функции
f0 . Утвер-
ждение доказано.
Список литературы
1.
Батухтин В.Д., Майборода Л.А.
2.
Батухтин В.Д., Майборода Л.А.
3.
Рольщиков В.Е.
1984.
Оптимизация разрывных функций.
М.: Наука,
Разрывные экстремальные задачи.
СПб.: Гип-
пократ, 1995.
О соотношении экстремума и обобщенного экстремума для
// Некоторые вопросы оптимизации разрывных функций. Свердловск: УНЦ АН СССР. 1984. С. 81 93.
недифференцируемых функций
4.
Васильев Ф.П.
5.
Рокафеллар Р.Т.
6.
Варга Дж.
1988.
Численные методы решения экстремальных задач.
Выпуклый анализ.
M.: Мир, 1973.
Оптимальное управление дифференциальными и функциональны-
ми уравнениями.
M.: Наука, 1977.
7.
Канторович Л.В., Акилов Г.П.
8.
Батухтин В.Д.
9.
Бигильдеев С.И., Рольщиков В.Е.
Функциональный анализ.
М.: Наука, 1984.
Задачи анализа разрывных функций и негладкая оптимизация.
Свердловск, 1989. (Препринт / УрО АН СССР ИММ).
Свойства аппроксимационного градиента в
зависимости от весовой функции
1997. ќ4. С. 89 94.
10.
М.: Наука,
Александров П.С.
// Изв. РАН. Теория и системы управления,
Введение в теорию множеств и общую топологию.
ука, 1977.
Челябинский государственный университет
ver@csu.ru
M.: На-
Документ
Категория
Без категории
Просмотров
5
Размер файла
261 Кб
Теги
минимум, условия, апироксимационного, необходимо, условного
1/--страниц
Пожаловаться на содержимое документа