К численной эффективности одной модификации r-алгоритма

К численной эффективности одной модификации r-алгоритма

Рассматривается одна модификация r-алгоритма – алгоритма минимизации с использованием операции растяжения пространства в направлении разности двух последовательных субградиентов. В отличие от r-алгоритма, значения коэффициентов растяжения в предложенной модификации рассчитываются в процессе работы а...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2019
Автори: Журбенко, Н.Г., Лиховид, А.П.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Назва видання:Компьютерная математика
Теми:
Теория и методы оптимизации
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/161942
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:К численной эффективности одной модификации r-алгоритма / Н.Г. Журбенко, А.П. Лиховид // Компьютерная математика. — 2019. — № 1. — С. 124-131. — Бібліогр.: 5 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-161942
record_format dspace
spelling irk-123456789-1619422019-12-28T01:26:27Z К численной эффективности одной модификации r-алгоритма Журбенко, Н.Г. Лиховид, А.П. Теория и методы оптимизации Рассматривается одна модификация r-алгоритма – алгоритма минимизации с использованием операции растяжения пространства в направлении разности двух последовательных субградиентов. В отличие от r-алгоритма, значения коэффициентов растяжения в предложенной модификации рассчитываются в процессе работы алгоритма. Алгоритм может использоваться с постоянным шагом. Приводятся результаты исследования численной эффективности алгоритма. Розглядається одна модифікація r-алгоритму – алгоритму мінімізації з використанням операції розтягування простору в напрямку різниці двох послідовних субградієнтів. На відміну від r-алгоритму, значення коефіцієнтів розтягування в запропонованій модифікації розраховуються в процесі роботи алгоритму. Алгоритм може використовуватися з постійним кроком. Наводяться результати дослідження чисельної ефективності алгоритму. We consider a modification of the r-algorithm, the minimization algorithm using the operation of space dilation in the direction of the difference of two successive subgradients. In contrast to the r-algorithm, the proposed modification of the algorithm calculate the values of dilation coefficients . The algorithm can be used with a constant step. The results of the study of the numerical efficiency of the algorithm are given. 2019 Article К численной эффективности одной модификации r-алгоритма / Н.Г. Журбенко, А.П. Лиховид // Компьютерная математика. — 2019. — № 1. — С. 124-131. — Бібліогр.: 5 назв. — рос. 2616-938Х http://dspace.nbuv.gov.ua/handle/123456789/161942 519.8 ru Компьютерная математика Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
topic Теория и методы оптимизации
Теория и методы оптимизации
spellingShingle Теория и методы оптимизации
Теория и методы оптимизации
Журбенко, Н.Г.
Лиховид, А.П.
К численной эффективности одной модификации r-алгоритма
Компьютерная математика
description Рассматривается одна модификация r-алгоритма – алгоритма минимизации с использованием операции растяжения пространства в направлении разности двух последовательных субградиентов. В отличие от r-алгоритма, значения коэффициентов растяжения в предложенной модификации рассчитываются в процессе работы алгоритма. Алгоритм может использоваться с постоянным шагом. Приводятся результаты исследования численной эффективности алгоритма.
format Article
author Журбенко, Н.Г.
Лиховид, А.П.
author_facet Журбенко, Н.Г.
Лиховид, А.П.
author_sort Журбенко, Н.Г.
title К численной эффективности одной модификации r-алгоритма
title_short К численной эффективности одной модификации r-алгоритма
title_full К численной эффективности одной модификации r-алгоритма
title_fullStr К численной эффективности одной модификации r-алгоритма
title_full_unstemmed К численной эффективности одной модификации r-алгоритма
title_sort к численной эффективности одной модификации r-алгоритма
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2019
topic_facet Теория и методы оптимизации
url http://dspace.nbuv.gov.ua/handle/123456789/161942
citation_txt К численной эффективности одной модификации r-алгоритма / Н.Г. Журбенко, А.П. Лиховид // Компьютерная математика. — 2019. — № 1. — С. 124-131. — Бібліогр.: 5 назв. — рос.
series Компьютерная математика
work_keys_str_mv AT žurbenkong kčislennojéffektivnostiodnojmodifikaciiralgoritma
AT lihovidap kčislennojéffektivnostiodnojmodifikaciiralgoritma
first_indexed 2025-07-14T14:31:50Z
last_indexed 2025-07-14T14:31:50Z
_version_ 1837633121461207040
fulltext 124 ISSN 2616-938X. Компьютерная математика. 2019, № 1 Теория и методы оптимизации Рассматривается одна модифи- кация r-алгоритма – алгоритма минимизации с использованием операции растяжения простран- ства в направлении разности двух последовательных субградиентов. В отличие от r-алгоритма, значе- ния коэффициентов растяжения в предложенной модификации рассчитываются в процессе ра- боты алгоритма. Алгоритм мо- жет использоваться с постоян- ным шагом. Приводятся резуль- таты исследования численной эф- фективности алгоритма.  Н.Г. Журбенко, А.П. Лиховид, 2019 УДК 519.8 Н.Г. ЖУРБЕНКО, А.П. ЛИХОВИД К ЧИСЛЕННОЙ ЭФФЕКТИВНОСТИ ОДНОЙ МОДИФИКАЦИИ R-АЛГОРИТМА1 Рассматривается задача безусловной мини- мизации субдифференцируемой функции ( )f x в nR . Предполагается, что в произволь- ной точке nx R для функции ( )f x опреде- лен субградиент – вектор ( ) .ng x R Обозна- чим ( )f x – множество субградиентов функ- ции ( )f x в точке .x Эффективным алгорит- мом минимизации субдифференцируемой функции является r-алгоритм – алгоритм, использующий операцию растяжения про- странства в направлении разности двух по- следовательных субградиентов [1], [2]. r-алгоритм относится к классу субградиент- ных алгоритмов с преобразованием про- странства. Численная схема r -алгоритма. В r -ал- горитме в качестве оператора преобразова- ния пространства используется оператор рас- тяжения пространства по направлению [2]: ( ) ( 1) .TR I      ,nR  направ- ление и коэффициент растяжения про- странства, || || 1, 1.    Заметим, что 1( ) ( ),R R     1/ .   * ( ) ( )R R    ( ( )R  – самосопряженный оператор). Вычислительная схема r -алгоритма применительно к задаче отыскания без- условного минимума функции ( )f x состоит в следующем. 1Работа выполнена при частичной поддержке Volkswagen Foundation (грант No 90 306 – Н. Г. Журбенко)). К ЧИСЛЕННОЙ ЭФФЕКТИВНОСТИ ОДНОЙ МОДИФИКАЦИИ R-АЛГОРИТМА ISSN 2616-938X. Компьютерная математика. 2019, № 1 125 0-ый шаг алгоритма. Выбираем начальное приближение 0 0x X ( 0X – исходное пространство пе- ременных) и невырожденное линейное преобразование 0 .A пространства 0 .X 0 0 0 .Y A X – преобразованное пространство, 0 0 0 ,X B Y где 1 0 .B A Вычисляем: 1) 0 0( ) ( )g x f x (субградиент в точке 0x ); 2) * * 0 0 0g B g – субградиент в преобразованном пространстве 0 0 0 .Y A X Переходим к первому шагу алгоритма. Пусть на шаге k алгоритма ( 0,1,2, )k   получены определенные значения векторов ,kx * kg (субградиент в преобразованном пространстве) и матрицы kB (обратная матрица преобразова- ния пространства). ( 1)k  -вый шаг алгоритма ( 0,1,2, ).k   Вычисляем: 1) 1kh   шаговый множитель, 1 0;kh   2) * * 1 1 / || ||;k k k k k kx x h B g g   вычисление 1kx  соответствует субградиент- ный шагу в преобразованном пространстве kY по нормированному субградиен- ту: * * 1 1 / || ||;k k k k ky y h g g   3) 1( ) ( );k kg x f x  (субградиент в точке 1kx  исходного пространства 0X ); 4) * * 1 1( )k k kg B g x  (субградиент в преобразованном пространстве 0k kY A X ); 5) * * * * 1 1 1( )/ || ||k k k k kg g g g       (направление растяжения пространства kY ); 6) 1 1 11, 1 /k k k       ( k коэффициент растяжения пространства kY ); 7) 11 ( ), kk k kB B R    (обратный оператор преобразования пространства 1 1 0k kY A X  ); 8) 1 * 1 1 1( ) kk k kg R g      * * 1 1( ( ).k k kg B g x  (субградиент в преобразованном пространстве 1 1k kY A X  ). Переходим к ( 2)k  -му шагу алгоритма, или прекращаем работу при вы- полнении критерия останова. В известных вариантах r -алгоритма выбор коэффициентов растяжения пространства и шаговых множителей определяется следующим образом. Значе- ния коэффициентов растяжения пространства k выбираются одинаковыми на всех итерациях: 1.k     – параметр r -алгоритма. На практике рекоменду- ется значение  выбирать порядка 2.0. Величина шагового множителя опреде- ляется выбранной процедурой минимизации (процедурой «спуска») по направ- лению * */ || || .k k k kp B g g  Применяемые процедуры являются достаточно грубой реализацией алгоритма локализации минимума по направлению .kp Основное требование при этом – это выполнение условия: 1( , ( )) 0k kp g x   (это условие обеспечивает, что * * 1|| || 0k kg g   ). Н.Г. ЖУРБЕНКО, А.П. ЛИХОВИД 126 ISSN 2616-938X. Компьютерная математика. 2019, № 1 Наиболее часто используется следующая процедура регулировки шаговых множителей. Пусть на ( 1)k  -ой итерации помимо точки ,kx вектора спуска kp определено значение «пробного шага» 0.kh  Значение 0h – параметр r -алго- ритма – «величина начального шага». Пусть заданы числа 10 1,q  2 1q  и целое число 2.L  Эти величины яв- ляются параметрами (константами) алгоритма. Они будут определять регули- ровку величин пробного шага. Параметр 1q используется для уменьшения проб- ного шага, а 2q – для его увеличения. Положим 0 .kz x Вычисляем: 1 ;i i k kz z h p   ( ) ( ),i i ig g z f z  1,2, ,i   до тех пор, пока при некотором i l выполнится неравенство ( , ) 0.i kg p  Тогда 1 .k lx z  Если 1,l  то 1 1: .k kh q h   Наиболее часто используются следующие значения параметров регулировки пробного шага 1 0.9,q  2 1.1,q  3.L  Вычислительная схема ( )r  -алгоритмов. Вычислительная схема ( )r  -алгоритмов соответствует приведенной схеме r -алгоритма. Отличие со- стоит лишь в следующем. Вместо оператора растяжения ( )R  используется следующий оператор: ( ) .TR I        (1) Здесь  – вектор в ,nR  – нормирующий множитель, 1,R 0.  В отличие от оператора ( ),R  вектор  не нормирован, т. е. выполнение условия || || 1  не требуется. Различные варианты алгоритма будут определяться выбором нормирующего множителя . Далее будут рассмотрены несколько вариантов такого выбора. Остановимся на простейших свойствах оператора ( )R   и его связи с опе- ратором ( ).R  Обратный к ( )R  оператор 1( )R   определяется следующим образом:  1 2( ) / (1 ) .TR I              Очевидно, что (0)R I  (при этом значение нормирующего множителя не имеет значения). Пусть || || 0  и / || || .     Тогда ( ) ( ),R R     где 21 || || .     (2) К ЧИСЛЕННОЙ ЭФФЕКТИВНОСТИ ОДНОЙ МОДИФИКАЦИИ R-АЛГОРИТМА ISSN 2616-938X. Компьютерная математика. 2019, № 1 127 Таким образом, если 0,  то оператор ( )R   – оператор растяжения по направлению / || ||   с указанным значением коэффициента растяжения (2). Формально, для 0  можно считать, что коэффициент растяжения равен 1, так как в этом случае оператор ( )R   равен .I Значение нормирующего множителя  будет определяться на основании двух последовательных субградиентов * * 1,k kg g в преобразованном пространстве. Естественным требованием на функцию 1 2( , )g g будет выполнение следу- ющего условия (условия «однородности»): 2 1 2 1 2( , ) ( , ) / ,g g g g      где 1, 0.R   Это условие обеспечивает независимость работы алгоритма от множителя на целевую функцию. Легко видеть, что алгоритм 0( ) :r  2 0 1 2 2 1( , ) 1/ || ||g g g g   фактически яв- ляется r -алгоритмом с коэффициентом растяжения равным 2. Любопытно отметить, что именно это значение рекомендуется на практике использования r -алгоритма. Однако в r -алгоритме (и 0( )r  -алгоритме) необходимо преду- смотреть выполнение условия 2 1|| || 0.g g  Это условие обеспечивается выше- приведенной процедурой регулировки шаговых множителей (процедурой при- ближенного спуска по антисубградиенту). Выбирая различные нормирующие множители , мы будем получать раз- личные алгоритмы рассматриваемого класса. Проблема рационального выбора этих множителей требует дальнейшего исследования. Приведем примеры нор- мирующих множителей (помимо приведенного 0( )r  ). 1. 1( )r  -алгоритм: 2 1 1 2 1 2( , ) 1/ || { , } || ,g g Nr g g  где 1 2{ , }Nr g g – кратчайший вектор выпуклой оболочки векторов 1 2, .g g 2. 2( )r  -алгоритм: 2 1 2 2 1( , ) 1 / (|| || * || ||).g g g g  3. 3( )r  -алгоритм: 2 2 3 1 2 1 2( , ) 1 / max{|| || ,|| || }.g g g g  Для алгоритмов 1( ),r  2( )r  значения коэффициентов растяжения не огра- ничены: 11 .k    Для алгоритма 3( )r  значения коэффициентов ограничены: 11 5.k   В данной работе приводятся результаты исследования численной эффек- тивности алгоритма 3( )r  (для 1( ),r  2( )r  такие результаты приведены в работах [3, 4]). Численная эффективность 3( )r  -алгоритма. Приведем результаты чис- ленных исследований эффективности алгоритма 3( )r  в сравнении с r -алго- ритмом ( 0( )r  -алгоритмом). Н.Г. ЖУРБЕНКО, А.П. ЛИХОВИД 128 ISSN 2616-938X. Компьютерная математика. 2019, № 1 Рассматривались три тестовые задачи. Первая и вторая тестовые задачи являлись задачами минимизации следую- щих двух функций: 1 2 1 1 ( ) , n i n i i f x x    1 2 1 ( ) | |, n i n i i f x x    где параметр n выбирался в зависимости от размерности задачи n по формуле 6/( 1)10 .n n   Таким образом, степень вытянутости линий уровня («овражности») функций определяется значением параметра 1 610 ,n n   она одинакова для всех функций независимо от числа переменных. Начальная точка 1.0, 1,2,... .ix i n  Критерий останова: 610 ,kf  где kf – значение функции на итерации останова .k Третья тестовая задача – это задача минимизации функции Лемарешаля [5]. Задача состоит в минимизации существенно овражной выпуклой негладкой функции от 10 переменных: 3 1 5 ( ) max ( ) mink xk f x f x     , где ( ) ( ) ( )T T k k kf x x A x b x  , kA – симметричные 10 10 -матрицы, такие, что / cos( )sini j kijA e ij k , если i j , и sin /10kii kij j i A i k A    , а компоненты векто- ров kb определяются / sin( )i k kib e ik . Начальное приближение – это точка 10 0 (1, ,1)Tx R  , в которой реализуется значение функции 0 5337.0 643( ) 6f x  . Функция имеет единственную точку минимума. Минимальное значение функ- ции * 3 ( )f x определяется его достаточно точным приближением * min 0.841408334596f   (с точностью 1210 , 12 цифр после точки). Результаты решения тестовых задач приведены в таблицах 1, 2, 3 соответ- ственно, где приняты следующие обозначения: n – размерность пространства переменных; k – номер итерации, на которой алгоритм прекратил работу; kg – количество вычислений обобщенного градиента; max – максимальное значение коэффициента растяжения; avrg – среднее значение коэффициента растяжения; r – результаты работы r -алгоритма с параметрами 1 2 1.q q  В алгоритмах, отмеченных символом “ * ”, используется постоянная величи- на шага (в преобразованном пространстве). В алгоритмах, не отмеченных символом “ * ”, используется вышеописанная регулировка шаговых множителей r-алгоритма. К ЧИСЛЕННОЙ ЭФФЕКТИВНОСТИ ОДНОЙ МОДИФИКАЦИИ R-АЛГОРИТМА ISSN 2616-938X. Компьютерная математика. 2019, № 1 129 ТАБЛИЦА 1. Минимизация функции 1( )f x Параметры Алгоритм n k gk max avrg 3( )r  100 926 1136 4.90179 2.79076 * 3( )r  100 999 1000 4.80209 2.547 r 100 1197 1382 2.00 2.00 3( )r  300 2737 3301 4.65948 2.79623 * 3( )r  300 2961 2962 4.76045 2.59546 r 300 3416 3898 2.00 2.00 3( )r  1000 8784 9690 4.92057 2.73933 * 3( )r  1000 9271 9272 4.62152 2.62127 r 1000 10926 11930 2.00 2.00 ТАБЛИЦА 2. Минимизация функции 2 ( )f x Параметры Алгоритм n k gk max avrg 3( )r  100 2332 2343 3.47955 2.65213 * 3( )r  100 2330 2331 3.26849 2.65078 r 100 3258 3267 2.00 2.00 3( )r  300 7186 7197 3.25877 2.64139 * 3( )r  300 7198 7199 3.13601 2.6406 r 300 10116 10123 2.00 2.00 3( )r  1000 24651 24673 3.20645 2.63744 * 3( )r  1000 28215 28216 2.43678 2.32715 r 1000 35186 35199 2.00 2.00 Н.Г. ЖУРБЕНКО, А.П. ЛИХОВИД 130 ISSN 2616-938X. Компьютерная математика. 2019, № 1 ТАБЛИЦА 3. Минимизация функции 3( )f x Параметры Алгоритм k gk max avrg * 3 ( )f x 3( )r  206 257 4.87506 2.73264 – 0.841408334593403 * 3( )r  285 286 4.57635 2.46481 – 0.841408334596392 r 343 388 2.00 2.00 – 0.841408334596395 Выводы. Предложенный субградиентный алгоритм с преобразованием про- странства можно рассматривать как модификацию r -алгоритма. Величины коэффициентов растяжения пространства на итерациях 3( )r  -алгоритма не постоянны, они вычисляются в процессе его работы. Алгоритм не требуют использования процедуры одномерного спуска по направлению. Он может ис- пользоваться с постоянным шаговым множителем. Численная схема * 3( )r  -алгоритма (алгоритм с постоянным шаговым множителем в преобразованном пространстве) существенно проще схемы r -алгоритма. В этом алгоритме единственным существенным параметром явля- ется значение шагового множителя. При этом значения управляющих парамет- ров процедуры одномерного спуска ( 1,q 2 ,q L ) не используются. В r -алго- ритме эти параметры и значение коэффициента растяжения пространства выби- раются из эвристических соображений. Численные эксперименты показали достаточно высокую эффективность 3( )r  -алгоритма. Его эффективность не уступает эффективности r -алгоритма (с параметрами 1 2 1q q  ). М.Г. Журбенко, О.П. Лиховид ДО ЧИСЕЛЬНОЇ ЕФЕКТИВНОСТІ ОДНІЄЇ МОДИФІКАЦІЇ R-АЛГОРИТМУ Розглядається одна модифікація r-алгоритму – алгоритму мінімізації з використанням операції розтягування простору в напрямку різниці двох послідовних субградієнтів. На відміну від r-алгоритму, значення коефіцієнтів розтягування в запропонованій модифікації розраховуються в процесі роботи алгоритму. Алгоритм може використовуватися з постійним кроком. Наводяться результати дослідження чисельної ефективності алгоритму. M.G. Zhurbenko, O.P. Lykhovyd ON THE NUMERICAL EFFICIENCY OF A MODIFICATION OF R-ALGORITHM We consider a modification of the r-algorithm, the minimization algorithm using the operation of space dilation in the direction of the difference of two successive subgradients. In contrast to the r-algorithm, the proposed modification of the algorithm calculate the values of dilation coefficients . The algorithm can be used with a constant step. The results of the study of the numerical efficiency of the algorithm are given. К ЧИСЛЕННОЙ ЭФФЕКТИВНОСТИ ОДНОЙ МОДИФИКАЦИИ R-АЛГОРИТМА ISSN 2616-938X. Компьютерная математика. 2019, № 1 131 Список литературы 1. Шор Н.З., Журбенко Н.Г. Метод минимизации, использующий операцию растяжения пространства в направлении разности двух последовательных градиентов. Кибернетика. 1971. № 3. С. 51 – 59. 2. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. К.: Наук. думка, 1979. 199 с. 3. Журбенко Н.Г., Чумаков Б.М. Программное управление коэффициентами растяжения r-алгоритма. Теорія оптимальних рішень. Київ: Ін-т кібернетики імені В.М. Глушкова НАН України. 2012. С. 113–118. 4. Журбенко Н.Г. Численная эффективность одной модификации r-алгоритма. Теорія оп- тимальних рішень. Київ: Інститут кібернетики імені В.М. Глушкова НАН України. 2017. С. 33 – 38. 5. Nonsmooth optimization. Eds. C. Lemareshal, R. Mifflin. Oxford: Pergamon Press, 1978. 186 p. Получено 19.04.2019 Об авторах: Журбенко Николай Георгиевич, кандидат физико-математических наук, старший научный сотрудник Института кибернетики имени В.М. Глушкова НАН Украины, E-mail: zhurbnick@gmail.com Лиховид Алексей Петрович, научный сотрудник Института кибернетики имени В.М. Глушкова НАН Украины. E-mail: o.lykhovyd@gmail.com

Схожі ресурси