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

Размещено на http://www.allbest.ru/

Національна академія наук України

Інститут кібернетики імені В. М. Глушкова

Автореферат дисертації на здобуття наукового ступеню

доктора фізико-математичних наук

01.05.01 - теоретичні основи інформатики та кібернетики

СТОХАСТИЧНІ МЕТОДИ РОЗВ'ЯЗАННЯ ЗАДАЧ НЕОПУКЛОГО СТОХАСТИЧНОГО ПРОГРАМУВАННЯ ТА ЇХ ЗАСТОСУВАННЯ

НОРКІН Володимир Іванович

Київ 1998

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

mіn_xX [F(x)=Eu(f(x,),)], mіn_xX [P(x)=P{f(x,)B()}],

на основі спостереження значень (або градіентів) функції f(·,щ), де функції f(·,щ), u(·,щ), P(x) і F(x) можуть бути неопуклими, негладкими і навіть розривними, а змінна xXRⁿ може бути неперервною або дискретною; щ - випадкова величина; E і P - знаки математичного очікування та ймовірності по , B()R^m, f(,):RⁿR^m, u(,):R^mR¹.

Актуальність теми. Теорія опуклого стохастичного програмування розроблена в роботах Дж.Данцига, Ю.М.Єрмольєва, П.Калла, А.Прекопи, Р.Ветса, Д.Б.Юдіна та ін. Адреса http://mally.eco.rug.nl у мережі Іnternet містить бібліографію (понад 3000 посилань) робіт по стохастичному програмуванню (складена M.H. Van der Vlerk). Однак існує велика кількість прикладних задач неопуклого стохастичного програмування. Це, напри клад, задачі оптимізації динамічних систем з дискретними випадковими подіями (систем обслуговування з чергами, мереж зв'язку, гнучких автоматизованих виробництв, технічних систем з відмовами та ін.). Показники функціонування таких систем у загальному випадку є неопуклими негладкими функціями від параметрів систем і часто мають вигляд математичного сподівання (наприклад, середній час очікування обслуговування, середній час надходження повідомлення, середній час безвідмовної роботи і т.п.). Також є цікавою оптимізація цих показників за параметрами при обмеженнях на область допустимої зміни параметрів. Локальна оптимізація цих показників у загальному випадку повинна проводитися методами негладкого стохастичного програмування (наприклад, ліпшіцевого). Спеціальний випадок гладких показників є вивченим у роботах X.R.Cao, P.W.Glynn, Y.C.Ho, М.К.Кривуліна, G.Ch.Pflug, R.Rubіnsteіn, R.Surі.

Багато систем з дискретними подіями мають розривні показники функціонування (довжини черг в системах масового обслуговування, час обслуговування в системах з відмовами та регенерацією, рівні запасів за випадкового попиту в економічних системах). Локальна оптимізація цих систем потребує зовсім нового аналітичного апарату і відповідних чисельних методів (J.P.Aubіn, В.Д.Батухтін, F.H.Clarke, В.Ф.Дем'янов, Б.Ш.Мордухович, Б.Н.Пшеничний, R.T.Rockafellar, О.М.Рубінов, Н.З.Шор, R.J-B.Wets та ін.)

При оптимізації систем з дискретними подіями постає питання про глобальну оптимізацію системи, оскільки функції, що оптимізуються, взагалі неопуклі. Можна було б застосувати загальновідомі методи глобальної оптимізації, але справа ускладнюється тим, що функції, які підлягають оптимізації, являють собою математичні сподівання, тобто багатовимірні інтеграли, та їх точне обчислення або дуже трудомістке, або практично неможливе. Тому необхідні особливі підходи до глобальної оптимізації таких стохастичних систем. Серед підходів, які відомі на даний час, слід відмітити методи керованого випадкового пошуку (E.Aaarts, А.О.Жиглявський, S.Kіrkpatrіck, H.Kushner, Й.Б.Моцкус, Л.А.Растригін, Д.Б.Юдін та ін.)

Більшість класичних задач дослідження операцій, які часто формулюються як задачі дискретного (або мішаного) програмування (задача про рюкзак, про призначення, про розміщення, про розподілення ресурсів та ін.), в загальному випадку можуть містити випадкові параметри. В цьому випадку вони повинні бути переформульовані як задачі стохастичного дискретного програмування (одно-, дво- або багато-етапного, з ймовірнісними обмеженнями, з функціями ризику). Формально задача дискретного стохастичного програмування - це задача вибору, наприклад, мінімального математичного сподівання з скінченної (астрономічної) множини варіантів. При невеликій кількості варіантів - це задача математичної статистики. Деякі методи розв'язання задач стохастичного цілочисленного програмування розроблені в роботах І.Л.Авербаха, G.Laporte, F.H.Louveaux, A.H.G.Rіnnoy-Kan, R.L.Schultz, L.Stougіe, M.H.Van der Vlerk, Д.Б.Юдіна та ін. Адреса http://mally.eco.rug.nl у мережі Іnternet містить понад 130 посилань на роботи по стохастичному цілочисловому стохастичному програмуванню.

Будь-яка задача стохастичної оптимізації є сама по собі задачею багатокритеріальної оптимізації: по суті, кожній реалізації випадкових параметрів (сценарію) відповідає своя цільова функція і свій розв'язок. У стохастичному програмуванні, як правило, агрегують ці випадкові цільові функції за допомогою операцій математичного сподівання. Однак це не єдиний спосіб побудови узагальненої цільової функції. Інша важлива функція такого роду - це функція ймовірності, яка виражає ймовірність того, що деяка випадкова величина, що залежить від неперервних та дискретних параметрів, не перебільшує заданої межі або належить заданій області. За допомогою функцій ймовірності описують надійність технічних систем, ризик в економіці та бізнесі. Локальна та глобальна оптимізація функцій ймовірності - це своєрідна спеціальна задача стохастичного програмування, яка потребує особливих методів розв'язання. Задача локальної оптимізації гладких функцій ймовірності розглянута в роботах А.І.Кібзуна, І.М.Коваленка, Р.Леппа, К.Martі, О.М.Наконечного, Б.Т.Поляка, А.Prekopa, Е.Райка, Е.Тамм, С.П.Урясьєва, Т.Szantaі та ін.

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

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

Наукова новизна результатів роботи полягає в наступному.

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

2. Введені та вивчені деякі нові класи розривних функцій (кусково-неперервні, неперервні за напрямками, сильно напівнеперервні знизу).

3. Для розривних функцій уведено та вивчено нове поняття зглад-женого субдиференціала, вивчено його зв'язок з субдиференціалами Ф.Кларка, Р.Т.Рокафеллара, Дж.Варги та Б.Ш.Мордуховича. Для опису сингулярних (нескінченних) значень градієнтів розривних функцій уведено та досліджено нове поняття розширеного згладженого субдиференціала у "космічному" векторному просторі Р.Т.Рокафеллара та Р.Ветса.

4. Знайдені необхідні умови екстремуму в термінах згладжених субдиференціалів для неперервних та розривних функцій за неопуклих обмежень.

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

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

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

8. Для розв'язання "ущелинних" задач стохастичного неопуклого програмування запропоновано та обгрунтовано методи усереднених стохастичних градієнтів, наприклад, стохастичні методи "важкої кульки" та "ущелинного кроку".

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

10. Запропоновано новий прийом перестановочної релаксації (пере-становки операторів мінімізації та математичного сподівання або ймо-вірності (або підсумовування)) для оцінки знизу оптимальних значень задач стохастичної дискретної та стохастичної глобальної оптимізації.

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

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

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

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

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

Апробація роботи. Результати роботи доповідалися на ІV-VІІ Міжнародних конференціях по стохастичному програмуванню (Енн-Арбор, США, 1989; Удіне, Італія, 1992; Нахарайя, Ізраїль, 1995), на Міжнародному математичному конгресі (Берлін, Німеччина, 1998), на XV Міжнародному симпозіумі по математичному програмуванню (Енн-Арбор, США, 1994), на міжнародних симпозіумах "Глобальна оптимізація" (Шопрон, Угорщина, 1990), "Апроксимація задач стохастичного програмування" (Лаксенбург, Австрія, 1993), "Стохастичне програмування" (Берлін, Німеччина, 1994), "Негладка та розривна оптимізація і застосування" (Лаксенбург, Австрія, 1995), "Стохастична оптимізація: обчислювальні методи та технічне застосування" (Ньюбіберг/Мюнхен, Німеччина, 1996), на міжнародній конференції ІNFORMS (Сан Дієго, США, 1997). Матеріали дисертації обговорювалися на наукових семінарах в Інституті кібернетики ім. В.М.Глушкова НАН України, Інституті математики НАН України, Національному технічному університеті України, Інституті системного аналізу НАН України та Міносвіти України, а також на факультеті кібернетики Київського національного університету ім. Т.Г.Шевченка.

Публікації. Результати роботи опубліковані у 25 друкованих роботах (із них 13 з співавторами), у тому числі в одній монографії (з співавторами), 13 журнальних публікаціях, 7 статтях в зібраннях праць, 4 препринтах.

Структура та обсяг роботи. Дисертація складається з вступу, 6 розділів, висновків та списку літератури. Обсяг роботи - 250 сторінок, 3 рисунки, 4 таблиці. Список літератури містить 337 найменувань.

неопуклий стохастичний програмування локальний

ЗМІСТ РОБОТИ

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

1. Задачі неопуклої стохастичної оптимізації.

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

Під функцією ризику F(x), що залежить від параметрів x, мається на увазі будь-який функціонал від розподілу випадкових "збитків-виграшу" f(x,), що відповідає тому або іншому вибору параметрів x та реалізації випадкових параметрів . За допомогою функцій ризику здійснюється вибір раціональних рішень за умов стохастичної невизначеності.

У підрозділі 1.1 та у [18] обговорюються математичні властивості функцій ризику та розглядаються методи прийняття рішень на базі функцій ризику. Типовими представниками функцій ризику є функції математичного сподівання F(x)=Ef(x,), дисперсії F(x)=E(f(x,)Ef(x,))², ймовірності F(x)=P{f(x,)c} та ін., що залежать від параметрів xRⁿ, причому випадкові функції можуть бути неопуклими та негладкими. У підрозділі 1.5 та в [10, 11, 25] наведені приклади задач оптимізації деяких систем з дискретними випадковими подіями - DES, у яких випадкові функції f(x,) будуються з гладких функцій за допомогою операцій максимуму та мінімуму. Наприклад, задача максимізації середнього часу життя мережі має вигляд

max_{x X} [F(x)= E max_pP mіn_ep f_ep(x,)], (1)

де p - деякий шлях з множини P шляхів, що ведуть від входу до виходу мережі; f_ep(x,) - випадковий час життя елемента e шляху p. У даному випадку функція корисності u(t)=max_pP mіn_ep t_ep є неопуклою та негладкою. Проблема полягає в обчисленні стохастичних узагальнених градієнтів неопуклої негладкої функії F(x).

Під функцією сподіваної корисності маються на увазі функції вигляду F(x)=Eu(f(x,)), де функція u(·) виражає корисність (для особи, що приймає рішення) тих або інших значень f(·,·). Ясно, що корисність u(f(x,)) може бути неопуклою по x, навіть якщо функція f(x,) опукла по x. Якщо u(·)= c(·), де c(t)={0 для t<0 та 1 для t ? 0}, відповідна функція сподіваної корисності співпадає з функцією ймовірності. Коли u(t)=max(0,t) відповідна функція корисності є функція ризику вигляду F(x)=Ef(x)c(f(x,)). Очевидно, функція ймовірності може бути негладкою і навіть розривною. Властивості функції ймовірності та інших функцій сподіваної корисності (неперервність, узагальнена диференційовність, квазіувігнутість) детально розглядаються у підрозділі 4.4.

Функція u(·) може бути функцією належності (0u()1) розмитої цілі бажаної області значень критерію f, тоді u(f(x,)) виражає ступінь досягнення розмитої цілі при розв'язку x, а F(x)= Eu(f(x,)) виражає сподівану ступінь досягнення цілі. У підрозділі 1.4 та в [4] обговорюються математичні властивості задачі нечіткої оптимізації.

На практиці задача прийняття рішень або оптимізації функціонування деякої стохастичної системи зводиться до оптимізації тих або інших функцій ризику або їх комбінацій за обмежень. Функції ризику можуть бути неопуклими, негладкими і навіть розривними та можуть залежати від неперервних та дискретних параметрів. У підрозділах 1.5 - 1.8 наведені приклади задач стохастичної оптимізації з такими функціями ризику (оптимізація зупинки небезпечного виробництва, стохастичних мереж з відмовами, функціонування мереж зв'язку, простої транспортної лінії, емісії забруднювачів, розміщення виробництва, реконструкції стохастичної мережі, ризику у страховому бізнесі, фінансування проектів, портфеля цінних паперів та ін.). Актуальною є задача розробки методів локальної оптимізації таких складних функцій ризику. Цьому присвячені розділи 2 - 4. Оскільки функції ризику можуть бути неопуклими, ми не можемо уникнути проблеми глобальної оптимізації таких функцій, що вивчається в розділі 5.

Якщо параметр x приймає дискретні значення, то задача вибору, скажімо, мінімального математичного сподівання F(x)= Ef(x,) на основі реалізацій f(x,) є класичною задачею математичної статистики. Відмінність задачі стохастичної дискретної оптимізації полягає в тому, що число можливих розв'язків x може бути астрономічно великим. Наприклад, стохастична двоетапна задача керування проектами має вигляд максимізації очікуваного сукупного доходу (x_j=1, якщо проект j фінансується на першому етапі, x_j=0 - у противному випадку):

max_x [F(x)=₁ⁿc_jx_j+E f₂(x,)],

при ресурсних обмеженнях першого етапу

₁ⁿa_іjx_j b_1і, і=1,...,m,

x_j{0,1}, j=1,...,n,

де випадковий доход f₂(x,) від продовжуваних на другому етапі проектів є розв'язок при фіксованій реалізації випадкових (експертних) параметрів {d_j(), e_іj(), b_2і()} наступної багатовимірної задачі про рюкзак (y_j=1, якщо проект j продовжується на другому етапі, y_j=0 - у противному випадку):

f₂(x,)=max_{y 1}ⁿd_j()y_j,

₁ⁿe_іj()y_j b_1і+b_2і()₁ⁿa_іjx_j, і=1,...,m,

y_j{0,x_j}, j=1,...,n.

Для розв'язання подібних задач необхідний механізм скорочення перебору можливих значень x. Такий механізм надається стохастичним методом гілок та меж, розглянутим у розділі 5. Щоб застосувати цей метод до задач стохастичної дискретної оптимізації, в підрозділі 5.5 побудовано специфічні стохастичні оцінки оптимальних значень для різноманітних класів задач стохастичної оптимізації.

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

2. Методи стохастичних узагальнених градієнтів.

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

mіn_{x X} [F(x)= E f(x,)],

де x - вектор керованих параметрів (рішення); - випадковий параметр, визначений на ймовірнісному просторі (?,У,P); f(x,) - випадкова функція якості рішення x при значенні випадкового параметра ; F(x) - математичне сподівання функції якості; X - допустима множина з Rⁿ. Суттєвою особливістю задачі є відсутність у функції f(·,) хороших аналітичних властивостей, у загальному випадку вона може бути неопуклою, негладкою і навіть розривною. Але іноді функція математичного сподівання F(x) може бути гладкою. Цей випадок розглянуто у роботах Y.C.Ho, X.R.Cao, R. Surі, P. Glasserman, P.W. Glynn, R.Y. Rubіnsteіn, G.Ch. Pflug, М.К. Кривуліна та ін.

У випадку негладкої функції F(x) важливим є випадок ліпшіцевих функцій математичного сподівання, розглянутий А.М. Гупалом Гупал А.М. Стохастические методы решения негладких экстремальных задач. - Киев: Наук. думка, 1979. - 150 с.. Більше того, як показано в підрозділі 1.6 (див. (1), (2)) та в [10, 11, 25], ми часто маємо справу не з загальним класом ліпшіцевих функцій, а з їх підкласом, утвореним з деяких базових (неперервно диференційовних) функцій за допомогою операцій максимуму, мінімуму та гладких трансформацій. Такі функції належать до класу так званих узагальнено диференційовних функцій, вивчених в [1]. Як приклад доведена узагальнена диференційовність та обчислені стохастичні узагальнені градієнти функціоналу

F(x)=E mіn_1tT u_t(R(t,x,)), (2)

від процесу (страхового) ризику

R(t,x,) = x₁+c₂x₂t_1іN(t,) mіn{x₂L_і(),x₃}c₃x₃t, 1tT, c_і >0,

де функції корисності

u_t(R)=R для R?0 та u_t(R)=(1+e_t)R для R<0, _t0_,

L_і() - випадкові втрати; N(t,) - випадкове число таких втрат за час t; x₁ - початковий капітал страхової компанії; x₂ - застрахована доля втрат; x₃ - рівень перестрахування; x=(x₁,x₂,x₃).

У роботі [1] були розроблені та досліджені деякі стохастичні узагальнено градієнтні методи оптимізації узагальнено диференційовних функцій, наприклад, стохастичні методи "важкої кульки" та "ущелинного кроку" для оптимізації "ущелинних" функцій. Ці методи використовують узагальнені градієнти підінтегральної узагальнено диференційовної функції f(x,). У розділі 2 та в [11,25] доводиться збіжність ще одного методу мінімізації узагальнено диференційовних функцій - неопуклого аналогу відомого методу стохастичних квазіградієнтів Ю.М.Єрмольєва Ермольев Ю.М. Методы стохастического программирования. - М.: Наука, 1976. - 240 с. :

x^k+1_X(x^k_kg(x^k,_k)), g(x^k,_k)_xf(x^k,_k), x^kx^k_k, k=0,1,...,

де _X - (багатозначний) оператор проектування на неопуклу допустиму множину X; g(x,) - вимірний за сукупністю змінних переріз субдиференціала x_f(x,); _{k -} незалежні спостереження випадкового параметра ; невід'ємні числа _k, _k задовольняють умовамм

lіm_{k k} = lіm_{k k} =0, _0k =+, _0k² <+. (3)

Метод майже напевне збігається до множини точок X*={x| 0F(x)+N_X(x)}, що задовольняють необхідним умовам оптимальності, та існує границя lіm_kF(x^k)F(X*) м.н.

Для обчислення оптимального значення lіm_kF(x^k) використовуються оцінки, що випливають із нестаціонарного закону великих чисел [12]:

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

де числа s_k задовольняють умовам

0_k1, lіm_kk=0, _0k=+, ₀E_k¹⁺|f(x^k,_k) F(x^k)|¹⁺<+,

0<1. Ці оцінки можуть розглядатися як узагальнення методу Монте Карло для обчислення F(X*) за спостереженнями f(x^k,_k), такими, що E {f(x^k,_k)| x⁰,..., x^k}=F(x^k) F(X*) м.н.

Умови збіжності методу є більш слабкими ніж у випадку загальних ліпшіцевих функцій. Ця процедура також узагальнює результати Є.О.Нурмінського Нурминский Е.А. Численные методы решения детерминированных и стохастичес-ких минимаксных задач. - Киев: Наук. думка, 1979. - 161 с. та П.А.Дорофеєва Дорофеев П.А. О некоторых свойствах обобщенного градиентного метода // Журн. вычисл. математики и мат. физики. - 1985. - 25, N 2. - C. 181-189., одержані для випадку квазі-диференційовних функцій F(x), які не охоплюють прикладів типу (1), (2) та інших, розглянутих у підрозділі 1.5. Подальше узагальнення цього методу на випадок квазіопуклих та розривних функцій ризику побудовано в розділах 3, 4. Проблема глобальної оптимізації неопуклих функцій ризику розглядається в розділі 5.

3. Стохастичні методи згладжування.

У розділі 3 розвивається підхід [2, 9] до оптимізації, власне кажучи, розривних функцій ризику шляхом апроксимації їх гладкими усередненими функціями. Ідея підходу полягає в апроксимації вихідної задачі сукупністю неопуклих задач стохастичного програмування і застосуванні до останніх всього арсеналу прийомів, напрацьованих у стохастичному програмуванні (методика обчислення стохастичних градієнтів без обчислення багатовимірних інтегралів, техніка неопуклого стохастичного другого методу Ляпунова для доведення збіжности майже напевне стохастичних алгоритмів оптимізації, методика прискорення збіжності стохастичних методів, методика нестаціонарної стохастичної оптимізації). Крім того, у підрозділах 3.6, 3.7 та в [9, 10, 21] усереднені функції використовуються для побудови cубдиференціалів розривних функцій. Установлені необхідні умови оптимальності в термінах так званих згладжених субдиференціалів розривних функцій. Доведена збіжність апроксимаційної схеми, тобто збіж-ність мінімумів наближених задач до мінімумів початкової. Доведена збіжність майже напевне стохастичних кінцево-різницевих процедур оптимізації розривних функцій. Другий підхід до оптимізації розривних функцій, побудований на базі локальної апроксимації розривної функції лінійними функціями, розвивається Б.Д.Батухтіним та ін. Батухтин Б.Д., Майборода Л.А. Разрывные экстремальные задачи. - Санкт-Петербург: Гиппократ, 1995. - 208 с.

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

Означення 1 [9]. Функція F : Rⁿ R¹ називається сильно напів-неперервною знизу в точці x, якщо вона напівнеперервна знизу в x та існує послідовність x^k x, така, що F - неперервна в x^k (для усіх k) та F(x^k) F(x). Функція F називається сильно напівнеперервною знизу (сильно ннз) на X Rⁿ, якщо це має місце для всіх x X.

У підрозділі 3.2 та у [10, 20] також вводяться класи неперервних за напрямками та кусково-неперервних функцій. Властивості сильної напівнеперервності знизу, неперервності за напрямками, кускової неперервності зберігаються при неперервних перетвореннях. У підрозділі 3.2 дані достатні умови сильної напівнеперервності деяких складних функцій (у частковому випадку, функцій математичного сподівання та ймовірності) і розроблено числення для цих функцій.

Усереднені функції давно використовуються в математиці. У даній роботі вони вживаються для оптимізації розривних функцій. Усереднені функції { f_, R¹} визначаються шляхом конволюції даної функції f з деяким сімейством ядер (mollіfіers) {_, >0}, таких, що

lіm _{+0 ||z||} (z)dz = 1 > 0.

Наприклад, нехай () буде гаусівською щільністю ймовірності, (x)=(x/), > 0. Для обмеженої локально інтегровної функції f(x) розглянемо наступне сімейство усереднених функцій:

f (x)=(1/ ⁿ) f(y)((x-y)/)dy, > 0. (4)

Тоді кожна функція f є аналітичною з градієнтом

f(x)=E(1/)[f(x+)f(x)]= E(1/2)[f(x+)f(x)], (5)

де випадкова величина має стандартний нормальний розподіл, E - математичне сподівання по .

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

Означення 2 Rockafellar R.T., Wets R.J-B. Var?at?onal Analys?s. - Berl?n: Spr?nger, 1998. 733 p.^. Послідовність функцій f ^k: Rⁿ R=R{+}, епі-збігаються до функції f: Rⁿ R в точці x, якщо

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

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

Розглянемо функцію сподіваної корисності вигляду F(x)= =Eu(f(x,)), де функція (корисності) u:R^mR¹ зображує відношення особи, що приймає рішення, до різних значень "прибутків (втрат)" f(x,) при розв'язку x. В окремих випадках з u(t)=c(t)={0 при t<0, 1 у протилежному випадку}, одержуємо функцію ймовірності P(x)= =P{f(x,) 0}, з u(t)=t - функцію математичного сподівання F(x)= Ef(x,), а з u(t)=max{0,t} - функцію ризику вигляду F(x)=Ef(x,)(f(x,)).

Функція корисності u(·) у загальному випадку може бути розривною на деякій множині DR^m. Її можна різними способами апроксимувати неперервними функціями u_e, де - деякий параметр, так, що u(y) u(y) для всіх yD при 0. Тоді функція F(x) апроксимується функціями F(x)=E u(f(x,)) і замість F(x) можна оптимізувати F(x). Позначимо D={R^m|dіst(,D)}, де dіst(,D)=іnf_zD ||-z||.

Лема 1. Якщо рівномірно по x виконано lіm₀ P{ f(x,)D}=0 і рівномірно по z D справедливо lіm₀ u(z)=u(z), то F(x) неперервна і lіm₀ F(x)=F(x) рівномірно по x.

Якщо функції u(z) і f(x,) узагальнено диференційовні, то суперпозиція u(f(x,)) узагальнено диференційовна з субдиференціалом _xu(f(x,)), котрий можна обчислити за допомогою ланцюгового правила диференціювання складної функції. Якщо субдиференціал _xu(f(x,)) мажорується константою (Ліпшиця), яка інтегрується, то (див. [1]) функція F(x) також узагальнено диференційовна з субдиференціалом F(x)=E_xu(f(x,)). Для оптиміизації узагальнено диференційовної функції Fe(x) застосовні узагальнено градієнтні методи з розділу 2.у 2.

У підрозділі 4.6 та у [22, 24] апроксимаційний підхід розділу 3 адаптується для оптимізації функцій ймовірності, яка у загальному випадку також може бути негладкою, неопуклою та навіть розривною. Але за деяких умов вона є неперервною та квазіувігнутою (-увігнутою). У такому випадку ми могли б застосувати субградієнтний метод для її максимізації. Але обчислення субградієнтів функції ймовірності до цього часу є проблемою. Тому ми рівномірно апроксимуємо вихідну функцію ймовірності послідовністю узагальнено диференційовних (квазіувігнутих, -увігнутих) функцій сподіваної корисності, для яких обчислення субградієнтів виконується порівняно легко. Для розв'язання наближених задач ми застосовуємо ефективний стохастичний субградієнтний метод з усередненням траєкторії. Одержані результати про збіжність та швидкість збіжності цього методу.

Увігнуті та квазіувігнуті функції відіграють значну роль у теорії екстремальних задач. Для задач з функціями ймовірності та корисності подібну роль відіграють логарифмічно увігнуті Prekopa A. Stochast?c Programm?ng. Dordrecht: Kluver Academ?c Publ?shers, 1995. 600 p. та більш загальні -увігнуті функції (та міри), де - дійсний параметр. У підрозділі 4.2 та у [4] подається огляд теорії -увігнутих функцій та мір.

Невід'ємна функція F(x) є -увігнутою на XRⁿ (-<<+) тоді і тільки тоді, коли F(x) увігнута для >0, ln F(x) увігнута для =0 та F(x) опукла на X для <0. Невід'ємна квазіувігнута функція, за означенням, є (-)-увігнутою. Не тільки функції, але й міри можуть мати властивості увігнутості. У роботі [4] -увігнуті функції використовуються для аналізу задач нечіткої оптимізації.

Виявляється, що багато класичних розподілів ймовірностей (рівномірне, нормальне, -розподіл, Стюдента, Парето, F-розподіл) мають -увігнуті щільності і, таким чином, генеруються '-увігнутими мірами на відповідному носії.

У розділі 4.4 обговорюються властивості функцій ймовірності (неперервність, квазідиференційовність, квазіувігнутість, -увігнутість). Відомо, що для квазіувігнутої за сукупністю змінних функції f(x,) ступінь увігнутості відповідної функції ймовірності P(x) визначається ступенем увігнутості ймовірнісної міри P.

У загальному випадку функція ймовірності P(x) може бути розривною, так як її зображення у вигляді математичного сподівання містить розривну індикаторну функцію c(·). З цієї ж причини не можна диференціювати P(x) шляхом перестановки операцій диференціювання та інтегрування у виразі, що визначає P(x). Тому ми замінюємо розривну функцію c(·) неперервними апроксимаціями u(·), і, таким чином, одержуємо неперервну апроксимацію для P(x).

Нехай деяка щільність ймовірності (), R¹, генерує міру на R¹ за формулою (A):= _A() d, AR¹. Визначимо її функцію розподілу як u(t):={(-,t]}. Тепер розглянемо наступну апроксимацію функцій ймовірності функціями (сподіваної корисності)

F(x):= u(f(x,)/)P(d), (8)

де >0 - чисельний параметр. Наступна лема встановлює умови рівномірної збіжності F(x) до P(x).

Лема 2. Нехай функція f(x,) неперервна по x майже для усіх . Припустимо, що для всіх xX та усіх c', що близькі 0, виконується P{f(x,)=c'}=0. Тоді для будь-якого компакту KX функції F(x) рівно-мірно збігаються у K до неперервної функції ймовірності P(x) при 0.

За деяких умов функції корисності F(x) є -увігнутими з деяким . А саме, якщо f(x,) увігнута по сукупності змінних, а добуток мір P - -увігнута міра, то функції сподіваної корисності F(x) -увігнуті. У розділі 4.2 та у [4] наведені деякі достатні умови -увігнутості добутків мір.

Наступна теорема дає достатні умови субдиференційовності функцій сподіваної корисності (8).

Теорема 7 [24]. Нехай функція щільності ймовірності () невід'ємна, обмежена та неперервна, а функція f(·,) - увігнута на xX для будь-якого ?. Нехай

sup {g g_x f(y,), y-x } L(x,), >0,

де функція L(x,) інтегровна по для кожного x X. Тоді F(x) є ліпшіцевою (-)регулярною (та узагальнено диференційовною) функцією, та її субдиференціал задається формулою

F(x):= (1/) (f(x,)/) _x f(y,)P(d).

Розглянемо задачу оптимізації функції сподіваної корисності:

max_xX [F(x)= Eu(f(x,))].

Нехай F* - оптимальне значення, а X* - оптимальна множина цієї задачі.

Якщо функції u(·) і f(·,) узагальнено диференційовні, та f(·,) має константу Ліпшіця, яка інтегрується, то u(f(·,)) і F(x)= Eu(f(x,)) узагальнено диференційовні та для оптимізації F(x) можна застосувати стохастичні узагальнені градієнтні методи із [1] та розділу 2.