Об одном алгоритме ε-субградиентного типа минимизации выпуклой функции
An algorithm of constructing two cutting planes localizing the set of solutions to the problem of convex function e-minimum. This algorithm provides for as small as needed angle between cutting planes. It is based on the procedure of one-dimensional descent. The results of numerical experiments are...
Gespeichert in:
| Datum: | 2004 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2004
|
| Schriftenreihe: | Теорія оптимальних рішень |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/84873 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Об одном алгоритме ε-субградиентного типа минимизации выпуклой функции / Н.Г. Журбенко, Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 27-33. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84873 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-848732015-07-17T03:02:14Z Об одном алгоритме ε-субградиентного типа минимизации выпуклой функции Журбенко, Н.Г. Ненахов, Э.И. An algorithm of constructing two cutting planes localizing the set of solutions to the problem of convex function e-minimum. This algorithm provides for as small as needed angle between cutting planes. It is based on the procedure of one-dimensional descent. The results of numerical experiments are given. 2004 Article Об одном алгоритме ε-субградиентного типа минимизации выпуклой функции / Н.Г. Журбенко, Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 27-33. — Бібліогр.: 8 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/84873 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
An algorithm of constructing two cutting planes localizing the set of solutions to the problem of convex function e-minimum. This algorithm provides for as small as needed angle between cutting planes. It is based on the procedure of one-dimensional descent. The results of numerical experiments are given. |
| format |
Article |
| author |
Журбенко, Н.Г. Ненахов, Э.И. |
| spellingShingle |
Журбенко, Н.Г. Ненахов, Э.И. Об одном алгоритме ε-субградиентного типа минимизации выпуклой функции Теорія оптимальних рішень |
| author_facet |
Журбенко, Н.Г. Ненахов, Э.И. |
| author_sort |
Журбенко, Н.Г. |
| title |
Об одном алгоритме ε-субградиентного типа минимизации выпуклой функции |
| title_short |
Об одном алгоритме ε-субградиентного типа минимизации выпуклой функции |
| title_full |
Об одном алгоритме ε-субградиентного типа минимизации выпуклой функции |
| title_fullStr |
Об одном алгоритме ε-субградиентного типа минимизации выпуклой функции |
| title_full_unstemmed |
Об одном алгоритме ε-субградиентного типа минимизации выпуклой функции |
| title_sort |
об одном алгоритме ε-субградиентного типа минимизации выпуклой функции |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2004 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84873 |
| citation_txt |
Об одном алгоритме ε-субградиентного типа минимизации выпуклой функции / Н.Г. Журбенко, Э.И. Ненахов // Теорія оптимальних рішень: Зб. наук. пр. — 2004. — № 3. — С. 27-33. — Бібліогр.: 8 назв. — рос. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT žurbenkong obodnomalgoritmeesubgradientnogotipaminimizaciivypuklojfunkcii AT nenahovéi obodnomalgoritmeesubgradientnogotipaminimizaciivypuklojfunkcii |
| first_indexed |
2025-07-06T11:59:50Z |
| last_indexed |
2025-07-06T11:59:50Z |
| _version_ |
1836898782994759680 |
| fulltext |
Теорія оптимальних рішень. 2004, № 3 27
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Предложен алгоритм построения
двух отсекающих плоскостей,
локализующих множество реше-
ний задачи минимизации выпуклой
функции. Обеспечивается сколь
угодно малый угол между отсе-
кающими плоскостями. Алгоритм
основан на процедуре одномерно-
го спуска. Приведены результаты
численных экспериментов.
Н.Г. Журбенко, Э.И. Ненахов,
2004
ÓÄÊ 519.8
Í.Ã. ÆÓÐÁÅÍÊÎ, Ý.È. ÍÅÍÀÕÎÂ
ÎÁ ÎÄÍÎM ÀËÃÎÐÈÒÌÅ
εεεε-ÑÓÁÃÐÀÄÈÅÍÒÍÎÃÎ ÒÈÏÀ
ÌÈÍÈÌÈÇÀÖÈÈ ÂÛÏÓÊËÎÉ
ÔÓÍÊÖÈÈ1
Введение. В работе [1] предложен ε-субгра-
диентный алгоритм решения задачи ε -мини-
мизации ограниченной снизу выпуклой
функции )(xf в −n мерном евклидовом
пространстве n
R :
.Rf(x)|xf
n* }min{ ∈=
Для краткости этот алгоритм будем назы-
вать α(ε)-алгоритмом. Он обеспечивает ре-
шение задачи минимизации выпуклых функ-
ций с заданной точностью.
Для заданного числа 0≥ε введем ε -опти-
мальное множество :)(* εX
.}{)(* ε ff(x)|RxX
*n +≤∈=ε (1)
Произвольную точку )ε(Xx
*∈~ и значение
функции )~(
~
xff = будем называть решени-
ем задачи ε -оптимизации ( ε -решением).
Пусть задан шар ),( RzD начальной лока-
лизации ε -решения: −∈ nRz центр шара,
−> 0R его радиус. Будем предполагать, что
.)(),( * ∅≠εXRzD I
Будем использовать несколько отличное
от классического определение ε -
субградиента [2]. Вектор n
Rg ∈ называется
условным )
~
,( fε -cубградиентом функции
)(xf в точке z , если для ),( RzDx∈∀ вы-
полняется неравенство
1 Работа выполнена при частичной финансовой
поддержке Украинского научно-технологического цен-
тра (грант № 1625)
Н.Г. ЖУРБЕНКО, Э.И. НЕНАХОВ
28 Теорія оптимальних рішень. 2004, № 3
,),(
~
)( ε−−+≥ zxgfxf (2)
где .;
~
)( 1*
Rffzf ∈ε≥≥ Обычное классическое определение ε -субградиента
[3] соответствует определению )
~
,( fε -cубградиента (2) для .0);(
~
≥ε= zff
Обобщенный градиент функции )(xf в точке z в классическом смысле [4]
является ))(,0( zf –cубградиентом.
)(),,
~
,( zfzfG ∂ε будет обозначать множество −ε )
~
,( f субградиентов и мно-
жество обобщенных градиентов в точке z соответственно. В дальнейшем пред-
полагается, что имеются алгоритмы вычисления )(zf и )()( zfzg ∂∈ в произ-
вольной точке .z
Пусть );,
~
,( 111 zfGg ε∈ )( 22
*
zfff ≤≤ , тогда ),
~
,( 222 zfGg ε∈ , где
).,(
~~
121212 zzgff −−−+ε=ε (3)
Таким образом, )
~
,( fε –cубградиент в некоторой точке 1z является )
~
,( fε –
cубградиентом в любой другой точке 2z . Формула (3) определяет правило пере-
счета параметров )
~
,( fε –cубградиента. ),
~
,( zfG ε по своим свойствам аналогич-
но множеству )(zf∂ (выпуклость, замкнутость и т. д.).
Утверждение 1. Для заданных точки z , числа 0≥τ , направления спуска
)1|(| =ηη и 0>ε можно гарантировать вычисление такого ε –cубградиента
),
~
,( zfGg ε∈ , что ε≤ε и .||),( gg τ−≥η
В силу ограничения объема работы, доказательство утверждения и описание
соответствующего алгоритма не приводится. Отметим, что алгоритм аналогичен
известным процедурам генерации субградиентов множеств [3, 5].
Пусть .}εf f(x)|RxfX
n −≤∈=ε
~
{)
~
,(
~
Отметим, что
};решениемявляется~
{)
~
,(
~ −ε⇒∅=ε ffX
).
~
,(
~
)(2
~ **
fXXff ε⊂ε⇒ε+≥
Введем обозначения: }0),(|{),( =η−∈=η zxRxzP
n – плоскость, проходя-
щая через точку z с нормалью n
R∈η , 1|| =η ; =η+ ),(zP }0),(|{ ≥η−∈ zxRx
n –
полупространство, определяемое плоскостью ).,( ηzP
Пусть
),
~
,( zfGg ε∈ ; ||/)( gh ε−ε= ; .||/~ ghgzz −= (4)
Тогда |)|/,~()
~
,(
~
ggzzPfX −−⊂ε +
. Этот факт соответствует обычному по-
строению отсекающих плоскостей "со сдвигом".
Основной операцией α(ε)-алгоритма является процедура (Localization's
Algorithm) построения двух отсекающих плоскостей ),(),,( 21 ηη zPzP . При
ОБ ОДНОM АЛГОРИТМЕ ε-СУБГРАДИЕНТНОГО ТИПА МИНИМИЗАЦИИ ВЫПУКЛОЙ ФУНКЦИИ
Теорія оптимальних рішень. 2004, № 3 29
этом угол ϕ между векторами 21, ηη должен быть достаточно велик, точнее:
для заданного (сколь угодно малого) числа 0>δ выполнено неравенство
.1)(cos),( 21 δ+−≤ϕ=ηη В работе [1] Localization's Algorithm использует опера-
цию вычисления наименьшего по норме вектора выпуклой оболочки конечного
множества векторов. Для решения такой простейшей задачи квадратичного про-
граммирования имеются достаточно эффективные алгоритмы (например [6]).
Однако для больших размерностей трудоемкость такой операции становится
существенной. Приведенный ниже Localization's Algorithm не использует ука-
занную операцию и имеет существенно меньшую трудоемкость.
Localization's Algorithm.
Итерация 1 (инициализация).
Вычисляем ).(1 zfg ∂∈ Если ,01 =g то останов (задача минимизации )(xf
решена), иначе: };{ 11 gG = |;|/ 111 gge −= };{ 11 eE = .11 ep =
Пусть на итерации ),2,1( K=kk получены множества },,,,{ 21 kk eeeE K=
},,,{ 21 kk gggG K= и вектор
.0
1
1
≠= ∑
=
k
l
lk e
k
p (5)
Итерация )1( +k ).2,1( K=k
Используя процедуру одномерной минимизации по направлению ||/ kk pp
вычисляем ε –cубградиент ),
~
,(1 zfGgk ε∈+ , для которого выполнены условия
(см. утверждение 1):
,ε≤ε ./||),( 11 kgpg kkk ++ −≥ (6)
Если ,01 =+kg то останов – задача ε -минимизации решена (заметим, что в
результате одномерной минимизации значение f
~
может уменьшиться, в этом
случае производится пересчет )
~
,( fε параметров субградиентов множества kG
согласно (3)).
Полагаем:
;11 ++ = kkk gGG U |;|/ 111 +++ −= kkk gge ;11 ++ = kkk eEE U
.
1
1 1
1
1 ∑
+
=
+
+
=
k
l
lk e
k
p (7)
Если ,01 =+kp то останов (задача минимизации )(xf решена).
Так как 1+kp внутренняя точка выпуклой оболочки множества ,1+kE то со-
гласно теоремы Каратеодори справедливо представление
∑
=
+ λ=
m
i
lik i
ep
1
1 , (8)
Н.Г. ЖУРБЕНКО, Э.И. НЕНАХОВ
30 Теорія оптимальних рішень. 2004, № 3
где };1,,2,1{ +∈ kli K .21 ≥≥+ mn Пусть коэффициенты iλ в (8) упорядочены:
.021 >λ≥λ≥λ mK
Полагаем |,|/, 21 1
ξξ=η=η le где ∑
= λ−
λ
=ξ
m
i
l
i
i
e
2 11
; ),()cos( 211 ηη=ϕ +k .
Если ,1)cos( 1 δ+−≤ϕ +k то останов, иначе переход на следующую ите-
рацию.
Замечание 1. Задача определения коэффициентов iλ представления (8) -
стандартная процедура линейного программирования.
Замечание 2. Процедура одномерной минимизации выпуклой функции по
направлению (7) использовалась в [6].
Утверждение 2. Алгоритм Localization's Algorithm конечен. При останове
алгоритма выполняется одно из следующих условий:
задача ε –минимизации )(xf решена;
получены такие отсекающие плоскости ),(),,( 21 ηη zPzP , что
.1)cos(),( 121 δ+−≤ϕ=ηη +k
Справедлива следующая оценка значения || 1+kp
.,2,1,0;
1
3
|| 1 K=
+
≤+ k
k
pk . (9)
Доказательство. Первая часть утверждения 2 следует из условий останова
алгоритма. Для этого достаточно заметить, что }.{0}{0 11 ++ ∈⇔∈ kk GCoECo
Докажем конечность алгоритма. Пусть на шагах 1, 2, 3 итерации критерий
останова не выполняется.
Докажем оценку (9). Учитывая определение 1+kp (7) и (6), получаем сле-
дующее рекуррентное соотношение
≤+−=++=+ ++++++
2
111
222
11
222
1
2 ||),(2),(2)1( kkkkkkkkkk egpgkpkepekpkpk
).1(33131|||||)|/,(2 22
11
22 +<+≤+≤+−≤ ++ kkpkgpppgkpk kkkkkkk
Отсюда следует (9).
Из определения вектора ξ следует, что .)1( 1111 ξλ−+λ=+ epk Отсюда не-
трудно получить, что
.
),(2
),(
),()cos(
2
111
2
1
11
211
λ+λ−
λ−
=ηη=ϕ
++
+
+
epp
ep
kk
k
k (10)
Так как ,1;0;1
1
+≤>λ=λ∑
=
nmi
m
i
i то
).1/(11 +≥λ n (11)
ОБ ОДНОM АЛГОРИТМЕ ε-СУБГРАДИЕНТНОГО ТИПА МИНИМИЗАЦИИ ВЫПУКЛОЙ ФУНКЦИИ
Теорія оптимальних рішень. 2004, № 3 31
Из оценки (9) следует, что .0lim
2
1 =+
∞→
k
k
p Но тогда из (10-11) получаем
,1)cos(lim 1 −=ϕ +
∞→
k
k
что и доказывает конечность алгоритма.
Качественная интерпретация алгоритма [1] состоит в следующем. Алгоритм
относится к классу методов с преобразованием пространства. На каждой итера-
ции алгоритма преобразование пространства состоит в применении операторов
растяжения пространства по ортогональным направлениям. Параметры ортого-
нальных преобразований (коэффициенты и направления растяжения) определя-
ются на основе построения множеств локализации ε-решений по информации,
получаемой в результате применения процедуры одномерной минимизации по
направлениям. На каждой итерации обеспечивается уменьшение объема лока-
лизации ε -решения не менее чем в qVolum раз (параметр алгоритма). Параметр
qVolum определяет минимальное значение используемых коэффициентов рас-
тяжения пространства. Согласно полученным в [1] оценкам, для обеспечения
существенного уменьшения объема локализации ( 7.0qVolum ≈ раз) достаточно
применения 2
n процедур одномерной минимизации. Значению параметра
7.0qVolum ≈ соответствует значение коэффициента растяжения .4.2≈ Таким
образом, согласно этой оценки, для такого коэффициента уменьшения объема
локализации трудоемкость одной итерации алгоритма может быть достаточно
большой. Однако эта оценка достаточно груба. Кроме того, отметим, что пове-
дение алгоритма в отличие от метода эллипсоидов [8] существенно зависит от
конкретных характеристик минимизируемой функции.
Приведем результаты численного исследования эффективности разработан-
ной модификации α(ε)-алгоритма.
В качестве тестовых задач рассматривались задачи минимизации двух сле-
дующих функций:
,)(
1
21
1 ∑
=
−ρ=
n
i
i
i
n xxf ∑
=
−ρ=
n
i
i
i
n xxf
1
1
2 )( ,
где параметр nρ выбирался в зависимости от размерности задачи n по формуле
.10 )1/(6 −=ρ n
n Таким образом, степень вытянутости линий уровня («овражно-
сти») функций определяется значением параметра ,1061 =ρ −n
n она одинакова
для всех функций независимо от числа переменных. Начальная точка
.,...2,1,0.1 nixi == Параметр точности решения по функционалу .10 6−=ε Ре-
зультаты решения тестовых задач минимизации функций )(),( 21 xfxf приведе-
ны в табл. 1 и 2 соответственно, где приняты следующие обозначения:
nVarbl – число переменных;
qVolum – значение параметра уменьшения объема локализации
ε -решения на итерации ;
Н.Г. ЖУРБЕНКО, Э.И. НЕНАХОВ
32 Теорія оптимальних рішень. 2004, № 3
nIter – число итераций;
gnLStep_Avr – среднее число применения алгоритма одномерной миними-
зации на одной итерации;
Alph_Avrg - среднее значение коэффициента растяжения пространства.
ТАБЛИЦА 1
NVarbl Qvolum nIter nLStep_Avrg Alph_Avrg
5 0.7 36 2.25 3.624
10 0.99 107 1.364 1.661
10 0.7 56 3.214 3.035
20 0.99 195 1.297 1.621
20 0.7 86 3.686 2.724
30 0.99 283 1.254 1.606
30 0.7 109 3.872 2.848
40 0.99 360 1.236 1.611
40 0.7 134 4.127 2.761
50 0.99 435 1.205 1.6
50 0.7 153 4.255 2.759
100 0.99 711 1.136 1.592
100 0.7 243 4.407 2.744
ТАБЛИЦА 2
Nvarbl Qvolum nIter nLStep_Avrg Alph_Avrg
5 0.99 142 1.204 2.524
5 0.7 67 2.179 4.748
10 0.99 413 1.165 1.855
10 0.7 133 3.015 3.38
20 0.99 1274 1.095 1.552
20 0.7 289 4.173 2.842
30 0.99 2164 1.081 1.52
30 0.7 445 5.231 2.69
40 0.99 1930 1.09 1.508
40 0.7 374 6.035 2.607
50 0.99 2594 1.076 1.465
50 0.7 455 6.868 2.601
100 0.9 4062 2.597 1.755
100 0.7 1559 9.201 2.547
Заключение. Результаты численных экспериментов показывают достаточно вы-
сокую эффективность α(ε)-алгоритма и выявляют следующие интересные его
особенности. Среднее число применения алгоритма одномерной минимизации
на одной итерации оказывается малым в сравнении с приведенной гарантиро-
ОБ ОДНОM АЛГОРИТМЕ ε-СУБГРАДИЕНТНОГО ТИПА МИНИМИЗАЦИИ ВЫПУКЛОЙ ФУНКЦИИ
Теорія оптимальних рішень. 2004, № 3 33
ванной его оценкой ( 2
n ). Даже если параметр уменьшения объема локализации
ε -решения на итерации задается малым (0.99), тем не менее, среднее значение
коэффициента растяжения пространства оказывается существенно больше еди-
ницы.
М.Г. Журбенко, Е.І. Ненахов
ПРО ОДИН АЛГОРИТМ ε-СУБГРАДІЄНТНОГО ТИПУ МІНІМІЗАЦІЇ ОПУКЛОЇ ФУНКЦІЇ
Запропоновано алгоритм побудови двох відтинаючих площин, які локалізують множину
розв’язків задачі мінімізації опуклої функції. Алгоритм гарантує досягнення задовільно ма-
лого кута між відтинаючими площинами. Він заснований на процедурі одномірного спуску.
Наведені результати обчислювальних експериментів.
N.G. Gurbenko, E.I. Nenakhov
ON ONE ε-SUBGRADIENT ALGORITHM OF CONVEX FUNCTION MINIMIZATION
An algorithm of constructing two cutting planes localizing the set of solutions to the problem of
convex function ε-minimum. This algorithm provides for as small as needed angle between cutting
planes. It is based on the procedure of one-dimensional descent. The results of numerical
experiments are given.
1. Журбенко Н.Г. Об одном ε-субградиентном алгоритме минимизации // Теория опти-
мальных решений. – Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины,
2002. – С. 111–118.
2. Журбенко Н.Г. Об одном классе методов минимизации с преобразованием простран-
ства // Методы решения экстремальных задач. – Киев: Ин-т кибернетики
им. В.М.Глушкова НАН Украины, 1996. – С. 68–80.
3. Lemarechal C., Mifflin K. Nonsmooth Optimization. Oxford: Pergamon Press, 1978. –
180 p.
4. Шор Н.З. Методы минимизации недифференцируемых функций и их применение. –
Киев: Наук.думка, 1979. – 200 с.
5. Ржевский С.В. Монотонные методы выпуклого программирования. – Киев: На-
ук.думка, 1993. – 319 с.
6. Wolfe P. Finding the nearest point in a polytope // Math. Progr. – 1976. – Vol. 11. – № 2. –
P. 128 – 149.
7. Ненахов Э.И. Об одном методе отсечений для минимизации выпуклых функций //
Теория оптимальных решений. – Киев: Ин-т кибернетики им. В.М. Глушкова НАН
Украины, 1992. – C. 14–19.
8. Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимиза-
ции. – М. Наука, 1979. – 384 с.
Получено 15.07.2004
|