О сходимости rµ(α)-алгоритма
Приводится описание rµ(α)-алгоритма для минимизации почти-дифференцируемой функции. Рассматривается кусочно-линейная выпуклая функция, для которой две точки с линейно зависимыми почти-градиентами могут служить «ловушками» для rµ(α)-алгоритма. Для минимизации выпуклой функции предложен rµ(α)-алгоритм...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2015 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/168372 |
| 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: | О сходимости rµ(α)-алгоритма / П.И. Стецюк, А.В. Ивличев, А.А. Ищенко // Компьютерная математика. — 2015. — № 1. — С. 142-152. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860261517866303488 |
|---|---|
| author | Стецюк, П.И. Ивличев, А.В. Ищенко, А.А. |
| author_facet | Стецюк, П.И. Ивличев, А.В. Ищенко, А.А. |
| citation_txt | О сходимости rµ(α)-алгоритма / П.И. Стецюк, А.В. Ивличев, А.А. Ищенко // Компьютерная математика. — 2015. — № 1. — С. 142-152. — Бібліогр.: 4 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Приводится описание rµ(α)-алгоритма для минимизации почти-дифференцируемой функции. Рассматривается кусочно-линейная выпуклая функция, для которой две точки с линейно зависимыми почти-градиентами могут служить «ловушками» для rµ(α)-алгоритма. Для минимизации выпуклой функции предложен rµ(α)-алгоритм. Показано, что его нельзя «зациклить» в точках-ловушках рассмотренной кусочно-линейной выпуклой функции.
Наводиться опис rµ(α)-алгоритма для мінімізації майже-диференційовної функції. Розглядається кусочно-лінійна опукла функція, для якої дві точки з лінійно залежними майже-градієнтами можуть служити «пастками» для rµ(α)-алгоритма. Для мінімізації опуклої функції запропоновано rµ(α)-алгоритм і показано, що його не можна «зациклити» в точках-пастках розглянутої кусочно-лінійної опуклої функції.
A description of the rµ(α)-algorithm for minimizing the near-differentiable function is given. We consider piecewise-linear convex function, for which two points with linearly dependent almostgradients can serve as the “traps” for the rµ(α) -algorithm. The rµ(α)-algorithm for minimizing a convex function is proposed. It is shown that rµ(α)-algorithm can not be “looped” at point-traps for the piecewise-linear convex function considered.
|
| first_indexed | 2025-12-07T18:55:52Z |
| format | Article |
| fulltext |
142 Компьютерная математика. 2015, № 1
Приводится описание ( )r -алго-
ритма для минимизации почти-
дифференцируемой функции. Рас-
сматривается кусочно-линейная
выпуклая функция, для которой
две точки с линейно зависимыми
почти-градиентами могут слу-
жить «ловушками» для ( )r -ал-
горитма. Для минимизации выпук-
лой функции предложен 0 ( )r -ал-
горитм. Показано, что его нельзя
«зациклить» в точках-ловушках
рассмотренной кусочно-линейной
выпуклой функции.
П.И. Стецюк, А.В. Ивличев,
А.А. Ищенко, 2015
УДК 519.85
П.И. СТЕЦЮК, А.В. ИВЛИЧЕВ, А.А. ИЩЕНКО
О СХОДИМОСТИ r()-АЛГОРИТМА
Введение. ( )r -алгоритм – это один из вари-
антов r -алгоритмов [1]. Он был предложен
Н.З. Шором в 1975 году [2] для миними-
зации почти-дифференцируемых функций.
С ( )r -алгоритмом связаны самые сильные
результаты о сходимости r -алгоритмов: при
определенных условиях ( )r -алгоритм
сходится к локальному минимуму почти-
дифференцируемой кусочно-гладкой функ-
ции [1, 2]. Эти условия не всегда выпол-
няются даже для кусочно-линейных выпук-
лых функций [3].
Далее опишем ( )r -алгоритм и условия
его применения для минимизации почти-
дифференцируемых функций. Обсудим при-
мер кусочно-линейной выпуклой функции от
двух переменных, такой, что ( )r -алгоритм
«зацикливается» в точке, которая не является
точкой минимума. Центральный результат
статьи – это построенная модификация
( )r -алгоритма, преодолевающая точки-ло-
вушки для кусочно-линейной выпуклой
функции.
Материал статьи изложен в таком порядке.
В разделе 1 описаны почти-дифференци-
руемые функции и их свойства. В разделе 2
описан ( )r -алгоритм и приведена основ-
ная теорема о его сходимости. В разделе 3
обсуждается ситуация с зацикливанием
( )r -алгоритма для кусочно-линейной вы-
пуклой функции. В разделе 4 описана мо-
дификация ( )r -алгоритма – 0( )r -алго-
ритм и показано, что его нельзя «зациклить»
в точках-ловушках для кусочно-линейной
выпуклой функции от двух переменных.
О СХОДИМОСТИ ( )r -АЛГОРИТМА
Компьютерная математика. 2015, № 1 143
1. Почти-дифференцируемые функции и их свойства. Понятия почти-
дифференцируемой функции и почти-градиента введены Н.З. Шором в [4].
Дадим их определения и теоремы о свойствах почти-дифференцируемых функ-
ций, которые нам понадобятся в дальнейшем.
Определение 1 [4]. Непрерывная функция ( ),f x заданная в открытой обла-
сти S n -мерного эвклидового пространства ,nE называется почти-диф-
ференцируемой, если: а) в любой ограниченной области ( )f x удовлетворяет
условию Липшица; б) функция ( )f x почти везде дифференцируема; в) градиент
функции ( )f x непрерывен на множестве ,M S где он определен.
Определение 2 [4]. Почти-градиентом функции ( )f x в точке x называется
вектор, являющийся предельной точкой некоторой последовательности гради-
ентов 1( ),g x 2( ),g x …, ( ),kg x …, где =1k kx – последовательность точек
сходящаяся к точке ,x и такая, что во всех точках этой последовательности
функция ( )f x дифференцируема.
Множество ( )fG x – множество почти-градиентов в любой точке x почти-
дифференцируемой функции ( )f x является непустым, ограниченным и зам-
кнутым.
Теорема 1 [4]. Произвольная выпуклая функция ( )f x , определенная в ,nE
является почти-дифференцируемой, а ее любой почти-градиент в точке x
совпадает c некоторым субградиентом.
Теорема 2 [4]. Если две функции 1( )f x и 2( )f x – почти-дифферен-
цируемы, то 3 1 2( ) ( ) ( )f x f x f x и 4 1 2( ) ( ) ( )f x f x f x – также почти-диф-
ференцируемы.
Теорема 3 [4]. Если функции 1( )f x и 2( )f x – почти-дифференцируемы, то
функция 1 2( ) max( ( ), ( ))f x f x f x – также почти-дифференцируема.
Ввести класс почти-дифференцируемых функций Н.З. Шора побудило от-
сутствие свойств выпуклости и гладкости для широкого круга минимаксных
задач и задач нелинейного программирования, а также задач нахождения реше-
ний систем нелинейных уравнений. Так, например, решение системы нелиней-
ных уравнений: ( ) 0,i x ,nx E 1,..., ,i m где ( )i x – почти-дифферен-
цируемые функции, можно свести к нахождению точек минимума таких
функций 1 1
( ) max ( ) ,ii m
x x
либо 2
1
( ) ( ) ,
m
i
i
x x
либо 2
3
1
( ) ( ).
m
i
i
x x
Легко увидеть (см. теоремы 2 и 3), что функции 1( ),x 2( ),x 3( )x будут
почти-дифференцируемыми. Точка локального минимума *,x для которой
*( ) 0,j x 1, 2, 3,j соответствует одному из решений системы нелинейных
уравнений.
П.И. СТЕЦЮК, А.В. ИВЛИЧЕВ, А.А. ИЩЕНКО
144 Компьютерная математика. 2015, № 1
2. μ (α)r -алгоритм. Для минимизации почти-дифференцируемых функций
в [2] Н.З. Шор предложил ( )r -алгоритм – метод градиентного типа с рас-
тяжением пространства переменных в направлении разности двух последо-
вательных почти-градиентов. Ключевую роль здесь играет оператор растяжения
пространства, который в матрично-векторной форме имеет вид
( ) = ( 1) , , = 1, > 1,T n
nR I E
где ( )T означает транспонирование, nI – единичная n n -матрица, – коэф-
фициент растяжения пространства, – направление растяжения. Подробно
свойства оператора ( )R изложены в монографии [1, стр. 68 – 69].
При описании алгоритма в B -форме (на каждой итерации корректируется
матрица kB ) используется оператор
1 1( ) = ( ) = ( 1) , = < 1.T
nR R I
Оператор ( )R является обратным к оператору ( )R и в методах с растяже-
нием пространства переменных он обеспечивает одноранговый пересчет матри-
цы 1kB по такому правилу:
1 = ( ) = ( ( 1) ) = ( 1)( ) .T T
k k k n k kB B R B I B B
Пусть ( )f x – почти-дифференцирумая функция; ( )fG x – множество
почти-градиентов ( )f x в точке ;x > 1 – коэффициент растяжения прост-
ранства; – константа, такая что 0 1; 0x – начальная точка; 0( )fg x –
почти-градиент в точке 0;x 0B – невырожденная n n -матрица (в качестве мат-
рицы 0B часто выбирают либо единичную матрицу ,nI либо диагональную
матрицу nD с положительными элементами на диагонали, с помощью которой
осуществляется масштабирование переменных).
( )r -алгоритмом называется итерационная процедура построения
последовательностей векторов =0k kx и матриц =0k kB , где переход от k -ой
итерации к ( 1)k -ой итерации осуществляется по следующему правилу:
1) вычислим очередную точку
1 = ( ),
kk k k k kx x h B g y (1)
где ( ) = ( ),
k
T
k k f kg y B g x а величина шага kh выбирается из условий:
a) на отрезке 0, kh функция 1( ) ( ( ))k kh f x h не возрастает;
b) существует 1( )f kg G x такой, что
( , ( ))
;
( )
k
k
T
k k
T
k k
B g g y
B g g y
О СХОДИМОСТИ ( )r -АЛГОРИТМА
Компьютерная математика. 2015, № 1 145
2) пересчитаем матрицу (преобразования пространства)
1 = ( ) ( 1) ,T
k k k k k k kB B R B B (2)
где
1= , = ( ), = < 1;
T
k k
k k f kT
k k
B r r g g x
B r
3) переходим к очередной итерации с 1,kx 1kB и 1( ) .f kg x g
Здесь kh – неотрицательный шаг на k -ой итерации (может равняться
нулю), ( ) = ( 1) T
nR I – оператор «сжатия» пространства почти-гради-
ентов в нормированном направлении с коэффициентом
1= < 1,
( )f kg x и
1( )f kg x – почти-градиенты функции ( )f x в точках kx и 1.kx
Комментарий. Если обе части формулы (1) умножить слева на матрицу
1,k kA B то получаем
1 1 ( ) ( ).
k kk k k k k k k k k ky A x A x h g y y h g y
Таким образом формула (1) фактически реализует шаг градиентного спуска для
функции ( ) ( ).k ky f B y При 0 получается аналог шага наискорейшего
спуска. Введение константы 0 дает возможность рассматривать алгоритмы,
в которых поиск минимума по направлению производится приближенно.
Теорема 4 [2]. Пусть ( )f x – почти-дифференцируемая функция, такая,
что lim ( ) ,
x
f x
и последовательность =0
,k kx полученная в результате
реализации ( )r -алгоритма, удовлетворяет условию
1lim 0.k kk
x x
(3)
Если *x – изолированная точка локального минимума, а точка 0x – такая,
что связная компонента множества *
0: ( ) ( ) ( )x f x f x f x , содержащая 0x
и *,x не содержит, кроме *,x других точек ,z в которых семейство ( )fG z
линейно зависимо, то последовательность =0k kx сходится к точке *.x
Теорема 4 определяет достаточные условия, при которых ( )r -алгоритм
сходится к локальному минимуму почти-дифференцируемой кусочно-гладкой
функции ( ).f x Однако, эти условия слишком сильные и не выполняются даже
для кусочно-гладких выпуклых функций. Наиболее типичная ситуация, когда
это происходит, связана с нарушением линейной независимости множества
почти-градиентов ( ).fG x
П.И. СТЕЦЮК, А.В. ИВЛИЧЕВ, А.А. ИЩЕНКО
146 Компьютерная математика. 2015, № 1
3. О зацикливании μ (α)r -алгоритма. В работе [3] построена кусочно-
линейная выпуклая функция от двух переменных, для которой возможно
«зацикливание» ( )r -алгоритма. Если коэффициент растяжения пространства
3, то примером такой функции является выпуклая функция
1 2 1 2 1 2 1 21,...,8 1,...,4 5,...,8
( , ) max ( , ) max max ( , ) , max ( , ) ,
i i ii i i
f x x f x x f x x f x x
(4)
где линейные функции 1 2( , ), 1,...,8,i if f x x i имеют следующий вид:
1 1 2 2 1 2 3 1 2 4 1 210 1, 6 9 9, 10 1, 6 9 9,f x x f x x f x x f x x
5 1 2 6 1 2 7 1 2 8 1 210 1, 6 9 9, 10 1, 6 9 9.f x x f x x f x x f x x
Ее поверхности уровня показаны на рис. 1.
РИС. 1. Поверхности уровня функции (4)
Минимальное значение функция (4) принимает в точке * (0,0)Tx и
* 1.f Кроме оптимальной, для нее имеются точки 1 (0,1)Tz и
2 (0, 1) :Tz 1 2( ) ( ) 0,f z f z в которых нарушено условие линейной
независимости семейств почти-градиентов 1( )fG z и 2( ).fG z
О СХОДИМОСТИ ( )r -АЛГОРИТМА
Компьютерная математика. 2015, № 1 147
Множество 1( )fG z состоит из четырех почти-градиентов: 1 (10,1) ;Tg
2 ( 6,9) ;Tg 3 ( 10,1) ;Tg 4 (6,9) .Tg Им сответствуют градиенты линей-
ных функций 5,f 6 ,f 7f и 8,f значения которых в точке 1 (0,1)Tz равны
нулю. Множество 1 1 2 3 4( ) , , ,fG z g g g g показано на рис. 2, где выпуклая
оболочка почти-градиентов закрашена в синий цвет. Любой из анти-почти-
градиентов в точке 1z не является направлением убывания функции (4), так как
существует антипочти-градиент, образующий с ним тупой угол.
РИС. 2. Множество 1 1 2 3 4( ) , , ,fG z g g g g для функции (4)
Множество 2( )fG z состоит из четырех таких почти-градиентов:
1 ( 10, 1) ;Tg 2 (6, 9) ;Tg 3 (10, 1) ;Tg 4 ( 6, 9) ,Tg которым соот-
ветствуют градиенты линейных функций 1,f 2 ,f 3f и 4.f Множеству 2( )fG z
будет соответствовать рисунок, который является «зеркальным» отражением
рис. 2. относительно оси .Ox
Пусть 0 1x z – стартовая точка для ( )r -алгоритма, 3, 0
1 0
0 1
B и
0 1g g – почти-градиент в точке 0.x Тогда в качестве последовательных почти-
градиентов по итерациям выберем такую последовательность 1 2{ , },g g 2 3{ , },g g
3 4{ , },g g 4 1{ , }.g g Здесь «штрихами» обозначены почти-градиенты в преобразо-
ванном пространстве: одним – после первого растяжения, двумя – после двух
и т. д. Такая последовательность удовлетворяет требованиям ( )r -алгоритма
при 3 и произвольном 0 [3]. При этом шаг на каждой итерации будет
П.И. СТЕЦЮК, А.В. ИВЛИЧЕВ, А.А. ИЩЕНКО
148 Компьютерная математика. 2015, № 1
нулевым, т. е. сдвига с точки 0x происходить не будет. Картина почти-
градиентов после четырех итераций останется такой же, как и вначале, только
длины всех векторов уменьшатся в 2 9 раз. Это связано с тем, что растя-
жение пространства реализуется по взаимно-ортогогальным направлениям.
Если этот цикл повторять, то ( )r -алгоритм с коэффициентом растяжения
пространства 3 не сможет выбраться из точки 0 (0,1),x хотя она не явля-
ется оптимальной для функции (4). Поэтому, точки 1z и 2z могут служить
«ловушками» для минимизирующей последовательности ( )r -алгоритма.
4. μ (α)r -алгоритм. Далее рассмотрим 0( )r -алгоритм – модификацию
( )r -алгоритма для выпуклой функции ( ),f x ,nx E которая для функции (4)
позволяет преодолевать стартовые точки 0 1x z и 0 2.x z Выпуклая функция
( )f x – почти-дифференцируемая функция (см. теорему 1). Будем предпола-
гать, что множество ( )fG x состоит из конечного количества почти-градиентов
функции ( )f x в точке .x
Пусть > 1, 0x – начальная точка; 0( )fg x – почти-градиент функции ( )f x
в точке 0;x 0 nB I единичная n n -матрица. 0( )r -алгоритм строит после-
довательности векторов =0k kx и матриц =0k kB по следующему правилу:
1) вычислим очередную точку
1 = ( ),
kk k k k kx x h B g y (5)
где ( ) = ( ),
k
T
k k f kg y B g x а величина шага kh выбирается по формуле
а)
0
arg min ( ) .
kk k k kh
h f x hB g y
Если kh определяется неоднозначно, то выбираем его наименьшее значение;
2) вычислим 1 1
( ) km
f k i iG x g
– множество почти-градиентов функции
( )f x в точке 1.kx Если 1km и 1 0,g то *
1kx x и останов алгоритма.
Иначе выбираем ,jg g где индекс :1 kj j m такой, на котором достигается
минимум скалярного произведения , ( ) .
k
T
k j kB g g y Если таких векторов боль-
ше чем один, то выбираем произвольный из них;
3) пересчитаем матрицу (преобразования пространства)
1
1= 1 ,T
k k k k kB B B
(6)
О СХОДИМОСТИ ( )r -АЛГОРИТМА
Компьютерная математика. 2015, № 1 149
где
= , = ( ).
T
k k
k k f kT
k k
B r r g g x
B r
4) переходим к очередной итерации с 1,kx 1kB и 1( ) .f kg x g
Здесь kh – величина шага, такая что 0,kh ( )f kg x и 1( )f kg x – почти-
градиенты функции ( )f x в точках kx и 1.kx
Теорема 5. Пусть ( )f x выпуклая функция, такая, что lim ( ) ,
x
f x
и последовательность =0
,k kx генерируемая 0( )r -алгоритмом, удовлетворяет
условию
1lim 0.k kk
x x
(7)
Если *x изолированная точка глобального минимума, а точка 0x такая,
что выпуклое множество *
0: ( ) ( ) ( ) ,x f x f x f x содержащее 0x и *,x не
содержит, кроме *,x других точек ,z в которых семейство ( )fG z линейно зави-
симо, то последовательность =0k kx сходится к точке *.x
Доказательство. Для доказательства достаточно показать, что: (i) теорема 5
– это частный случай теоремы 4; (ii) 0( )r -алгоритм – это частный случай
( )r -алгоритма.
Справедливость (i) следует из того, что выпуклая функция ( )f x – это
почти-дифференцируемая (см. теорему 1). Поэтому для нее изолированную
точку локального минимума (теорема 4) можно заменить на изолированную
точку глобального минимума, а связную компоненту множества, где предпо-
лагается наличие точки локального минимума почти-дифференцируемой функ-
ции (теорема 4), можно заменить на выпуклое множество, в котором содержится
единственная точка глобального минимума функции ( ).f x
Справедливость (ii) следует из того, что условие (п. 1 и условия п. 3)
в 0( )r -алгоритме являются одним из вариантов условий раздела 2 п. a) и b) в
( )r -алгоритме и выполняются при всех значениях 0. На самом деле, из
раздела 4, п. 1 условие a) означает, что неотрицательную величину шага kh мы
выбираем на отрезке 0, ,kh где функция 1( ) ( ( ))k kh f x h не возрастает.
Оно же в сочетании с условиями пункта 3) гарантирует выбор шага из условия
минимума функции по направлению антисубградиента, а lim ( )
x
f x
гарантирует, что такой минимум всегда достижим и для него выполняется
П.И. СТЕЦЮК, А.В. ИВЛИЧЕВ, А.А. ИЩЕНКО
150 Компьютерная математика. 2015, № 1
условие , ( ) 0.
k
T
k j kB g g y Последнее можно заменить условием
, ( ) ,
k
T
k j kB g g y справедливым для любого параметра 0.
Доказательство завершено.
Теорему 5 можно усилить, разрешив множеству *
0: ( ) ( ) ( )x f x f x f x
содержать определенного вида точки с линейно зависимыми почти-градиен-
тами. Это подтверждает
Теорема 6. Если 3, то 0( )r -алгоритм не будет зацикливаться в точках
0 1x z и 0 2x z для функции (4).
Доказательство. Пусть стартовая точка 0 2.x z Множество почти-
градиентов функции (4) в точке 0x состоит из четырех векторов: 1 (10,1) ,Tg
2 ( 6,9) ,Tg 3 ( 10,1) ,Tg 4 (6,9)Tg (см. рис. 2). Если в качестве 0( )fg x
выбран почти-градиент 1,g то 0 0,h так как 1 3( , ) 99 0g g (т. е. в точке
0x существует такой почти-градиент с которым 1g составляет тупой угол).
Следовательно, очередная точка 1 0x x и множество почти-градиентов в ней
состоит из тех же четырех векторов. Согласно п. 3) в качестве почти-градиента в
точке 1x будет выбран вектор 3,g g так как 1 3( , ) 99g g меньше, чем
1 2( , ) 51g g и 1 4( , ) 69.g g Следовательно, первое растяжение пространства
будет производиться в направлении разности почти-градиентов 3g и 1,g в
результате чего на первой итерации 0(3)r -алгоритма получаем направление
растяжения 1 ( 1,0)T и матрицу 1
1 / 3 0
.
0 1
B
Почти-градиент функции 1 1( ) ( )y f B y в точке 1
1 1 1y B x вычисляется
по формуле
1 1 1 1( ) = ( ),T
fg y B g x где 1( )fg x – почти-градиент функции ( )f x в
точке 1x . Следовательно, образами почти-градиентов 1g , 2g , 3g и 4g в пре-
образованном пространстве переменных 1
1 1Y B X будут такие почти-градиен-
ты: '
1 (10 / 3,1) ,Tg '
2 ( 2,9) ,Tg '
3 ( 10 / 3,1)Tg и '
4 (2,9) .Tg Для функ-
ции 1( )y шаг градиентного спуска определяется почти-градиентом '
3g и,
учитывая, что ' '
3 1( , ) 91 / 9 0,g g для второй итерации 0(3)r -алгоритма вели-
чина шага также будет нулевой, т. е. 1 0.h Следовательно, точка 2 0x x и со-
гласно п. 3) в качестве почти-градиента в точке 2x будет выбран 1,g g так как
' '
3 1( , ) 91 / 9g g меньше, чем ' '
3 2( , ) 47 / 3g g и ' '
3 4( , ) 7 / 3.g g
Следовательно, на второй итерации растяжение пространства будет произво-
О СХОДИМОСТИ ( )r -АЛГОРИТМА
Компьютерная математика. 2015, № 1 151
диться в направлении разности почти-градиентов '
1g и '
3,g в результате чего
получаем 2 (1,0)T и матрицу 2
1 / 9 0
.
0 1
B
Образами почти-градиентов 1,g 2 ,g 3g и 4g в преобразованном прост-
ранстве 1
2 2Y B X будут почти-градиенты: ''
1 (10 / 9,1) ,Tg ''
2 ( 2 / 3,9) ,Tg
''
3 ( 10 / 9,1)Tg и ''
4 (2 / 3,9) .Tg Для функции 2( )y шаг градиентного спу-
ска определяется почти-градиентом ''
1.g Учитывая, что '' ''
1 3( , ) 19 / 81 0,g g
для третьей итерации 0(3)r -алгоритма величина шага 2 0.h Следовательно,
точка 3 0x x и в ней будет выбран 3,g g так как '' ''
1 3( , ) 19 / 81,g g а
'' '
1 2( , ) 223/ 27g g и '' ''
1 4( , ) 263/ 27g g . Следовательно, на третьей итерации рас-
тяжение пространства будет производиться в направлении разности почти-
градиентов ''
3g и ''
1 ,g в результате чего 3 ( 1,0)T и 3
1 / 27 0
.
0 1
B
Образами почти-градиентов 1,g 2 ,g 3g и 4g в преобразованном простран-
стве 1
3 3Y B X будут почти-градиенты '''
1 (10 / 27,1) ,Tg '''
2 ( 2 / 9,9) ,Tg
'''
3 ( 10 / 27,1)Tg и '''
4 (2 / 9,9) .Tg Для функции 3( )y шаг градиентного
спуска определяет почти-градиент '''
3g и, учитывая, что, ''' '''
3 1( , ) 629 / 729 0,g g
''' '''
3 2( , ) 2261/ 243 0g g и ''' '''
3 2( , ) 2221/ 243 0g g , то для четвертой итерации
0(3)r -алгоритма величина шага станет ненулевой, т. е. 3 0.h Это означает, что
алгоритм перейдет в точку 4x c меньшим значением функции (4).
По аналогичной схеме можно показать, что за три итерации 0(3)r -алгоритм
найдет направления убывания функции из стартовой точки 0 2x z (симмет-
ричный случай). Теорема доказана.
Заключение. В ( )r -алгоритме за приближенный поиск минимума
функции по направлению антисубградиента в преобразованном пространстве
переменных отвечает параметр . Он обеспечивает выполнение неравенства
*,k kh h где *
kh соответствует минимуму функции. В практических вариантах
r -алгоритмов шаг kh выбирается так, чтобы выполнялось неравенство *.k kh h
Для них «приближенный» поиск минимума функции направлен на уменьшение
общего количества вычислений значений функции и ее субградиента и делается
так, чтобы на одну итерацию алгоритма приходилось в среднем два-три таких
вычисления. Одной из эффективных реализаций такой стратегии является ( )r -
алгоритм с адаптивной регулировкой шага, который преодолевает «ловушки»
для минимизирующей последовательности ( )r -алгоритма.
Работа выполнена при поддержке НАНУ, проект № 0114U001055.
П.И. СТЕЦЮК, А.В. ИВЛИЧЕВ, А.А. ИЩЕНКО
152 Компьютерная математика. 2015, № 1
П.І. Стецюк, А.В. Івлічев, А.О. Іщенко
ПРО ЗБІЖНІСТЬ ( )r -АЛГОРИТМА
Наводиться опис ( )r -алгоритма для мінімізації майже-диференційовної функції. Розгля-
дається кусочно-лінійна опукла функція, для якої дві точки з лінійно залежними майже-гра-
дієнтами можуть служити «пастками» для ( )r -алгоритма. Для мінімізації опуклої функції
запропоновано ( )r -алгоритм і показано, що його не можна «зациклити» в точках-пастках
розглянутої кусочно-лінійної опуклої функції.
P.I. Stetsyuk, A.V. Ivlichev, A.A. Ischenko
ON THE CONVERGENCE OF THE ( )r -ALGORITHM
A description of the ( )r -algorithm for minimizing the near-differentiable function is given. We
consider piecewise-linear convex function, for which two points with linearly dependent almost-
gradients can serve as the “traps” for the ( )r -algorithm. The ( )r -algorithm for minimizing a
convex function is proposed. It is shown that ( )r -algorithm can not be “looped” at point-traps for
the piecewise-linear convex function considered.
1. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. –
Киев: Наук. думка, 1979. – 199 с.
2. Шор Н.З. Исследования сходимости метода градиентного типа с растяжением прост-
ранства в направлении разности двух последовательных субградиентов // Кибернетика. –
1975. – № 4. – С. 48 – 53.
3. Стецюк П.И. К вопросу сходимости r -алгоритмов // Кибернетика и системный анализ –
1995. – № 6. – С. 173 – 177.
4. Шор Н.З. О классе почти-дифференцируемых функций и одном методе минимизации
функций этого класса // Кибернетика. – 1972. – № 4. – С. 65 – 70.
Получено 20.01.2015
Об авторах:
Стецюк Петр Иванович,
доктор физико-математических наук,
заведующий отделом Института кибернетики имени В.М. Глушкова НАН Украины,
E-mail: stetsyukp@gmail.com
Ивличев Андрей Владимирович,
ведущий инженер-программист
Института кибернетики имени В.М. Глушкова НАН Украины,
E-mail: ivlichev1990@gmail.com
Ищенко Андрей Александрович,
студент 5 курса Киевского отделения Московского физико-технического института.
E-mail: andrey.ischenko@gmail.com
|
| id | nasplib_isofts_kiev_ua-123456789-168372 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 2616-938Х |
| language | Russian |
| last_indexed | 2025-12-07T18:55:52Z |
| publishDate | 2015 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Стецюк, П.И. Ивличев, А.В. Ищенко, А.А. 2020-04-30T18:21:03Z 2020-04-30T18:21:03Z 2015 О сходимости rµ(α)-алгоритма / П.И. Стецюк, А.В. Ивличев, А.А. Ищенко // Компьютерная математика. — 2015. — № 1. — С. 142-152. — Бібліогр.: 4 назв. — рос. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/168372 519.85 Приводится описание rµ(α)-алгоритма для минимизации почти-дифференцируемой функции. Рассматривается кусочно-линейная выпуклая функция, для которой две точки с линейно зависимыми почти-градиентами могут служить «ловушками» для rµ(α)-алгоритма. Для минимизации выпуклой функции предложен rµ(α)-алгоритм. Показано, что его нельзя «зациклить» в точках-ловушках рассмотренной кусочно-линейной выпуклой функции. Наводиться опис rµ(α)-алгоритма для мінімізації майже-диференційовної функції. Розглядається кусочно-лінійна опукла функція, для якої дві точки з лінійно залежними майже-градієнтами можуть служити «пастками» для rµ(α)-алгоритма. Для мінімізації опуклої функції запропоновано rµ(α)-алгоритм і показано, що його не можна «зациклити» в точках-пастках розглянутої кусочно-лінійної опуклої функції. A description of the rµ(α)-algorithm for minimizing the near-differentiable function is given. We consider piecewise-linear convex function, for which two points with linearly dependent almostgradients can serve as the “traps” for the rµ(α) -algorithm. The rµ(α)-algorithm for minimizing a convex function is proposed. It is shown that rµ(α)-algorithm can not be “looped” at point-traps for the piecewise-linear convex function considered. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации О сходимости rµ(α)-алгоритма Про збіжність rµ(α)-алгоритма On the convergence of the rµ(α)-algorithm Article published earlier |
| spellingShingle | О сходимости rµ(α)-алгоритма Стецюк, П.И. Ивличев, А.В. Ищенко, А.А. Теория и методы оптимизации |
| title | О сходимости rµ(α)-алгоритма |
| title_alt | Про збіжність rµ(α)-алгоритма On the convergence of the rµ(α)-algorithm |
| title_full | О сходимости rµ(α)-алгоритма |
| title_fullStr | О сходимости rµ(α)-алгоритма |
| title_full_unstemmed | О сходимости rµ(α)-алгоритма |
| title_short | О сходимости rµ(α)-алгоритма |
| title_sort | о сходимости rµ(α)-алгоритма |
| topic | Теория и методы оптимизации |
| topic_facet | Теория и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/168372 |
| work_keys_str_mv | AT stecûkpi oshodimostirμαalgoritma AT ivličevav oshodimostirμαalgoritma AT iŝenkoaa oshodimostirμαalgoritma AT stecûkpi prozbížnístʹrμαalgoritma AT ivličevav prozbížnístʹrμαalgoritma AT iŝenkoaa prozbížnístʹrμαalgoritma AT stecûkpi ontheconvergenceoftherμαalgorithm AT ivličevav ontheconvergenceoftherμαalgorithm AT iŝenkoaa ontheconvergenceoftherμαalgorithm |