Стохастичні методи розв'язання задач неопуклого стохастичного програмування та їх застосування

У підрозділі 4.6 метод стохастичних квазіградієнтів Ю.М.Єрмольєва (з усередненням Брука - Немировського - Юдіна Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. - М.: Наука, 1979. - 383 с. ) поширюється для оптимізації функцій сподіваної корисності та наближеної оптимізації функцій ймовірності.

Припустимо, що функція корисності (ризику) F(x) є -увігнутою, а X - замкнена опукла множина. Побудуємо наступну послідовність апроксимацій (x⁰=x⁰ X):

x^k+1 = _X(x^k+_k ^k),

x ^k+1 = (1_k+1)x^k +_k+1 x^k+1, k=0,1,...,

де стохастичний квазіградієнт ^k функції F(x) у точці x^k, такий, що

E{^k | x⁰,..., x^k}F(x^k), E{^k2| x⁰,..., x^k}C< ,

_X - оператор проектування на множину X, _k=_k /₀^k_і, невід'ємні числа _k задовольняють умовам (3). Наприклад, стохастичний квазіградієнт ^k = ^k(x^k,^k) функції (8) можна взяти у вигляді

(x,) = (1/)(f(x,)/) g(x,), g(x,) _x f(x,),

де g(x,) - вимірний по (x,) переріз багатозначного відображення _xf(x,) і ^k, k=0,1,..., - незалежні однаково розподілені спостереження випадкового параметра ..

Теорема 8 [24]. За зроблених припущень для майже усіх траєкторій {x^k}, що породжені вищезазначеним стохастичним квазіградієнтним методом, виконано

1) усі граничні точки послідовностей {x^k}, {x^k} належать множині максимумів argmax _xX F(x);

2) lіm_k F(x^k)=lіm_k F(x^k)=max_xX F(x).

Теорема 9 [24] (швидкість збіжності). Припустимо, що функція F(x) -увігнута та F(x) >0, x X, тоді для будь-якого максимума x* та будь-якої послідовності кроків _k 0 слушні оцінки

F(x*)EF(x^k) (F(x*)/)^{max(1- ,0)}(Ex⁰ x*² +C₀^k_і²)/(2₀^k_і).

5. Стохастичні методи гілок та меж.

Метою цього розділу є розробка стохастичної версії методу гілок та меж для розв'язання неопуклих задач оптимізації, що містять дискретні та неперервні змінні, а також невизначені параметри. Пропонований метод може бути застосований, коли звичайні детерміновані підходи стикаються з труднощами при обчисленні точних меж значень цільової функції. Ці ситуації є типовими для оптимізації дискретних та неперервних стохастичних систем.

Частковими випадками розглянутої задачі є задача перевірки гіпотез, задача навчання автоматів, задача про багаторукого бандита, для яких існують спеціалізовані методи розв'язання. У підрозділі 1.6 розглянуто інші застосування та моделі стохастичної дискретної оптимізації.

Важлива властивість таких задач стохастичної дискретної оптимізації полягає в тому, що число N можливих рішень (дій) може бути надзвичайно великим, а в неперервному випадку - і нескінченним. Отже, використання стандартної техніки перевірки гіпотез або техніки, що розроблена для задач навчання автоматів, стає практично неможливим тому, що вони грунтуються на послідовному спостереженні наслідків усіх допустимих дій.

Формально задача, що розглядається, має вигляд находження глобального мінімуму

mіn_x [F₀(x)= E f₀ (x,)], (9)

за обмежень

F_k(x)= E f_k (x,) 0, k=1,...,K; (10)

x XD Rⁿ, (11)

де f_k(·,), k=0,1,...,K, - деякі неопуклі (наприклад, квазіопуклі) функції; X - дискретна або неперервна множина простої структури (наприклад, перетин деякої дискретної решітки та паралелепіпеду в Rⁿ); множина D={xRⁿ|G(x)0} задається деякою детермінованою функцією G:RⁿR¹, E - математичне сподівання стосовно випадковій величини , що визначена на деякому ймовірнісному просторі (,,P).

Особливо цікавий окремий випадок задачі, коли деякі функції F_k (x) мають вигляд ймовірності:

F_k(x)= P{ f_k(x,)=(f_k1 (x,),..., f_km (x,)) B() R^m }.

Таким чином, функція F_k (x) може бути негладкою, неопуклою та навіть розривною.

Для розв'язання задачі (9) - (11) розвивається стохастична версія методу гілок та меж. Для цього ми виводимо спеціальні стохастичні нижні та верхні межі оптимального значення задач вигляду (9) - (11), побудовані за допомогою перестановки операцій максимізації та математичного сподівання (або оператора ймовірності, або оператора підсумовування) - так звана перестановочна релаксація.

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

Такі межі були введені та вивчені у роботах [13, 14, 19, 20] для розв'язання деяких стохастичних дискретних та неперервних задач глобальної оптимізації. У зв'язку з випадковим характером меж, метод гілок та меж набуває стохастичних рис.

Розглянемо, наприклад, задачу стохастичного дискретного програмування (9) - (11) без обмежень (10):

max _xXD [F(x)= E f (x,)], (12)

Нехай X* - множина рішень, а F* - оптимальне значення задачі. Зробимо наступні припущення.

П1. Існують функції L:2^X R та U:2^X R, такі, що для кожного ZX,

L(Z)F*(Z)=max_xZF(x)U(Z), U(Z)=F(x) для деякого xZ,

і якщо Z вироджується у точку, то L(Z)=F*(Z)=U(Z). Допускаємо також, якщо ZD = , то ця ситуація може бути ідентифікована і, по означенню, L(Z)=U(Z)=+ .

Функції L та U взагалі визначаються за допомогою розв'язання деяких допоміжних стохастичних оптимізаційних задач, що означені на підмножинах Z X. У підрозділі 5.5 розглядаються способи побудови таких допоміжних задач. У загальному випадку можна тільки припускати існування статистичних оцінок величин L(Z) та U(Z).

П2. У деякому ймовірнісному просторі (,,P) для кожної підмножини Z X існує послідовність випадкових величин ^l(Z), l=1,2,..., та ^m(Z), m=1,2,..., таких, що майже напевне

lіm_l ^l(Z) = L(Z), lіm_m ^m(Z) = U(Z).

Концептуальний алгоритм гілок та меж.

У методі гілок та меж вихідна "проста" множина X ітеративно розбивається на підмножини Z X, що утворюють розбиття P_k множини X або його частини. Ключову роль в алгоритмі відіграють рекордні множини Y^k, тобто множини, що мають найменшу нижню межу. Наближені розв'язки x^k задачі вибираються із множин X^k, що мають найменшу верхню межу. В міру того як рекордна множина розбивається на менші підмножини, генеруються нові оцінки цільової функції для усіх підмножин, знаходяться нові наближені розв'язки, далі ітерації повторюються. Так як межі випадкові, то і рекордні множини випадкові, отже усі об'єкти, що генеруються алгоритмом, є випадковими.

Ініціалізація. Сформувати початкове розбиття P₀ ={X}. Обчислити межі ₀ = ^l(0)(X) та ₀ = ^m(0)(X). Покласти k=0.

Розбиття. Вибрати рекордну підмножину Y^kargmіn{_k (Z): ZP_k} та відповідний наближений розв'язок x^kX^kargmіn {_k(Z): ZP_k}. Якщо рекордна підмножина є точкою, то покласти P_k = P_k і йти на крок Оцінка меж. У противному випадку побудувати розбиття P_k(Y^k)={Y_і^k, і=1,2,...} рекордної множини Y^k, таке, що Y^k =_і Y_і^k і Y_і^kY_j^k= для Y_і^k, Y_j^kP_k(Y^k), і j. Визначити нове повне розбиття P_k = (P_k\Y^k ) P_k”(Y^k).

Оцінка меж. Для усіх підмножин ZP_k виберемо деякі оцінки

_k (Z) = ^l(k,Z)(Z) і _k(Z) = ^m(k,Z)(Z) для L(Z) і U(Z) відповідно.

Видалення підмножин. Очистити розбиття P_k від недопустимих підмножин, тобто визначити розбиття P_k = P_k \{ZP_k : ZD=}. Покласти k:=k+1 і йти на крок Розбиття.

Зауваження. Якщо оцінки є точними, тобто _k (Z) L(Z) і _k(Z)U(Z), тоді на кроці Видалення підмножин можна також видаляти усі підмножини Z, для яких

_k (Z) > _k(Z). (13)

Збіжність методу встановлюється наступною теоремою.

Теорема 10 [13]. Припустимо, що індекси l(k,Z) і m(k,Z) вибираються таким чином, що якщо ZP_k для нескінченної кількості k, то майже напевне lіm_k l(k,Z) = lіm_k m(k,Z) = +. Тоді з ймовірністю одиниця існує номер ітерації k*, такої, що для усіх k k*:

1) рекордні множини Y^k є точками і Y^k X*;

2) наближені розв'язки x^k X*.

Ймовірнісні оцінки точності поточних наближень x^k можуть бути одержані за наступних додаткових припущень.

П3. Для кожного Z X випадкові величини _k (Z), _k(Z), k=0,1,..., незалежні і нормально розподілені з середніми значеннями L(Z), U(Z) та дисперсіями _k(Z), _k (Z) відповідно.

П4. Для дисперсій _k(Z), _k (Z), Z X, відомі верхні межі:

_k(Z) _k(Z), _k (Z) _k (Z).

Візьмемо довірчі межі для L(Z), U(Z) у вигляді

_k (Z) =_k (Z)c(k)_k(Z), _k(Z) = _k(Z) c(k)_k (Z).

де константи c(k), k=0,1,..., такі, що

(c_k)=(1/2)_-^c(k) e^-/2 d = 1 _k, 0 < _k < 1.

Лема 3 [13]. В припущеннях П3, П4 для кожного k справедлива наступна оцінка точності:

P{F(x^k) F* _k(X^k) mіn{_k (Z)|ZP_k} (1 _k).

Важливою рисою методу гілок та меж є можливість видаляти за умовою (13) неперспективні підмножини із поточного розбиття за допомогою нижніх та верхніх меж оптимальних значень цільової функції на підмножинах розбиття. В стохастичному випадку, одначе, в силу випадковості меж видалення підмножин може призвести до втрати оптимального розв'язку. У наступному правилі видалення підмножин ми не видаляємо їх на кожній ітерації, а робимо це тільки після виконання досить великої кількості ітерацій N, а також після обчислення незалежної оцінки значення цільової функції у точці поточного наближеного розв'язку. Зробимо наступне додаткове припущення.

П5. Існує рівномірна межа ² для дисперсій усіх випадкових величин _k (Z) і _k(Z), Z X, k=1,2,...

Правило видалення підмножин. Після N кроків зупиняємося, візьмемо рекордну підмножину X^N (або Y^N ) із фінального розбиття P_N та зробимо N додаткових спостережень _Nі(X^N ), і=1,...,N, і обчислимо нову оцінку для U(X^N ): U(X^N)= (1/N) ₁^N _Nі (X^N ).

Тоді для деякої точності (0,1) видалимо усі підмножини ZP_N такі, що L_N(Z) > U(X^N) + 2c_N, де c_N = ²/(N).

Лема 4 [14]. Нехай x* - деякий розв'язок задачі (12). Тоді

P{ x* втрачається під час видалення} 2.

У підрозділі 5.3 та у [20] стохастичний метод гілок та меж поширюється на задачі з нелінійними стохастичними обмеженнями (10), а у розділі 5.4 та у [14] - на неперервні багатоекстремальні задачі стохастичного програмування.

Основна проблема у стохастичному методі гілок та меж - це оцінка меж оптимальних значень для задач стохастичного програмування.

Як верхню межу U(X) оптимального значення F*(X) можна взяти значення цільової функції у деякій допустимій точці x' X:

U(X) = F(x') = E f(x',).

Важливо вибрати точку x' таким чином, щоб значення F(x') було якомога меншим. Такі точки можуть бути найдені будь-яким (можливо, еврістичним) методом локальної стохастичної оптимізації.

Для побудови нижніх меж в підрозділі 5.5 розглядаються два загальних підходи: перестановка операторів мінімізації та математичного сподівання або оператора ймовірності (перестановочна релаксація) і двоїсті оцінки. Крім того, деякі відомі детерміновані методи побудови меж (такі, як релаксація умов цілочисельності) можуть бути використані у комбінації з зазначеними підходами. Ідея перестановочної релаксації для задачі (12) ілюстрована наступною нерівністю [13, 14, 19]:

F*(X)=mіn_xX Ef(x,) E mіn_xXf(x,) = Ef(x*(),), (14)

де x*( ) argmіn _xX f(x, ). Таким чином, величина L(X)=Ef(x*(),) дає нижню оцінку оптимального значення F*(X). У багатьох випадках для фіксованого розв'язок x*( ) може бути знайдено порівняно легко. Складність задач стохастичої дискретної оптимізації виявляється тут у тому, що для отримання оцінки (14) необхідно розв'язати багато (тобто для кожного ) детермінованих оціночних задач вигляду mіn_xX f(x,).

Простий шлях поліпшити нижню межу (14) та її оцінку Монте -Карло полягає у використанні M незалежних копій ^l випадкової величини :

F*(X)=(1/M)mіn_{xX 1}^mEf(x, ^l)

E_M mіn_xX(1/M)₁^Mf(x,^l) =L_M(X), (15)

де E_M - оператор математичного сподівання з усіх ^l. Більше того, збільшуючи число спостережень M всередині операції мінімізації, можна зробити точність емпіричних оцінок L_M (X) як завгодно високою.

Використання емпіричних оцінок (15) - не єдиний спосіб використати кратні спостереження. Нехай знову ^l, l=1,...,M (непарне) - незалежні копії . Тоді задача мінімізації F(x) еквівалентна мінімізації з x X функції

(F(x))^M=(E f(x,))^M = ₁^M E f(x,^l ) = E {₁^M f(x,^l )},

де в останній рівності ми використали незалежність ^l, l=1,...,M. Перестановка операторів мінімізації та математичного сподівання призводить до наступної стохастичної межі:

mіn_xX F(x) (E mіn_xX {₁^M f(x,^l )})^1/M. (16)

Якщо ln f(·,) - увігнута функція, то внутрішня оптимізаційна задача в (16) еквівалентна задачі опуклого програмування: mіn_xX{₁^Mlnf(x,^l)}. Існує широкий клас так званих -увігнутих функцій f(·,) (які розглядалися у підрозділі 4.2), для яких внутрішня задача в (16) також зводиться до задачі опуклого програмування.

У підрозділі 5.5 метод перестановочної релаксації проілюстровано на задачах фінансування проектів, розміщення виробництва, оптимізації портфеля цінних паперів, контролю над викидом забруднень.

Нижні межі для F*(X) іноді можна отримати виходячи із властивості монотонності випадкової цільової функції f(x,) (і, отже, монотонності F(x)). Монотонність випадкових показників функціонування систем f(x,) може допускатися щодо таких змінних x, як інвестиції, ресурси, продуктивність і т. ін. Нижні межі для F*(X) також можуть бути отримані за допомогою стохастичних дотичних мінорант функцій f(x,) та методу перестановочної релаксації. Детерміновані дотичні міноранти у контексті глобальної оптимізації були введені С.А.Піявським Пиявский С.А. Об одном алгоритме поиска абсолютного экстремума функций // Журн. вычисл. математики. и мат. физики. - 1972. - 12, N 4. - C.888-896. та використані у [8]. В підрозділі 5.5 та у [19] ми використовуємо стохастичні дотичні міноранти цільової функції F(x) для потреб глобальної стохастичної оптимізації.

Двоїсті оцінки в комбінації з методами негладкої оптимізації широко використуються в детермінованому дискретному програмуванні Див., наприклад, Shor N.Z. Nondіfferentіable optіmіzatіon and polynomіal problems. - Dordrecht: Kluver Academіc Publіshers, 1998. - 600 p. ^. У підрозділі 5.5 також розглядаються особливості двоїстих оцінок у комбінації з методом перестановочної релаксації стосовно до задач стохастичної оптимізації.

У підрозділі 5.6 будуються межі для ймовірностей. Розглянемо задачу

max_xX[P(x)=P{ f(x, )B}]= P*(X),

де X Rⁿ, f(x,)=(f₁(x,),...,f_m(x,)) - випадкова вектор-функція; B - замкнена підмножина в R^m.

Оцінимо зверху P*(X) за допомогою перестановки операторів максимізації та ймовірності (перестановочна релаксація). Очевидно,

P*(X) P{ x()X: f(x(),) B}= U(X)

P{ x()conv X: f(x(),) B}= U(X), (17)

де conv X - опукла оболонка множини X.

Наприклад, щоб обчислити стохастичні оцінки (X',)=_A(X')() величини U(X'), треба перевірити для даного допустимість умов f(x',)B, x'X. Якщо функції f_і(x,), і=1,...,m, лінійні по x, X і B - багатогранні множини, то задача перевірки спільності умов f(x',)B, x'X є задачею лінійного цілочислового програмування (і лінійною задачею для умов f(x',)B, x' conv X).

Можна зробити межі (17) точнішими, одночасно використовуючи декілька незалежних спостережень (₁,...,_l )= ^l випадкової величини . Тоді

U_l(X)= P^1/l{ x()X: f(x(^l),₁)B,..., f(x(^l),_l)B }

є верхня межа для ймовірностей P(x), xX.

У підрозділі 5.7, а також у [13, 14, 20] наводяться приклади чисельного розв'язання задач стохастичного дискретного програмування, стохастичної глобальної оптимізації та глобальної оптимізації ймовірностей стохастичним методом гілок та меж.

6. Метод емпіричних середніх.

У розділі 6 та у [6] відомий метод емпіричних середніх (або статис-тичний метод) поширюється на задачі стохастичного програмування, що містять складні (складані і недиференційовні) функції ризику. Збіжність методу емпіричних середніх трактується як наслідок стійкості деякої задачі функціонального параметричного програмування. Швидкість збіжності методу вивчається на основі поняття нормалізованої збіжності випадкових величин.

Розглянемо задачу стохастичного програмування вигляду

F(x) = E₀(x,E₀(x,),...,E_m(x,),) mіn_xX, (18)

f_j(x) = E_j(x,) = ₀(x,)P(d), jІ={1,...,m};

g₀(x,y) = E₀(x,y,)= ₀(x,y,)P(d), yY R^m;

X - компакт в Rⁿ; Y - деяка множина в R^m; ?, (,,P) - деякий ймовірнісний простір; _j :X R¹ і ₀ :XY R¹ - інтегровні при кожному x X і y Y функції. В часткових випадках може бути F(x) = E₀(x,), F(x) =max_jJ E_j(x,), F(x)=D₀(x,)=E₀²(x,) (E₀(x,))² і т.п.

Метод емпіричних середніх (або статистичний метод) для розв'язання задачі (18) полягає в наступному: вона замінюється послідовністю задач вигляду

F_S(x)=(1/s)₁^s₀(x,(1/s)₁^s₀(x,_k),...,(1/s)₁^s_m(x,_k),_k) mіn_xX, (19)

де _k - незалежні однаково розподілені випадкові величини (спостереження), розподіл яких визначається мірою P.

Позначимо F*, F_s* і X*, X_s* оптимальні значення та розв'язки задач (18), (19), X*={xX| F(x) F*+}, X_s*= {xX| F_s(x) F_s*+} - наближені розв'язки задач (18), (19), 0.

Наша мета полягає в тому, щоб дослідити збіжність, у деякому ймовірнісному сенсі, випадкових величин F_s*, X_s*, X_s* до відповідних значень F*, X*, X*.

Наступна теорема визначає умови збіжності майже напевне методу емпіричних середніх для розв'язання задачі мінімізації складної функції ризику при детермінованих обмеженнях.

Теорема 11 (збіжність). Припустимо, що

1) функції _j(x,), j=0,...,m, неперервні по xX, а ₀(x,y,) неперервна по (x,y)X R^m за всіх , та вимірні по за фіксованих x,y;

2) існують інтегровні функції C_j(), j=0,...,m, такі, що для всіх xX, |_j(x,)| C_j();

3) для будь-якого компакту YR^m існує невід'ємна інтегровна функція D(), така, що для всіх (x,y)XY, |₀ (x,y,)|D().

Тоді функції _{0, j}, F неперервні, F_s* F* і відхилення (X_s*,X*)0 майже напевне.

Наступна теорема визначає умови збіжності та швидкість збіжності (порядку 1/s ) за функціоналом для методу емпіричних середніх.

Теорема 12 (швидкість збіжності). Припустимо, що

1) функції _j(x,), j=0,...,m, неперервні по xX, а ₀(x,y,) неперервна по (x,y)X R^m за всіх , та вимірні по за фіксованих x,y;

2) функції _j(x,) і ₀(x,y,) інтегровні (по ) в квадраті для всіх xX і yR^m;

3) існують інтегровні в квадраті функції L_j(), j=1,...,l, такі, що для будь-яких x₁,x₂X виконано

|_j(x₁,) _j(x₂,)| L_j() x₁ x₂;

4) для будь-якого компакту Y R^m існують інтегровні в квадраті функції M₀() такі, що для будь-яких x₁, x₂ X і y₁, y₂ Y буде

|₀(x₁,y₁,) ₀(x₂,y₂,)| M₀() (x₁ x₂ + y₁ y₂ ).

Тоді F_s* F* і (X_s*,X*) 0 майже напевне, і крім того, F_s*() F* нормалізовано (див. означення 7) зі швидкістю 1/s. Якщо додатково до умов 1)-4) виконано

5) функція F(x) в задачі (17) опукла на опуклій компактній множині X Rⁿ, то відхилення (X_s*,X*) 0 нормалізовано зі швидкістю 1/s.

У підрозділі 6.6 вивчається так звана нормалізована збіжність випадкових величин, що використовується в теоремі 12.

У теорії ймовірностей відомі наступні основні види збіжності випадкових величин: майже напевне, в середньому, за ймовірністю та розподілом. При вивченні швидкості збіжності (скажімо, до нуля) випадкової послідовності _n, n=1,2,..., також розглядають збіжність (майже напевне і т.п.) послідовностей вигляду {_nn}, де числова послідовність {_n 0} така, що lіm_n 1/_n=0. У тому випадку, коли lіm_nP{_nn }=0 >0, говорять про збіжність {_n} до нуля за ймовірністю зі швидкістю 1/_n. Часто при дослідженні стохастичних ітераційних алгоритмів оптимізації і в прикладних застосуваннях методу емпіричних середніх отримуються оцінки швидкості збіжності, які (після елементарних перетворень) мають вигляд

P{_nn<t}F(t) t 0, або lіmіnf_n P{_nn<t}F(t) t 0, (20)

де невід'ємна числова послідовність {_n} задовольняє умові lіm_nn=+, а F - деяка одновимірна функція розподілу. Ясно, що твердження (20) близькі за сенсом до твердження про збіжність {_n} до нуля за ймовірністю з деякою швидкістю.В [3, 5, 7, 23] співвідношення (20) покладені в основу означення так званої нормалізованої збіжності випадкових величин, яка об'єднує в одному понятті збіжність за ймовірністю (з деякою швидкістю) та слабку збіжність (норм).

Означення 7. Нехай (,,P) - ймовірнісний простір, X - сепара-бельний метричний простір з функцією відстані (,). Будемо вважати, що послідовність випадкових величин _n : X, n=1,2,..., нормалізовано збігається до випадкової величини : X зі швидкістю (послідовності) 1/_n та розподілом F(t), якщо існує послідовність чисел _n +, 0 _n <+, і функція розподілу F:R¹ [0,1], такі, що

lіmіnf_n P{_n(_n,)<t} F(t) tR¹, (21)

де lіmіnf позначає нижню границю послідовності.

Теорема 13 [3]. Якщо співвідношення (21) виконано рівномірно по t, то існує одновимірна функція розподілу Ф(t), така, що для всіх n і tR¹ має місце P{_n(_n,)<t} Ф(t).

У підрозділі 6.6 та у [3, 5, 7, 23] визначені наступні властивості нормалізованої збіжності. Із нормалізованої збіжності виходить збіжність за ймовірністю (з деякою меншою швидкістю). Обернено, формально збіжність за ймовірністю з деякою швидкістю є нормалізована збіжність з виродженою функцією розподілу при F(t)={0 при t0, і 1 при t> 0}. Зі збіжності у середньому випливає не тільки збіжність за ймовірністю (що загальновідомо), але й нормалізована збіжність відповідних випадкових величин. Нормалізована збіжність зберігається при гельдерових перетвореннях випадкових величин. Вона зберігається також при додаванні, множенні, діленні та декартовому добутку нормалізовано збіжних послідовностей випадкових величин. Кожна гранична теорема теорії ймовірностей тягне за собою нормалізовану збіжність відповідних випадкових величин. Для нормалізованої збіжності має місце критерій збіжності типу критерію Коші.

Отже, серед послідовностей, що збігаються за ймовірністю з деякою швидкістю, нормалізована збіжність вилучає по-різному збіжні послідовності. Для нормалізовано збіжних випадкових величин можна будувати довірчі області (чого неможливо зробити для загальних, збіжних за ймовірністю з деякою швидкістю, випадкових величин), і, крім того, у застосуваннях часто доводиться більше, ніж збіжність за ймовірністю з деякою швидкістю, а саме нормалізована збіжність.

ВИСНОВКИ

1. У дисертації розглянуто велику кількість прикладних задач неопуклого стохастичного програмування з негладкими, розривними або дискретними функціями, для яких немає адекватних методів розв'язання.

2. Досліджено властивості задач неопуклого стохастичного програ-мування: моделі неопуклих негладких залежностей, субдиференціальні властивості функцій очікуваної корисності, необхідні умови оптимальності, оцінки оптимальних значень.

3. Розроблені та досліджені стохастичні методи розв'язання задач неопуклого стохастичного програмування, побудовані на використанні реалізацій випадкових функцій задачі або їх градієнтів.

4. Зокрема, відомий метод стохастичних квазіградієнтів Ю.М.Єрмольєва поширений на задачі локальної оптимізації стохастичних систем з дискретними подіями, задачі оптимізації функцій очікуваної корисності, задачі оптимізації ймовірностей з неопуклими негладкими та розривними функціями.

5. Зокрема, розроблено та обгрунтовано стохастичний метод гілок та меж для розв'язання задач стохастичної глобальної та стохастичної дискретної оптимізації, глобальної оптимізації ймовірностей.

І, на закінчення, автор вдячний передчасно відійшлому співавтору монографії [1] академіку Володимиру Сергійовичу Михалевичу.

Автор щиро дякує своїм колегам та співавторам Ю.М.Єрмольєву, А.М.Гупалу, М.В.Роєнку, Р.Ветсу, А.Рущинському, Г.Пфлюгу за неоціниму допомогу і співробітництво під час виконання цієї роботи.

ЛІТЕРАТУРА

1. Михалевич В.С., Гупал А.М., Норкин В.И. Методы невыпуклой оптимизации. - М.: Наука, 1987. - 286 с.

2. Гупал А.М., Норкин В.И. Алгоритм минимизации разрывных функций // Кибернетика. - 1977. - N 2. - C.73-75.

3. Ермольев Ю.М., Норкин В.И. Нормализованная сходимость слу-чайных величин и ее применения //Кибернетика. -1990.-N 6.-C.89-93.

4. Норкин В.И., Роенко Н.В. a-вогнутые функции и меры и их применения // Кибернетика и системный анализ. - 1991. - N 6. -

С.77-88.

5. Ermolіev Yu.M., Norkіn V.І. Normalіzed convergence іn stochastіc optіmіzatіon // Ann. of Oper. Res. 1991. 30. P.187-198.

6. Норкин В.И. Об условиях и скорости сходимости метода эмпи-рических средних в математической статистике и стохастическом про-граммировании // Кибернетика и системный анализ. - 1992. - N 2. - C.107-120.

7. Норкин В.И. Нормализованная сходимость случайных величин // Кибернетика и системный анализ. - 1992. - N 3. - C.84-92.

8. Норкин В.И. О методе Пиявского для решения общей задачи глобальной оптимизации //Журн. вычисл. математики и мат. физики. - 1992. - 32, N 7. - C. 992-1006.

9. Ermolіev Yu.M, Norkіn V.І. and Wets R.J-B. The mіnіmіzatіon of semі-contіnuous functіons: Mollіfіer subgradіents // SІAM J. Contr. and Opt. 1995. N 1. P.149-167.

10. Ermolіev Yu.M., Norkіn V.І. Om nonsmooth and dіscontіnuous problems of stochastіc systems optіmіzatіon // European J. of Oper. Research. 1997. 101. P. 230-244.

11. Ермольев Ю.М., Норкин В.И. Стохастический обобщенный градиентный метод для решения невыпуклых негладких задач стохас-тической оптимизации//Кибернетика и системный анализ.- 1998. -

N 2.- С.50-71.

12. Ермольев Ю.М., Норкин В.И. О нестационарном законе боль-ших чисел для зависимых случайных величин и его применении в сто-хастической оптимизации //Кибернетика и системный анализ. - 1998. - N 4. - С.94-106.

13. Norkіn V.І., Ermolіev Yu.M. and Ruszczynskі A. On Optіmal Allocatіon of Іndіvіsіbles under Uncertaіnty //Operatіons Research. 1998. 46, N 4. P.381-395.

14. Norkіn V.І., Pflug G.Ch. and Ruszczynskі A. A Branch and Bound Method for Stochastіc Global Optіmіzatіon // Mathematіcal Programmіng. 1998. 83. P.425-450.

15. Норкин В.И. Построение релаксационных методов невыпуклой негладкой оптимизации // Мат. методы анализа и оптимизации систем, функционирующих в условиях неопределенности / Под ред. Ю.М.Ермольева, И.Н.Коваленко. - Киев: Ин-т кибернетики В.М.Глушкова АН УССР, 1986. - С.35-41.

16. Норкин В.И. Метод приведенного градиента для решения задач негладкого и стохастического программирования // Мат. методы анализа и оптимизации сложных систем, функционирующих в условиях неопределенности. - Киев: Ин-т кибернетики им. В.М.Глушкова АН УССР, 1989. - С. 4-9.

17. Норкин В.И. О целочисленном стохастическом программировании // Математические методы моделирования и системного анализа в условиях неполной информации. - Киев: Ин-т кибернетики им. В.М.Глушкова АН УССР, 1991. - С. 28-34.

18. Норкин В.И. Оптимизация функций риска // Модели и методы исследования операций, теории риска и надежности. - Киев: Ин-т кибернетики им. В.М.Глушкова АН Украины, 1992. - С.13-23.

19. Норкин В.И. Глобальная стохастическая оптимизация: метод ветвей и вероятностных границ // Методы управления и принятия решений в условиях риска и неопределенности. - Киев: Ин-т кибернетики им. В.М.Глушкова АН Украины, 1993. - С. 3-12.

20. Norkіn V.І. Global Optіmіzatіon of Probabіlіtіes by the Stochastіc Branch and Bound Method / Lecture Notes іn Econ. and Mat. Systems 458. Stochastіc Progr. and Tech. Appl. (K.Martі and P.Kall, eds.).Berlіn: Sprіnger, 1998. P.186-201.

21. Ermolіev Yu.M., Norkіn V.І. Constraіned optіmіzatіon of dіscontіnuous systems / Lecture Notes іn Econ. and Mat. Syst. 458. Stochastіc Progr. and Tech. Appl. (K.Martі and P.Kall, eds.). Berlіn: Sprіnger, 1998.P.128-142.

22. Норкин В.И. Оптимизация вероятностей. - Киев, 1989. - 19 c. - (Препр./ АН УССР. Ин-т кибернетики им. В.М.Глушкова; 89-6).

23. Норкин В.И. Устойчивость стохастических оптимизационных моделей и статистические методы стохастического программирования. - Киев, 1989. - 24с. - (Препр./ АН УССР. Ин-т кибернетики им. В.М. Глушкова; 89-53).

24. Norkіn V.І. The anaysіs and optіmіzatіon of probabіlіty functіons //Workіng Paper WP-93-6, Іnt. Іnst. for Appl. Syst. Anal. Laxenburg, Austrіa, 1993. 23 p.

25. Ermolіev Yu.M. and Norkіn V.І. Stochastіc generalіzed gradіent method wіth applіcatіon to іnsurance rіsk management // Іnterіm Report ІR-97-021, Іnt. Іnst. for Appl. Syst. Anal. Laxenburg, Austrіa, 1997. 19p.

Размещено на Allbest.ru

...