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

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

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

Повний опис

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

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-131435
record_format dspace
spelling irk-123456789-1314352018-03-24T03:03:05Z Численная эффективность одной модификации r-алгоритма Журбенко, Н.Г. Рассматривается модификация r-алгоритма – алгоритма минимизации с использованием операции растяжения пространства в направлении разности двух последовательных субградиентов. В отличие от r-алгоритма, значения коэффициентов растяжения в предложенной модификации программно рассчитываются в процессе работы алгоритма. Алгоритм может использоваться с постоянным шагом. Приводятся результаты исследования численной эффективности алгоритма. Розглядається модифікація r-алгоритму – алгоритму мінімізації з використанням операції розтягування простору в напрямку різниці двох послідовних субградієнтів. На відміну від r-алгоритму, значення коефіцієнтів розтягування у запропонованій модифікації програмно розраховуються в процесі роботи алгоритму. Алгоритм може використовуватися з постійним кроком. Наводяться результати дослідження чисельної ефективності алгоритму. The modification of r-algorithm, the minimization algorithm using space dilation operation along the direction of the difference of two successive subgradients, is considered. In contrast to r-algorithm, in the proposed modification the values of dilation coefficients are calculated during the execution of the algorithm. The algorithm can be used with a constant step size. The results of the study of the numerical efficiency of the algorithm are presented. 2017 Article Численная эффективность одной модификации r-алгоритма / Н.Г. Журбенко // Теорія оптимальних рішень: Зб. наук. пр. — 2017. — № 2017. — С. 33-38. — Бібліогр.: 4 назв. — рос. 2616-5619 http://dspace.nbuv.gov.ua/handle/123456789/131435 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
description Рассматривается модификация r-алгоритма – алгоритма минимизации с использованием операции растяжения пространства в направлении разности двух последовательных субградиентов. В отличие от r-алгоритма, значения коэффициентов растяжения в предложенной модификации программно рассчитываются в процессе работы алгоритма. Алгоритм может использоваться с постоянным шагом. Приводятся результаты исследования численной эффективности алгоритма.
format Article
author Журбенко, Н.Г.
spellingShingle Журбенко, Н.Г.
Численная эффективность одной модификации r-алгоритма
Теорія оптимальних рішень
author_facet Журбенко, Н.Г.
author_sort Журбенко, Н.Г.
title Численная эффективность одной модификации r-алгоритма
title_short Численная эффективность одной модификации r-алгоритма
title_full Численная эффективность одной модификации r-алгоритма
title_fullStr Численная эффективность одной модификации r-алгоритма
title_full_unstemmed Численная эффективность одной модификации r-алгоритма
title_sort численная эффективность одной модификации r-алгоритма
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2017
url http://dspace.nbuv.gov.ua/handle/123456789/131435
citation_txt Численная эффективность одной модификации r-алгоритма / Н.Г. Журбенко // Теорія оптимальних рішень: Зб. наук. пр. — 2017. — № 2017. — С. 33-38. — Бібліогр.: 4 назв. — рос.
series Теорія оптимальних рішень
work_keys_str_mv AT žurbenkong čislennaâéffektivnostʹodnojmodifikaciiralgoritma
first_indexed 2025-07-09T15:26:14Z
last_indexed 2025-07-09T15:26:14Z
_version_ 1837183562029203456
fulltext Теорія оптимальних рішень. 2017 33 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Рассматривается модификация r-алгоритма – алгоритма мини- мизации с использованием опера- ции растяжения пространства в направлении разности двух по- следовательных субградиентов. В отличие от r-алгоритма, значе- ния коэффициентов растяжения в предложенной модификации программно рассчитываются в процессе работы алгоритма. Ал- горитм может использоваться с постоянным шагом. Приводятся результаты исследования числен- ной эффективности алгоритма.  Н.Г. Журбенко, 2017 УДК 519.8 Н.Г. ЖУРБЕНКО ЧИСЛЕННАЯ ЭФФЕКТИВНОСТЬ ОДНОЙ МОДИФИКАЦИИ r -АЛГОРИТМА  Введение. Более 40 лет назад разработан субградиентный алгоритм минимизации с растяжением пространства в направлении разности двух последовательных градиентов – r-алгоритм [1]. Практика использования r-алгоритма показывает, что до настоящего времени – это один из наиболее эффектив- ных алгоритмов негладкой оптимизации. Од- нако теоретическое исследование эффектив- ности алгоритма далеко не закончено. Ос- новная проблема теоретического обоснова- ния r-алгоритма состоит в согласованном выборе значений коэффициента растяжения пространства и шагового множителя. В рабо- те [2] предложено семейство модификаций r-алгоритма – ( )r  -алгоритмы. Величины ко- эффициентов растяжения пространства на итерациях ( )r  -алгоритмов не постоянны, они вычисляются в процессе его работы. Алгоритмы не требуют использования проце- дуры одномерного спуска по направлению. В работе [3] приведены результаты исследова- ния численной эффективности конкретных вариантов ( )r  -алгоритмов. В данной работе предлагается новая модификация r-алгоритма из этого семейства и приводятся результаты численного исследования ее эффективности. Численная схема r-алгоритма. Рассмат- ривается задача безусловной минимизации субдифференцируемой функции ( )f x в .nR *Работа выполнена при частичной поддержке Volkswagen Foundation (грант № 90 306). Н.Г. ЖУРБЕНКО 34 Теорія оптимальних рішень. 2017 ( )f x обозначим множество субградиентов функции ( )f x в точке .x В r -алго- ритме используется оператор растяжения пространства [4] ( ) ( 1) ,TR I     где ,nR  – направление и коэффициент растяжения пространства, | | 1, 0.   Вычислительная схема r -алгоритма применительно к задаче отыс- кания безусловного минимума функции ( )f x состоит в следующем. 0-ой шаг алгоритма (инициализация). Выбираем начальное приближение 0x и невырожденное линейное преобразование 0.B Вычисляем: 0 0( ) ( )g x f x ; * * 0 0 0( )g B g x (субградиент в преобразованном пространстве 1 0 0 0 ,Y B X A X  X – исходное пространство). Пусть на шаге k алгоритма ( 0,1,2, )k  получены определенные значения векторов ,kx * kg (субградиент в преобразованном про- странстве) и матрицы .kB ( 1 k kA B – матрица преобразования пространства). (k + 1)-й шаг алгоритма ( 0,1,2, ).k  Вычисляем: 1) 1kh   шаговый множитель, 1 0;kh   2) * * 1 1 / | |;k k k k k kx x h B g g   3) 1( ) ( ),k kg x f x  (субградиент в точке 1kx  ); 4) * * 1 1( )k k kg B g x  (субградиент в преобразованном пространстве k 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 1 1k k kY A X B X     ); 8) 1 * 1 1 1( ) kk k kg R g      * * 1 1( ( ),k k kg B g x  (субградиент в преобразованном пространстве 1 1 1 1k k kY A X B X     ). Переходим к ( 2)k  -му шагу алгоритма или прекращаем работу при выполнении критерия останова. В r -алгоритме значения коэффициентов растяжения пространства (пара- метр r -алгоритма) выбираются одинаковыми на всех итерациях: 1.k   На практике рекомендуется это значение выбирать порядка 2.0. Величина шагового множителя определяется процедурой минимизации («спуска») по направлению * */ | | .k k kB g g Обычно применяемые процедуры «спуска» являются достаточно грубой реализацией алгоритма локализации минимума по направлению. Наибо- лее часто используется процедура адаптивной регулировки шаговых множителей [1, 4]. Эта процедура определяется параметрами 10 1,q  2 1q  и целым чис- лом 2.L  Эти величины являются параметрами (константами) алгоритма. ЧИСЛЕННАЯ ЭФФЕКТИВНОСТЬ ОДНОЙ МОДИФИКАЦИИ r-АЛГОРИТМА Теорія оптимальних рішень. 2017 35 Вычислительная схема r ( )-алгоритмов соответствует приведенной схе- ме r -алгоритма. Отличие состоит лишь в следующем. Вместо оператора растя- жения ( )R   используем оператор ( ) ( 1) ,TR I     (1) где ,nR  – нормирующий множитель, 1,R 0.  В отличие от операто- ра ( ),R  вектор  не нормирован, т. е. выполнение условия | | 1  не требует- ся. Различные варианты алгоритма будут определяться выбором нормирующего множителя . Отметим простейшие свойства оператора ( ) :R  * ;R R 1( )R    2/ (1 ) ;T I       (0)R I  . Пусть | | 0  и / | | .   Тогда ( ) ( ) ,R R I    где 21 | | .    (2) Таким образом, если 0, то оператор ( )R  является оператором растя- жения по направлению / | | .  Значение коэффициента растяжения определяет- ся формулой (2). Значение нормирующего множителя  будет определяться на основании субградиентов (в преобразованном пространстве) * * 1, :k kg g * * 1 1( , ).k 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 -алгоритма. Выбирая различные нормирующие множители , мы будем получать различные алгоритмы рассматриваемого класса. В данной работе рассматривается 1( )r  -алгоритм с нормирующим множите- лем 1 1 2 2 1( , ) 1/ (| || |).g g g g  Основная особенность этого нормирующего мно- жителя состоит в следующем. Согласно (2) значение коэффициента растяжения определяется формулой 2 1 1 21 | | / | | | | / | | 2cos( ),g g g g     (3) где  – угол между субградиентами 2 1, .g g Отсюда следует, что значение коэф- фициента растяжения не ограничено сверху, оно может быть сколь угодно боль- Н.Г. ЖУРБЕНКО 36 Теорія оптимальних рішень. 2017 шим. Коэффициент может принимать большие значения в случае когда норма одного из субградиентов существенно больше нормы другого субградиента. Пусть, например, 2 1| | | | .g g Тогда направление растяжения пространства будет близким к направлению субградиента 2.g Поэтому операция растяжения про- странства будет существенно уменьшать значение 2 1| | / | | .g g То есть операция преобразования пространства будет направлена не только на уменьшение угла между субградиентами, но и на выравнивание их норм. Следует отметить, что это свойство может быть полезным в ситуации, когда по одним направлениям в точке минимума производная по направлению равна нулю, а по другим направ- лениям терпит разрыв (образно выражаясь, по одним направлениям функция гладкая, а по другим существенно не дифференцируемая). Численная эффективности 1( )r  -алгоритма. Приведем результаты численных исследований эффективности 1( )r  -алгоритма в сравнении с r -алгоритмом. Результаты численных исследований эффективности других вариантов алгоритм ( )r  приведены в [1, 2]. В качестве тестовых задач рассматривались задачи минимизации двух сле- дующих функций: 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 – значение функции на итерации останова. Результаты решения тестовых задач минимизации функций 1 2( ), ( )f x f x приведены в табл. 1 и 2 соответственно, где приняты следующие обозначения: 1( )r  – алгоритм с регулировкой шаговых множителей r-алгоритма; * 1( )r  – алгоритм с постоянным шагом; n – размерность пространства переменных; k – номер итерации, на которой алгоритм прекратил работу; gk – количество вы- числений субградиента; max – максимальное значение коэффициента растяже- ния; avrg – среднее значение коэффициента растяжения; r – результаты работы r -алгоритма с параметрами 1 2 1.q q  В алгоритмах отмеченных символом “ **” используется постоянная величина шага (в преобразованном простран- стве). В алгоритмах, не отмеченных символом “ **”, используется адаптивная ре- гулировка шаговых множителей r-алгоритма. ЧИСЛЕННАЯ ЭФФЕКТИВНОСТЬ ОДНОЙ МОДИФИКАЦИИ r-АЛГОРИТМА Теорія оптимальних рішень. 2017 37 ТАБЛИЦА 1 Параметры Алгоритм n k gk max avrg 1( )r  10 73 106 9.95 4.42 * 1( )r  10 78 79 9.39 3.94 r 10 135 168 2.00 2.00 1( )r  100 603 659 14.43 4.92 * 1( )r  100 629 630 12.36 4.83 r 100 1197 1382 2.00 2.00 1( )r  300 1775 1951 15.03 5.08 * 1( )r  300 1841 1842 15.03 4.98 r 300 3416 3898 2.00 2.00 1( )r  500 2972 3306 22.99 5.15 * 1( )r  500 3041 3042 27.43 5.00 r 500 6275 6946 2.00 2.00 ТАБЛИЦА 2 Параметры Алгоритм n k gk max avrg 1( )r  10 158 305 7.86 4.15 * 1( )r  10 181 182 7.52 3.64 r 10 304 350 2.00 2.00 1( )r  100 1536 1554 5.38 4.49 * 1( )r  100 1540 1541 5.76 4.49 r 100 3256 3264 2.00 2.00 1( )r  300 4669 4678 5.29 4.57 * 1( )r  300 4672 4673 5.22 4.57 r 300 10015 10023 2.00 2.00 1( )r  500 7847 7873 5.19 4.58 * 1( )r  500 7850 7851 5.19 4.58 r 500 16850 16864 2.00 2.00 Н.Г. ЖУРБЕНКО 38 Теорія оптимальних рішень. 2017 Выводы. 1( )r  -алгоритм – это модификация r -алгоритма. Вычислитель- ная схема 1( )r  -алгоритма с постоянным шагом существенно проще схемы r -алгоритма. Величины коэффициентов растяжения пространства на итерациях 1( )r  -алгоритма не постоянны, они вычисляются в процессе его работы. Алго- ритм может использоваться с постоянным шаговым множителем. Численные эксперименты показали достаточно высокую эффективность 1( )r  -алгоритма. М.Г. Журбенко ЧИСЕЛЬНА ЕФЕКТИВНІСТЬ ОДНІЄЇ МОДИФІКАЦІЇ r-АЛГОРИТМУ Розглядається модифікація r-алгоритму – алгоритму мінімізації з використанням операції роз- тягування простору в напрямку різниці двох послідовних субградієнтів. На відміну від r-алгоритму, значення коефіцієнтів розтягування у запропонованій модифікації програмно ро- зраховуються в процесі роботи алгоритму. Алгоритм може використовуватися з постійним кроком. Наводяться результати дослідження чисельної ефективності алгоритму. N.G. Zhurbenko NUMERICAL EFFICIENCY OF ONE MODIFICATION OF R-ALGORITHM The modification of r-algorithm, the minimization algorithm using space dilation operation along the direc- tion of the difference of two successive subgradients, is considered. In contrast to r-algorithm, in the proposed modification the values of dilation coefficients are calculated during the execu- tion of the algorithm. The algorithm can be used with a constant step size. The results of the study of the numerical efficiency of the algorithm are presented. 1. Шор Н.З., Журбенко Н.Г. Метод минимизации, использующий операцию растяжения пространства в направлении разности двух последовательных градиентов. Кибернети- ка. 1971. № 3. С. 51 – 59. 2. Журбенко Н.Г. Об одной модификации r-алгоритма. Материалы III Международной конференции. Математическое моделирование, оптимизация и информационные тех- нологии. Кишинеу: Эврика, 2012. С. 355 – 361. 3. Журбенко Н.Г., Чумаков Б.М. Программное управление коэффициентами растяжения r-алгоритма. Теорія оптимальних рішень. К.: Ін-т кібернетики імені В.М. Глушкова НАН України, 2012. С. 113 – 118. 4. Шор Н.З. Методы минимизации недифференцируемых функций и их применение. Киев: Наук. думка, 1979. 200 с. Получено 10.03.2017

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