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

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

ОНИЩЕНКО Борис Олегович

УДК 519.853.4

МІнорантнІ методи
глобальноЇ стохастичНОЇ оптимІзації

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

АВТОРЕФЕРАТ

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

Київ–2006

Дисертацією є рукопис.

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

Науковий керівник: | доктор фізико-математичних наук

Норкін Володимир Іванович,

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

провідний науковий співробітник.

Офіційні опоненти: |

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

Ненахов Едуард Іванович,

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

провідний науковий співробітник,

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

Домрачев Володимир Миколайович,

головний економіст Національного банку України.

Провідна установа: |

Київський національний університет імені Тараса Шевченка, факультет кібернетики, кафедра математичних методів еколого-економічних досліджень.

Захист відбудеться “28” квітня 2006 р. о(об) 12 годині на засіданні спеціалізованої вченої ради Д .194.02 при Інституті кібернетики імені В.М. Глушкова НАН України за адресою:

03680, МПС, Київ-187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві інституту.

Автореферат розісланий “14” березня 2006 р.

Учений секретар

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

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

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

Актуальність теми. Багато практичних задач оптимізації є неопуклими, наприклад: задачі проектування конструкцій та систем, задачі розміщення виробництва, планування промислового виробництва, керування товарними ресурсами, контролю якості випуску продукції, проектування технологічних ліній, планування обслуговування і ремонту, обліку і планування капіталовкладень та ін. Проблемам детермінованої глобальної оптимізації присвячені монографії А.Г. Жи-лінскаса, А.А. Жиглявського, Р. Хорста, Х. Туя, П. Пардалоса, Р.Г. Стронгіна, А.Г. Сухарева, Й.Б. Моцкуса, А.М. Рубінова, В.В. Васильєва, Я. Пінтера, А. Флау-даса, Б.Т. Поляка, статті А.С. Піявського, Ю.М. Даніліна, Н.З. Шора, Б.Н.Пшеніч-ного, В. Булатова, В.І. Норкіна, О.В. Хамісова, Е.І. Ненахова та ін. Проблеми гло-бальної оптимізації обговорюються в спеціалізованому міжнародному журналі “Global optimization”. Багато практичних задач оптимізації, крім того, включають випадкові параметри, такі задачі вивчаються в рамках теорії стохастичного програмування. В задачах стохастичного програмування цільова функція має вигляд функції математичного очікування або ймовірності. Теорія опуклого стохастичного програмування розвинена в роботах Ю.М. Єрмольєва, Р. Ветса, А. Прекопи, А. Рущінського, П. Кала, Д.Б. Юдіна, А.С. Неміровського, Р.Т. Рокафеллара, К. Мар-ті та ін. Виявляється, що багато задач стохастичної оптимізації також є неопуклими. Це задачі оптимізації систем, керованих дискретними подіями, задачі розміщення сервісних центрів з випадковим попитом на послуги, задачі керування сценаріями, задачі планування виробництва за умов невизначеності, двоетапні задачі стохастичної оптимізації, задачі стохастичного програмування з мірою, що залежить від детермінованих змінних, задачі максимізації середнього часу життя мережі та ін. Для локальної оптимізації таких систем часто використовують метод стохастичної апроксимації і його узагальнення, а для глобальної оптимізації – різні методики випадкового пошуку (рестарти з випадкових початкових точок і ін.). Практично відсутні роботи, що систематично вивчають проблему глобальної оптимізації в неопуклих (нелінійних) стохастичних задачах. Виключенням є роботи, у яких обговорюються евристичні підходи до вирішення задачі. Ті розділи оптимізації, що звичайно в літературі називаються стохастичною глобальною оптимізацією, як правило, розглядають стохастичні методи детермінованої глобальної оптимізації, а не проблеми пошуку глобального оптимуму в стохастичних задачах. Близькими за тематикою даної дисертації є роботи, які присвячені стохастичній цілочисловій та дискретній оптимізації (Ф. Луве, М. Ван дер Флерк, Л. Штугі, А. Шапіро, Р. Шульц, В.П. Шило та ін.), але вони істотно використовують лінійну структуру задач.

Зв’язок роботи з науковими програмами, планами, темами. Основні дослід-ження за темою дисертації виконувалися в Інституті кібернетики ім. В.М. Глушкова НАН України в рамках наступних науково-дослідних тем:

- ВФ 130.07 “Розробка методів оцінки ризику та їх застосувань у економіці, фінансовій та страховій математиці, теорії надійності” виконувалася за постановою Президії НАН України, протокол бюро ВІ № А від 10.02.2000 р;

- ВФК 130.09 “Розробка математичних методів та обчислювальних алгоритмів для аналізу, оптимізації та керування ризиком” виконувалася за постановою Президії НАН України, протокол бюро ВІ № від 12.01.2001 р.

Програмна реалізація для кластера виконана відповідно до проекту “Створення та підготовка серійного виробництва ряду високопродуктивних інтелектуальних ЕОМ та спеціалізованого паралельного програмного забезпечення для розв’язання складних завдань в економіці, науці, безпеці, оборони України та інших галузях народного господарства” (постанова бюро Президії НАН України від 24.06.04, № ), в рамках програми “Створення ефективних інтелектуальних інформаційних технологій, високопродуктивних ЕОМ та засобів захисту інформації” (шифр “Інтелект”), яка виконувалася у відповідності з розпорядженням Президії НАН України від 01.07.03, № 404.

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

Об’єкт дослідження – складні стохастичні технічні й операційні системи, функціонування яких описується набором показників, що залежать від детермінованих і випадкових параметрів.

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

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

Наукова новизна отриманих результатів.

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

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

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

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

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

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

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

Особистий внесок здобувача. У спільних роботах [1], [3–6], [12] науковому керівникові належать вибір напрямків досліджень, постановки задач і вироблення загальних підходів до їхнього вирішення, а здобувачеві – реалізація загальних підло-дів для конкретних задач, розробка алгоритмів і програм, чисельні експерименти. Зокрема у роботі [3] дисертанту належить розробка числення стохастичних міно-рант, обчислення конкретних мінорант, чисельні експерименти; [4, 5] – розробка алгоритмів стохастичних аналогів методу Піявського та гілок і меж; [6] – алгоритм оптимізації надійності мережі та чисельні експерименти; [1], [12] – узагальнюють результати спільних робіт [3–6] та особистих робіт здобувача [2], [7–11].

Апробація результатів дисертації.

1. Результати роботи доповідалися на семінарах в Інституті кібернетики ім. В.М. Глушкова НАН України, Черкаському державному університеті та на наступних конференціях:

- VIII Міжнародна науково-практична конференція “Наука і освіта 2005”, м. Дніпропетровськ, 7–21 лютого, 2005 р.;

- міжнародна науково-практична конференція “Прийняття рішень в умовах невизначеності 2004”, м. Тернопіль, 25–30 травня, 2004 р.;

- X Міжнародна науково-практична конференція ім. академіка М. Кравчука, м. Київ, 13–15 травня, 2004 р.;

- IV Всеукраїнська науково-практична конференція “Інформаційні тех-нології в науці, освіті і техніці 2004”, м. Черкаси, 28–30 квітня, 2004 р.;

- міжнародна науково-практична конференція “Прийняття рішень в умовах невизначеності 2003”, м. Алушта, 8–12 вересня, 2003 р.

2. Розроблений у дисертації паралельний метод гілок і границь з мінорантими оцінками для розв’язання неперервної стохастичної задачі розміщення був запрогра-мований, відлагоджений на кластері Інституту кібернетики ім. В.М. Глушкова НАН України і зданий замовникові в рамках теми “Створення та підготовка серійного виробництва ряду високопродуктивних інтелектуальних ЕОМ та спеціалізованого паралельного програмного забезпечення для розв’язання складних завдань в економіці, науці, безпеці та оборони України та інших галузях народного господарства”.

3. Програма “Паралельний метод гілок і границь з мінорантими оцінками для розв’язання неперервної стохастичної задачі розміщення” брала участь у презентації обчислювального кластера Інституту кібернетики ім. В.М. Глушкова НАН України на міжнародній виставці в Ганновері в 2004 р.

Публікації. Результати роботи опубліковані в 12 друкованих працях, із них
6 – статей в наукових виданнях, які входять у список № ВАК України [1–6], із них одна виконана без співавторів, 5 тез доповідей конференцій [7–11], та одна [12] є інтернет-публікацією.

Структура та обсяг дисертації. Дисертаційна робота складається із вступу, п’яти розділів, висновків, списку використаних джерел та додатків. Повний обсяг роботи – 120 сторінок, 10 рисунків, 18 таблиць, список використаних джерел 120 найменувань.

Зміст роботи

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

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

, (1.)

, , (1.)

де F(x) – цільова функція; – деяка неперервна або дискретна множина допустимих значень змінних задачі; E – символ математичного очікування;– вектор випадкових параметрів; – носій деякого ймовірнісного простору.

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

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

Означення .1. Нехай X – топологічний простір, функції , , зв’язані умовами:

(i) для всіх,;

(ii) для всіх;

(iii) функція неперервна по x рівностепенево по y.

Тоді функції називаються дотичними (у точках y) мінорантами для F(x).

Дотичні міноранти тісно пов’язані з функціями максимуму. З одного боку, для функцій максимуму легко будуються дотичні міноранти, а з іншого – функції, що допускають дотичні міноранти, є функціями максимуму. Відомі наступні результати.

Теорема .1. Якщо – сімейство дотичних мінорант функції у термінах означення 2.1, то неперервна і може бути представлена у вигляді функції максимуму:.

Лема .3. Якщо – функція максимуму, де – неперервна по x рівностепенево по, то F(x) неперервна, а функція є дотичною у точці y мінорантою для F(x).

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

Міноранти функції мінімуму. Нехай і функції для всіх допускають (вгнуті) дотичні в точках y міноранти. Тоді функція є (вгнутою) дотичною у точці y мінорантою для F(x).

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

У глобальній оптимізації широко використовують дотичні конуси: Якщо функції F(x) Ліпшіцеві (Гельдерові) з константою Ліпшиця L і показником :

, , ,

то в якості дотичної у точці міноранти для F(x) можна взяти функцію

.

Але в гладких задачах глобальної оптимізації більш доцільно використовувати гладкі міноранти, наприклад дотичні параболоїди. Для гладких по x функцій F(x) з Ліпшіцевим градієнтом (з константою) у якості дотичних мінорант можна використати дотичні до графіка F(x) у точках параболоїди:

.

У підрозділі 2.2 також розглядаються деякі нові модифікації методу Піявського (алгоритми 2.1, 2.2), що використовують різні міноранти (у тому числі і не дотичні). Для описаних методів сформульовані й доведені теореми про збіжність. Зроблені числові експерименти за порівнянням ефективності використання гладких та негладких мінорант. Показано, що методи глобальної оптимізації, які використовують гладкі міноранти, працюють значно ефективніше ніж методи з Ліпшіцевими мінорантами.

Алгоритм .1. Точки довільні. Нехай побудовані точки. Позначимо

.

Точку, знайдемо як розв’язок наступної спеціальної багатоекстремальної задачі:

, (2.)

де. Задача є задачею параметричного програмування з параметром. При отримуємо стандартний метод Піявського. В цій модифікації не змінюється форма складових мінорант.

Алгоритм .2. Точки довільні. Нехай побудовані точки. Позначимо

,

.

Точку, знайдемо як розв’язок наступної спеціальної багатоекстремальної задачі:

, (2.)

де. Задача є задачею параметричного програмування з параметром. При отримуємо стандартний метод Піявського. В цій модифікації використовувані міноранти деформуються.

У підрозділі 2.3 представлені мінорантні оцінки значень цільової функції, з використанням яких побудовано варіант алгоритму методу гілок і границь. Нехай – сімейство дотичних у точках мінорант для F(x), – деяка скінченна або нескінченна множина точок з X. Розглянемо ряд оцінок оптимального значення, побудованих на основі інформації, закладеної у сімействі дотичних мінорант. Ці оцінки мають такий вигляд:

;

;

,;

.

Лема .6 (про порівняння оцінок). Припустимо, що опукла оболонка coZ деякої скінченної множини точок співпадає з компактом X, а міноранти мають вигляд, , причому монотонно спадає і неперервна за другим аргументом. Тоді.

Алгоритм 2.3 (методу гілок та меж).

Крок  (розгалуження). Нехай множина обирається для розгалуження, тобто вона представляється у вигляді об’єднання декількох підмножин, k=1,2,…, так, що. Тоді нове розбиття має вигляд.

Крок  (оцінка). Для елементів нового розбиття переобчислюються оцінки і оптимальне значення функції F(y) на елементі Y.

Крок 3 (видалення). З розбиття віддаляються безперспективні множини, такі, що, і т.д.

Теорема .3 (про збіжність алгоритму 2.3). Нехай F(x) – неперервна функція на X,. Припустимо, оцінки підмножин мають властивість, що для будь-якої послідовності множин, такої, що при. Припустимо, що розбиття здійснюються так, що діаметри отримуваних множин, прямують до нуля, при необмеженому числі поділів. Тоді послідовність нескінченна і для будь-якої граничної точки y рекордних множин виконано.

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

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

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

Означення .1 (стохастичних міноранти). Функції, де – носій деякого ймовірнісного простору, називаються стохастичними дотичними мінорантами для F(x), якщо функції вимірні по, а математичні очікування скінченні і для кожного є дотичними в точці y мінорантами для F(x) (у термінах означення 2.1).

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

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

1)

2)

3)

4) –

5)

Тоді функції неперервні і є дотичними мінорантами для функції математичного очікування.

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

Якщо ймовірнісна міра дискретна, то операція взяття математичного очікування зводиться до сумування:, де – значення ймовірності елементарної події.

У випадку загальної ймовірнісної міри апроксимуємо задачу () емпіричними середніми із зростаючим числом спостережень:

, (3.)

де – незалежні спостереження випадкового параметра. Якщо функції рівномірно сходяться до при, то замість вихідної задачі () можна розв’язувати наближену задачу . У роботі наведені (відомі) умови рівномірної збіжності функцій до F(x) (лема 3.1).

Нехай функції є дотичними мінорантами для випадкових функцій. Очевидно, функції

(3.)

будуть дотичними мінорантами для.

Алгоритм .1 (стохастичний аналог методу Піявського). Точки довільні. Нехай уже побудовані точки.

Точку, , знайдемо як розв’язок наступної спеціальної багатоекстремальної задачі:

. (3.)

Теорема .4 (про збіжність стохастичного аналога методу Піявського). Нехай цільова функція F(x) задачі () апроксимується послідовністю емпіричних функцій із , що мають дотичні міноранти . Тоді за умови рівномірної збіжності функцій до F(x) послідовність, породжена алгоритмом 3.1, з ймовірністю 1 збігається до множини глобальних мінімумів вихідної функції на X.

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

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

,

,

, ,

.

Наступні оцінки є специфічними для функції математичного очікування, основна їх ідея полягає у внесенні операцій взяття максимуму та/або мінімуму під знак математичного очікування:

,

,

,

.

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

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

Четвертий розділ присвячений опису застосувань, у яких використовуються методи, описані в попередніх розділах.

Для вивчення роботи методів, представлених у розділах 2 і 3, були побудовані відповідні алгоритми. Отримані алгоритми використовувалися при створенні програмного комплексу, призначеного для розв’язання задач глобальної і стохастичної глобальної оптимізації. Програмний комплекс розроблений у середовищі програмування Delphi 6 фірми Borland Software Corporation.

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

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

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

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

,.

Якщо є n сервісних центрів у точках, а клієнт обирає найближчий до нього центр, то вартість обслуговування клієнта задається функцією

,.

Задача полягає у розміщенні n сервісних центрів таким чином, щоб сукупні очікувані витрати обслуговування всіх споживачів послуги були мінімальними:

,

де D – множина допустимих позицій центрів. Координати центрів можуть задовольняти деяким додатковим обмеженням, наприклад, вони можуть бути впорядкованими за відношенням до деякого напрямку, тоді

.

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

Якщо – гладка по x функція з Ліпшіцевим градієнтом, то в якості дотичних мінорант можна взяти дотичні параболоїди. Зауважимо також, що функція може бути представлена як різниця двох опуклих функцій, тому в якості її дотичної у точці y міноранти можна взяти вгнуту функцію

.

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

Для оптимізації надійності розглянуто мережу з точки зору її часу життя. Мережа складається із множини вузлів, з’єднаних дугами. Повідомлення входять у мережу в деяких вузлах входу проходять по мережі до деяких вузлів призначення. Дуги і вузли можуть виходити з ладу, в такому випадку повідомлення може не пройти через них. Мережа вважається працездатною, якщо є шлях від кожного вузла входу до кожного вузла призначення. Вважаємо, що кожна дуга має випадковий час життя. Тоді надійність мережі виражається через часи життя дуг. Якщо є тільки один вхід і один вихід, то випадковий час життя рівняється

,

де максимум береться за шляхами, що з’єднують вхід і вихід, а мінімум – за часом життя дуг a, що входять у шлях p.

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

Позначимо випадковий час життя дуги i. Якщо збільшувати надійність відповідного з’єднання резервною (не працюючою) дугою з часом життя, то час життя цього з’єднання стає рівним. Якщо використати змінну для позначення наявності () або відсутності () резервної дуги, то час життя стає рівним.

Модель залежності може бути введена з іншого погляду. Припустимо, що час життя дуги i має експонентний розподіл,

,

де середній час життя залежить від інвестиції ресурсу в надійність дуги. Введемо випадкову змінну, рівномірно розподілену на [0,1]. Тоді випадковий час життя дуги може бути виражений у вигляді

.

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

,

де I – множина дуг, які можна зарезервувати. Позначимо F(x) очікуваний час життя мережі, наприклад

.

Тоді типова задача оптимізації резерву має вигляд

при обмеженнях

.

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

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

для часу життя всієї схеми. Очевидно, і для всіх x.

Аналогічно, для знайдемо критичний елемент в i-у шляху і дотичну мажоранту для часу життя i-го шляху. Очевидно, для всіх x і. Функція є дотичною мажорантою для.

Тоді для кожного допустимого x

і, отже,

.

Таким чином, час життя паралельно-послідовної схеми мінорується часом життя деякої послідовної схеми й мажорується часом життя деякої паралельної схеми.

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

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

При розміщені достатньо великої кількості сервісних центрів (тобто розв’язування задачі великої розмірності) виникає ряд ускладнень при програмуванні та виконанні алгоритму на персональних ЕОМ, а саме:

– нестача оперативної пам’яті для розташування даних задачі;

– порівняно невелика швидкість обчислень, що збільшує час роботи програми до неприпустимої величини.

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

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

Для реалізації паралельного варіанта алгоритму методу гілок і границь використовується бібліотека MPI, реалізована під мову програмування Сі.

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

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

Висновки

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

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

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

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

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

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

6. Розроблено програмний комплекс для розв’язування задач глобальної та стохастичної глобальної оптимізації, у якому реалізована більшість розроблених у роботі методів.

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

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

9. Розроблено паралельний алгоритм стохастичного методу гілок і границь для розв’язання задачі про оптимальне розміщення сервісних центрів, який був реалізований на мові програмування Сі з використанням бібліотеки MPI та випробуваний на кластерній системі Інституту кібернетики ім. В.М. Глушкова НАН України.

основні положення дисертації опубліковані в таких працях:

1. Норкин В.И., Онищенко Б.О. Минорантные методы стохастической глобальной оптимизации // Кибернетика и системный анализ. – 2005. – № 2. – С. 56–70.

2. Онищенко Б.О. Решение одной задачи стохастической глобальной оптимизации параллельным методом ветвей и границ на кластере // Компьютерная математика. – Вып. 3. – Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 2005. – С. 153–160.

3. Норкин В.И., Онищенко Б.О. О глобальной минимизации функций минимума методом минорант // Теория оптимальных решений. – Вып. 3. – Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 2004. – С. 56–63.

4. Норкин В.И., Онищенко Б.О. Метод ветвей и границ с минорантными оценками для решения задач стохастической глобальной оптимизации // Компьютерная математика. – Вып. 1. – Киев: Ин-т кибернетики НАН Украины, 2004. – С. 91–101.

5. Норкин В.И., Онищенко Б.О. О стохастическом аналоге метода глобальной оптимизации Пиявского // Теорія оптимальних рішень. – Вып. 2. – Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 2003. – С. 61–67.

6. Норкин В.И., Онищенко Б.О. О методе ветвей и приближенных границ // Компьютерная математика. – Вып. 1. – Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины, 2005. – С. 152–160.

7. Онищенко Б.О. Решение одной задачи стохастической глобальной оптимизации параллельным методом ветвей и границ // Материалы VIII Междунар. научно-практической конф. "Наука и образование 2005", Днепропетровск, 7–21 февраля, 2005. – 23. – С. 52–54.

8. Онищенко Б.О. Об обобщении минорантных методов стохастической глобальной оптимизации // Тезисы междунар. научно-практической конф. "", Тернополь, 25–30 мая, 2004. – С. 45–47.

9. Онищенко Б.О. Об обобщении метода глобальной оптимизации Пиявского // Материалы X Междунар. научно-практической конф. им. академика М. Кравчука. – Киев, 13–15 мая, 2004. – С. .

10. Онищенко Б.О. Пакет программ для решения задач стохастической глобальной оптимизации // Материалы IV Всеукраинской научно-практической конф. "Информационные технологии в науке, образовании и технике", Черкассы, 28–30 апреля, 2004. – 1. – С. 24–25.

11. Онищенко Б.О. О минорантных методах стохастической глобальной оптимизации // Тезисы междунар. научно-практической конф. "", Алушта, 8–12 сентября, 2003. – С. 140–141.

12. NorkinOnischenkoMinorant methods for stochastic global optimi-zation // Dagstuhl Seminar Proceedings “Algorithms for Optimization with In-complete Information”. – 2005. – http://drops.dagstuhl.de/opus/volltexte/2005/211.

АНОТАЦІЯ

Онищенко Б.О. Мінорантні методи глобальної стохастичної оптимізації. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 – теоретичні основи інформатики та кібернетики. – Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, 2006.

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

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

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

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

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

Алгоритм розв’язання задачі оптимального розміщення сервісних центрів також реалізований за допомогою засобів паралельного програмування і випробуваний на кластерному комплексі Інституту кібернетики ім. В.М. Глушкова НАН України.

Ключові слова: глобальна оптимізація, стохастична глобальна оптимізація, дотичні міноранти, стохастичні дотичні міноранти, метод Піявського, мінорантні оцінки, метод гілок і границь, стохастичний метод гілок і границь, паралельний метод гілок і границь.

Аннотация

Онищенко Б.О. Минорантные методы стохастической глобальной опти-мизации. – Рукопись.

Диссертация на соискание ученой ступени кандидата физико-математических наук по специальности 01.05.01 – теоретические основы информатики и кибер-нетики. – Институт кибернетики им. В.М. Глушкова НАН Украины, Киев, 2006.

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

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

В диссертации также разработано обобщение детерминированного метода глобальной оптимизации Пиявского для решения задач стохастической глобальной оптимизации и некоторые его модификации. Это обобщение подобно обобщению детерминированного градиентного метода на метод стохастических квазиградиентов для решения задач стохастического программирования. При этом нахождение детерминированных минорант, как и детерминированных градиентов функции математического ожидания, может быть затруднительным, в то время как использование стохастических минорант и стохастических квазиградиентов вполне возможно.

Ввиду того, что метод Пиявского не является эффективным при решении задач большой размерности из-за сложности решения вспомогательных подзадач, в работе разработано несколько модификаций стохастического метода ветвей и границ с минорантными оценками значений целевой функции на подмножествах и доказана их сходимость. Минорантные оценки ветвей (подмножеств) основаны на аппроксимации снизу исходной функции с помощью одной или нескольких касательных минорант, построенных в точках подмножества. Для получения оценок в стохастических задачах, кроме стохастических минорант, используется также прием перестановочной релаксации, т.е. перестановки операций минимизации и математического ожидания.

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

Алгоритм решения задачи оптимального размещения сервисных центров также реализован с помощью средств параллельного программирования и испытан на кластерном комплексе Института кибернетики им. В.М. Глушкова НАН Украины.

Ключевые слова: глобальная оптимизации, стохастическая глобальная оптимизация, касательные миноранты, стохастические касательные миноранты, метод Пиявского, минорантные оценки, метод ветвей и границ, стохастический метод ветвей и границ, параллельный метод ветвей и границ.

Abstract

OnischenkoMinorant methods for stochastic global optimization. – Manuscript.

Thesis for a candidate’s degree in physical-mathematical sciences by speciality 01.05.01 – theoretical bases of the informatics and cybernetics. V.M. Glushkov Institute of Cybernetics NAS of Ukraine, Kyiv, 2006.

The dissertation is