Cover Image

Алгоритм Поляка на основе агрегатных ε-субградиентов

Предложена модификация субградиентного алгоритма Б.Т. Поляка. Алгоритм основан на использовании ε-субградиентов. Результаты численных расчетов показывают улучшение скорости сходимости алгоритма. Запропоновано модифікацію субградієнтного алгоритму Б.Т. Поляка. Алгоритм заснований на використанні ε-су...

Full description

Saved in:
Bibliographic Details
Published in:Теорія оптимальних рішень
Date:2015
Main Author: Журбенко, Н.Г.
Format: Article
Language:Russian
Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/112412
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:Алгоритм Поляка на основе агрегатных ε-субградиентов / Н.Г. Журбенко // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 146-153. — Бібліогр.: 4 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1859914201217105920
author Журбенко, Н.Г.
author_facet Журбенко, Н.Г.
citation_txt Алгоритм Поляка на основе агрегатных ε-субградиентов / Н.Г. Журбенко // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 146-153. — Бібліогр.: 4 назв. — рос.
collection DSpace DC
container_title Теорія оптимальних рішень
description Предложена модификация субградиентного алгоритма Б.Т. Поляка. Алгоритм основан на использовании ε-субградиентов. Результаты численных расчетов показывают улучшение скорости сходимости алгоритма. Запропоновано модифікацію субградієнтного алгоритму Б.Т. Поляка. Алгоритм заснований на використанні ε-субградієнтів. Результати чисельних розрахунків показують поліпшення швидкості збіжності алгоритму. A modification of B.T.Poljak’s subgradient algorithm is proposed. The algorithm is based on application of ε-subgradients. The numerical results show the convergences rate improvement of the algorithm.
first_indexed 2025-12-07T16:04:17Z
format Article
fulltext 146 Теорія оптимальних рішень. 2015 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Предложена модификация субгра- диентного алгоритма Б.Т. Поляка. Алгоритм основан на использова- нии ε-субградиентов. Результаты численных расчетов показывают улучшение скорости сходимости алгоритма.  Н.Г. Журбенко, 2015 УДК 519.8 Н.Г. ЖУРБЕНКО АЛГОРИТМ ПОЛЯКА НА ОСНОВЕ АГРЕГАТНЫХ -СУБГРАДИЕНТОВ  Введение. Субградиентный алгоритм Б.Т. Поляка [1] предназначен для решения задачи мини- мизации ограниченной снизу выпуклой функции )(xf в n -мерном евклидовом пространстве nR : .Rf(x)|xf n* }min{  При этом предполагается, что оптимальное значе- ние *f известно и множество точек мини- мума .* X Алгоритм определяется такой итеративной процедурой: 1 / | |,k k k k kx x h g g   (1) где *( ( ) )/ | |,k k kh f x f g   ( )k kg f x – множество субградиентов [2] в точке ,kx 0 2.   Алгоритм Поляка реализует теоре- тическую оценку скорости сходимости  kO /1 (для алгоритмов с равномерной по размерности пространства переменных скоростью). Алгоритм Поляка, также как классический субградиентный алгоритм Н.З. Шора [2], чрезвычайно прост по числен- ной реализации и до настоящего времени яв- ляется эффективным средством для решения задач больших размерностей. Хорошо известно [2], что малая скорость сходимости этих алгоритмов ярко прояв- ляется для «овражных» функций (функций с сильно вытянутыми линиями уровня). В данной работе делается попытка моди- фикации алгоритма Поляка для по- вышения его скорости сходимости для овражных функций. Алгоритм будет основан *При поддержке Национальной академии наук Украины (тема 0114U001055). АЛГОРИТМ ПОЛЯКА НА ОСНОВЕ АГРЕГАТНЫХ -СУБГРАДИЕНТОВ Теорія оптимальних рішень. 2015 147 на использовании  -субградиентов, его скорости сходимости для овражных функций. Алгоритм будет основан на использовании  -субградиентов. 1. Агрегатный  -субградиент. (Содержание данного пункта соответствует работе [3]). Для заданного числа 0  введем  -оптимальное множество *( ) :X  *( ) { .n *X x R | f(x) f      Произвольную точку *( )x X  и значение функции ( )f f x будем называть решением задачи  -оптимизации (  -решением). Мы будем использовать несколько отличное от классического определение  -субградиента [4]. Вектор nRg  называется ( , )f -cубградиентом функции )(xf в точке ,z если для x выполняется неравенство: ( ) ( , ) ,f x f g x z     (2) где * 1( ) ; .f z f f R   Значение f ~ на итерации алгоритма решения задачи  -оптимизации обычно равно полученному рекордному значению функции )(xf . Если значение *f известно априори, то . ~ *ff  Обычное классическое определение  -субградиента соответствует опре- делению ( , )f -субградиента (2) при ( ); 0.f f z   Обобщенный градиент функции )(xf в точке z в классическом смысле [2] является ))(,0( zf -cуб- градиентом. ( , , ),G f z )(zf обозначим множество ( , )f -субградиентов и множество обобщенных градиентов функции )(xf в точке z соответственно. В дальнейшем предполагается, что имеются алгоритмы вычисления )(xf и )()( xfxg  в произвольной точке x . Пусть 1 1 1( , , );g G f z  * 2 2( ),f f f z  тогда 2 2 2( , , ),g G f z  где 2 1 2 1 2 1( , ).f f g z z       (3) Таким образом, ( , )f -субградиент в некоторой точке 1z является ( , )f -cубградиентом в любой другой точке 2z . Формула (3) определяет правило пересчета параметров ( , )f -субградиента. Пусть ( , ) { |( , ) 0}nP z x R x z      плоскость, проходящая через точку z с нормалью , | | 0.nR   ( , ) { |( , ) 0}nP z x R x z        полупро- странство, определяемое (секущей) плоскостью ( , ).P z  Следующее утвержде- ние соответствует обычному построению отсекающих плоскостей «со сдвигом» Н.Г. ЖУРБЕНКО 148 Теорія оптимальних рішень. 2015 для множества ( , ).X f Пусть ( , , );g G f z  ( )/ | |;h g   / | | .z z hg g  Легко показать, что тогда ( , ) ( , ).X f P x z g    Замечание. Если *~ ff  (задача с известным значением минимума), то субградиент ( )g f z является *( , )f -субградиент с *( ( ) ).f z f    Для случая обычной задачи минимизации ( 0,  * ( , )X X f  ) величина «сдвига» *( )/ | | ( ( ) )/ | |h g f z f g      в точности соответствует шаговому множи- телю метода Поляка (1). Легко видеть, что ),~( gzxP  определяется неравенством: ( , )x z g  ( ),    а вектор «сдвига» z z отсекающей плоскости можно определить как результат решения следующей задачи 2min{1/ 2 | | : ( , ) ),y y g   где .    Обобщим этот результат для множества субградиентов. Пусть ( , , ), 1, , , .i i i ig G f z i m        Тогда ( , )X f содержится в пересече- нии подпространств: ( , ) ,i ix z g   (не исключается, что это пересечение пусто). Вектор сдвига y для множества  -субградиентов ( , , )iG f z из точки z определим решением следующей задачи: 2min1/ 2 || || ,y (4) ( , ) ; 1, , .i iy g i m   (5) Если система (5) несовместна, то вектор y не определен. Утверждение 1. Пусть система ограничений (5) – несовместна. Тогда f ~ – решение задачи  -оптимизации и выпуклая оболочка множества  -суб- градиентов ( , , )iG f z содержит 0. Утверждение 2. Пусть: a) система (5) совместна; b) ,y  – оптимальные значения прямых и двойственных переменных задачи (4 – 5); c) 1, 1, / ;i i i i m i m g g       1, 1, / .i i i i m i m        Тогда: ( , , ),g G f z  (( )/ | |) / | | .y g g g    Если условие a) не выпол- нено, то, учитывая утверждение 1, положим 0.g  Вектор ,g определяемый в утверждении 2, будем называть агрегатным  -субградиентом множества субградиентов ( , , ).iG f z АЛГОРИТМ ПОЛЯКА НА ОСНОВЕ АГРЕГАТНЫХ -СУБГРАДИЕНТОВ Теорія оптимальних рішень. 2015 149 Геометрический смысл агрегатного  -субградиента: агрегатный  -суб- градиент принадлежит выпуклой оболочке множества субградиентов ( , , )iG f z и обеспечивает максимальный сдвиг отсекающей плоскости. Утверждение 3. Пусть для всех субградиентов , 1, , .i i m      Тогда агрегатный  -субградиент – это вектор наименьшей длины выпуклой оболочки множества субградиентов ( 1{ , , }mg Nr g g ). Таким образом, для множества  -субградиентов ( , , )iG f z с одинаковыми значениями i агрегатный  -субградиент совпадает с кратчайшим вектором выпуклой оболочки ( , , ).iG f z Именно этот вектор обычно используется при построении  -субградиентных методов оптимизации. Введенное выше опреде- ление агрегатного  -субградиента полезно в следующих смыслах. Во-первых, при решении задачи (3 – 4) может оказаться, что некоторое значение 0i  даже если соответствующее значение .i   Обычно такие  -субградиенты при решении задачи  -оптимизации не используются. Во-вторых, при исполь- зовании 1{ , , }mg Nr g g все  -субградиенты при выборе направления сдвига из точки z оказываются «равноправными» по отношению к значениям :i вектор 1{ , , }mg Nr g g не зависит от  -параметров. Однако значения  -параметров существенны для локализации  -решения. Использование введенного агрегатного  -субградиента позволяет получать модификации  -субградиентных методов минимизации по обычной схеме их построения. В следующих пунктах агрегатный  -субградиент используется для построения модификации алгоритма Поляка. Отметим, что приведенное выше определение ( , )f -субградиента можно рассматривать как удобный (по мнению автора) способ отслеживания локализа- ции множества *( )X  с учетом накопленного множества отсекающих плоскостей. 2. Численная схема алгоритма Поляка на основе агрегатного  -субградиента. Поскольку для рассматриваемой задачи оптимальное значение *f задано, то в дальнейшем значение параметра f ~ для ( , )f -субградиентов полагаем равным :*f . ~ *ff  Кроме того, рассматривается обычная задача минимизации: 0.  Так как субградиент )(zfg  является *( , )f -субградиентом с  *( ( ) ),f z f   то .||/))(( * gfzfh  Величина сдвига отсекающей плоскости для такого субградиента (как отмечалось выше) соответствует значению шага алгоритма Поляка (1) при 1.  Н.Г. ЖУРБЕНКО 150 Теорія оптимальних рішень. 2015 По поводу параметра  отметим следующее. В алгоритме Поляка выбор значения (0,2) для произвольной выпуклой функции обеспечивает «фейеровское» свойство алгоритма относительно |:| *xxk  * 1| |kx x   *| |,kx x  для * *.x X  Наше определение *( , )f -субградиента фактически основано на следующем требовании: ни одна точка множества из *X не должна отсекаться: ).,~(* gzxPX   Для 1  это обеспечивается для произвольной выпуклой функции. Но для конкретной функции это требование может выполняться и для больших значений . Например, для квадратичной функции указанное условие выполняется для 2.  Нетрудно видеть, что учет значения параметра  можно осуществить следующим образом: субградиент )(zfg  является *( , )f -субградиент с *( ( ) ).f z f    При описании численной схемы алгоритма будет использоваться множество ]}.[],2[],1[{ sizeGradGradGradSetGrad  Здесь: size – число элементов мно- жества ;SetGrad ][lGrad – элемент l множества ,SetGrad определяющий информацию о  -субградиенте: вектор ,g значение параметра , номер итера- ции алгоритма ,k на которой он был вычислен. Для обозначения этих компонент элемента ][lGrad будет использоваться следующая форма (в стиле указателей языка C++): [ ] ,SetGrad l g  [ ] ,SetGrad l    [ ] .SetGrad l k  В приведенной далее численной схеме алгоритма, элемент [1]Grad будет содержать информацию об агрегатном субградиенте. Вычислительная схема рассматриваемых алгоритмов состоит в следующем. 0-й шаг алгоритма. Задаем значения параметров алгоритма: 2m  и . Значение параметра m определяет максимальное число ранее вычисленных *( , )f -субградиентов (включая агрегатный субградиент), которые используются на итерации алгоритма. Выбираем начальное приближение 0.x Вычисляем: 1) 0 0( ) ( )g x f x (субградиент в точке 0x ); * 0 0( ) ( ( ) );x f x f    2) 0[1] ( ),SetGrad g g x   0[1] ( ),SetGrad x     [1] 0,SetGrad k   1.size  Пусть на шаге k алгоритма ( 0,1,2, )k  получены: ,kx ,SetGrad .size ( 1)k  -ая итерация алгоритма ( 0,1,2, ).k  1) [1] ;g SetGrad g   [1] ;SetGrad     ( g – агрегатный субградиент,  – значение его  -параметра); АЛГОРИТМ ПОЛЯКА НА ОСНОВЕ АГРЕГАТНЫХ -СУБГРАДИЕНТОВ Теорія оптимальних рішень. 2015 151 2) 1 / | |;kh g   3) 1 1 / | |;k k kx x h g g   4) )()( 11   kk xfxg (субградиент в точке 1kx ); * 1 1( ) ( ( ) );k kx f x f      5) Пересчет  -параметров субградиентов множества ;SetGrad (пересчет ведется в соответствии с формулой (3): 1: ( , )k kg x x    ); 6) если ,msize то { ;1:  sizesize 1[ ] ( );kSetGrad size g g x    1[ ] ( );kSetGrad size x      [ ] 1;SetGrad size k k    7goto }; 6') если ,msize то {определить номер ,kDelete 1kDelete  удаляемого субградиента из множества ;SetGrad [ ]SetGrad kDelete – 1( );kg g x   1[ ] ( );kSetGrad kDelete x      [ ] 1;SetGrad kDelete k k    7;goto (ввод нового субградиента на место удаленного); 7) вычислить агрегатный субградиент agrg множества SetGrad и значение его параметра .agr Положить [1] ;agrSetGrad g g   [1]SetGrad     ;agr [1] 1;SetGrad k k    (вычисление агрегатного субградиента основано на решении задачи (4 – 5)). Переходим к ( 2)k  -у шагу алгоритма или прекращаем работу при выполнении критерия останова. Приведенная численная схема определяет конкретный алгоритм при уточнении процедуры отсева субградиентного множества SetGrad (п. 6')). Свойства агрегатного алгоритма обеспечивают справедливость следующего утверждения, в точности соответствующего работе [1]. Теорема 1. Пусть множество точек минимума .* X Тогда * *;kx x X  *lim ( ( ) ) 0.kk f x f  3. Результаты решения тестовых задач. Приведем результаты численных исследований следующего варианта процедуры отсева субградиентного множества .SetGrad Из множества накопленных субградиентов удаляется наиболее «старый»: kDelete  argmin{ [ ] | 2,3, ;}.SetGrad i k i m    В качестве тестовых задач рассматривались задачи минимизации двух следующих функций: 1 1 1, ( ) | |;i n i i n f x x    1 2 2 1, ( ) ,i n i i n f x x    где параметр n выбирался в зависимости от размерности задачи n по формуле 3/( 1)10 .n n   Таким образом, степень вытянутости линий уровня («овра- жности») функций определяется значением параметра 1 310 ,n n   она одинакова для всех функций независимо от числа переменных. Начальная точка Н.Г. ЖУРБЕНКО 152 Теорія оптимальних рішень. 2015 1.0, 1,2,... .ix i n  Критерий останова: 610 ,kf  где kf – значение функции на итерации останова .k Результаты решения тестовых задач минимизации функций )(),( 21 xfxf приведены в табл. 1 и 2 соответственно, где приняты следующие обозначения: n – размерность пространства переменных; m – максимальное число ранее вычисленных субградиентов, которые используются на итерации алгоритма. В таблицах указываются номера итерации, на которых алгоритм прекратил работу. Данные для 1m соответствуют алгоритму Поляка. Прочерк в колонке означает, что заданная точность решения не достигнута за 10000 итераций. ТАБЛИЦА 1 n\m 1 2 20 40 60 80 100 120 2 – 2 2 2 2 2 2 2 10 – 937 22 22 22 22 22 22 100 – 11129 264 268 257 265 287 298 ТАБЛИЦА 2 n\m 1 2 20 40 60 80 100 120 2 21 2 2 2 2 2 2 2 10 3413 13 10 10 10 10 10 10 100 3570 113 115 100 87 69 69 69 Результаты решения тестовых задач показывают существенное повышение скорости сходимости алгоритма при минимизации овражных функций. Однако следует учитывать, что трудоемкость итерации алгоритма увеличивается с ростом параметра алгоритма m (число используемых на итерации ранее вычи- сленных субградиентов). Для 2m трудоемкость итерации алгоритма фактиче- ски такая же, как в алгоритма Б.Т. Поляка: вычисление агрегатного субгради- ента выполняется по простым аналитическим соотношениям. Поэтому для задач большой размерности целесообразно использование, данного простейшего варианта алгоритма. В программной реализации алгоритма вычисление агрегатного  -суб- градиента основывается на решении двойственной к (4 – 5) задаче. При этом используется специальные меры по ее нормировке. Это связано с тем, что точность решения двойственной задачи необходимо увеличивать по мере приближения к точке минимума (по мере уменьшения шага 1kh ). Заключение. В работе приведен простейший вариант рассматриваемого семейства алгоритмов. В этом варианте используется только субградиенты, вычисленные в точках, соответствующих шагу алгоритма Поляка. Нетрудно АЛГОРИТМ ПОЛЯКА НА ОСНОВЕ АГРЕГАТНЫХ -СУБГРАДИЕНТОВ Теорія оптимальних рішень. 2015 153 привести примеры функций (даже в одномерном случае), для которых приведенный алгоритм в точности совпадет с алгоритмом Б.Т. Поляка. Фактически приведенный вариант алгоритма отличается от алгоритма Б.Т. Поляка [1] только тем, что множество SetGrad содержит агрегатные  субградиенты. Однако можно использовать более сложные процедуры генерации множества  -субградиентов .SetGrad Такие процедуры могут, например, основываться на алгоритме одномерной оптимизации (аналогично работе [3]). Кроме того, можно использовать более сложные процедуры удаления «устаревших» субградиентов. М.Г. Журбенко АЛГОРИТМ ПОЛЯКА НА ОСНОВІ АГРЕГАТНИХ  -СУБГРАДІЄНТІВ Запропоновано модифікацію субградієнтного алгоритму Б.Т. Поляка. Алгоритм заснований на використанні ε-субградієнтів. Результати чисельних розрахунків показують поліпшення швидкості збіжності алгоритму. N.G. Zhurbenko POLJAK’S ALGORITHM ON BASE OF AGGREGATE  -SUBGRADIENTS A modification of B.T.Poljak’s subgradient algorithm is proposed. The algorithm is based on application of ε-subgradients. The numerical results show the convergences rate improvement of the algorithm. 1. Поляк Б.Т. Минимизация негладких функционалов // Вычислительная математика и математическая физика. – 1969.– № 3. – С. 509 – 521. 2. Шор Н.З. Методы минимизации недифференцируемых функций и их применение. – Киев: Наук.думка, 1979. – 200 с. 3. Журбенко Н.Г. Об одном классе методов минимизации с преобразованием пространства // Методы решения экстремальных задач. – 1996. – С. 68 – 80. 4. Lemarechal C., Mifflin K. Nonsmooth Optimization.Oxford: Pergamon Press, 1978. – 180 p. Получено 22.03.2015
id nasplib_isofts_kiev_ua-123456789-112412
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn XXXX-0013
language Russian
last_indexed 2025-12-07T16:04:17Z
publishDate 2015
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
record_format dspace
spelling Журбенко, Н.Г.
2017-01-20T21:55:31Z
2017-01-20T21:55:31Z
2015
Алгоритм Поляка на основе агрегатных ε-субградиентов / Н.Г. Журбенко // Теорія оптимальних рішень: Зб. наук. пр. — 2015. — № 2015. — № 2015. — № 2015. — С. 146-153. — Бібліогр.: 4 назв. — рос.
XXXX-0013
https://nasplib.isofts.kiev.ua/handle/123456789/112412
519.8
Предложена модификация субградиентного алгоритма Б.Т. Поляка. Алгоритм основан на использовании ε-субградиентов. Результаты численных расчетов показывают улучшение скорости сходимости алгоритма.
Запропоновано модифікацію субградієнтного алгоритму Б.Т. Поляка. Алгоритм заснований на використанні ε-субградієнтів. Результати чисельних розрахунків показують поліпшення швидкості збіжності алгоритму.
A modification of B.T.Poljak’s subgradient algorithm is proposed. The algorithm is based on application of ε-subgradients. The numerical results show the convergences rate improvement of the algorithm.
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Теорія оптимальних рішень
Алгоритм Поляка на основе агрегатных ε-субградиентов
Алгоритм Поляка на основі агрегатних ε-субградієнтів
Poljak’s algorithm on base of aggregate ε-subgradients
Article
published earlier
spellingShingle Алгоритм Поляка на основе агрегатных ε-субградиентов
Журбенко, Н.Г.
title Алгоритм Поляка на основе агрегатных ε-субградиентов
title_alt Алгоритм Поляка на основі агрегатних ε-субградієнтів
Poljak’s algorithm on base of aggregate ε-subgradients
title_full Алгоритм Поляка на основе агрегатных ε-субградиентов
title_fullStr Алгоритм Поляка на основе агрегатных ε-субградиентов
title_full_unstemmed Алгоритм Поляка на основе агрегатных ε-субградиентов
title_short Алгоритм Поляка на основе агрегатных ε-субградиентов
title_sort алгоритм поляка на основе агрегатных ε-субградиентов
url https://nasplib.isofts.kiev.ua/handle/123456789/112412
work_keys_str_mv AT žurbenkong algoritmpolâkanaosnoveagregatnyhεsubgradientov
AT žurbenkong algoritmpolâkanaosnovíagregatnihεsubgradíêntív
AT žurbenkong poljaksalgorithmonbaseofaggregateεsubgradients

Similar Items