Алгоритм минимизации с использованием модификации метода эллипсоидов
An ε-subgradient algorithm for minimization of a convex function in a finite-dimensional Euclidean space is proposed. The algorithm is updating of the ellipsoid method, it is based on a dimensional minimization procedure and it is somewhat monotonous. Algorithm’s efficiency evaluation for e -optimiz...
Збережено в:
| Дата: | 2005 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2005
|
| Назва видання: | Теорія оптимальних рішень |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/84939 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Алгоритм минимизации с использованием модификации метода эллипсоидов / Н.Г. Журбенко, Б.М. Чумаков // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 152-157. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84939 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-849392015-07-18T03:01:46Z Алгоритм минимизации с использованием модификации метода эллипсоидов Журбенко, Н.Г. Чумаков, Б.М. An ε-subgradient algorithm for minimization of a convex function in a finite-dimensional Euclidean space is proposed. The algorithm is updating of the ellipsoid method, it is based on a dimensional minimization procedure and it is somewhat monotonous. Algorithm’s efficiency evaluation for e -optimizations problem is given. 2005 Article Алгоритм минимизации с использованием модификации метода эллипсоидов / Н.Г. Журбенко, Б.М. Чумаков // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 152-157. — Бібліогр.: 8 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/84939 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
An ε-subgradient algorithm for minimization of a convex function in a finite-dimensional Euclidean space is proposed. The algorithm is updating of the ellipsoid method, it is based on a dimensional minimization procedure and it is somewhat monotonous. Algorithm’s efficiency evaluation for e -optimizations problem is given. |
| format |
Article |
| author |
Журбенко, Н.Г. Чумаков, Б.М. |
| spellingShingle |
Журбенко, Н.Г. Чумаков, Б.М. Алгоритм минимизации с использованием модификации метода эллипсоидов Теорія оптимальних рішень |
| author_facet |
Журбенко, Н.Г. Чумаков, Б.М. |
| author_sort |
Журбенко, Н.Г. |
| title |
Алгоритм минимизации с использованием модификации метода эллипсоидов |
| title_short |
Алгоритм минимизации с использованием модификации метода эллипсоидов |
| title_full |
Алгоритм минимизации с использованием модификации метода эллипсоидов |
| title_fullStr |
Алгоритм минимизации с использованием модификации метода эллипсоидов |
| title_full_unstemmed |
Алгоритм минимизации с использованием модификации метода эллипсоидов |
| title_sort |
алгоритм минимизации с использованием модификации метода эллипсоидов |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2005 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84939 |
| citation_txt |
Алгоритм минимизации с использованием модификации метода эллипсоидов / Н.Г. Журбенко, Б.М. Чумаков // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 152-157. — Бібліогр.: 8 назв. — рос. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT žurbenkong algoritmminimizaciisispolʹzovaniemmodifikaciimetodaéllipsoidov AT čumakovbm algoritmminimizaciisispolʹzovaniemmodifikaciimetodaéllipsoidov |
| first_indexed |
2025-07-06T12:03:39Z |
| last_indexed |
2025-07-06T12:03:39Z |
| _version_ |
1836899022946697216 |
| fulltext |
152 Теорія оптимальних рішень. 2005, № 4
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Для решения задачи минимизации
выпуклой функции в конечномер-
ном евклидовом пространстве
предлагается ε –субградиентный
алгоритм с преобразованием про-
странства. Алгоритм является
модификацией метода эллипсо-
идов, основан на процедуре одно-
мерного спуска и является, в
некотором смысле, монотонным.
Приводится оценка трудоемкости
алгоритма при решении задачи
ε -оптимизации.
Н.Г. Журбенко, Б.М. Чумаков,
2005
ÓÄÊ 519.8
Í.Ã. ÆÓÐÁÅÍÊÎ, Á.Ì. ×ÓÌÀÊÎÂ
ÀËÃÎÐÈÒÌ ÌÈÍÈÌÈÇÀÖÈÈ
Ñ ÈÑÏÎËÜÇÎÂÀÍÈÅÌ
ÌÎÄÈÔÈÊÀÖÈÈ ÌÅÒÎÄÀ
ÝËËÈÏÑÎÈÄÎÂ
Рассматривается задача минимизации огра-
ниченной снизу выпуклой функции )(xf в
n -мерном евклидовом пространстве n
R :
.Rf(x)|xf
n* }min{ ∈=
Для заданного числа 0≥ε введем
ε -оптимальное множество :)(* εX
.}ε ff(x)|RxX
*n +≤∈= {)(* ε (1)
Произвольную точку )Xx * ε(∈ и значе-
ние функции )~(
~
xff = будем называть реше-
нием задачи ε -оптимизации (ε -решением).
Будем использовать несколько отличное от
классического [1] определение ε -суб-
градиента. Вектор
nRg ∈ называется
−)
~
,( fε cубградиентом функции )(xf в точ-
ке z , если для nRx ∈∀ выполняется нера-
венство
,),(
~
)( ε−−+≥ zxgfxf (2)
где .;
~ 1* Rff ∈≥ ε Обычное классическое
определение ε –субградиента [2] соответ-
ствует определению −)
~
,( fε cубградиента
для )(
~
zff = и .0≥ε Обобщенный градиент
функции )(xf в точке z в классическом
смысле [3] является ))(,0( zf –cубгра-
диентом. )(),,
~
,( zfzfG ∂ε будет обозначать
множество −)
~
,( fε субградиентов и множе-
ство обобщенных градиентов функции
АЛГОРИТМ МИНИМИЗАЦИИ С ИСПОЛЬЗОВАНИЕМ МОДИФИКАЦИИ МЕТОДА ЭЛЛИПСОИДОВ
Теорія оптимальних рішень. 2005, № 4 153
)(xf в точке z соответственно. В дальнейшем предполагается, что имеются
алгоритмы вычисления )(xf и )()( xfxg ∂∈ в произвольной точке x .
Пусть );,
~
,( 111 zfGg ε∈ 2
* ff ≤ . Тогда ),
~
,( 222 zfGg ε∈ , где
).,(
~~
121212 zzgff −−−+= εε (3)
Таким образом, )
~
,( fε -cубградиент в некоторой точке 1z является
)
~
,( fε -cубградиентом в любой другой точке 2z . Формула (3) определяет
правило пересчета параметров )
~
,( fε –cубградиента. ),
~
,( zfG ε по своим
свойствам аналогично множеству )(zf∂ (выпуклость, замкнутость и т.д.).
Например, }
~
{}),,
~
,(0{ * εεεε +≤⇔≤∈ ffzfG ).
Пусть .}εf
~
f(x)|Rx{)f
~
,(X
~ n −≤∈=ε
Отметим, что
};решениемявляетсяf
~
{)f
~
,(X
~
−ε⇒∅=ε
).
~
,(
~
)(2
~ ** fXXff εεε ⊂⇒+≥ (4)
Обозначения: −=−∈= }0),(|{),( ηη zxRxzP n плоскость, проходящая
через z с нормалью ;0||,R n >η∈η −≥η−∈=η+ }0),(|{),( zxRxzP n полу-
пространство, определяемое плоскостью ).,( ηzP
Пусть
),
~
,( zfGg ε∈ ; ||/)( gh εε −= ; .||/~ ghgzz −= (5)
Тогда ),~()
~
,(
~
gzzPfX −−⊂ +ε . Этот факт соответствует обычному построению
отсекающих плоскостей "со сдвигом".
Утверждение 1.
Для заданной точки z , направления спуска )1|(| =ηη и 0>ε можно
гарантировать вычисление такого ε –cубградиента ),
~
,( zfGg ε∈ , что εε ≤ и
.0),( ≥ηg
Доказательство.
Пусть −*
ηz точка минимума функции на луче .ηtzx += Возможны два
случая.
1. .* zz =η Тогда 0)),((,
~
)()( ≥+≥≥+ ηηη tzgfzftzf для ,0>∀t где
)()( ηη tzftzg +∂∈+ . Поэтому ≥+−+++≥ ))(),(()()( ηηη tzxtzgtzfxf
).),(()),((
~
ηη+−−η++≥ txgtzxtzgf Пусть точность одномерного спуска
обеспечивает неравенство .)),(( εηη ≤+ txgt Тогда вектор )( ηtzgg +=
Н.Г. ЖУРБЕНКО, Б.М. ЧУМАКОВ
154 Теорія оптимальних рішень. 2005, № 4
удовлетворяет условиям утверждения. При этом найденное рекордное значение
f
~
не изменяется.
2. .0., *** >+= ttzz ηη Процедурой одномерного поиска определяем две
точки ,21, ,itzz ii =η+= для которых выполнены неравенства: δ+= 12 tt ;
;0;01 >δ>t ,0),(;0),( 21 ≥η≤η gg где ).( ii zfg ∂∈ Заметим, что −−= || 12 zzδ
точность одномерного поиска минимума. Тогда из определения обобщенного
градиента следует неравенство
),,(),(),()()()( 222211122112211 ηδλ−ηλ+λ−−λ+λ+λ+λ≥ gggtzxggzfzfxf (6)
где .1;0; 212211 =λ+λ≥λλ+λ= iggg Выберем iλ из дополнительного условия
.0),( =ηg Тогда из (6), с учетом ,12 ≤λ следует
).,(),()()()( 22211 ηδλλ gzxgzfzfxf −−++≥ (7)
Определим новое рекордное значение },,
~
min{:
~
21 ffff = . Тогда
.
~
)()( 2211 fzfzf ≥+ λλ Пусть одномерный поиск минимума осушествляется с
точностью, обеспечивающей выполнение неравенства .),( 2 ε≤ηδ g Тогда из (7)
получаем .),(
~
)( ε−−+≥ zxgfxf Следовательно, вектор g удовлетворяет условию
леммы.
Приведенное доказательство утверждения 1 содержит алгоритм вычисления
указанного ε –cубградиента. Этот алгоритм во многом аналогичен известным
процедурам генерации субградиентов множеств [2,4].
Следующее утверждение касается построения описанного эллипсоида мини-
мального объема, содержащего сегмент шара.
Обозначения: ),( 0 RzD – шар радиусом 0>R и центром ;0
n
Rz ∈
−η= + ),(),( 10 zPRzDW I часть шара ),( 0 RzD , определяемая секущей
плоскостью ),,( 1 ηzP где ;1||,0;01 =η<ρ≤ρη+= Rzz ;
R
ρ=σ
*
W – эллипсоид
минимального объема, содержащий множество ;W *
0z -центр эллипсоида ;*
W
−+−= IR
Tηηαηα )1()( оператор растяжения пространства [3] по направлению
η с коэффициентом ;α )
~
,(
~ *
0
*
RzD
w
– шар в преобразованном пространстве
,)( zRz ηα=
w
где
;)( *
0
*
0 zRz ηα=
w
;0
*
0 ηhzz += ;)1(
1
1
Rn
n
h σ+
+
= ;1
1
~ 2
2
R
n
n
R σ−
−
=
.)1/()1()1/()1( σ−σ+−+=α nn
АЛГОРИТМ МИНИМИЗАЦИИ С ИСПОЛЬЗОВАНИЕМ МОДИФИКАЦИИ МЕТОДА ЭЛЛИПСОИДОВ
Теорія оптимальних рішень. 2005, № 4 155
Утверждение 2 [5].
;)()
~
,(
~ **
0
* WRRzD η= α
w );,(()( 1
* RzDqVWV ≤ ( (.)V – объем тела);
.)1(
1
1
11
1
)
~
,((/)( 22
2
*
n
n
n
n
n
n
RzDVWVq σ−
σ+
σ−
−+
−
==
Пусть задан шар начальной локализации некоторого решения *x задачи (1)
),( 0 RzD ( −∈ nRz0 центр шара, −> 0R его радиус): .),( *
0
* ∅≠∈ XRzDx I
0max{| || ( ), ( , )}C g g f x x D z R= ∈∂ ∈ (C – максимум нормы обобщенного
градиента в шаре ),( 0 RzD ). Рассмотрим шар )./,()(
~ * CxDD ε=ε Предполагаем,
что шар начальной локализации 0( , )D z R наряду с *
x содержит ).(
~
εD Пусть
).(
~
ε∈ Dx Тогда * * *( ) ( ( ), ) ( ) | ( ( ) || |f f x g x x x f x g x x x≥ + − ≥ − − ≥
( ) ( / ) ( ) .f x C C f xε ε≥ − = − ( ) ( / ) ( ) .f x C C f xε ε≥ − = −
Поэтому все точки из ).(
~
εD являются решением задачи ε -оптимизации (1):
).()(
~ * ε⊂ε XD Отсюда, учитывая (4),
).
~
,(
~
)(
~
2
~ * fXDff ε⊂ε⇒ε+≥ (8)
Пусть 0 0( ),g f z∈∂ 0 0/ | | .z z gε′ = − Тогда (см. формулу (3))
|).|/,(())(,(
~
00
'
000 ggzPzDDzfX −∩=⊂ε ++
Введем обозначение: ),( 0 SzK –конус, порожденный множеством ,nRS ∈ с
полюсом в точке :0z .}0,,;|{),( 1
00 ≥∈∈+== tRtSztzzxxSzK
Рассмотрим конус 0( , ).K z D
+
Он является круговым конусом с осью
симметрии 0g− и углом ,2θ ,θ π ϕ= − где sin( ) /(| | ) /( ).g R CRθ ε ε= ≥
Величину /( )CRγ ε= естественно определить как относительную точность
решения задачи ε -оптимизации (1) (с учетом начального шара-локализатора
),( 0 RzD ). Пусть 0 0 0 0 0( / sin( ))( / | |, / cos( ).K K
u z R g g R Rθ θ= − = Тогда
нетрудно видеть, что )),((),( 000
KK RuDKDzK =+ и 0 0( , ).K K
D D u R
+ ∈ Таким
образом шар ),( 00
KKK RuD порождает конус 0( , ).K z D
+
Так как
),())(,(
~
00
++ ∩⊂⊂ε DzKDzfX то этот конус можно интерпретировать как
конус направлений на решение задачи ε -оптимизации.
Для описания предлагаемого алгоритма решения задачи ε -оптимизации,
достаточно рассмотреть одну его итерацию.
Н.Г. ЖУРБЕНКО, Б.М. ЧУМАКОВ
156 Теорія оптимальних рішень. 2005, № 4
Для точки 0z , направления спуска |)(|/)( 0000 zuzu −−=η и 0>ε , согласно
утверждения 2, вычислим такой ε –cубградиент ),
~
,( 0zfGg ε∈ , что εε ≤ и
.0),( ≥ηg Тогда множество )
~
,(
~
fX ε содержится в конусе =1
~
K
),,(),( 000
kk RuKzP ∩ξ= + где .||/ gg−=ξ Однако конус 1
~
K не является
круговым. Круговой конус 1K , содержащий конус 1
~
K (следовательно и
множество )
~
,(
~
fX ε ), определим следующим образом:
),(),( 000 ξ∩= + zPRuDW KK – часть шара ),( 00
KK RuD , определяемая секущей
плоскостью ).,( 1 ξzP
*
W – эллипсоид минимального объема, содержащий
множество .W Параметры эллипсоида *
W определяются в соответствии с
утверждением 2. Пусть ),( *
1 WKK = тогда нетрудно видеть, что .
~
11 KK ⊂
Причем в преобразованном оператором растяжения )(ηαR (утверждение 2)
пространстве конус 1)( KR ηα является круговым: образ эллипсоида *
W в
преобразованном пространстве является образующим шаром этого конуса.
Таким образом, на основании процедуры одномерной минимизации по
направлению ,η получаем новый круговой конус направлений в
преобразованном пространстве.
На этом итерация алгоритма закончена. Следующая итерация осуществляется в
точности так же, но в преобразованном пространстве.
На основании [6] можно доказать следующее утверждение об эффективности
приведенного алгоритма.
Утверждение 3
Для числа итераций k алгоритма, за которые он обеспечивает решение
2ε -оптимизации, справедлива следующая асимптотическая оценка по
,1<<γ 1>>n :
22 ln(1/ )k n γ≤ , где: γ –относительная точность решения задачи,
/( );RCγ ε= C – оценка сверху норм субградиентов в исходном шаре
),( RzD .
Приведенный алгоритм можно использовать непосредственно для решения
задачи ε -оптимизации. Однако основная цель этого алгоритма состоит в
генерации “узких ” конусов–локализаторов направлений на решение задачи
ε -оптимизации. Два таких алгоритма рассматривались в работах [7,8]. В
отличие от алгоритмов [7,8], предложенный в данной работе алгоритм
использует операцию преобразования пространства.
АЛГОРИТМ МИНИМИЗАЦИИ С ИСПОЛЬЗОВАНИЕМ МОДИФИКАЦИИ МЕТОДА ЭЛЛИПСОИДОВ
Теорія оптимальних рішень. 2005, № 4 157
М.Г. Журбенко, Б.М. Чумаков
АЛГОРИТМ МІНІМІЗАЦІЇ З ВИКОРИСТАННЯМ МОДИФІКАЦІЇ МЕТОДУ ЕЛІПСОЇДІВ
Для розв'язання задачі мінімізації випуклої функції в скінченновимірному евклідовому
просторі пропонується ε -субградієнтний алгоритм з перетворенням простору. Алгоритм є
модифікацією методу еліпсоїдів, базується на процедурі одномірного спуску і в деякому
розумінні монотонний. Наводиться оцінка трудомісткості алгоритму при розв'язанні задачі
ε - оптимізації.
N.G. Zhurbenko, B.M. Сhumakov
MINIMIZATION ALGORITHM USING THE MODIFIED ELLIPSOID METHOD
An ε -subgradient algorithm for minimization of a convex function in a finite-dimensional
Euclidean space is proposed. The algorithm is updating of the ellipsoid method, it is based on a
dimensional minimization procedure and it is somewhat monotonous. Algorithm’s efficiency
evaluation for ε -optimizations problem is given.
1. Журбенко Н.Г. Об одном классе методов минимизации с преобразованием про-
странства // Методы решения экстремальных задач. – Киев: Ин-т кибернетики
им.В.М. Глушкова НАН Украины, 1996. – С. 68 – 80.
2. Lemarechal C., Mifflin K. Nonsmooth Optimization. – Oxford: Pergamon Press, 1978. –
180 p.
3. Шор Н.З. Методы минимизации недифференцируемых функций и их применение.
Киев: Наук. думка, 1979. – 200 с.
4. Ржевский С.В. Монотонные методы выпуклого программирования. – Киев: Наук.
думка, 1993. – 319 с.
5. Шор Н.З., Гершович В.И. Об одном семействе алгоритмов для решения задач
выпуклого программирования // Кибернетика. – 1979. – №4. – С.62 – 67.
6. Журбенко Н.Г. Оценка эффективности одного класса ε –субградиентных методов
минимизации с преобразованием пространства // Оптимизация и ее приложения. –
Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 1997. – С. 49 – 54.
7. Журбенко Н.Г. Об одном ε-субградиентном алгоритме минимизации // Теория
оптимальных решений. – Киев: Ин-т кибернетики им.В.М.Глушкова НАН Украины,
2002. – С. 111 – 118.
8. Журбенко Н.Г., Ненахов Э.И. Об одном алгоритме ε-субградиентного типа мини-
мизации выпуклой функции // Теорія оптимальних рішень. – К.: Ін-т кібернетики
ім. В.М. Глушкова НАН України, 2004. – С. 27 – 33.
Получено 22.03.2005
|