Про одне сімейство субградієнтних алгоритмів з перетворенням простору
The article presents a brief description of the results of the development of a family of subgradient algorithms for minimization using dilation operators of space of variables (r(σ)-algorithms). r(σ)-algorithms are modifications of N.Z. Shor's r-algorithm. Unlike r-algorithm, the...
Gespeichert in:
| Datum: | 2023 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Schlagworte: | |
| Online Zugang: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/281 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
| Завантажити файл: |  |
Institution
Physico-mathematical modeling and informational technologies| _version_ | 1867479648938491904 |
|---|---|
| author | Zhurbenko, Mykola Lykhovyd, Oleksii |
| author_facet | Zhurbenko, Mykola Lykhovyd, Oleksii |
| author_institution_txt_mv | [
{
"author": "Mykola Zhurbenko",
"institution": "к. ф.-м. н., с.н.с, Інститут кібернетики ім. В.М. Глушкова НАН України, Проспект академіка Глушкова, 4003187, Київ"
},
{
"author": "Oleksii Lykhovyd",
"institution": "н.с., Інститут кібернетики ім. В.М. Глушкова НАН України, Проспект академіка Глушкова, 4003187, Київ"
}
] |
| author_sort | Zhurbenko, Mykola |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:32:19Z |
| description | The article presents a brief description of the results of the development of a family of subgradient algorithms for minimization using dilation operators of space of variables (r(σ)-algorithms). r(σ)-algorithms are modifications of N.Z. Shor's r-algorithm. Unlike r-algorithm, the values of space dilation coefficients in r(σ)-algorithms are programmatically determined during the execution of the algorithm. It is essential that to determine the values of step coefficients in r(σ)-algorithms, there is no need to use the procedure of one-dimensional minimization in the direction – the algorithms can be used with a constant step in the transformed space of variables. |
| first_indexed | 2026-06-09T01:09:37Z |
| format | Article |
| fulltext |
83
doi.org/10.15407/fmmit2023.36.083
Про одне сімейство субградієнтних алгоритмів з перетворенням
простору
Микола Журбенко1, Олексій Лиховид2
1к. ф.-м. н., с.н.с, Інститут кібернетики ім. В.М. Глушкова НАН України, Проспект академіка Глушкова, 4003187,
Київ, e-mail: zhurbnick@gmail.com
2н.с., Інститут кібернетики ім. В.М. Глушкова НАН України, Проспект академіка Глушкова, 4003187, Київ, e-mail:
o.lykhovyd@gmail.com
У статті наведено короткий опис результатів розробки сімейства субградієнтних алгоритмів мінімізації з
використанням операторів розтягу простору змінних (r(σ)-алгоритмів). r(σ)-алгоритми є модифікаціями r-
алгоритму Н.З. Шора. На відміну від r-алгоритму, значення коефіцієнтів розтягу простору в r(σ)-
алгоритмах визначаються програмно під час виконання алгоритму. Суттєво, що в r(σ)-алгоритмах немає
необхідності використовувати процедуру одновимірної мінімізації за напрямком – алгоритми можна
використовувати з постійним кроком у перетвореному просторі змінних.
Ключові слова: негладка оптимізація, субградієнтний алгоритм,
перетворення простору, чисельна ефективність
Вступ. Понад 50 років тому було розроблено субградієнтний алгоритм мінімізації з розтягом
простору у напрямку різниці двох послідовних градієнтів – r-алгоритм [1], [2]. Практика
використання r-алгоритму показує, що і досі він є одним із найефективніших алгоритмів
негладкої оптимізації. Проте теоретичне дослідження ефективності алгоритму не закінчено.
Основна проблема теоретичного обґрунтування r-алгоритму полягає у узгодженому виборі
значень коефіцієнтів розтягу простору та крокових множників. З метою подолання певною
мірою цієї проблеми та спрощення чисельної схеми було розроблено сімейство модифікацій
r-алгоритму з програмним вибором значень коефіцієнтів розтягу простору [3], [4], [5]. У
доповіді буде надано коротку характеристику r(σ)-алгоритмів та запропоновано нові елементи
процедури управління значеннями коефіцієнтів розтягу.
1.Загальна схема субградієнтних алгоритмів з перетворенням простору
Загальна схема субградієнтних алгоритмів з перетворенням простору для задачі безумовної
мінімізації субдиференційованої функції ( )f x в
nR полягає у наступному. Нехай A –
невироджений лінійний оператор (невироджена матриця) в .nR Нехай 1( ) ( ),y f A y
,y Ax ( ) ( ).g x f x Функцію ( )y можна розглядати як функцію ( )f x у перетвореному
оператором A просторі: .Y AX Множина субградієнтів ( )g y функції ( )y
визначається співвідношенням * 1( ) ( ),y A f x яке визначає перетворення субградієнтів
під час перетворення простору змінних [2]. Нехай на ітерації k методу отримана точка kx та
перетворення простору визначається невиродженим лінійним оператором : .k k kA Y A X
УДК 519.85
mailto:zhurbnick@gmail.com
mailto:o.lykhovyd@gmail.com
Микола Журбенко,Олексій Лиховид
Про одне сімейство субградієнтних алгоритмів з перетворенням простору
84
Точці kx відповідає точка ky перетвореного простору: .k k ky A x Для отримання наступного
наближення 1kx реалізуємо один крок субградієнтного спуску у перетвореному просторі
(ітерація 1k ):
1 ( )/ || ( ) ||,k k k k ky y h g y g y (1)
де * 1( ) ( ), ( ) ( ).k k f k f k kg y A g x g x f x
Застосувавши до (1) оператор 1,kA отримаємо
1 * 1 * 1
1 ( )/ || ( ) ||,k k k k k f k k f kx x h A A g x A g x
(2)
або
* *
1 ( )/ || ( ) ||,k k k k k f k k f kx x h B B g x B g x (3)
де 1.k kB A На ітерації 1k вибирається оператор kT перетворення простору :kY
1 .k k k k kY T Y T A X Таким чином, оператор перетворення на ітерації 1k
визначається оператором 1 .k k kA T A Обернене перетворення 1
1 .k k kB B T
Ітеративна процедура (3) породжує конкретні алгоритми при вказівці
послідовностей , ,k kh T оператора 0B та початкової точки 0.x
2. Обчислювальна схема r-алгоритму та r(σ)-алгоритмів
r-алгоритм. У r-алгоритмі в якості оператора перетворення простору kT
використовується оператор розтягу простору за напрямком [2]:
( ) ( 1) TR I , де I – одинична матриця, ,nR – напрямок та
коефіцієнт розтягу простору, || || 1, 0. Зауважимо, що: 1( ) ( ),R R
1/ . Напрямок розтягу * * * *
1 1 1( )/ || ||,k k k k kg g g g де * *
1,k kg g
– субградієнти
на ітераціях 1,k k у перетвореному просторі .kY Значення коефіцієнтів розтягу
простору k (параметр r-алгоритму) вибираються однаковими на всіх ітераціях:
1.k На практиці рекомендується вибирати це значення порядку 2. Розмір
крокового множника визначається процедурою мінімізації за напрямком
* */ || || .k k k kp B g g Застосовувані процедури є досить грубою реалізацією алгоритму
локалізації мінімуму за напрямком kp [1], [2]. Основною вимогою при цьому є
виконання умови 1( , ( )) 0k kp g x (ця умова забезпечує, що * *
1|| || 0k kg g ).
r(σ)-алгоритми. Обчислювальна схема r(σ)-алгоритмів переважно відповідає
r-алгоритму. Відмінність полягає лише в наступному. Замість оператора розтягу [2]
( ) ( 1) , || || 1TR I буде використовуватися наступний оператор
( ) ,TR I де ;nR – нормуючий множник, 1, 0;R –
додатне число. Число визначається таким чином, щоб значення коефіцієнтів
розтягу для всіх ітерацій були обмежені:
maxk . Тут
max 1 є вхідним
параметром алгоритму. Параметр
max у попередніх версіях r(σ)-алгоритмів був
відсутній.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 83-86
85
На відміну від оператора ( ),R вектор не нормовано, тобто виконання
умови || || 1 не вимагається. Легко бачити, що якщо 0, то ( ) ( / || ||)R R ,
де
21 || || . (4)
Зауважимо, що якщо 0, то 1, ( )R I (незалежно від множника ).
Значення нормуючого множника визначатиметься на підставі двох
послідовних субградієнтів * *
1,k kg g
у перетвореному просторі (обчислених на
ітераціях k і 1k ): * *
1 1( , ).k k kg g Природною вимогою на функцію
1 2( , )g g
буде виконання умови:
1 2( , )g g 2
1 2( , ) / ,g g де 1, 0.R Ця умова
забезпечує незалежність роботи алгоритму від множника на цільову функцію. Різні
варіанти алгоритму будуть визначатися вибором множника та значенням
параметра
max . Відмітимо, що r(σ)-алгоритм з нормуючим множником
2
0 1 2 2 1( , ) 1/ || ||g g g g та 1 фактично є r-алгоритмом з коефіцієнтом розтягу,
що дорівнює 2. Зазначимо, що це значення рекомендується при використанні
r-алгоритму.
Приклади нормуючих множників.
1. Алгоритм 1( ) :r 2 2
1 2 1 2( , ) 1/ (|| || || || );g g g g
max( 1) / 3.
2. Алгоритм
2( ) :r 2 2
2 1 2 1 2( , ) 1/ max{|| || ,|| || };g g g g
max( 1) / 4.
Якщо в якості вектора вибирається вектор * *
1 1k k kg g (за аналогією з
r-алгоритмом), то ми отримуємо модифікації r-алгоритму з програмним визначенням значень
коефіцієнтів розтягу простору (відповідно до формули (4)).
Особливий інтерес становить алгоритм з розтягом простору за напрямком різниці
нормованих субградієнтів –
nr -алгоритм. У
nr -алгоритмі вектор
* * * *
1 1 1/ || || / || ||k k k k kg g g g . Для цього алгоритму нормуючий множник можна
покласти рівним 1:
1 2( , ) 1.n g g При цьому
max( 1) / 4 .
Пояснимо зміст оператора ( )R на прикладі
nr -алгоритму. З рівності (4) випливає,
що
1 max 11 ( 1)(1 cos( )) / 2,k k де
1k
– кут між векторами * *
1, .k kg g Таким чином,
значення коефіцієнта розтягу на ітерації
nr -алгоритму має тим більше значення, чим більший
кут між векторами * *
1,k kg g . Максимальне значення коефіцієнта розтягу (
max ) досягається
при куті, що дорівнює . При куті, що дорівнює нулю, коефіцієнт розтягу дорівнює 1 (тобто
фактично перетворення простору не виконується).
У r(σ)-алгоритмах значення крокового множника можна визначати як і в r-алгоритмі – з
урахуванням використання процедури одномірного спуску. Однак, суттєво, що r(σ)-алгоритм
можна використовувати без процедури спуску за напрямком, з постійним кроком у
перетвореному просторі (параметр алгоритму). При цьому величина кроку у вихідному
просторі на ітераціях алгоритму визначатиметься (опосередковано) тільки операторами
перетворення, що використовуються. Зазначимо, що обчислювальна схема таких варіантів
r(σ)-алгоритмів значно простіша за схему r-алгоритму.
Микола Журбенко,Олексій Лиховид
Про одне сімейство субградієнтних алгоритмів з перетворенням простору
86
Для теоретичного обґрунтування збіжності r(σ)-алгоритмів пропонується наступний їх
варіант: максимальне значення коефіцієнта розтягу простору змінюється на ітераціях, тобто
визначається послідовність
max ( ).k Для цієї послідовності виконуються такі умови:
max ( ) 1;k
max ( ) 1k (коефіцієнти зменшуються); max
1
( )
k
j
j
(загальний розтяг
простору не обмежено). Приклад такої послідовності: /
max ( ) ;c kk e 0.c Зауважимо, що
така послідовність асоціюється з послідовністю вибору крокових множників у класичному
субградієнтному алгоритмі (крок прагне до нуля, сума кроків розходиться) [2].
У доповіді будуть представлені результати дослідження чисельної ефективності
сімейства алгоритмів, що розглядається.
Висновки. r(σ)-алгоритми є модифікаціями r-алгоритму. Обчислювальна схема
r(σ)-алгоритмів з постійним кроком суттєво простіше схеми r-алгоритму. Величини
коефіцієнтів розтягу простору на ітераціях r(σ)-алгоритмів не постійні, вони обчислюються у
процесі його роботи. Алгоритми можуть використовуватися з постійним кроковим
множником у перетвореному просторі. Чисельні експерименти показали досить високу
ефективність r(σ)-алгоритмів. Їхня ефективність не поступається ефективності r-алгоритму.
Результати дослідження чисельної ефективності показують, що найбільш ефективним
варіантом із сімейства r(σ)-алгоритмів є
nr -алгоритм.
Роботу частково підтримано грантом Volkswagen Foundation (грант № 97775).
Література
[1] Шор Н.З., Журбенко Н.Г. Метод минимизации, использующий операцию растяжения
пространства в направлении разности двух последовательных градиентов. Кибернетика. 1971.
№3. С. 51–59.
[2] Shor N.Z. Minimization methods for non-differentiable functions. Berlin: Springer-Verlag, 1985.
178 p.
[3] Журбенко Н.Г., Чумаков Б.М. Программное управление коэффициентами растяжения
r-алгоритма. Теорія оптимальних рішень. Київ: Ін-т кібернетики ім. В.М. Глушкова НАН
України, 2012. С. 113–118.
[4] Журбенко Н.Г. Численная эффективность одной модификации r-алгоритма. Теорія оптимальних
рішень. Київ: Інститут кібернетики ім. В.М. Глушкова НАН України. 2017. С. 33–38.
[5] Журбенко Н.Г., Лиховид А.П. К численной эффективности одной модификации r-алгоритма.
Комп’ютерна математика. К.: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 2019. № 1.
С. 2–10.
On one family of subgradient algorithms with space transformation
Mykola Zhurbenko, Oleksii Lykhovyd
The article presents a brief description of the results of the development of a family of subgradient algorithms for
minimization using dilation operators of space of variables (r(σ)-algorithms). r(σ)-algorithms are modifications of
N.Z. Shor's r-algorithm. Unlike r-algorithm, the values of space dilation coefficients in r(σ)-algorithms are
programmatically determined during the execution of the algorithm. It is essential that to determine the values of step
coefficients in r(σ)-algorithms, there is no need to use the procedure of one-dimensional minimization in the direction –
the algorithms can be used with a constant step in the transformed space of variables.
Отримано 25.03.23
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-281 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:09:37Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/f8/65dab51058c115940315f147f107a7f8.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-2812025-02-21T17:32:19Z On one family of subgradient algorithms with space transformation Про одне сімейство субградієнтних алгоритмів з перетворенням простору Zhurbenko, Mykola Lykhovyd, Oleksii негладка оптимізація, субградієнтний алгоритм, перетворення простору, чисельна ефективність The article presents a brief description of the results of the development of a family of subgradient algorithms for minimization using dilation operators of space of variables (r(σ)-algorithms). r(σ)-algorithms are modifications of N.Z. Shor's r-algorithm. Unlike r-algorithm, the values of space dilation coefficients in r(σ)-algorithms are programmatically determined during the execution of the algorithm. It is essential that to determine the values of step coefficients in r(σ)-algorithms, there is no need to use the procedure of one-dimensional minimization in the direction – the algorithms can be used with a constant step in the transformed space of variables. У статті наведено короткий опис результатів розробки сімейства субградієнтних алгоритмів мінімізації з використанням операторів розтягу простору змінних (r(σ)-алгоритмів). r(σ)-алгоритми є модифікаціями r-алгоритму Н.З. Шора. На відміну від r-алгоритму, значення коефіцієнтів розтягу простору в r(σ)-алгоритмах визначаються програмно під час виконання алгоритму. Суттєво, що в r(σ)-алгоритмах немає необхідності використовувати процедуру одновимірної мінімізації за напрямком – алгоритми можна використовувати з постійним кроком у перетвореному просторі змінних. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-13 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/281 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 83-86 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 83-86 2617-5258 1816-1545 10.15407/fmmit2023.36 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/281/249 Авторське право (c) 2023 Микола Журбенко, Олексій Лиховид (Автор) |
| spellingShingle | негладка оптимізація субградієнтний алгоритм перетворення простору чисельна ефективність Zhurbenko, Mykola Lykhovyd, Oleksii Про одне сімейство субградієнтних алгоритмів з перетворенням простору |
| title | Про одне сімейство субградієнтних алгоритмів з перетворенням простору |
| title_alt | On one family of subgradient algorithms with space transformation |
| title_full | Про одне сімейство субградієнтних алгоритмів з перетворенням простору |
| title_fullStr | Про одне сімейство субградієнтних алгоритмів з перетворенням простору |
| title_full_unstemmed | Про одне сімейство субградієнтних алгоритмів з перетворенням простору |
| title_short | Про одне сімейство субградієнтних алгоритмів з перетворенням простору |
| title_sort | про одне сімейство субградієнтних алгоритмів з перетворенням простору |
| topic | негладка оптимізація субградієнтний алгоритм перетворення простору чисельна ефективність |
| topic_facet | негладка оптимізація субградієнтний алгоритм перетворення простору чисельна ефективність |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/281 |
| work_keys_str_mv | AT zhurbenkomykola ononefamilyofsubgradientalgorithmswithspacetransformation AT lykhovydoleksii ononefamilyofsubgradientalgorithmswithspacetransformation AT zhurbenkomykola proodnesímejstvosubgradíêntnihalgoritmívzperetvorennâmprostoru AT lykhovydoleksii proodnesímejstvosubgradíêntnihalgoritmívzperetvorennâmprostoru |