Кукурба Віктор Романович . Неперервна процедура стохастичної оптимізації з напівмарковськими переключеннями

Короткий опис

Кукурба Віктор Романович . Назва дисертаційної роботи: "Неперервна процедура стохастичної оптимізації з напівмарковськими переключеннями"

МIНIСТЕРСТВО ОСВIТИ I НАУКИ УКРАЇНИ
НАЦIОНАЛЬНИЙ УНIВЕРСИТЕТ "ЛЬВIВСЬКА ПОЛIТЕХНIКА"
На правах рукопису
Кукурба Вiктор Романович
УДК 519.715: 519.857.4
НЕПЕРЕРВНА ПРОЦЕДУРА СТОХАСТИЧНОЇ ОПТИМIЗАЦIЇ З
НАПIВМАРКОВСЬКИМИ ПЕРЕКЛЮЧЕННЯМИ
01.05.04 – системний аналiз i теорiя оптимальних рiшень
Дисертацiя на здобуття наукового ступеня
кандидата фiзико-математичних наук
Науковий керiвник:
Чабанюк Ярослав Михайлович,
доктор фiзико-математичних наук, професор
ЛЬВIВ – 2016
2
ЗМIСТ
ПЕРЕЛIК УМОВНИХ ПОЗНАЧЕНЬ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
ВСТУП . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
РОЗДIЛ 1. Огляд лiтературних джерел та допомiжнi вiдомостi . . . . 13
1.1. Огляд лiтературних джерел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2. Марковськi процеси . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3. Напiвмарковськi процеси . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4. Стохастичнi системи з випадковими збуреннями . . . . . . . . . . . . . . . . 30
1.5. Вихiд траекторiї з областi, збiжнiсть випадкових процесiв . . . . . . . 35
РОЗДIЛ 2. Збiжнiсть неперервної процедури стохастичної оптимiзацiї . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.1. Збiжнiсть процедури стохастичної оптимiзацiї в схемi усереднення . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2. Збiжнiсть процедури стохастичної оптимiзацiї в схемi дифузiйної
апроксимацiї . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.3. Висновки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
РОЗДIЛ 3. Асимптотична нормальнiсть процедури стохастичної оптимiзацiї в схемi дифузiйної апроксимацiї та неперервна процедура з iмпульсними
збуреннями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.1. Асимптотична нормальнiсть процедури стохастичної оптимiзацiї в
схемi дифузiйної апроксимацiї . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3
3.2. Процедура стохастичної оптимiзацiї з iмпульсними збуреннями в напiвмарковському середовищi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.3. Висновки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
РОЗДIЛ 4. Застосування процедури стохастичної оптимiзацiї. . . . . . . 96
4.1. Опис процесу тестування через марковський та напiвмарковський
процес . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.2. Аналiз математичної моделi тестування програмного продукту з
iндексом величини проекту . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.3. Процедура стохастичної оптимiзацiї для задачi тестування
програмного продукту . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4. Висновки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
ВИСНОВКИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ . . . . . . . . . . . . . . . . . . . . . . 115
ДОДАТОК . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4
ПЕРЕЛIК УМОВНИХ ПОЗНАЧЕНЬ
N - множина всiх натуральних чисел
R - множина всiх дiйсних чисел
(Ω, F, P) - ймовiрносний простiр
(X, X ) - фазовий вимiрний простiр
B(X) - банахiвський простiр дiйснозначних обмежених функцiй з супремум нормою
xn, n ≥ 0, - вкладений ланцюг Маркова
x(t), t ≥ 0 - напiвмарковський процес
P(x, B), B ∈ X , - перехiднi ймовiрностi ланцюга Маркова
ρ(B) - стацiонарний розподiл ланцюга Маркова xn, n ≥ 0
π(B) - стацiонарний розподiл марковського процесу x(t)
Q - генератор марковського процесу
R0 - потенцiал генератора Q
B(X) = NQ ⊕ RQ
C
k
(X) - простiр k разiв неперервно диференцiйованих обмежених на X
функцiй
:= - рiвнiсть за означенням
Ex[·] - математичне сподiвання подiї [·] при x0 = x
o(ε) - числова функцiя: o(ε)/ε → 0, ε → 0
O(ε) - числова функцiя: O(ε) → 0, ε → 0
НМП - напiвмарковський процес
ПСО - процедура стохастичної оптимiзацiї.
5
ВСТУП
Актуальнiсть теми.
Основнi алгоритми стохастичної апроксимацiї, що були запропонованi Робiнсом i Монро [89] та Кiферем i Вольфовицем [75] на початку 1950-х рокiв стали
об’єктом теоретичних та практичних дослiджень у зв’язку з великою кiлькiстю
прикладних та теоретичних проблем, що виникають в аналiзi стохастичних процесiв. В основi алгоритмiв лежить стохастичне рiзницеве рiвняння
un+1 = un + εnYn,
де un набуває значень з евклiдового простору та описує стан системи, Yn випадковий вектор, εn > 0 малий параметр.
В данiй роботi розглядається процедура стохастичної оптимiзацiї в неперервному випадку. Вперше даний пiдхiд був запропонований в роботi Kiefer E.,
Wolfowitz J. [75] в дискретному випадку при цьому були встановленi асимптотичнi властивостi та отримано збiжнiсть процедури в середньому квадратичному. Метод полягає в пошуку точки максимуму u0, невiдомої функцiї регресiї
f(u), u ∈ R, за умови його єдиностi. Крiм того, значення функцiї f(u) вимiрюється з випадковими помилками, що не дозволяє застосувати градiєнтний метод
u(t + 1) − u(t) = af0
(u(t)), де константа a > 0 . Iдея процедури Кiфера та Вольфовиця зводиться до наближеного пiдрахунку похiдної як вiдношення приросту
функцiї до приросту аргументу ∆u = 2c(t) → 0, t → ∞ i одночасним сповiльненням руху u до u0 вводячи залежнiсть вiд часу для параметра a.
Аналогiчна процедура стохастичної оптимiзацiї для неперервного випадку була введена Хасьминским Р. З. [40] i розглядались в роботах Невельсо-
6
на М. Б. [27],[28], Дячкова А. Г. i Пинскера М. С. [9], Гладишева Е. Г. [5], Логiнова
Н. В. [25], Benveniste A., Metivier M., Priouret P. [58], та iнших авторiв.
Збiжнiсть неперервної процедури Кiфера-Вольфовиця розглянув Sakrison D. T. [91], а Derman C. [62] довiв збiжнiсть процедури з ймовiрнiстю 1 при
слабших умовах. В роботi Невельсон М. Б., Хасьминский Р. З. [30] збiжнiсть
встановлюється через властивостi функцiй типу Ляпунова ([30], с. 100) та мартингальнi властивостi випадкових процесiв, що значно спрощує вивчення та застосування процедури стохастичної оптимiзацiї.
Застосування стохастичної апроксимацiї з точки зору проблем оптимiзацiї
розглянутi в роботi Ljung L., Pflug G., Walk H. [87], при цьому авторами модифiковано процедури Роббiнса-Монро та отримано ряд застосувань при знаходженнi
глобального мiнiмуму функцiї F(u), u ∈ S, S∈Rd
, S - обмежена область, i локального мiнiмуму при u ∈ S
T
U, де U вiдкритий окiл точки u0. В неперервному
випадку використано принцип iнварiантностi для процесiв.
Основними властивостивостями процедури стохастичної оптимiзацiї є її
асимптотична нормальнiсть, а також властивiсть флуктуацiй вiдносно дифузiйної складової процедури. Данi властивостi були розглянутi в роботах Невельсона М. Б., Хасьминского Р. З. [30], I. А. Iбрагiмова, Fabian V. [70], Ruppert D.
[90], та iнших. При цьому, в роботах [87], [30] використовується нормування по
часу на √
t з центруванням флуктуацiй по точцi рiвноваги u0, або по граничному
процесу, також активно використовувався метод "зрiзання"введений Hodges J.
L. та Lehman E. L. для доведення асимптотичної нормальностi випадкової еволюцiї. Асимптотична нормальнiсть для iнших процедур стохастичної апроксимацiї
показана в роботах Fabian V. [69],Derman C. [62],Dupach V. [63] i iнших.
7
До найважливiших питань теорiї еволюцiйних систем в випадковому середовищi вiдносять стiйкiсть. Стiйкiсть динамiчної системи, що задовольняє принципу усереднення, вперше була встановлена М.М. Боголюбовим[1], а також розглянута Ю.О. Митропольським та А.М. Самойленко в роботi [26]. Розвиток теорiї випадкових еволюцiй започаткований Hersh T. ,Griego R. [65], призвiв до
вивчення стiйкостi динамiчних систем у випадковому середовищi.
Стiйкiсть динамiчної системи з марковським збуренням при умовi стiйкостi усередненої системи вивчалась в роботах А.В. Скорохода, Є.Ф. Царькова,
а також В.С. Королюка. В умовах дифузiйної апроксимацiї динамiчної системи
з марковським збуренням проблема стiйкостi вперше була розв’язана в роботi
Blankenship G. L., Papanicolaou G. C. [59] з використанням мартингальної характеризацiї вiдповiдного марковського процесу.
Стiйкiсть динамiчної системи у напiвмарковському середовищi в умовах
усереднення та дифузiйної апроксимацiї вивчалась А.В.Свiщуком [94], а також
В.С. Королюком [79]. При цьому використовувалася мартингальна характеризацiя марковського процесу з додатковою компонентою лiнiйчатого процесу. У
випадку з напiвмарковськими збуреннями, для вивчення стiйкостi динамiчної
системи використовують всластивостi компенсуючого оператора введеного в роботах М.Н. Свiрiденко [32].
В роботi О.М. Iксанова [66] розглянуто процеси дробового ефекту, граничними для яких є дробово iнтегровнi стiйкi процеси Левi (згорки степеневих
функцiй та стiйких процесiв Левi) та дробово iнтегровнi оберненi стiйкi субординатори.
У роботах Я.М. Чабанюка отримано збiжнiсть процедури стохастичної
8
апроксимацiї у випадках залежностi функцiї регресiї вiд марковського [48][49]
та напiвмарковського процесу, в схемах усереднення та дифузiйної апроксимацiї.
Також розглянута асимптотична нормальнiсть процедури в зазначених схемах.
Процедура стохастичної оптимiзацiї у марковському середовищi в схемах
усереднення та дифузiйної апроксимацiї розглянута в роботах У.Т. Хiмки [45],
[42], з використанням двокомпонентного марковського процесу. Крiм цього в роботi [43] дослiджено флуктуацiї процедур стохастичної оптимiзацiї з iмпульсним
та дифузiйним збуреннями.
Зв’язок роботи з науковими програмами, планами, темами.
Результати дисертацiї виконано у рамках наукових дослiджень кафедри
прикладної математики в межах теми "Стохастична оптимiзацiя в марковському
та напiвмарковському середовищах ” , (Державний реєстрацiйний номер 0109U008846,
на перiод з 2009-2014 рр.).
Мета дослiдження.
Метою дисертацiї є встановлення достатнiх умов збiжностi та асимптотичної нормальностi неперервної процедури стохастичної оптимiзацiї в напiвмарковському середовищi.
Задачi дослiдження
- модифiкувати процедуру Кiфера-Вольфовиця методом вводу другого
параметру у функцiю регресiї, що описує вплив зовнiшнiх випадкових факторiв
i задається напiвмарковським процесом.
- отримати достатнi умови збiжностi неперервної процедури стохастичної
оптимiзацiї з напiвмарковськими переключеннями в схемах усереднення та ди-
9
фузiйної апроксимацiї;
- отримати умови збiжностi неперервної процедури стохастичної оптимiзацiї з iмпульсним збуренням в напiвмарковському середовищi;
- встановити асимптотичну поведiнку процедури стохастичної оптимiзацiї
в умовах збiжностi в схемi дифузiйної апроксимацiї;
Об’єкт дослiдження – неперервна процедура стохастичної оптимiзацiї у випадку
залежностi функцiї регресiї вiд зовнiшнього середовища, що описується напiвмарковськими переключеннями.
Предметом – збiжнiсть неперервної процедури стохастичної оптимiзацiї з напiвмарковськими переключеннями до дифузiйних процесiв.
Методи дослiдження. У роботi використовуються результати та методи теорiї випадкових еволюцiй, марковських та напiвмарковських процесiв, другий
метод Ляпунова, схема серiй з малим параметром в схемi усереднення, дифузiйної апроксимацiї. При побудовi граничних операторiв використовується метод
розв’язку проблеми сингулярного збурення для генератора двокомпонентного
марковського процесу.
Наукова новизна отриманих результатiв:
- вперше отримано властивостi процедури стохастичної оптимiзацiї у випадку, коли функцiя регресiї залежить вiд напiвмарковського процесу переключень;
- вперше побудовано компенсуючий оператор розширеного процесу марковського вiдновлення для процедури стохастичної оптимiзацiї, отримано його
асимптотичний розклад та розвязано проблему сингулярного збурення для асим-
10
птотичного оператора з використанням збуреної функцiї типу Ляпунова;
- вперше встановлено достатнi умови збiжностi неперервної процедури
стохастичної оптимiзацiї до точки екстремуму усередненої системи в напiвмарковському середовищi в схемах усереднення та дифузiйної апроксимацiї;
- вперше отримано асимптотична дифузiйнiсть флуктуацiй неперервної
процедури стохастичної оптимiзацiї з напiвмарковськими переключеннями в схемi дифузiйної апроксимацiї;
- вперше встановлено достатнi умови збiжностi неперервної процедури
стохастичної оптимiзацiї з напiвмарковськими переключеннями та iмпульсними
збуреннями до точки екстремуму усередненої системи;
- дослiджено асимптотичну поведiнку математичної моделi для встановлення оптимальних параметрiв на завершенiсть тестування програмного продукту
в стохастичних умовах та вперше введено параметр впливу зовнiшнiх чинникiв
процесу тестування, що описується напiвмарковським процесом.
Практичне значення одержаних результатiв.
Результати дисертацiйної роботи носять теоретичний i практичний характер. Розглянутi методи стохастичної оптимiзацiї можуть використовуватися
для розв’язку прикладних проблем, що задаються стохастичними системами з
зовнiшнiми впливами, що описуються напiвмарковськими процесами. В данiй
роботi оптимiзацiйна процедура застосована для аналiзу надiйностi програмного забезпечення, що описується динамiчними моделями на основi неоднорiдного
пуассонового процесу, при цьому врахованi зовнiшнi впливи, що можуть бути
описанi напiвмарковським процесом.
11
Особистий внесок здобувача. Постановка задач належить науковому керiвнику дисертацiйної роботи Чабанюку Ярославу Михайловичу, доведення теорем
та допомiжних тверджень належить дисертанту - Кукурбi Вiктору Романовичу. Застосування процедури стохастичної оптимiзацiї для математичної моделi
прогнозування надiйностi програмного забезпечення проведено дисертантом. У
публiкацiях, виконаних у спiвавторствi, особистий внесок здобувача полягав у
виконаннi основних розрахункiв, доведень та формулюваннi висновкiв, спiвавторам належить постановка задач та рекомендацiї щодо методiв їх розв’язування.
Отриманi результати дисертацiйної роботи сформульованi у виглядi теорем та
строго доведенi з використанням допомiжних лем та тверджень i обґрунтованi
автором з посиланнями на використанi джерела.
Апробацiя результатiв дисертацiї.
Результати дисертацiї доповiдались на всеукраїнських та мiжнародних
конференцiях, зокрема на:
— мiжнароднiй конференцiї "Problems Of Decision Making Under Uncertainties"
(PDMU, Skhidnytsia, 2011, Yalta, 2011, Mukachevo, 2012, Skhidnytsia, 2013,
Skhidnytsia, 2014, Brno, 2014, Skhidnytsia, 2015),
— XIII мiжнароднiй науковiй конференцiї iм. акад. М.Кравчука (Київ,
2010),
— мiжнароднiй математичнiй конференцiї iм. В.Я. Скоробагатька (Дрогобич, 2011),
— V мiжнароднiй науковiй конференцiї OPTIMA-2012: "Сучаснi проблеми математичного моделювання, прогнозування та оптимiзацiї" (Кам’янець-По-
12
дiльський, 2012),
— VI мiжнароднiй науково-практичнiй конференцiї студентiв, аспiрантiв
та молодих вчених ”Сучаснi задачi прикладної статистики, промислової, актуарної та фiнансової математики”, присвяченiй 75-рiччю Донецького нацiонального
унiверситету (Донецьк, 2012),
— International conference Modern Stochastics: Theory and Applications III
(MSTA, Kyiv, 2012),
— IV мiжнароднiй науково-практичнiй конференцiї "Системний аналiз.
Iнформатика. Управлiння" (Запорiжжя, 2013),
— IV всеукраїнськiй науково-практичнiй "Iнформатика та системнi науки" (Полтава, 2013),
— Конференцiя молодих учених "ПIДСТРИГАЧIВСЬКI ЧИТАННЯ –
2015" (Львiв, 2015),
а також на науковому семiнарi кафедри прикладної математики Iнституту прикладної математики та фундаментальних наук Нацiонального унiверситету "Львiвська Полiтехнiка" (Львiв, 2013,2015) та на науковому семiнарi кафедри
системного аналiзу та теорiї прийняття рiшень Київського нацiонального унiверситету iменi Тараса Шевченка (Київ, 2015).
Публiкацiї. За результатами дисертацiйних дослiджень опублiковано 13
наукових праць, серед яких 1 наукова стаття у виданнi, що включене до мiжнародної науковометричної бази [16], 4 науковi статтi у фахових журналах України
[17, 18, 19, 21] (загальним обсягом 1,96 умовних друкованих аркушiв), 1 наукова
стаття у вiснику НУЛП [20], та 7 матерiалах i тезах наукових конференцiй.

Список літератури

ВИСНОВКИ
У дисертацiйнiй роботi отримано новi науково-обгрунтованi результати
в галузi системного аналiзу та теорiї прийняття рiшень в умовах невизначеностi, що описується впливами випадкової природи. Дисертацiя є комплексним
дослiдженням, де встановлено збiжнiсть процедури стохастичної оптимiзацiї з
залежною вiд напiвмарковського процесу функцiєю регресiї в схемах усереднення, дифузiйної апроксимацiї та з iмпульсним збуренням, розглянуто поведiнку
флуктуацiй процедури в зазначених схемах. Напiвмарковський процес описує
ширший спектр природнiх та технологiчних процесiв, а нiж марковський, тому
має свої переваги в описi середовища в якому вiдбувається процес.
Основними науковими результатами є:
Вперше отримано достатнi умови слабкої збiжностi процедури до точки
екстремуму в термiнах властивостей функцiї Ляпунова чисто градiєнтної усередненої системи за стацiонарним розподiлом напiвмарковського процесу. Побудовано вигляд генератора процедури в схемi усереднення та розв’язано проблему
сингулярного збурення для такого генератора.
Вперше отримано достатнi умови збiжностi процедури стохастичної оптимiзацiї з iмпульсним збуренням в напiвмарковському середовищi.
Вперше розглянуто неперервну процедуру стохастичної оптимiзацiї в схемi дифузiйної апроксимацiї з залежною вiд напiвмарковського переключаючого
процесу функцiєю регресiї, такої, що задовольняє умовi Лiпшиця в умовах глобального балансу на сингулярне збурення функцiї регресiї. Отримано достатнi
умови збiжностi процедури до точки екстремуму в термiнах властивостей функ-
114
цiї Ляпунова усередненої системи.
Вперше встановлено асимптотичну нормальнiсть флуктуацiї одновимiрної процедури стохастичної оптимiзацiїв схемi дифузiйної апроксимацiї, що описується стохастичним диференцiальним рiвнянням.
Робота має як теоретичний так i практичний характер та може бути корисною при моделювання стохастичних оптимiзацiйних проблем.
Отриманi результати мiстять внесок у дослiдження властивостей випадкових еволюцiй у виглядi стохастичних систем з напiвмарковськими переключеннями. Запропонованi пiдходи можуть бути використанi при розробцi нових
методiв стохастичної оптимiзацiї та їх застосуванню до конкретних прикладних
задач, а також при вивченнi асимптотичних властивостей випадкових еволюцiй з напiвмарковськими переключеннями та при дослiдженнi асимптотичних
флуктуацiй стохастичних систем та процедури стохастичної оптимiзацiї