Вероятностно-градиентный метод решения некоторых задач выпуклой оптимизации

Рассматриваются два стохастических варианта градиентного метода с программным способом регулировки шага. Указаны определенные достаточные условия, при которых описанные алгоритмы сходятся к множеству оптимальных решений с вероятностью единица....

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2014
Hauptverfasser:	Годонога, А.Ф., Чумаков, Б.М.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2014
Schriftenreihe:	Теорія оптимальних рішень
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/111520
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Вероятностно-градиентный метод решения некоторых задач выпуклой оптимизации / А.Ф. Годонога, Б.М. Чумаков // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 132-138. — Бібліогр.: 7 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-111520
record_format	dspace
spelling	irk-123456789-1115202017-01-11T03:03:39Z Вероятностно-градиентный метод решения некоторых задач выпуклой оптимизации Годонога, А.Ф. Чумаков, Б.М. Рассматриваются два стохастических варианта градиентного метода с программным способом регулировки шага. Указаны определенные достаточные условия, при которых описанные алгоритмы сходятся к множеству оптимальных решений с вероятностью единица. Розглядаються два стохастичних варіанта градієнтного методу з програмним засобом регулювання кроком. Зазначені певні умови, за яких описані алгоритми сходяться до множини оптимальних рішень з імовірністю одиниця. The consider two variants of stochastic gradient method with the programmatically regulation of step. The shown are certain sufficient conditions under which the described algorithms converge to the set of optimal solutions with probability one. 2014 Article Вероятностно-градиентный метод решения некоторых задач выпуклой оптимизации / А.Ф. Годонога, Б.М. Чумаков // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 132-138. — Бібліогр.: 7 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/111520 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Рассматриваются два стохастических варианта градиентного метода с программным способом регулировки шага. Указаны определенные достаточные условия, при которых описанные алгоритмы сходятся к множеству оптимальных решений с вероятностью единица.
format	Article
author	Годонога, А.Ф. Чумаков, Б.М.
spellingShingle	Годонога, А.Ф. Чумаков, Б.М. Вероятностно-градиентный метод решения некоторых задач выпуклой оптимизации Теорія оптимальних рішень
author_facet	Годонога, А.Ф. Чумаков, Б.М.
author_sort	Годонога, А.Ф.
title	Вероятностно-градиентный метод решения некоторых задач выпуклой оптимизации
title_short	Вероятностно-градиентный метод решения некоторых задач выпуклой оптимизации
title_full	Вероятностно-градиентный метод решения некоторых задач выпуклой оптимизации
title_fullStr	Вероятностно-градиентный метод решения некоторых задач выпуклой оптимизации
title_full_unstemmed	Вероятностно-градиентный метод решения некоторых задач выпуклой оптимизации
title_sort	вероятностно-градиентный метод решения некоторых задач выпуклой оптимизации
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2014
url	http://dspace.nbuv.gov.ua/handle/123456789/111520
citation_txt	Вероятностно-градиентный метод решения некоторых задач выпуклой оптимизации / А.Ф. Годонога, Б.М. Чумаков // Теорія оптимальних рішень: Зб. наук. пр. — 2014. — № 2014. — С. 132-138. — Бібліогр.: 7 назв. — рос.
series	Теорія оптимальних рішень
work_keys_str_mv	AT godonogaaf veroâtnostnogradientnyjmetodrešeniânekotoryhzadačvypuklojoptimizacii AT čumakovbm veroâtnostnogradientnyjmetodrešeniânekotoryhzadačvypuklojoptimizacii
first_indexed	2025-07-08T02:16:57Z
last_indexed	2025-07-08T02:16:57Z
_version_	1837043305304555520
fulltext	132 Теорія оптимальних рішень. 2014 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Рассматриваются два стохасти- ческих варианта градиентного метода с программным способом регулировки шага. Указаны опре- деленные достаточные условия, при которых описанные алгорит- мы сходятся к множеству опти- мальных решений с вероятностью единица.   А.Ф. Годонога, Б.М. Чумаков, 2014 УДК 519.8 А.Ф. ГОДОНОГА, Б.М. ЧУМАКОВ ВЕРОЯТНОСТНО-ГРАДИЕНТНЫЙ МЕТОД РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ ВЫПУКЛОЙ ОПТИМИЗАЦИИ Задачи оптимизации занимают значительное место в теории и практики принятия обо- снованных решений. Несмотря на нынеш- нее, поистине революционное, развитие вы- числительных средств, интерес к вопросу, эффективности способов получения таких решений, остается актуальным. В данной работе рассматривается вероятностный под- ход к решению некоторых оптимизационных задач в сочетании с идеями градиентного мето- да, в котором программно реализуется выбор шагового множителя градиентного метода. Рассматривается следующая задача: ( ) min , F x x X    (1) где X – выпуклое компактное множество эвклидово пространство .nE  – окрест- ность множества ,X определяется следую- щим образом:  ,V X    , x X V x   .  ,V x  сферическая окрестность радиуса 0  точки ,nx E   , :nV x y E   : .x y   Пусть, при некотором 0,  функция ( )F x – выпуклая и непрерывно дифференцируемая [1, 2] (с непрерывным градиентом) на  , .V X  Следовательно, для x X  определен следующий вектор:  ,1 ,( ) ( ), , ( )F F nGF x g x g x  = 1 ( ) ( ) ( ) , , , , , i n F x F x F x x x x           ВЕРОЯТНОСТНО-ГРАДИЕНТНЫЙ МЕТОД РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ ... Теорія оптимальних рішень. 2014 133 где ( )GF x – градиент функции ( )F x и норма 2 , 1 ( ) ( ) n F i i GF x g x    – непрерывная функция на X и, следовательно, существует константа C   , при которой ( )GF x C для .x X  Тогда следует, что справедливы и неравенства вида , ( ) , 1, , .F ig x C i n x X     Численный метод, рассматривающий для решения задачи (1), имеет итерационный характер. А именно, если предположить что находимся на k -ой итерации и точка kx известна, то последовательно выполняются следующие действия: 1) в серии 1km  независимых испытаний наблюдаются значения случайной величины ,k заданной apriori известным законом распределения вероятностей k 1 2 n P 1 kP 2 kP k nP Таким образом, на каждой k -ой итерации генерируется, в соответствии с заданным законом распределения вероятностей, множество  1 2, , , , kk mI i i i элементы которого являются независимыми наблюдениями над случайной величиной ,k причем предполагается, что ,1,0 ,,1 ,0  kniPPk i (2) В частности, можно ограничиться всего лишь одним наблюдением на каждой итерации, т. е. 1;km  2) вычисляется направление движения ( )k k Fg x по правилу:   1 1 2 , если ( ) , , , , , , , 1, .( ) , если k i k k k k k k k k k F i n i k i g i I g x g g g g g i nF x i I x           (3) 3) точка 1kx  определяется следующим образом:  1 1 , k kx X x   где 1 ,k k k kx x    (4) где  1П k Х x  – проекция на множество X элемента 1 .k nx E  Начальная точка 0x может быть произвольным элементом из множества .X А.Ф. ГОДОНОГА, Б.М. ЧУМАКОВ 134 Теорія оптимальних рішень. 2014 Пусть числовая последовательность  k удовлетворяет классическим условиям 1 0, 0,k k k k          (5) и, кроме того, допустим, что существует число 0,  такое, что для  0,r   и  0,1 , сходится следующий ряд [3]: ( , ) 0 ,L k r k      где 1 0, если или 0 ( , ) , , если и k k k k k k l l l k s l k s r k L k r s r r                    (6) т. е. ks – наибольшее из всех целых чисел 0,j  при которых . k l l k j r     В работе [3] доказано, что существует такая числовая последовательность  ,k удовлетворяющая условиям (5) – (6), в частности, если , ( 1) k R k      0, 0,1 .R   Последовательность векторов  k строится следующим образом: , если 0, 1,2, . 0, при 0 k k kk k g g k g g         (7) Справедливо следующее утверждение. Tеорема 1. Пусть выполняются условия (2) – (7). Тогда, для произвольного фиксированного числа 0,  все элементы случайной последовательности   0 ,k k x  почти наверное [4], принадлежат множеству  ,2 ,V X  за исклю- чением, быть может, конечного числа ее членов. Схема доказательства теоремы. 1. Если  , 2 ,X V X  то утверждение очевидно. 2. При  \ , 2X V X   рассматриваются два этапа. На первом этапе доказывается существование подпоследовательности 0{ } { } ,lk k kx x  которая почти наверное содержится в  , ,V X  т. е.   lk P x     * 0 : , 1.lkk k x x V X      Для этого, при некотором > 0q и натуральном числе < ,qK  определяется событие  : , ,k q qA K k K x x       т. е.    * , , ,kx V X x X    ВЕРОЯТНОСТНО-ГРАДИЕНТНЫЙ МЕТОД РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ ... Теорія оптимальних рішень. 2014 135 причем, предпологается что вероятность реализации данного события   .P A q Используя механизм построения векторов ,k свойства целевой функции ( )F x и лемму Бореля – Кантелли [4] относительно последовательно- сти событий  ,k FB где событие k FB  {по крайней мере один раз, на какой-то итерации вида ,kj k s k  генерируется каждое возможное значение случай- ной величины { k }; 0,1,...},k  получается противоречие состоящее в том, что ( ) 0.q P A  На втором этапе, используя уже полученный результат первого этапа, доказывается, что все, кроме, быть может, конечного числа членов последова- тельности  kx , содержатся в  ,2V X  с вероятностью 1. Далее рассматривается следующее обобщение задачи (1): ( ) min, ( ) 0, . F x x x X       (8) Предположим, что задача (8) имеет решение. Пусть, при некотором 0,  функции ( )F x и ( )x – выпуклые и непрерывно дифференцируемые (с непре- рывными градиентами) на  , .V X  Следовательно, для x X  определены векторы  ,1 , 1 ( ) ( ) ( ) ( ) ( ), , ( ) , , , , ,F F n i n F x F x F x GF x g x g x x x x              ,1 , 1 ( ) ( ) ( ) ( ) ( ), , ( ) , , , , .n i n x x x G x g x g x x x x                Тогда, очевидно, нормы 2 , 1 ( ) ( ), n F i i GF x g x    2 , 1 ( ) ( ) n i i G x g x     – непрерывные функции на X и, следовательно, существует постоянная ,C   при которой ( ) ,GF x C ( )G x C  для .x X  Непосредственно следует, что справедливы и неравенства , ,( ) , ( ) ,F i ig x C g x C  ,,1 ni  .x X  Численный метод, который предлагается для решения задачи (8), имеет формально тот же вид, как алгоритм для решения предыдущей задачи. Только в данном случае на каждой итерации k рассматриваются две серии 1,km  1kl  независимых испытаний в которых наблюдаются две случайные величины ,k ,k заданные дискретными законами распределения вероятностей: А.Ф. ГОДОНОГА, Б.М. ЧУМАКОВ 136 Теорія оптимальних рішень. 2014 k 1 2 n P ,1 kP , 2 kP , k nP k 1 2 n P ,1 kP , 2 kP , k nP Точнее, на каждой итерации k генерируются множества  1 2, , , kk mI i i i ,  1 2, , , kk lJ j j j , элементы которых представляют независимые реализации величин ,k ,k соответственно, с заданными распределениями вероятностей, причем , , 0, 1, , 0,1, 0, 1, , 0,1, k i k i P P i n k P P i n k                 (9) В частности, также можно брать 1,k km l  т. е. можно ограничиться лишь одним наблюдением ,k k на каждой итерации. Итак: 1) векторы ( ),k k Fg x ( )k kg x определяются по правилу:     1 , ,1 , , , 1 , ,1 , , , , если , ( ) , , , , , ( ) , если , , если ( ) , , , , , ;( ) , если k F i k k k k k k k k F F F i F n F i k i k i k k k k k k k k i n i k i g i I g x g g g g F x i I x g i J g x g g g g x i J x                           (10) 2) аналогично определяется точка 1,kx   1 1 1, ;k k k k k kX x x x x      (11) 3) последовательность векторов  k строится также как и в (7); 4) относительно направления движения ,kg последуем идеи работы [5], но определим если если ( ), ( ) ( ) , 0. ( ), ( )> k k k Fk k k k k k g x x g g x g x x           (12) Имеет место, следующее утверждение. Tеорема 2. Пусть последовательность случайных точек  kx строится в соответствии с правилами (4) – (7), (9) – (12). Тогда, для произвольного числа 0,  существует такое число 0,  при котором все элементы последова- ВЕРОЯТНОСТНО-ГРАДИЕНТНЫЙ МЕТОД РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ ... Теорія оптимальних рішень. 2014 137 тельности   0 k k x  , почти наверное принадлежат множеству  , 2V X  , за исключением, быть может, конечного числа ее членов. Следует отметить, что, в основном, схема доказательства данной теоремы примерно совпадает со схемой доказательства теоремы 1. Основное отличие состоит в следующем. На первом этапе доказательства, при достаточно малом положительным значении , для заданного числа 0,  можно найти общее число  min , 0,F      при котором     * * * ( ), 2 ( ) , если ( ) , ( ), 2 ( ) , если ( ) . k k k k k k k k k k GF x x x GF x x x x G x x x G x x x x                   Тем самым, при достаточно больших значений ,k для которых выполня- ются условия  ,kx V X  и ( ) ,kx   получаются неравенства вида   ( ), ( ) ,k k k k k k F Fg x x x g x x x     а при  ,kx V X  и ( ) ,kx   неравенства –  * ( ), ( ) .k k k k k kg x x x g x x x      Эти неравенства являются, соответственно, следствиями следующих событий: а) k FB ={по крайней мере один раз, на какой-то итерации вида ,kj k s k  генерируется каждое возможное значение случайной величины k }; б) kB ={по крайней мере один раз, на какой-то итерации вида ,kj k s k  генерируется каждое возможное значение случайной величины k }. Далее определяются события вида 1 ,k k k FB B B причем для 1 ,kB также как и для k FB из первой теоремы, можно получить неравенство  1 ,kskP B   в соот- ветствии с которым, почти наверное, существует подпоследовательность после- довательности  kx , которая полностью содержится в  , .V X  Второй этап доказательства аналогичен соответствующему этапу доказательства первой теоремы. В ряде научных работ, в частности [6], доказано, что некоторые методы случайного поиска, при решении определенных классов оптимизационных задач, являются эффективней, нежели детерминированные алгоритмы. Поэтому, отказ от точного вычисления градиента, и тем более применение принципа случайного подбрасывания индексов частных производных, которых следовало бы «время от время» обновить, может не только существенно сократить объем вычислений, но и ускорить процесс достижения приемлемых решений в реаль- ном масштабе времени. Некоторые детерминированные аспекты, рассмотренных здесь методов, анализируются в работе [7]. А.Ф. ГОДОНОГА, Б.М. ЧУМАКОВ 138 Теорія оптимальних рішень. 2014 А.Ф. Годонога, Б.М. Чумаков ЙМОВІРНІСНО-ГРАДІЄНТНИЙ МЕТОД РОЗВ’ЯЗАННЯ ДЕЯКИХ ЗАДАЧ ОПУКЛОЇ ОПТИМІЗАЦІЇ Розглядаються два стохастичних варіанта градієнтного методу з програмним засобом регу- лювання кроком. Зазначені певні умови, за яких описані алгоритми сходяться до множини оптимальних рішень з імовірністю одиниця. A.F. Godonoga, B.M. Chumakov PROBALISTIC-GRADIENT METHOD FOR SOLVING CERTAIN PROBLEMS CONVEX OPTIMIZATION The consider two variants of stochastic gradient method with the programmatically regulation of step. The shown are certain sufficient conditions under which the described algorithms converge to the set of optimal solutions with probability one. 1. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. – М.: Наука, 1978. – 352 с. 2. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. – Киев: Наук. думка, 1979. – 199 с. 3. Ермольев Ю.М., Гайворонский А.А. Стохастический метод решения минимаксных задач // Кибернетика. – 1983. – № 4. – С. 92 – 97. 4. Ширяев А.Н. Вероятность. – М.: Наука, 1980. – 575 с. 5. Поляк Б.Т. Один общий метод решения экстремальных задач // Докл. АН СССР. – 1967. – 174. – № 1. – С. 33 – 36. 6. Шор Н.З., Щепакин М.Б. Об оценке скорости сходимости метода случайного поиска // Кибернетика. – 1974. – № 4. – С. 55 – 58. 7. Balan P., Godonoaga A. Solutionarea unui model diferentiabil cu modificarea succesiva a componentelor gradientilor // Analele ATIC – Chisinau: Evrica, 2007. – P. 25 – 34. Получено 03.04.2014

Вероятностно-градиентный метод решения некоторых задач выпуклой оптимизации

Institution

Ähnliche Einträge