Модифікація методу січних площин на випадок задачі відшукання чебишовської точки системи опуклих обмежених замкнених множин, які неперервно змінюються, відносно скінченновимірного підпростору
У статті узагальнено метод січних площин розв’язування задачі опуклого програмування на випадок задачі відшукання чебишовської точки системи опуклих обмежених замкнених множин лінійного над полем комплексних чисел нормованого простору, які неперервно змінюються у розумінні метрики Гаусдорфа, відносн...
Saved in:
| Date: | 2010 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Series: | Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/18613 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Модифікація методу січних площин на випадок задачі відшукання чебишовської точки системи опуклих обмежених замкнених множин, які неперервно змінюються, відносно скінченновимірного підпростору / В.О. Гнатюк // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2010. — Вип. 3. — С. 37-46. — Бібліогр.: 3 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-18613 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-186132025-02-09T11:05:11Z Модифікація методу січних площин на випадок задачі відшукання чебишовської точки системи опуклих обмежених замкнених множин, які неперервно змінюються, відносно скінченновимірного підпростору Гнатюк, В.О. У статті узагальнено метод січних площин розв’язування задачі опуклого програмування на випадок задачі відшукання чебишовської точки системи опуклих обмежених замкнених множин лінійного над полем комплексних чисел нормованого простору, які неперервно змінюються у розумінні метрики Гаусдорфа, відносно скінченновимірного підпростору цього простору. Generalized method of cutting planes for solving a convex programming to the case of the problem of finding the Chebyshev point of a system of convex closed bounded sets of linear over the complex numbers normed spaces that are continually changing in the sense of Hausdorff metric, relatively the finite-dimensional subspace of this space. 2010 Article Модифікація методу січних площин на випадок задачі відшукання чебишовської точки системи опуклих обмежених замкнених множин, які неперервно змінюються, відносно скінченновимірного підпростору / В.О. Гнатюк // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2010. — Вип. 3. — С. 37-46. — Бібліогр.: 3 назв. — укр. XXXX-0059 https://nasplib.isofts.kiev.ua/handle/123456789/18613 517.5 uk Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
У статті узагальнено метод січних площин розв’язування задачі опуклого програмування на випадок задачі відшукання чебишовської точки системи опуклих обмежених замкнених множин лінійного над полем комплексних чисел нормованого простору, які неперервно змінюються у розумінні метрики Гаусдорфа, відносно скінченновимірного підпростору цього простору. |
| format |
Article |
| author |
Гнатюк, В.О. |
| spellingShingle |
Гнатюк, В.О. Модифікація методу січних площин на випадок задачі відшукання чебишовської точки системи опуклих обмежених замкнених множин, які неперервно змінюються, відносно скінченновимірного підпростору Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки |
| author_facet |
Гнатюк, В.О. |
| author_sort |
Гнатюк, В.О. |
| title |
Модифікація методу січних площин на випадок задачі відшукання чебишовської точки системи опуклих обмежених замкнених множин, які неперервно змінюються, відносно скінченновимірного підпростору |
| title_short |
Модифікація методу січних площин на випадок задачі відшукання чебишовської точки системи опуклих обмежених замкнених множин, які неперервно змінюються, відносно скінченновимірного підпростору |
| title_full |
Модифікація методу січних площин на випадок задачі відшукання чебишовської точки системи опуклих обмежених замкнених множин, які неперервно змінюються, відносно скінченновимірного підпростору |
| title_fullStr |
Модифікація методу січних площин на випадок задачі відшукання чебишовської точки системи опуклих обмежених замкнених множин, які неперервно змінюються, відносно скінченновимірного підпростору |
| title_full_unstemmed |
Модифікація методу січних площин на випадок задачі відшукання чебишовської точки системи опуклих обмежених замкнених множин, які неперервно змінюються, відносно скінченновимірного підпростору |
| title_sort |
модифікація методу січних площин на випадок задачі відшукання чебишовської точки системи опуклих обмежених замкнених множин, які неперервно змінюються, відносно скінченновимірного підпростору |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2010 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/18613 |
| citation_txt |
Модифікація методу січних площин на випадок задачі відшукання чебишовської точки системи опуклих обмежених замкнених множин, які неперервно змінюються, відносно скінченновимірного підпростору / В.О. Гнатюк // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2010. — Вип. 3. — С. 37-46. — Бібліогр.: 3 назв. — укр. |
| series |
Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки |
| work_keys_str_mv |
AT gnatûkvo modifíkacíâmetodusíčnihploŝinnavipadokzadačívídšukannâčebišovsʹkoítočkisistemiopuklihobmeženihzamknenihmnožinâkíneperervnozmínûûtʹsâvídnosnoskínčennovimírnogopídprostoru |
| first_indexed |
2025-11-25T20:57:02Z |
| last_indexed |
2025-11-25T20:57:02Z |
| _version_ |
1849797349386223616 |
| fulltext |
Серія: Фізико-математичні науки. Випуск 3
37© В. О. Гнатюк, 2010
УДК 517.5
В. О. Гнатюк, канд. фіз.-мат. наук
Кам’янець-Подільський національний університет імені Івана Огієнка,
м. Кам’янець-Подільський
МОДИФІКАЦІЯ МЕТОДУ СІЧНИХ ПЛОЩИН НА ВИПАДОК
ЗАДАЧІ ВІДШУКАННЯ ЧЕБИШОВСЬКОЇ ТОЧКИ СИСТЕМИ
ОПУКЛИХ ОБМЕЖЕНИХ ЗАМКНЕНИХ МНОЖИН,
ЯКІ НЕПЕРЕРВНО ЗМІНЮЮТЬСЯ, ВІДНОСНО
СКІНЧЕННОВИМІРНОГО ПІДПРОСТОРУ
У статті узагальнено метод січних площин розв’язування за-
дачі опуклого програмування на випадок задачі відшукання че-
бишовської точки системи опуклих обмежених замкнених мно-
жин лінійного над полем комплексних чисел нормованого прос-
тору, які неперервно змінюються у розумінні метрики Гаусдорфа,
відносно скінченновимірного підпростору цього простору.
Ключові слова: система опуклих обмежених замкнених
множин, відносна чебишовська точка, метод січних площин.
Вступ. У роботі для відшукання чебишовської точки системи
опуклих обмежених замкнених множин лінійного над полем компле-
ксних чисел нормованого простору, які неперервно змінюються у
розумінні метрики Гаусдорфа, відносно скінченновимірного підпрос-
тору цього простору модифіковано метод січної площини розв’язу-
вання задачі опуклого програмування, запропонований у праці [1], а
також доведено його збіжність.
Постановка задачі. Нехай X – лінійний над полем комплексних
чисел нормований простір. Для підмножини F та елемента g цього
простору покладемо ( ) infF y F
E g g y
∈
= − . Величину ( )FE g назива-
ють найкращим наближенням елемента g множиною F або відстанню
від цього елемента до множини F.
Будемо позначати через ( )O X сукупність опуклих обмежених
замкнених множин простору X, через
( ) ( ) ( ), max sup ,supB A
x A y B
H A B E x E y
∈ ∈
⎧ ⎫
= ⎨ ⎬
⎩ ⎭
— гаусдорфову відстань між
множинами ,A B із ( )O X .
Нехай, крім того, S – компакт, ( )( ),C S O X – множина багато-
значних відображень компакта S в X таких, що для кожного s S∈
Математичне та комп’ютерне моделювання
38
( ) ( )sa s O O X= ∈ і вони неперервні на S відносно метрики Гаусдор-
фа на ( )O X , ( )( ),a C S O X∈ , V – лінійний підпростір простору X,
породжений лінійно незалежними векторами ig X∈ , 1,i n= .
Поставимо задачу відшукання величини
( ) ( ) ( )
( )
( ) ( )1
*
,..., 1
min max min max inf
min max inf .
n
n
a a sg V g V y a ss S s S
n
i iy a ss S i
V E g g y
g y
α α
α
α
∈ ∈ ∈∈ ∈
∈∈∈ =
= = − =
= −∑
(1)
Існує елемент *g V∈ такий, що ( )
( )
* *max infa y a ss S
V g yα
∈∈
= − . Його
будемо називати чебишовською точкою відносно підпростору V (у
підпросторі V) системи ( ){ },a s s S∈ опуклих обмежених замкнених
множин простору X, які неперервно змінюються щодо гаусдорфової
відстані на ( )O X , або екстремальним елементом для величини (1).
Актуальність теми. Задача про відшукання відносної чебишов-
ської точки виникає, зокрема, при найкращій рівномірній апроксима-
ції неперервного у розумінні метрики Гаусдорфа багатозначного ві-
дображення множинами сталих однозначних відображень.
Практичне відшукання величини (1) та її екстремального елеме-
нта вимагає побудови відповідних чисельних методів.
Мета роботи. Побудувати чисельний метод відшукання величи-
ни (1) та її екстремального елемента.
Допоміжні твердження. Позначимо через X* – простір, спряже-
ний з X, через B* – замкнену одиничну кулю простору X*:
{ }* *: , 1B f f X f= ∈ ≤ . Як відомо (див., наприклад, [2, с. 156]), для
будь-якого елемента z X∈ існує елемент *
zf B∈ такий, що
( )zf z z= . Звідси випливає, що для всіх z X∈
( )
*
max Re
f B
z f z
∈
= . (2)
Твердження 1. Нехай ig , 1,i n= , – лінійно незалежні елементи
простору X . Тоді існують функціонали *
jf B∈ , 11,j m= , такі, що
( )
( )
11 1,..., 1
min max Re 0,
n n
n
i j ij mS i
f g
α α α
α μ
≤ ≤= ∈ =
= >∑
Серія: Фізико-математичні науки. Випуск 3
39
де ( )1
1
: ,..., , 1n
n
n
n i
i
S Rα α α α α
=
⎧ ⎫
= = ∈ =⎨ ⎬
⎩ ⎭
∑ – одинична сфера прос-
тору n .
Твердження 2. Нехай g X∈ , ( )( ),a C S O X∈ ,
( ) ( )
( )
inf ,a s y a s
E g g y s S
∈
= − ∈ .
Функція ( ) ( )a ss S E g∈ → є неперервною по s на S.
Твердження 3. Нехай F – опукла замкнена множина простору
X, g – довільний елемент цього простору. Має місце рівність
( ) ( ) ( )
*
inf max Re sup ReF y F f B y F
E g g y f g f y
∈ ∈ ∈
⎛ ⎞
= − = −⎜ ⎟
⎝ ⎠
.
Твердження 4. Функція
( )
( )1
1
,..., max inf
n
n
n i iy a ss S i
g yα α α
∈∈ =
∈ → −∑
є неперервною по ( )1,..., nα α на n .
Основні результати. Поряд із задачею відшукання величини (1)
будемо розглядати таку задачу лінійного програмування з нескінчен-
ною кількістю обмежень:
inf θ (3)
при обмеженнях
( )
( )
( )
1
Re sup Re
n
i i
y a si
f g f yα θ
∈=
− ≤∑ , *f B∈ , s S∈ . (4)
Теорема 1. Задача (3), (4) має оптимальний розв’язок. Справед-
лива рівність ( )* *
a Vθ α= , де *θ – оптимальне значення цільової фу-
нкції задачі (3), (4).
Для того щоб елемент * *
1
n
i i
i
g gα
=
= ∑ був екстремальним елеме-
нтом для величини (1), необхідно і достатньо, щоб вектор
( )* * *
1 ,..., ;nα α θ був оптимальним розв’язком задачі (3), (4).
Доведення. Нехай * *
1
n
i i
i
g gα
=
= ∑ є екстремальним елементом для
величини (1). Тоді з урахуванням твердження 3
Математичне та комп’ютерне моделювання
40
( )
( )
( )
( )
( )
*
* *
1
*
1
max inf
max max Re sup Re .
n
a i iy a ss S i
n
i is S f B y a si
V g y
f g f y
α α
α
∈∈ =
∈ ∈ ∈=
= − =
⎛ ⎞
= −⎜ ⎟⎜ ⎟
⎝ ⎠
∑
∑
(5)
З (5) випливає, що
( ) ( )
( )
( )* *
1
Re sup Re
n
i i a
y a si
f g V f yα α
∈=
− ≤∑ , *f B∈ , s S∈ .
Тому вектор ( )( )* * *
1 ,..., ;n a Vα α α є допустимим розв’язком задачі
(3), (4). У зв’язку з цим
{ } ( )*inf : при обмеженнях (4) a Vθ α≤ . (6)
Нехай тепер ( )1,..., ;nα α θ′ ′ ′ є довільним допустимим розв’язком
задачі (3), (4). Тоді
( )
( )
( )
1
Re sup Re
n
i i
y a si
f g f yα θ
∈=
′ ′− ≤∑ , *f B∈ , s S∈ .
З цієї нерівності з урахуванням твердження 3 отримаємо
( ) ( )
( )
( )
( )
*
*
1
1
max max Re sup Re
max inf .
n
a i is S f B y a si
n
i iy a ss S i
V f g f y
g y
α α
α θ
∈ ∈ ∈=
∈∈ =
⎛ ⎞
′≤ − =⎜ ⎟⎜ ⎟
⎝ ⎠
′ ′= − ≤
∑
∑
(7)
Тому
( ) { }* inf : при обмеженнях (4)a Vα θ≤ . (8)
З (6), (8) маємо, що
{ } ( )* *inf : при обмеженнях (4) a Vθ θ α= = . (9)
Оскільки вектор ( )( )* * *
1 ,..., ;n a Vα α α є допустимим розв’язком за-
дачі (3), (4), то звідси випливає, що він є її оптимальним розв’язком.
Нехай тепер вектор ( )* * *
1 ,..., ;nα α θ є оптимальним розв’язком за-
дачі (3), (4). Оскільки має місце рівність (9) і для будь-якого допус-
тимого розв’язку ( )1,..., ;nα α θ′ ′ ′ задачі (3), (4) справедливе співвідно-
шення (7), то
( )
( )
( )* * * *
1
max inf .
n
a i i ay a ss S i
V g y Vα α θ α
∈∈ =
≤ − ≤ =∑
Серія: Фізико-математичні науки. Випуск 3
41
Звідси випливає, що елемент * *
1
n
i i
i
g gα
=
= ∑ є екстремальним еле-
ментом для величини (1).
Теорему доведено.
Перейдемо до описання запропонованого методу. На попередньому
кроці методу вибираємо функціонали *
jf B∈ , 11,j m= , такі, що
( )
( )
11 1,..., 1
min max Re 0,
n n
n
i j ij mS i
f g
α α
α μ
≤ ≤∈ =
= >∑ (10)
та довільні точки js S∈ , 11,j m=
Відповідно до твердження 1 вищеназвані функціонали існують.
Нехай на l -му кроці методу отримано оптимальний розв’язок
( )1 ,..., ;l l l
nα α θ такої задачі лінійного програмування
minθ (11)
при обмеженнях
( )
( )
( )
1
Re sup Re
j
n
i j i j
y a si
f g f yα θ
∈=
− ≤∑ , 1, lj m= , (12)
де 1 1lm m l= + − , 1, 2,...l = , js S∈ , *
jf B∈ , 1, lj m= .
Оскільки має місце співвідношення (10), то цільова функція за-
дачі (11), (12) обмежена знизу на множині її допустимих розв’язків.
Тому оптимальний розв’язок ( )1 ,..., ;l l l
nα α θ цієї задачі існує (див.,
наприклад, [3, с. 110]).
Теорема 2. Має місце співвідношення
( )*
1
n
l l
a i i
i
V g yθ α α
=
≤ ≤ −∑ , 1, 2,...l = . (13)
Якщо
( ) 1
max inf
n
l l
i iy a ss S i
g yθ α
∈∈ =
= −∑ , (14)
то вектор
1
n
l l
i i
i
g gα
=
= ∑ є екстремальним елементом для величини (1)
і справедлива рівність
( )
( )
*
1
max inf
n
l l
a i iy a ss S i
V g yθ α α
∈∈ =
= = −∑ . (15)
Математичне та комп’ютерне моделювання
42
Доведення. Оскільки вектор ( )1 ,..., ;l l l
nα α θ є оптимальним роз-
в’язком задачі (11), (12), то з урахуванням теореми 1 одержимо, що
{ }
{ } ( )*
inf : при обмеженнях (12)
inf : при обмеженнях (4) .
l
a V
θ θ
θ α
= ≤
≤ =
Справедливість лівої частини співвідношення (13) встановлена.
Оскільки вектор
1
n
l l
i i
i
g g Vα
=
= ∈∑ , то має місце права нерівність спів-
відношення (13). Якщо має місце рівність (14), то з (13) випливає, що
має місце рівність (15) і, отже, вектор
1
n
l l
i i
i
g gα
=
= ∑ є екстремальним
елементом для величини (1).
Теорему доведено.
Продовжимо опис методу. Якщо для { }1,2,...l∈ має місце рів-
ність (14), то згідно з теоремою 2 вектор
1
n
l l
i i
i
g gα
=
= ∑ є екстремаль-
ним елементом для величини (1) і ( )* l
a Vα θ= .
В цьому випадку процес відшукання величини (1) і її екстрема-
льного елемента завершено.
Якщо ж
( ) 1
max inf
n
l l
i iy a ss S i
g yθ α
∈∈ =
< −∑ , то знаходимо 1lms S+ ∈ ,
*
1lmf B+ ∈ такі, що
( ) ( )11 1
max inf inf
ml
n n
l l
i i i iy a ss S y a si i
g y g yα α
+∈∈ ∈= =
− = − =∑ ∑
( )
( )
( )
*
11
max Re sup Re
ml
n
l
i i
f B y a si
f g f yα
+
∈ ∈=
⎛ ⎞
⎜ ⎟= − =
⎜ ⎟
⎝ ⎠
∑ (16)
( )
( )
( )
1
1 1
1
Re sup Re .
l l
ml
n
l
i m i m
y a si
f g f yα
+
+ +
∈=
= −∑
Тоді до обмежень (12) задачі лінійного програмування (11), (12)
добавляємо обмеження
( )
( )
( )
1
1 1
1
Re sup Re
l l
ml
n
i m i m
y a si
f g f yα θ
+
+ +
∈=
− ≤∑ ,
Серія: Фізико-математичні науки. Випуск 3
43
знаходимо оптимальний розв’язок ( )1 1 1
1 ,..., ;l l l
nα α θ+ + + отриманої в
результаті цього нової задачі лінійного програмування і т.д.
Теорема 3. Послідовність { }
1
l
l
θ
∞
=
є неспадною, існує lim l
l
θ
→∞
. По-
слідовність { }
1
l
l
α
∞
=
, де ( )1 ,...,l l l
nα α α= , 1, 2,...,l = є обмеженою по-
слідовністю простору n . Для будь-якої часткової границі
( )* * *
1 ,..., nα α α= послідовності { }
1
l
l
α
∞
=
елемент * *
1
n
i i
i
g gα
=
= ∑ є екст-
ремальним елементом для величини (1).
Має місце співвідношення ( )
( )
* *lim max infl
al y a ss S
V g yθ α
→∞ ∈∈
= = − .
Доведення. Оскільки обмеження задачі лінійного програмування
(11), (12), яка розв’язується на l -му кроці, включаються в обмеження
задачі лінійного програмування, яка розв’язується на 1l + -му кроці
методу, а цільові функції цих задач однакові, то для відповідних їх
оптимальних розв’язків ( )1 ,..., ;l l l
nα α θ і ( )1 1 1
1 ,..., ;l l l
nα α θ+ + + викону-
ється нерівність 1l lθ θ +≤ , 1, 2,...l = . Згідно з теоремою 2 ( )*l
a Vθ α≤ .
Тому існує lim l
l
θ
→∞
і справедлива нерівність
( )*lim l
al
Vθ α
→∞
≤ . (17)
Переконаємося, що послідовність { }
1
l
l
α
∞
=
, де ( )1 ,...,l l l
nα α α= ,
1, 2,...l = , є обмеженою послідовністю простору n .
Припустимо супротивне. Тоді існує її підпослідовність { }
1
lν
ν
α
∞
=
така, що lim lν
ν
α
→∞
= +∞ . Без обмеження загальності будемо вважати,
що уже lim l
l
α
→∞
= +∞ . Оскільки ( )1 ,..., ;l l l
nα α θ є оптимальним
розв’язком задачі (11), (12), то
( )
( )
( )
1
Re sup Re
j
n
l l
i j i j
y a si
f g f yα θ
∈=
− ≤∑ , 11,j m= , 1, 2,...l = .
Звідки
Математичне та комп’ютерне моделювання
44
( )
( )
( )
1
1 1Re sup Re
j
ln
li
j i jl l l
y a si
f g f y
α
θ
α α α ∈=
− ≤∑ , 11,j m= , 1, 2,...l = .(18)
Оскільки 1 ,..., n
ll
n
l l
S
αα
α α
⎛ ⎞
⎜ ⎟∈
⎜ ⎟
⎝ ⎠
, то з послідовності
1
1
,...,
ll
n
l l
l
αα
α α
∞
=
⎧ ⎫⎛ ⎞⎪ ⎪⎜ ⎟⎨ ⎬⎜ ⎟⎪ ⎪⎝ ⎠⎩ ⎭
можна вибрати збіжну підпослідовність
1
1
,...,
l l
n
l l
ν ν
ν ν
ν
α α
α α
∞
=
⎧ ⎫⎛ ⎞
⎪ ⎪⎜ ⎟⎨ ⎬⎜ ⎟⎜ ⎟⎪ ⎪⎝ ⎠⎩ ⎭
. Нехай ( )1
1lim ,..., ,...,
l l
n
nl l
ν ν
ν νν
α α
α α
α α→∞
⎛ ⎞
⎜ ⎟ ′ ′=⎜ ⎟⎜ ⎟
⎝ ⎠
.
Зрозуміло, що ( )1,..., nn Sα α′ ′ ∈ . З урахуванням зазначеного ви-
ще, обмеженості послідовності { }
1
l
l
θ
∞
=
(існує lim l
l
θ
→∞
) з (18) одержи-
мо, що ( )
11 1
max Re 0
n
i j ij m i
f gα
≤ ≤ =
⎛ ⎞
′ ≤⎜ ⎟
⎝ ⎠
∑ , що суперечить (10).
Отже, { }
1
l
l
α
∞
=
є обмеженою послідовністю простору n . Нехай
( )* * *
1 ,..., nα α α= її часткова границя. Переконаємося, що вектор
* *
1
n
i i
i
g gα
=
= ∑ є екстремальним елементом для величини (1).
Існує підпослідовність { }
1
lν
ν
α
∞
=
послідовності { }
1
l
l
α
∞
=
така, що
( ) ( )1
* * *
1lim lim ,..., ,...,n
l ll
n
ν νν
ν ν
α α α α α α
→∞ →∞
= = = .
На кроці 1lν + до обмежень задачі лінійного програмування ти-
пу (11), (12), яка розв’язана на кроці lν , добавляється обмеження
( )
( )
( )
1
1 1
1
Re sup Re
l l
ml
n
i m i m
i y a s
f g f y
ν ν
ν
α θ
+
+ +
= ∈
− ≤∑ ,
де
( ) ( )11 1
max inf inf
ml
n n
l l
i i i iy a ss S y a si i
g y g yν ν
ν
α α
+
∈∈ ∈= =
− = − =∑ ∑
Серія: Фізико-математичні науки. Випуск 3
45
( )
( )
( )
*
11
max Re sup Re
ml
n
l
i i
f B i y a s
f g f yν
ν
α
+
∈ = ∈
⎛ ⎞
⎜ ⎟= − =⎜ ⎟⎜ ⎟
⎝ ⎠
∑ (19)
( )
( )
( )
1
1 1
1
Re sup Re .
l l
ml
n
l
i m i m
i y a s
f g f yν
ν ν
ν
α
+
+ +
= ∈
= −∑
Тому
( )
( )
( )1 1
1
1 1
1
Re sup Re
l l
ml
n
l l
i m i m
i y a s
f g f yν ν
ν ν
ν
α θ+ +
+
+ +
= ∈
− ≤∑ , 1,2,...ν = . (20)
Маємо далі з урахуванням (19), що
( )
( )
( )
( )1
1
1
1 1
1
max inf
Re sup Re
l l
ml
n
l
i iy a ss S i
n
l
i m i m
i y a s
g y
f g f y
ν
ν
ν ν
ν
α
α +
+
∈∈ =
+ +
= ∈
− −
⎞⎛ ⎟− − =⎜ ⎟⎟⎝ ⎠
∑
∑
( )
( )
( )
1
1 1
1
Re sup Re
l l
ml
n
l
i m i m
i y a s
f g f yν
ν ν
ν
α
+
+ +
= ∈
= − −∑
( )
( )
( )1
1
1 1
1
Re sup Re
l l
ml
n
l
i m i m
i y a s
f g f yν
ν ν
ν
α +
+
+ +
= ∈
− + =∑
( ) ( )1
1
1
Re
l
n
l l
i i m i
i
f gν ν
ν
α α +
+
=
= − ≤∑
1
1
, 1,2,....
n
l l
i i i
i
gν να α ν+
=
≤ − =∑
Оскільки ( ) ( )1
* *
1lim ,..., ,...,n
l l
n
ν ν
ν
α α α α
→∞
= , то звідси, неперервності
функції ( )
( )1
1
,..., max inf
n
n
n i iy a ss S i
g yα α α
∈∈ =
∈ → −∑ по ( )1,..., nα α на n
(див. твердження 4) та нерівностей (13), (20) випливає, що
( )
( ) ( )
* *
1 1
lim max inf max inf
n n
l
a i i i iy a s y a ss S s Si i
V g y g yν
ν
α α α
→∞ ∈ ∈∈ ∈= =
≤ − = − =∑ ∑
Математичне та комп’ютерне моделювання
46
( )
*max inf
y a ss S
g y
∈∈
= − =
( )
( )
( )1
1
1 1
1
lim Re sup Re
l l
ml
n
l
i m i m
i y a s
f g f yν
ν ν
ν
ν
α +
+
+ +
→∞ = ∈
⎛ ⎞
⎜ ⎟= − ≤⎜ ⎟⎜ ⎟
⎝ ⎠
∑
( )1 *lim lim .l l
al
Vν
ν
θ θ α+
→∞ →∞
≤ = ≤
Звідси маємо, що
( )
( )
* *lim max infl
al y a ss S
V g yθ α
→∞ ∈∈
= = − .
Тому * *
1
n
i i
i
g gα
=
= ∑ є екстремальним елементом для величини (1).
Теорему доведено.
Зауваження. З доведеної теореми випливає, що оцінки (13) мож-
на використати для відшукання величини ( )*
a Vα з наперед заданою
точністю.
Список використаних джерел:
1. Kelly J. E. The „Cutting plane” methods for solving convex programs /
J. E. Kelly // SIAM J. – 1960. – 8, № 4. – P. 703–712.
2. Иосида К. Функциональный анализ / К. Иосида. – М. : Мир, 1967. – 624 с.
3. Юдин Д. Б. Линейное программирование (теория и конечные методы) /
Д. Б. Юдин, Е. Г. Гольштейн. – М. : Физматгиз, 1963. – 774 с.
Generalized method of cutting planes for solving a convex program-
ming to the case of the problem of finding the Chebyshev point of a system
of convex closed bounded sets of linear over the complex numbers normed
spaces that are continually changing in the sense of Hausdorff metric, rela-
tively the finite-dimensional subspace of this space.
Key words: Chebyshev point, a system of convex bounded closed sets,
method of cutting planes.
Отримано: 25.05.2010
|