.

Стохастичні методи розв’язання задач неопуклого стохастичного програмування та їх застосування: Автореф. дис… д-ра фіз.-мат. наук / В.І. Норкін, НАН

Язык: украинский
Формат: реферат
Тип документа: Word Doc
0 5223
Скачать документ

Національна академія наук України
Інститут кібернетики імені В. М. Глушкова

На правах рукопису

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

УДК 519.8

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

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

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

Київ 1998

Дисертацією є рукопис.
Робота виконана в Інституті кібернетики імені В.М.Глушкова НАН України.

Науковий консультант: доктор фізико-математичних наук,
професор, академік НАН України,
ЄРМОЛЬЄВ Юрій Михайлович,
Інститут кібернетики імені В.М.Глушкова
НАН України, завідуючий відділом.

Офіційні опоненти: доктор фізико-математичних наук,
професор, академік НАН України,
КОРОЛЮК Володимир Семенович,
Інститут математики НАН України,
головний науковий співробітник;

доктор фізико-математичних наук,
професор, академік НАН України,
ШОР Наум Зуселевич, Інститут
кібернетики імені В.М.Глушкова НАН
України, завідуючий відділом;

доктор фізико-математичних наук,
ДАНИЛІН Юрій Михайлович,
Інститут прикладного системного
аналізу НАН України та Міносвіти
України, провідний науковий співробітник.

Провідна установа: Київський національний університет
ім. Т.Г.Шевченка, факультет кібернетики, кафедра системного
аналізу і прийняття рішень

Захист відбудеться “26” лютого 1999 р. об 11 год. на засіданні спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики імені В.М.Глушкова НАН України
за адресою: 252022 Київ 22, проспект Глушкова, 40.
З дисертацією можна ознайомитись у науково-технічному архіві інституту.

Автореферат розісланий “15” лютого 1999 р.

Учений секретар
спеціалізованої вченої ради СИНЯВСЬКИЙ В.Ф.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Дисертацiя присвячена стохастичним методам розв’язання задач неопуклого стохастичного програмування, наприклад, задач локальної та глобальної оптимiзацiї негладких функцій очікуваної корисності та ймовірності, стохастичної оптимiзацiї розривних функцiй, цiлочислового стохастичного програмування. Формально в дисертації розвиваються методи розв’язання задач стохастичного програмування вигляду
minxX [F(x)=Eu(f(x,),)], minxX [P(x)=P{f(x,)B()}],
на основі спостереження значень (або градіентів) функції f(·,ω), де функції f(·,ω), u(·,ω), P(x) і F(x) можуть бути неопуклими, негладкими і навіть розривними, а змінна xXRn може бути неперервною або дискретною; ω – випадкова величина; E і P – знаки математичного очікування та ймовірності по , B()Rm, f(,):RnRm, u(,):RmR1.
Актуальн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в є вивченим у роботах X.R.Cao, P.W.Glynn, Y.C.Ho, М.К.Кривулiна, G.Ch.Pflug, R.Rubinstein, R.Suri.
Багато систем з дискретними подiями мають розривнi показники функцiонування (довжини черг в системах масового обслуговування, час обслуговування в системах з вiдмовами та регенерацiєю, рiвнi запасiв за випадкового попиту в економiчних системах). Локальна оптимiзацiя цих систем потребує зовсiм нового аналiтичного апарату i вiдповiдних чисельних методiв (J.P.Aubin, В.Д.Батухтiн, F.H.Clarke, В.Ф.Дем’янов, Б.Ш.Мордухович, Б.Н.Пшеничний, R.T.Rockafellar, О.М.Рубiнов, Н.З.Шор, R.J-B.Wets та 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тити методи керованого випадкового пошуку (E.Aaarts, А.О.Жиглявський, S.Kirkpatrick, H.Kushner, Й.Б.Моцкус, Л.А.Растриг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 в роботах І.Л.Авербаха, G.Laporte, F.H.Louveaux, A.H.G.Rinnoy-Kan, R.L.Schultz, L.Stougie, M.H.Van der Vlerk, Д.Б.Юд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бзуна, І.М.Коваленка, Р.Леппа, К.Marti, О.М.Наконечного, Б.Т.Поляка, А.Prekopa, Е.Райка, Е.Тамм, С.П.Урясьєва, Т.Szantai та 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в роботи полягає в наступному.
1. Розглянуто нові практичні класи задач негладкої та розривної (неопуклої) оптимізації, пов’язані з оптимізацією так званих стохастичних систем з дискретними подіями. Показано, що адекватною моделлю параметричних неперервних показникiв функцiонування стохастичних систем з дискретними подiями та функцiй сподiваної корисностi є так званi узагальнено диференцiйовнi функцiї.
2. Введенi та вивченi деякi нові класи розривних функцiй (кусково-неперервнi, неперервнi за напрямками, сильно напiвнеперервнi знизу).
3. Для розривних функцій уведено та вивчено нове поняття зглад-женого субдиференцiала, вивчено його зв’язок з субдиференцiалами Ф.Кларка, Р.Т.Рокафеллара, Дж.Варги та Б.Ш.Мордуховича. Для опису сингулярних (нескінченних) значень градієнтів розривних функцій уведено та дослiджено нове поняття розширеного згладженого субдиференцiала у “космiчному” векторному просторi Р.Т.Рокафеллара та Р.Ветса.
4. Знайденi необхiднi умови екстремуму в термiнах згладжених субдиференцiалiв для неперервних та розривних функцiй за неопуклих обмежень.
5. Для обчислення згладжених субдиференціалів розривних функцій запропоновано скінченно-різницеві стохастичні оцінки.
6. Запропоновано та обгрунтовано новий (апроксимаційний) підхід до оптимізації негладких та розривних функцій математичного сподівання, функцій ймовiрностi та сподіваної корисності за обмежень.
7. Метод стохастичних квазiградiєнтiв Ю.М.Єрмольєва узагальнений i поширюється на неопуклі стохастичнi задачi оптимiзацiї узагальнено диференцiйовних, локально лiпшіцевих та розривних функцiй математичного сподівання за неопуклих обмежень.
8. Для розв’язання “ущелинних” задач стохастичного неопуклого програмування запропоновано та обгрунтовано методи усереднених стохастичних градієнтів, наприклад, стохастичні методи “важкої кульки” та “ущелинного кроку”.
9. Розглянуто нові (стохастичні нелінійні) задачі дискретної оптимізації (стохастичну двоетапну задачу про рюкзак, стохастичну задачу фiнансування проектiв, стохастичну задачу розмiщення виробництва, лiнiйну стохастичну двоетапну задачу, стохастичну задачу про реконструкцію мережі, стохастичну задачу про максимальний потік у мережі та ін.).
10. Запропоновано новий прийом перестановочної релаксації (пере-становки операторів мінімізації та математичного сподівання або ймо-вірності (або підсумовування)) для оцінки знизу оптимальних значень задач стохастичної дискретної та стохастичної глобальної оптимізації.
11. За допомогою перестановочної релаксацiї та лагранжевої релаксацiї одержанi новi стохастичнi оцiнки оптимальних значень дискретних та неперервних задач стохастичного програмування, включаючи стохастичну двоетапну задачу про рюкзак, стохастичну задачу фiнансування проектiв, стохастичну задачу розмiщення виробництва, лiнiйну стохастичну двоетапну задачу, задачу оптимiзацiї функцiї ймовiрностей.
12. На базi стохастичних оцiнок оптимальних значень розроблено новий стохастичний варіант методу гiлок та меж для розв’язання задач стохастичного дискретного програмування та стохастичної глобальної оптимiзацiї за детермiнованих та стохастичних обмежень. Дослiдженi умови збiжностi методу майже напевне.
13. Розроблено варiанти стохастичного методу гiлок та меж для конкретних задач стохастичного програмування, таких, як стохастична двоетапна задача фiнансування проектiв, стохастична задача розмiщення виробництва, задача оптимiзацiї ймовiрностей, задача оптимiзацiї за ймовiрнісних обмежень. Проведенi експериментальнi розрахунки, що пiдтведжують дiєздатнiсть та ефективнiть розробленного стохастичного методу гiлок та меж.
14. Досл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далися на ІV-VII Мiжнародних конференцiях по стохастичному програмуванню (Енн-Арбор, США, 1989; Удiне, Iталiя, 1992; Нахарайя, Iзраїль, 1995), на Міжнародному математичному конгресі (Берлін, Німеччина, 1998), на XV Мiжнародному симпозiумi по математичному програмуванню (Енн-Арбор, США, 1994), на мiжнародних симпозiумах “Глобальна оптимiзацiя” (Шопрон, Угорщина, 1990), “Апроксимацiя задач стохастичного програмування” (Лаксенбург, Австрiя, 1993), “Стохастичне програмування” (Берлiн, Нiмеччина, 1994), “Негладка та розривна оптимiзацiя i застосування” (Лаксенбург, Австрiя, 1995), “Стохастична оптимiзацiя: обчислювальнi методи та технiчне застосування” (Ньюбiберг/Мюнхен, Нiмеччина, 1996), на мiжнародній конференцiї INFORMS (Сан Дієго, США, 1997). Матеріали дисертації обговорювалися на наукових семінарах в Інституті кібернетики ім. В.М.Глушкова НАН України, Інституті математики НАН України, Національному технічному університеті України, Інституті системного аналізу НАН України та Міносвіти України, а також на факультеті кібернетики Київського національного університету ім. Т.Г.Шевченка.
Публiкацiї. Результати роботи опублiкованi у 25 друкованих роботах (iз них 13 з спiвавторами), у тому числi в однiй монографiї (з спiвавторами), 13 журнальних публiкацiях, 7 статтях в зiбраннях праць, 4 препринтах.
Структура та обсяг роботи. Дисертацiя складається з вступу, 6 роздiлiв, висновкiв та списку лiтератури. Обсяг роботи – 250 сторiнок, 3 рисунки, 4 таблицi. Список лiтератури мiстить 337 найменувань.

ЗМIСТ РОБОТИ
У вступi пояснено актуальнiсть теми дисертацiї, коротко викладено змiст дисертацiї, дано огляд лiтератури за темою дисертацiї та вказано зв’язок роботи з iншими дослiдженнями.
1. Задачі неопуклої стохастичної оптимізації.
У роздiлi 1 обговорюється загальна методологiя прийняття рiшень за умов стохастичної невизначеностi за допомогою так званих функцiй ризику, функцiй сподiваної корисностi та нечiтких цiльових функцiй, а також наведені приклади неопуклих задач оптимізації систем з дискретними подіями, задач стохастичної дискретної та стохастичної глобальної оптимізації.
Пiд функцiєю ризику F(x), що залежить вiд параметрiв x, мається на увазi будь-який функцiонал вiд розподiлу випадкових “збиткiв-виграшу” f(x,), що вiдповiдає тому або iншому вибору параметрiв x та реалiзацiї випадкових параметрiв . За допомогою функцiй ризику здiйснюється вибiр рацiональних рiшень за умов стохастичної невизначеностi.
У підрозділі 1.1 та у [18] обговорюються математичнi властивостi функцiй ризику та розглядаються методи прийняття рiшень на базi функцiй ризику. Типовими представниками функцiй ризику є функцiї математичного сподiвання F(x)=Ef(x,), дисперсiї F(x)=E(f(x,)Ef(x,))2, ймовiрностi F(x)=P{f(x,)c} та iн., що залежать вiд параметрiв xRn, причому випадкові функції можуть бути неопуклими та негладкими. У пiдроздiлi 1.5 та в [10, 11, 25] наведенi приклади задач оптимiзацiї деяких систем з дискретними випадковими подiями – DES, у яких випадковi функцiї f(x,) будуються з гладких функцiй за допомогою операцiй максимуму та мiнiмуму. Наприклад,

задача максимізації середнього часу життя мережі має вигляд
maxx X [F(x)= E maxpP minep fep(x,)], (1)
де p – деякий шлях з множини P шляхів, що ведуть від входу до виходу мережі; fep(x,) – випадковий час життя елемента e шляху p. У даному випадку функція корисності u(t)=maxpP minep tep є неопуклою та негладкою. Проблема полягає в обчисленні стохастичних узагальнених градієнтів неопуклої негладкої функії F(x).
Під функцiєю сподiваної корисностi маються на увазi функцiї вигляду F(x)=Eu(f(x,)), де функцiя u(·) виражає кориснiсть (для особи, що приймає рiшення) тих або iнших значень f(·,·). Ясно, що кориснiсть u(f(x,)) може бути неопуклою по x, навiть якщо функцiя f(x,) опукла по x. Якщо u(·)= c(·), де c(t)={0 для t0,
де функції корисності
ut(R)=R для R≥0 та ut(R)=(1+et)R для R0}, таких, що
lim +0 ||z||    (z)dz = 1   > 0.
Наприклад, нехай () буде гаусiвською щiльнiстю ймовiрностi, (x)=(x/),  > 0. Для обмеженої локально інтегровної функцiї f(x) розглянемо наступне сiмейство усереднених функцiй:
f (x)=(1/ n)  f(y)((x-y)/)dy,  > 0. (4)
Тодi кожна функцiя f є аналiтичною з градiєнтом
f(x)=E(1/)[f(x+)f(x)]= E(1/2)[f(x+)f(x)], (5)
де випадкова величина  має стандартний нормальний розподiл, E – математичне сподiвання по .
Якщо функцiя f не є неперервною, то ми не можемо очiкувати, що усередненi функцiї f(x) збiгаються до f рiвномiрно. Але для цiлей оптимiзацiї це i не потрiбно. Потрiбна така збiжнiсть усереднених функцiй до f, яка тягне за собою збiжнiсть мiнiмумiв f(x) до мiнiмумiв f. Це гарантується так званою епiзбiжнiстю функцiй.
Означення 2 . Послiдовнiсть функцiй f k: Rn  R=R{+}, епi-збiгаються до функцiї f: Rn  R в точцi x, якщо
1) liminfk f k(xk)  f(x) для усіх xk  x;
2) limk f k(xk) = f(x) для деякої послідовності xk  x.
Послiдовнiсть {f k}{k N} епi-збiгається до f, якщо це справедливо у кожнiй точцi xRn.
Наступна важлива властивiсть епiзбiжних функцiй показує, що оп-тимiзацiя розривної функцiї F(x) за обмеженням xK, взагалi, може бути виконана за допомогою апроксимацiї F(x) епiзбiжними функцiями Fk(x) (наприклад, усередненими функцiями) та релаксації обмежень задачі.
Теорема 1 [10, 21]. Якщо послiдовнiсть функцiй {Fk: Rn  R } епi-збiгається до F: Rn  R, то для будь-якого компакту X  Rn
lim0 (liminfk (infX() Fk))= lim0 (liminfk (supX() Fk))= infX F ,
де X()=X+B, B={xRn| ||x|| 1}. Якщо Fk(xk )  infX() Fk +k , де xk X(), k  0, то
limsup0 (limsupk xk )  argminX F ,
де (limsupk xk ) визначає множину K граничних точок послiдовностей {xk } та ( limsup0 K ) визначає множину граничних точок сiмейства {K , R+}, коли   0.
Наступна теорема показує, що усередненi функцiї можуть бути використанi для мiнiмiзацiї сильно напiвнеперервних знизу функцiй в межах апроксимацiйної схеми теореми 1, так як епiзбiжнiсть тягне за собою збiжнiсть оптимальних значень та збiжнiсть мiнiмумiв. У пiдроздiлi 3.4 вивчаються апроксимацiйнi схеми для розривних екстремальних задач з функцiональними обмеженнями, а у пiдроздiлi 3.5 – метод розривних штрафних функцiй.
Теорема 2 [9]. Для обмеженої сильно напiвнеперервної локально iнтегровної функцiї f: RnR будь-яка асоцiйована послiдовнiсть усеред-нених функцiй { f k := f(k) , (k)  R+ } епi-збiгається до f, коли q(k)  0.
У пiдроздiлах 3.6, 3.7 усередненi функцiї використовуються для побудови узагальнених похiдних та субдиференцiалiв розривних функцiй, якi в свою чергу в пiдроздiлi 3.8 використовуються для формулювання необхiдних умов екстремуму.
Означення 3 [9]. Нехай { f k : = f(k) , (k)  0 } є гладкими. -зглад-женим (регулярним) субдиференцiалом функцiї f у точцi x називається множина
 f(x):= Limsupk {f k(xk)| xk  x},
тобто  f(x) є множина граничних точок усiх послiдовностей {fk(xk)}, таких, що xk  x.
Множина  f(x) -згладжених субградiєнтiв замкнена та у загальному випадку залежить вiд вибору послiдовностi {k}, використаної при його побудовi (в опуклому випадку не залежить та має мiсце  f(x) = f(x)).. Множина y f(x) завжди не порожня, якщо функцiя f майже скрiзь гладка та її градiєнти локально обмеженi на множинi, де вони iснують.
Означення 4 [9]. Нехай усередненi функцiї {f k:= f(k) , (k)  0} є гладкими; -згладженою похiдною функцiї f у точцi x та у напрямку u називається величина
f’(x;u):= sup{x(k)x} limsupk (f k)'(x(k);u),
де (f k)'(x;u) є похiдна f k в точцi x по напрямку u, супремум береться по вiдношенню до всiх послiдовностей x(k)x.
Теорема 3 [9]. Справедливе включення
conv  f(x)  G(x):= {gRn| g,u f’(x;u)  uR n },
де conv означає опуклу оболонку. Якщо множина G(x) обмежена, то conv  f(x) = G(x).
Для неперервної функцiї f введений субдиференцiал спiвпадає з похiдною множиною Дж.Варги , а для локально лiпшіцевої функцiї conv f(x) співпадає з субдиференціалом Ф.Кларка Cf(x)..
Необхiднi умови екстремуму (у тому числі для розривних функцій) детально розглянуті Б.М.Пшеничним , Р.Т.Рокафелларом та Б.Ш.Мордуховичем , але отримані результати не вичерпують проблему. Так необхiднi умови екстремуму для задачi мiнiмiзацiї без обмежень розривної функцiї f(x) у термінах згладженого субдиференціала мають стандартний вигляд: 0 f(x). Але при оптимiзацiї за обмежень загальних неперервних та розривних функцiй ми стикаємося з проблемою сингулярних градієнтів. Розглянемо задачу: min{x1/3|x0}. За будь-якого розумного означення узагальнених градiєнтiв градiєнт функцiї x1/3 в точцi x=0 дорiвнює +, тобто регулярна складова градієнта порожня, а сингулярна дорiвнює +. Отже, для того, щоб сформулювати необхiднi умови оптимальностi для таких задач та задач, якi включають розривностi, потрiбна мова, що мiстить нескiнченнi величини. Такою придатною конструкцiєю є поняття “космiчного” векторного простору Rn .
Означення 5. Позначимо R+ ={x  R| x  0} та R+ =R+ {+}. Позначимо “космiчний” простiр Rn як множину пар x=(x,a), де xRn, ||x||=1 i aR+ . Усi пари вигляду (x,0) вважаються iдентичними та позначаються як 0. Послiдовнiсть (xk,,ak ) Rn називається “космiчно” збiжною до елементу (x,a)  Rn, якщо x=limkxk , a=limk ak  R+ або limk ak =0 (в останньому випадку limk (xk ,,ak )=0). Позначимо
Limsupk (xk,ak)={(x,a)Rn|  k(m): (x,a)=limm (xk(m),ak(m))}.
Означення 6 [10, 21]. Розширеним -згладженим субдиференцiалом F у точцi x називається множина
F(x):= Limsupk { (Fk(xk)/||Fk(xk)||,||Fk(xk)||) | xk  x },
де вираз Fk(xk)/||Fk(xk)|| замiнюється будь яким одиничним вектором, якщо Fk(xk) =0, тобтоF(x) складається iз граничних точок (у “космiчному” просторi Rn ) усiх можливих послiдовностей
(Fk(xk)/||Fk(xk)|| ,||Fk(xk)||), таких, що xk  x.
Розширений згладжений субдиференцiал F(x) завжди є непорожня замкнена множина у Rn та вiдображення x  F(x) замкнене..
Теорема 4 [10, 21]. Нехай X – замкнена множина у Rn. Припустимо, що обмежена локально iнтегровна функцiя F має локальний мiнiмум вiдносно X у деякій точцi x  X та iснує послiдовнiсть xk  X, xk  x, така, що F неперервна в xk та F(xk)  F(x). Тодi для будь-якої послiдовностi {k } гладких ядер, має мiсце
F(x)  NX(x)   , (6)
де -F(x)={ (-g,a)  Rn | (g,a)  F(x) }, NX(x)={(y,a)Rn | yNX (x), ||y||=1, aR+ }, NX (x) – нормальний конус до множини X у точцi x.
Наслiдок 1. Для неперервної функцiї F умова (6) є необхiдною, тобто (6) задовольняється для будь яких локальних мiнiмумiв F на K.
Теорема 5 [10, 21]. Якщо F – сильно напiвнеперервна знизу та множина K компактна, то множина X* точок, що задовольняє умовам оптимальностi (6), не порожня та мiстить принаймні один глобальний мiнiмум функцiї F на K.
У роздiлi 3.8 cформульованi в термiнах розширеного субдиференцiала умови оптимальностi (типу Куна – Такера) для розривних задач з обмеженнями-нерiвностями.
Таким чином, для задач без обмежень умови оптимальностi зводяться до вiдомого вигляду 0F(x) та є необхiдними, тобто виконуються для усiх локальних мiнiмумiв задачi. Умови оптимальностi (6) є необхiдними також у випадку неперервностi цiльової функцiї F(x). У розривному випадку ситуацiя більш складна: не можна гарантувати, що усi локальнi мiнiмуми або навiть усi глобальнi мiнiмуми задовольняють (6). Причина цього полягає у тому, що не усi граничнi локальнi та глобальнi мiнiмуми F на K можна вiднайти за допомогою мiнiмiзацiї усереднених апроксимацiй F, що лежать в основi поняття згладженого субдиференцiала. Але множина X* точок, що задовольняють (6), не порожня, мiстить принаймні один глобальний мiнiмум. Умови оптимальностi (6) конструктивнi, вони дають iдею наближеного обчислення елементiв X*.
Розглянемо задачу безумовної мiнiмiзацiї сильно напiвнеперервної знизу функцiї f(x), xRn. Задача умовної оптимiзацiї може бути зведена до задачi безумовної оптимiзацiї за допомогою методу розривних штрафних функцiй, розглянутого в роздiлi 3.5. Припустимо, що послiдовнiсть гладких усереднених функцiй {f }, яка побудована iз f за допомогою ядер { }, епi-збiгається до f.
Нехай послiдовнiсть наближень x будується за наступним правилом. Кожна функцiя f мiнiмiзується, починаючи з попереднього наближення x-1, до точки x, такої, що ||f (x)||  , де   0. Початкова точка x0 береться довiльно. У цьому методi, якщо x’=limkx(k), то, по означенню згладженого субдиференціала,
limk  f (k)(x(k)) = 0   f(x’).
У монографiї [1] наведено багато методiв умовної та безумовної оптимiзацiї лiпшіцевих функцiй на основi згладжування. У пiдроздiлi 3.10 на прикладi задачi розривної оптимiзацiї з простими обмеженнями (такими, що на них легко здiйснювать проектування) показано, як будуються стохастичнi методи умовної розривної оптимiзацiї, що використовують iдею згладжування розривної функцiї.
Розглянемо оптимiзацiйну задачу
f(x)  min xX (7)
локальної мiнiмiзацiї функцiї f:Rn  R на опуклiй компактнiй множинi X Rn.
Припустимо, що f(x) – обмежена сильно напiвнеперервна знизу функцiя на Rn. Нехай (x) – функцiя щiльностi ймовiрностi. Визначимо сiмейство усереднених функцiй (4). Нехай базова щiльнiсть (x) вибирається такою, що усередненi функцiї f (x) неперервно диференцiйованi та для усiх x  X та деякого C0, ln F(x) увiгнута для =0 та F(x) опукла на X для 0 – чисельний параметр. Наступна лема встановлює умови рiвномiрної збiжностi F(x) до P(x).
Лема 2. Нехай функцiя f(x,) неперервна по x майже для усiх . Припустимо, що для всiх xX та усiх c’, що близькі 0, виконується P{f(x,)=c’}=0. Тодi для будь-якого компакту KX функцiї F(x) рiвно-мiрно збiгаються у K до неперервної функцiї ймовiрностi P(x) при 0.
За деяких умов функцiї корисностi F(x) є -увiгнутими з деяким . А саме, якщо f(x,) увiгнута по сукупностi змiнних, а добуток мiр P – -увiгнута мiра, то функцiї сподiваної корисностi F(x) -увiгнутi. У роздiлi 4.2 та у [4] наведенi деякi достатнi умови -увiгнутостi добуткiв мiр.
Наступна теорема дає достатнi умови субдиференцiйовностi функцiй сподiваної корисностi (8).
Теорема 7 [24]. Нехай функцiя щiльностi ймовiрностi () невiд’ємна, обмежена та неперервна, а функцiя f(·,) – увiгнута на xX для будь-якого   Ω. Нехай
sup {g gx f(y,), y-x }  L(x,), >0,
де функцiя L(x,) iнтегровна по  для кожного x  X. Тодi F(x) є лiпшіцевою (-)регулярною (та узагальнено диференцiйовною) функцiєю, та її субдиференцiал задається формулою
F(x):= (1/)  (f(x,)/) x f(y,)P(d).
Розглянемо задачу оптимiзацiї функцiї сподiваної корисностi:
maxxX [F(x)= Eu(f(x,))].
Нехай F* – оптимальне значення, а X* – оптимальна множина цiєї задачi.
Якщо функцiї u(·) і f(·,) узагальнено диференцiйовнi, та f(·,) має константу Лiпшіця, яка інтегрується, то u(f(·,)) і F(x)= Eu(f(x,)) узагальнено диференцiйовнi та для оптимiзацiї F(x) можна застосувати стохастичнi узагальненi градiєнтнi методи iз [1] та роздiлу 2.
У пiдроздiлi 4.6 метод стохастичних квазiградiєнтiв Ю.М.Єрмольєва (з усередненням Брука – Немировського – Юдiна ) поширюється для оптимiзацiї функцiй сподiваної корисностi та наближеної оптимiзацiї функцiй ймовiрностi.
Припустимо, що функцiя корисностi (ризику) F(x) є -увiгнутою, а X – замкнена опукла множина. Побудуємо наступну послiдовнiсть апроксимацiй (x0=x0  X):
xk+1 = X(xk+k k),
x k+1 = (1k+1)xk +k+1 xk+1, k=0,1,…,
де стохастичний квазiградiєнт k функцiї F(x) у точцi xk, такий, що
E{k | x0,…, xk}F(xk), E{k2| x0,…, xk}C0, x  X, тодi для будь-якого максимума x* та будь-якої послідовності кроків k 0 слушнi оцiнки
F(x*)EF(xk)  (F(x*)/)max(1- ,0)(Ex0 x*2 +C0ki2)/(20ki).

5. Стохастичн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 1.6 розглянуто iнші застосування та моделi стохастичної дискретної оптимiзацiї.
Важлива властивiсть таких задач стохастичної дискретної оптимiзацiї полягає в тому, що число N можливих рiшень (дiй) може бути надзвичайно великим, а в неперервному випадку – i нескiнченним. Отже, використання стандартної технiки перевiрки гiпотез або технiки, що розроблена для задач навчання автоматiв, стає практично неможливим тому, що вони грунтуються на послiдовному спостереженнi наслiдкiв усiх допустимих дiй.
Формально задача, що розглядається, має вигляд находження глобального мiнімуму
minx [F0(x)= E f0 (x,)], (9)
за обмежень
Fk(x)= E fk (x,)  0, k=1,…,K; (10)
x  XD  Rn, (11)
де fk(·,), k=0,1,…,K, – деякi неопуклi (наприклад, квазiопуклi) функцiї; X – дискретна або неперервна множина простої структури (наприклад, перетин деякої дискретної решiтки та паралелепiпеду в Rn); множина D={xRn|G(x)0} задається деякою детермiнованою функцiєю G:RnR1, E – математичне сподiвання стосовно випадковій величини  , що визначена на деякому ймовiрнісному просторi (,,P).
Особливо цiкавий окремий випадок задачi, коли деякi функцiї Fk (x) мають вигляд ймовiрностi:
Fk(x)= P{ fk(x,)=(fk1 (x,),…, fkm (x,))  B()  Rm }.
Таким чином, функцiя Fk (x) може бути негладкою, неопуклою та навiть розривною.
Для розв’язання задачi (9) – (11) розвивається стохастична версiя методу гiлок та меж. Для цього ми виводимо спецiальнi стохастичнi нижнi та верхнi межi оптимального значення задач вигляду (9) – (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 у роботах [13, 14, 19, 20] для розв’язання деяких стохастичних дискретних та неперервних задач глобальної оптимiзацiї. У зв’язку з випадковим характером меж, метод гiлок та меж набуває стохастичних рис.
Розглянемо, наприклад, задачу стохастичного дискретного програмування (9) – (11) без обмежень (10):
max xXD [F(x)= E f (x,)], (12)
Нехай X* – множина рiшень, а F* – оптимальне значення задачi. Зробимо наступнi припущення.
П1. Iснують функцiї L:2X  R та U:2X  R, такi, що для кожного ZX,
L(Z)F*(Z)=maxxZF(x)U(Z), U(Z)=F(x) для деякого xZ,
i якщо Z вироджується у точку, то L(Z)=F*(Z)=U(Z). Допускаємо також, якщо ZD = , то ця ситуацiя може бути iдентифiкована i, по означенню, L(Z)=U(Z)=+ .
Функцiї L та U взагалi визначаються за допомогою розв’язання деяких допомiжних стохастичних оптимiзацiйних задач, що означенi на пiдмножинах Z  X. У пiдроздiлi 5.5 розглядаються способи побудови таких допомiжних задач. У загальному випадку можна тiльки припускати iснування статистичних оцiнок величин L(Z) та U(Z).
П2. У деякому ймовiрнісному просторi (,,P) для кожної пiдмножини Z  X iснує послiдовнiсть випадкових величин l(Z), l=1,2,…, та m(Z), m=1,2,…, таких, що майже напевне
liml l(Z) = L(Z) , limm m(Z) = U(Z) .

Концептуальний алгоритм гiлок та меж.
У методi гiлок та меж вихiдна “проста” множина X iтеративно розбивається на пiдмножини Z  X, що утворюють розбиття Pk множини X або його частини. Ключову роль в алгоритмi відiграють рекорднi множини Yk, тобто множини, що мають найменшу нижню межу. Наближенi розв’язки xk задачi вибираються iз множин Xk, що мають найменшу верхню межу. В мiру того як рекордна множина розбивається на меншi пiдмножини, генеруються новi оцiнки цiльової функцiї для усiх пiдмножин, знаходяться новi наближенi розв’язки, далі iтерацiї повторюються. Так як межi випадковi, то i рекорднi множини випадковi, отже усi об’єкти, що генеруються алгоритмом, є випадковими.
Iнiцiалiзацiя. Сформувати початкове розбиття P0 ={X}. Обчислити межi 0 = l(0)(X) та 0 = m(0)(X). Покласти k=0.
Розбиття. Вибрати рекордну пiдмножину Ykargmin{k (Z): ZPk} та вiдповідний наближений розв’язок xkXkargmin {k(Z): ZPk}. Якщо рекордна пiдмножина є точкою, то покласти Pk = Pk i йти на крок Оцiнка меж. У противному випадку побудувати розбиття Pk(Yk)={Yik, i=1,2,…} рекордної множини Yk, таке, що Yk =i Yik i YikYjk= для Yik, YjkPk(Yk), i j. Визначити нове повне розбиття Pk = (Pk\Yk ) Pk”(Yk).
Оцiнка меж. Для усiх пiдмножин ZPk виберемо деякi оцiнки
k (Z) = l(k,Z)(Z) i k(Z) = m(k,Z)(Z) для L(Z) i U(Z) вiдповiдно.
Видалення пiдмножин. Очистити розбиття Pk вiд недопустимих пiдмножин, тобто визначити розбиття Pk = Pk \{ZPk : ZD=}. Покласти k:=k+1 i йти на крок Розбиття.
Зауваження. Якщо оцiнки є точними, тобто k (Z)  L(Z) i k(Z)U(Z), тодi на кроцi Видалення пiдмножин можна також видаляти усi пiдмножини Z, для яких
k (Z) > k(Z). (13)
Збiжнiсть методу встановлюється наступною теоремою.
Теорема 10 [13]. Припустимо, що iндекси l(k,Z) i m(k,Z) вибираються таким чином, що якщо ZPk для нескiнченної кількості k, то майже напевне limk l(k,Z) = limk m(k,Z) = +. Тодi з ймовiрністю одиниця iснує номер iтерацiї k*, такої, що для усiх k  k*:
1) рекорднi множини Yk є точками i Yk X*;
2) наближенi розв’язки xk  X*.
Ймовiрнiснi оцiнки точностi поточних наближень xk можуть бути одержанi за наступних додаткових припущень.
П3. Для кожного Z  X випадковi величини k (Z), k(Z), k=0,1,…, незалежнi i нормально розподiленi з середнiми значеннями L(Z), U(Z) та дисперсiями k(Z), k (Z) вiдповiдно.
П4. Для дисперсiй k(Z), k (Z), Z  X, вiдомi верхнi межi:
k(Z)  k(Z), k (Z)  k (Z).
Вiзьмемо довiрчi межi для L(Z), U(Z) у виглядi
k (Z) =k (Z)c(k)k(Z), k(Z) = k(Z) c(k)k (Z).
де константи c(k), k=0,1,…, такi, що
(ck)=(1/2)-c(k) e-/2 d = 1  k , 0 U(XN) + 2cN , де cN = 2/(N).
Лема 4 [14]. Нехай x* – деякий розв’язок задачi (12). Тодi
P{ x* втрачається пiд час видалення}  2.
У пiдроздiлi 5.3 та у [20] стохастичний метод гiлок та меж поширюється на задачi з нелiнiйними стохастичними обмеженнями (10), а у роздiлi 5.4 та у [14] – на неперервнi багатоекстремальнi задачi стохастичного програмування.

Основна проблема у стохастичному методi гiлок та меж – це оцiнка меж оптимальних значень для задач стохастичного програмування.
Як верхню межу U(X) оптимального значення F*(X) можна взяти значення цiльової функцiї у деякiй допустимiй точцi x’  X:
U(X) = F(x’) = E f(x’,).
Важливо вибрати точку x’ таким чином, щоб значення F(x’) було якомога меншим. Такi точки можуть бути найденi будь-яким (можливо, еврiстичним) методом локальної стохастичної оптимiзацiї.
Для побудови нижнiх меж в пiдроздiлi 5.5 розглядаються два загальних п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 (12) ілюстрована наступною нерівністю [13, 14, 19]:
F*(X)=minxX Ef(x,)  E minxXf(x,) = Ef(x*(),), (14)
де x*( )  argmin xX f(x, ). Таким чином, величина L(X)=Ef(x*(),) дає нижню оцiнку оптимального значення F*(X). У багатьох випадках для фiксованого  розв’язок x*( ) може бути знайдено порiвняно легко. Складність задач стохастичої дискретної оптимізації виявляється тут у тому, що для отримання оцінки (14) необхідно розв’язати багато (тобто для кожного ) детермінованих оціночних задач вигляду minxX f(x,).
Простий шлях полiпшити нижню межу (14) та її оцiнку Монте -Карло полягає у використаннi M незалежних копiй l випадкової величини :
F*(X)=(1/M)minxX 1mEf(x, l)
EM minxX(1/M)1Mf(x,l) =LM(X), (15)
де EM – оператор математичного сподiвання з усіх l . Бiльше того, збiльшуючи число спостережень M всерединi операцiї мiнiмiзацiї, можна зробити точнiсть емпiричних оцiнок LM (X) як завгодно високою.
Використання емпiричних оцiнок (15) – не єдиний спосiб використати кратнi спостереження. Нехай знову l, l=1,…,M (непарне) – незалежнi копiї . Тодi задача мiнiмiзацiї F(x) еквiвалентна мiнiмiзацiї з x  X функцiї
(F(x))M=(E f(x,))M = 1M E f(x,l ) = E {1M f(x,l )},
де в останнiй рiвностi ми використали незалежнiсть l, l=1,…,M. Перестановка операторiв мiнiмiзацiї та математичного сподiвання призводить до наступної стохастичної межi:
minxX F(x)  (E minxX {1M f(x,l )})1/M. (16)
Якщо ln f(·,) – увiгнута функцiя, то внутрiшня оптимiзацiйна задача в (16) еквiвалентна задачi опуклого програмування: minxX{1Mlnf(x,l)}. Iснує широкий клас так званих -увiгнутих функцiй f(·,) (які розглядалися у пiдроздiлi 4.2), для яких внутрiшня задача в (16) також зводиться до задачi опуклого програмування.
У пiдроздiлi 5.5 метод перестановочної релаксацiї проiлюстровано на задачах фiнансування проектiв, розмiщення виробництва, оптимiзацiї портфеля цiнних паперiв, контролю над викидом забруднень.
Нижнi межi для F*(X) iнодi можна отримати виходячи iз властивостi монотонностi випадкової цiльової функцiї f(x,) (i, отже, монотонностi F(x)). Монотоннiсть випадкових показникiв функцiонування систем f(x,) може допускатися щодо таких змiнних x, як iнвестицiї, ресурси, продуктивнiсть i т. iн. Нижнi межi для F*(X) також можуть бути отриманi за допомогою стохастичних дотичних мiнорант функцiй f(x,) та методу перестановочної релаксацiї. Детермiнованi дотичнi мiноранти у контекстi глобальної оптимiзацiї були введенi С.А.Пiявським та використанi у [8]. В підроздiлi 5.5 та у [19] ми використовуємо стохастичнi дотичнi мiноранти цiльової функцiї F(x) для потреб глобальної стохастичної оптимiзацiї.
Двоїстi оцiнки в комбiнацiї з методами негладкої оптимiзацiї широко використуються в детермiнованому дискретному програмуваннi . У пiдроздiлi 5.5 також розглядаються особливостi двоїстих оцiнок у комбiнацiї з методом перестановочної релаксацiї стосовно до задач стохастичної оптимiзацiї.

У пiдроздiлi 5.6 будуються межi для ймовiрностей. Розглянемо задачу
maxxX[P(x)=P{ f(x, )B}]= P*(X),
де X  Rn, f(x,)=(f1(x,),…,fm(x,)) – випадкова вектор-функцiя; B – замкнена пiдмножина в Rm.
Оцiнимо зверху P*(X) за допомогою перестановки операторiв максимiзацiї та ймовiрностi (перестановочна релаксацiя). Очевидно,
P*(X)  P{ x()X: f(x(),)  B}= U(X)
 P{ x()conv X: f(x(),)  B}= U(X), (17)
де conv X – опукла оболонка множини X.
Наприклад, щоб обчислити стохастичнi оцiнки (X’,)=A(X’)() величини U(X’), треба перевiрити для даного  допустимiсть умов f(x’,)B, x’X. Якщо функцiї fi(x,), i=1,…,m, лiнiйнi по x, X i B – багатограннi множини, то задача перевiрки спiльностi умов f(x’,)B, x’X є задачею лiнiйного цiлочислового програмування (i лiнiйною задачею для умов f(x’,)B, x’ conv X).
Можна зробити межi (17) точнiшими, одночасно використовуючи декiлька незалежних спостережень (1,…,l )= l випадкової величини . Тодi
Ul(X)= P1/l{ x()X: f(x(l),1)B,…, f(x(l),l)B }
є верхня межа для ймовiрностей P(x), xX.
У пiдроздiлi 5.7, а також у [13, 14, 20] наводяться приклади чисельного розв’язання задач стохастичного дискретного програмування, стохастичної глобальної оптимiзацiї та глобальної оптимiзацiї ймовiрностей стохастичним методом гiлок та меж.

6. Метод емпiричних середнiх.
У роздiлi 6 та у [6] в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 випадкових величин.
Розглянемо задачу стохастичного програмування вигляду
F(x) = E0(x,E0(x,),…,Em(x,),)  minxX, (18)
де
fj(x) = Ej(x,) = 0(x,)P(d), jI={1,…,m};
g0(x,y) = E0(x,y,)= 0(x,y,)P(d), yY Rm;
X – компакт в Rn; Y – деяка множина в Rm; Ω, (,,P) – деякий ймовiрнісний простiр; j :X  R1 i 0 :XY  R1 – iнтегровнi при кожному x  X i y  Y функцiї. В часткових випадках може бути F(x) = E0(x,), F(x) =maxjJ Ej(x,), F(x)=D0(x,)=E02(x,)  (E0(x,))2 i т.п.
Метод емпiричних середнiх (або статистичний метод) для розв’язання задачi (18) полягає в наступному: вона замiнюється послiдовнiстю задач вигляду
FS(x)=(1/s)1s0(x,(1/s)1s0(x,k),…,(1/s)1sm(x,k),k) minxX,
(19)
де k – незалежнi однаково розподiленi випадковi величини (спостереження), розподiл яких визначається мiрою P.
Позначимо F*, Fs* i X*, Xs* оптимальнi значення та розв’язки задач (18), (19), X*={xX| F(x)  F*+}, Xs*= {xX| Fs(x) Fs*+} – наближенi розв’язки задач (18), (19), 0.
Наша мета полягає в тому, щоб дослiдити збiжнiсть, у деякому
ймовiрнісному сенсi, випадкових величин Fs*, Xs*, Xs* до вiдповiдних значень F*, X*, X*.
Наступна теорема визначає умови збiжностi майже напевне методу емпiричних середнiх для розв’язання задачi мiнiмiзацiї складної функцiї ризику при детермiнованих обмеженнях.
Теорема 11 (збiжнiсть). Припустимо, що
1) функцiї j(x,), j=0,…,m, неперервнi по xX, а 0(x,y,) неперервна по (x,y)X Rm за всiх , та вимiрнi по  за фiксованих x,y;
2) iснують iнтегровнi функцiї Cj(), j=0,…,m, такi, що для всiх xX, |j(x,)|  Cj();
3) для будь-якого компакту YRm iснує невiд’ємна iнтегровна функцiя D(), така, що для всiх (x,y)XY, |0 (x,y,)|D().
Тодi функцiї 0 , j, F неперервнi, Fs*  F* i вiдхилення (Xs*,X*)0 майже напевне.
Наступна теорема визначає умови збiжностi та швидкiсть збiжностi (порядку 1/s ) за функцiоналом для методу емпiричних середнiх.
Теорема 12 (швидкiсть збiжностi). Припустимо, що
1) функцiї j(x,), j=0,…,m, неперервнi по xX, а 0(x,y,) неперервна по (x,y)X Rm за всiх , та вимiрнi по  за фiксованих x,y;
2) функцiї j(x,) i 0(x,y,) iнтегровнi (по ) в квадратi для всiх xX i yRm;
3) iснують iнтегровнi в квадратi функцiї Lj(), j=1,…,l, такi, що для будь-яких x1,x2X виконано
|j(x1,)  j(x2,)|  Lj() x1  x2;
4) для будь-якого компакту Y  Rm iснують iнтегровнi в квадратi функцiї M0() такi, що для будь-яких x1, x2  X і y1, y2  Y буде
|0(x1,y1,)  0(x2,y2,)|  M0() (x1  x2  + y1  y2 ).
Тодi Fs*  F* i (Xs*,X*)  0 майже напевне, i крiм того, Fs*()  F* нормалiзовано (див. означення 7) зi швидкiстю 1/s . Якщо додатково до умов 1)-4) виконано
5) функцiя F(x) в задачi (17) опукла на опуклiй компактнiй множинi X Rn,
то відхилення (Xs*,X*)  0 нормалiзовано зi швидкiстю 1/s.

У пiдроздiлi 6.6 вивчається так звана нормалiзована збiжнiсть випадкових величин, що використовується в теоремi 12.
У теорiї ймовiрностей вiдомi наступнi основнi види збiжностi випадкових величин: майже напевне, в середньому, за ймовiрністю та розподiлом. При вивченнi швидкостi збiжностi (скажiмо, до нуля) випадкової послiдовностi n , n=1,2,…, також розглядають збiжнiсть (майже напевне i т.п.) послiдовностей вигляду {nn}, де числова послiдовнiсть {n  0} така, що limn 1/n=0. У тому випадку, коли limnP{nn }=0  >0, говорять про збiжнiсть {n} до нуля за ймовiрністю зi швидкiстю 1/n. Часто при дослiдженнi стохастичних iтерацiйних алгоритмiв оптимiзацiї i в прикладних застосуваннях методу емпiричних середнiх отримуються оцiнки швидкостi збiжностi, якi (пiсля елементарних перетворень) мають вигляд
P{nn 0}. З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зована збiжнiсть.

ВИСНОВКИ
1. У дисертації розглянуто велику кількість прикладних задач неопуклого стохастичного програмування з негладкими, розривними або дискретними функціями, для яких немає адекватних методів розв’язання.
2. Досліджено властивості задач неопуклого стохастичного програ-мування: моделі неопуклих негладких залежностей, субдиференціальні властивості функцій очікуваної корисності, необхідні умови оптимальності, оцінки оптимальних значень.
3. Розроблені та досліджені стохастичні методи розв’язання задач неопуклого стохастичного програмування, побудовані на використанні реалізацій випадкових функцій задачі або їх градієнтів.
4. Зокрема, відомий метод стохастичних квазіградієнтів Ю.М.Єрмольєва поширений на задачі локальної оптимізації стохастичних систем з дискретними подіями, задачі оптимізації функцій очікуваної корисності, задачі оптимізації ймовірностей з неопуклими негладкими та розривними функціями.
5. Зокрема, розроблено та обгрунтовано стохастичний метод гілок та меж для розв’язання задач стохастичної глобальної та стохастичної дискретної оптимізації, глобальної оптимізації ймовірностей.

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

Основні результати дисертації опубліковані в таких працях:
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. Ermoliev Yu.M., Norkin V.I. Normalized convergence in stochastic optimization // 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. Ermoliev Yu.M, Norkin V.I. and Wets R.J-B. The minimization of semi-continuous functions: Mollifier subgradients // SIAM J. Contr. and Opt.  1995.  N 1.  P.149-167.
10. Ermoliev Yu.M., Norkin V.I. Om nonsmooth and discontinuous problems of stochastic systems optimization // European J. of Oper. Research.  1997.  101.  P. 230-244.
11. Ермольев Ю.М., Норкин В.И. Стохастический обобщенный градиентный метод для решения невыпуклых негладких задач стохас-тической оптимизации//Кибернетика и системный анализ.- 1998. –
N 2.- С.50-71.
12. Ермольев Ю.М., Норкин В.И. О нестационарном законе боль-ших чисел для зависимых случайных величин и его применении в сто-хастической оптимизации //Кибернетика и системный анализ. – 1998. – N 4. – С.94-106.
13. Norkin V.I., Ermoliev Yu.M. and Ruszczynski A. On Optimal Allocation of Indivisibles under Uncertainty //Operations Research.  1998.  46, N 4.  P.381-395.
14. Norkin V.I., Pflug G.Ch. and Ruszczynski A. A Branch and Bound Method for Stochastic Global Optimization // Mathematical Programming.  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. Norkin V.I. Global Optimization of Probabilities by the Stochastic Branch and Bound Method / Lecture Notes in Econ. and Mat. Systems 458. Stochastic Progr. and Tech. Appl. (K.Marti and P.Kall, eds.).Berlin: Springer, 1998. P.186-201.
21. Ermoliev Yu.M., Norkin V.I. Constrained optimization of discontinuous systems / Lecture Notes in Econ. and Mat. Syst. 458. Stochastic Progr. and Tech. Appl. (K.Marti and P.Kall, eds.). Berlin: Springer, 1998.P.128-142.
22. Норкин В.И. Оптимизация вероятностей. – Киев, 1989. – 19 c. – (Препр./ АН УССР. Ин-т кибернетики им. В.М.Глушкова; 89-6).
23. Норкин В.И. Устойчивость стохастических оптимизационных моделей и статистические методы стохастического программирования. – Киев, 1989. – 24с. – (Препр./ АН УССР. Ин-т кибернетики им. В.М. Глушкова; 89-53).
24. Norkin V.I. The anaysis and optimization of probability functions //Working Paper WP-93-6, Int. Inst. for Appl. Syst. Anal.  Laxenburg, Austria, 1993. 23 p.
25. Ermoliev Yu.M. and Norkin V.I. Stochastic generalized gradient method with application to insurance risk management // Interim Report IR-97-021, Int. Inst. for Appl. Syst. Anal.  Laxenburg, Austria, 1997.  19p.

Роботи [5, 9, 10, 13, 14, 21, 24, 25] опубіковані також у вигляді
препринтів у Міжнародному інституті прикладного системного аналізу (Лаксенбург, Австрія) і доступні через адресу у мережі Internet http://www.iiasa.ac.at/Publications/ .
У роботах, опублiкованих у спiвавторствi, особисто здобувачем отриманi наступнi результати:
[1] – параграфи 1, 14, 24, повнiстю глави 3, 6; [2, 11, 25] – теореми збiжностi методів; [3, 5] – поняття нормалiзованої збiжностi (введено в [23]), дослiдження її властивостей; [4] – означення a-увiгнутих функцiй через увiгнутi та опуклi функцiї, дослiдження їх субдиференцiальних властивостей, застосування до нечiткої оптимiзацiї; [9, 10, 21] – поняття сильно напiвнеперервних, неперервних за напрямками, кусочно неперервних функцiй, згладженого i розширеного згладженого субдиференцiалiв, згладженої узагальненої похiдної, дослiдження їх зв’язкiв та властивостей, факт епiзбiжностi усереднених функцiй, необхiднi умови екстремуму для розривних функцiй; [12] – доведення нестацiонарних законiв великих чисел методом функцій Ляпунова; [13, 14] – iдея перестановочної релаксацiї (висловлена в [19]) в рамках методу гiлок та меж, її реалiзацiя для рiзноманiтних класiв задач стохастичної оптимiзацiї.

Норкін В.І. Стохастичні методи розв’язання задач неопуклого стохастичного програмування та їх застосування. – Рукопис.
Дисертація на здобуття наукового ступеня доктора фізико-математичних наук за спеціальністю 01.05.01 – теоретичні основи інформатики і кібернетики. – Інститут кібернетики ім. В.М.Глушкова НАН України, Київ, 1998.
Дисертац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 та сподіваної корисності за обмежень.
Ключові слова: неопукле стохастичне програмування, стохастична глобальна оптимізація, стохастична дискретна оптимізація, функції сподіваної корисності, функції ймовірності, стохастичні узагальнено градієнтні методи, стохастичий метод гілок та меж, метод емпіричних середніх.

Норкин В.И. Стохастические методы решения задач невыпуклого стохастического программирования и их применения. – Рукопись.
Диссертация на соискание ученой степени доктора физико-математических наук по специальности 01.05.01 – теоретические основы информатики и кибернетики. – Институт кибернетики им. В.М.Глушкова НАН Украины, Киев, 1998.
В диссертации рассмотрено большое число прикладных задач невыпуклого стохастического программирования с негладкими, разрыв-ными и дискретными функциями цели и ограничений, например, задачи оптимизации динамических систем с дискретными событиями (стохастические сети с отказами, коммуникационные сети, транспорт-ная линия, выявление необратимых изменений, оптимальная остановка опасного производства), задачи оптимизации неклассических функций ожидаемой полезности (стохастическая нечеткая оптимизация, стохастическая лексикографическая оптимизация), задачи оптимизации вероятностей, задачи стохастической дискретной оптимизации (стохастическая задача финансирования проектов, стохастическая задача размещения, задача реконструкции стохастической сети, двухэтапная стохастическая задача о минимальном потоке в сети), стохастические задачи глобальной оптимизации (непрерывная стохастическая задача размещения, задача выбора портфеля ценных бумаг). Помимо невыпуклости трудность решения этих задач состоит в том, что функции задач являются математическими ожиданиями, т.е. многомерными интегралами, точное вычисление которых либо очень трудоемко, либо практически невозможно. Для задач стохастической оптимизации с гладкими функциями в литературе описаны некоторые стохастические градиентные методы. Для задач с невыпуклыми негладкими или разрывными функциями выбор методов крайне ограничен. Задачи стохастической глобальной оптимизации практически не изучались. В области стохастической дискретной оптимизации существуют лишь отдельные публикации.
В диссертации разработаны и изучены стохастические методы решения задач невыпуклого стохастического программирования с негладкими, разрывными и дискретными функциями цели и ограничений. Эти методы не требуют точного вычисления математических ожиданий, а используют случайные реализации значений подынтегральных функций или их градиентов, которые можно получить из иммитационной модели оптимизируемой системы.
В частности, известный метод стохастических квазиградиентов Ю.М.Ермольева обобщается для локальной оптимизации систем с дискретными событиями, задач оптимизации ожидаемой полезности, задач оптимизации вероятностей с невыпуклыми обобщенно дифферен-цируемыми, квазивогнутыми, липшицевыми и разрывными функциями. Сходимость (почти наверное) метода установлена с помощью невыпуклого стохастического варианта метода функций Ляпунова. Исследована скорость сходимости метода в случае квазивогнутых функций и для конечно-шагового метода. Такое обобщение потребовало введения и изучения некоторых классов невыпуклых негладких (в том числе разрывных) функций, исследования их субдифференциальных свойств, необходимых условий экстремума, а также развития способов вычисления стохастических градиентов (в том числе конечно-разностных) для невыпуклых негладких и разрывных функций. Разработаны стохас-тические методы оптимизации овражных функций математического ожидания – это стохастические аналоги методов “тяжелого шарика” и “овражного шага”.
Предложен и обоснован аппроксимационный подход (с помощью усредненных функций) к оптимизации негладких и разрывных функций математического ожидания, функций вероятности и ожидаемой полезности при ограничениях. В результате задача сводится к невыпуклой задаче стохастического программирования, к которой применяются разработанные в диссертации методы решения. Установлена сходимость аппроксимационной схемы, т.е. установлены условия, при которых минимумы приближенных задач сходятся к минимумам исходной.
Для решения задач стохастической глобальной оптимизации, а также задач стохастического дискретного программирования в диссертации разработан стохастический вариант метода ветвей и границ. Оказалось, что для многих задач стохастического программирования можно построить специфические оценки оптимальных значений, которые имеют вид математических ожиданий от некоторых вспомогательных случайных величин. Получение таких оценок основано на так называемой перестановочной релаксации задач стохастического программирования, когда операции минимизации и математического ожидания (или вероятности, или суммирования) меняются местами. Перестановочная релаксация может комбинироваться с лагранжевой релаксацией и релаксацией условий целочисленности. Поскольку оценки ветвей являются случайными величинами, то и метод ветвей и границ приобретает стохастический характер и сходится в некотором вероятностном смысле (почти наверное, с вероятностными оценками точности решения). Разработан вариант стохастического метода ветвей и границ для решения задач с нелинейными ограничениями. Работоспособность стохастического метода ветвей и границ проиллюстрирована численными решениями стохастической двухэтапной булевой задачи финансирования проектов, стохастической непрерывной задачи размещения, стохастической целочисленной задачи снижения загрязнений.
Ключевые слова: невыпуклое стохастическое программирование, стохастическая глобальная оптимизация, стохастическая дискретная оптимизация, функции ожидаемой полезности, функции вероятности, стохастические обобщенно градиентные методы, стохастический метод ветвей и границ, метод эмпирических средних.

Norkin V.I. Stochastic methods for solution of nonsmooth stochastic programming problems and their applications. – Manuscript.
Thesis for a doctor degree by speciality 01.05.01 – theoretical bases of informatics and cybernetics. – Institute of Cybernetics of the Ukrainian Academy of Sciences, Kiev, 1998.
The dissertation is devoted to solution of nonconvex stochastic programming problems, including local and global stochastic optimization, stochastic integer programming, local and global optimization of probability and expected utility functions, stochastic optimization of discontinuous functions. Stochastic quasigradient method by Yu.Ermoliev is generalized to nonconvex stochastic local optimization problems with generalized differentiable, locally Lipschitzian and discontinuous functions subject to constraints. A new stochastic branch and bound method based on interchange of minimization and expectation operations is developed for solution of stochastic discrete programming problems and stochastic global optimization problems. Approximation approach is proposed to optimization of nonsmooth and discontinuous mathematical expectation and probability functions.
Key words: nonconvex stochastic programming, stochastic global optimization, stochastic discrete optimization, expected utility functions, probability functions, stochastic generalized gradient method, stochastic branch and bound method, empirical mean method.

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2019