Розпаралелювання процесу розв’язання векторних задач комбінаторної оптимізації за умов невизначеності та ризику
Розроблено підхід до розпаралелювання процесу розв’язання векторних дискретних оптимізаційних задач за умов невизначеності й ризику, який полягає у зведенні пошуку розв’язків вхідної задачі до розв’язання послідовності однокритеріальних підзадач лінійної оптимізації. Методи розв’язання останніх ґрун...
Збережено в:
| Опубліковано в: : | Компьютерная математика |
|---|---|
| Дата: | 2014 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84813 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Розпаралелювання процесу розв’язання векторних задач комбінаторної оптимізації за умов невизначеності та ризику / В.В. Семенов, Н.В. Семенова // Компьютерная математика. — 2014. — № 1. — С. 83-92. — Бібліогр.: 15 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859804646641500160 |
|---|---|
| author | Семенов, В.В. Семенова, Н.В. |
| author_facet | Семенов, В.В. Семенова, Н.В. |
| citation_txt | Розпаралелювання процесу розв’язання векторних задач комбінаторної оптимізації за умов невизначеності та ризику / В.В. Семенов, Н.В. Семенова // Компьютерная математика. — 2014. — № 1. — С. 83-92. — Бібліогр.: 15 назв. — укр. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Розроблено підхід до розпаралелювання процесу розв’язання векторних дискретних оптимізаційних задач за умов невизначеності й ризику, який полягає у зведенні пошуку розв’язків вхідної задачі до розв’язання послідовності однокритеріальних підзадач лінійної оптимізації. Методи розв’язання останніх ґрунтуються на ідеях декомпозиції, відсікаючих площин, релаксації і зводяться до задач безумовної максимізації угнутих кусково-квадратичних функцій, які розв’язуються за допомогою паралельного алгоритму методу Ньютона.
Разработан подход к распараллеливанию процесса решения векторных дискретных оптимизационных задач при условиях неопределенности и риска, который состоит в сведении поиска решений исходной задачи к решению последовательности однокритериальных подзадач линейной оптимизации. Методы решения последних основаны на идеях декомпозиции, отсекающих плоскостей, релаксации и сводятся к задачам безусловной максимизации вогнутых кусочно-квадратичных функций, которые решаются с помощью параллельного алгоритма метода Ньютона.
An approach to parallelizing the solution process of vector discrete optimization problems under uncertainty and risk conditions is developed. This approach consists of the search of solution to initial problem as a sequence of solutions to linear optimization scalar criteria subproblems. The solution methods of linear optimization problems are based on the ideas of decomposition, cutting planes and relaxation, and are reduced to the problems of maximization of concave piecewise quadratic functions, which are solved with the use of the parallel algorithm of Newton method.
|
| first_indexed | 2025-12-07T15:15:08Z |
| format | Article |
| fulltext |
Компьютерная математика. 2014, № 1 83
Розроблено підхід до розпарале-
лювання процесу розв’язання век-
торних дискретних оптимізацій-
них задач за умов невизначеності
й ризику, який полягає у зведенні
пошуку розв’язків вхідної задачі до
розв’язання послідовності однок-
ритеріальних підзадач лінійної
оптимізації. Методи розв’язання
останніх ґрунтуються на ідеях
декомпозиції, відсікаючих площин,
релаксації і зводяться до задач
безумовної максимізації угнутих
кусково-квадратичних функцій,
які розв’язуються за допомогою
паралельного алгоритму методу
Ньютона.
В.В. Семенов, Н.В. Семенова,
2014
В.В. СЕМЕНОВ, Н.В. СЕМЕНОВА
Компьютерная математика. 2014, № 1 84
УДК 519.8
В.В. СЕМЕНОВ, Н.В. СЕМЕ-
НОВА
РОЗПАРАЛЕЛЮВАН
НЯ ПРОЦЕСУ
РОЗВ’ЯЗАННЯ
ВЕКТОРНИХ ЗАДАЧ
КОМБІНАТОРНОЇ
ОПТИМІЗАЦІЇ
ЗА УМОВ
НЕВИЗНАЧЕНОСТІ
ТА РИЗИКУ
Вступ. Різноманітність, а ча-
сто і суперечливість різних
вимог до системи чи об’єкта,
що проектується або оптимі-
зується, неповнота інформа-
ції, неточність моделей, що
застосовуються, неминуче
приводять до того, що реаль-
ні задачі оптимізації дово-
диться роз-в’язувати за умов
невизначеності та ризику [1 –
3]. Розрізняють задачі за
умов ризику, коли розподіл
випадкових факторів (пара-
метрів) відомий, і задачі оп-
тимізації за умов невизначе-
ності, коли розподіл випадко-
вих параметрів невідомий або
параметри є невизначеними,
тобто для них відомі лише
множини можливих значень.
Розглянемо спочатку вектор-
ні задачі оптимізації за умов
ризику. Для фіксованої аль-
тернативи критерії є випад-
ковими величинами з розпо-
ділами, що описуються відомими функціями
(або щільностями) розподілу. Частковий
критерій такого типу характеризує альтерна-
тиву не одним числом, а множиною чисел. За
допомогою таких критеріїв незручно робити
порівняння альтернатив. Тому їх спочатку
доцільно перетворити, використовуючи при-
йоми, які широко використовуються для ска-
лярних задач оптимізації за умов ризику.
Найпоширенішим є прийом, що полягає у
тому, що вхідний імовірнісний критерій за-
мінюється одним з його моментів. Найчасті-
ше використовується момент першого по-
рядку – математичне сподівання, іноді –
центральний момент другого порядку, тобто
дисперсія.
РОЗПАРАЛЕЛЮВАННЯ ПРОЦЕСУ РОЗВ’ЯЗАННЯ ВЕКТОРНИХ ЗАДАЧ ...
Компьютерная математика. 2014, № 1 85
Таким чином, векторна задача оптимізації за умов ризику приймає вигляд дете-
рмінованої векторної задачі, однак зберігає імовірнісний зміст. При цьому дете-
рмінована задача буде мати більше число часткових критеріїв, якщо, наприклад,
спочатку використовувати два перших моменти першого часткового критерію,
потім два перших моменти другого критерію і т. д. У задачах оптимізації за умов
невизначеності критерії, що характеризують якість альтернатив, залежать також
від параметрів, які є випадковими, але з невідомими розподілами, або невизна-
ченими, що виникають, наприклад, через недостатню або неможливу вивченість
будь-яких процесів і явищ. Незалежно від походження невизначені параметри,
як і випадкові параметри з невідомими розподілами, характеризуються тим, що
для них у математичній моделі не визначені конкретні значення, а задані лише
множини можливих значень [1 – 3].
Докладний критичний аналіз основних принципів оптимальності, запропо-
нованих для прийняття рішень за умов невизначеності, проведений у [4]. Розг-
лянемо одні з найбільш важливих принципів – принцип максиміна або найкра-
щого гарантованого результату, коли пошук оптимальних рішень здійснюється
за песимістичною стратегією; і коли пошук найкращого рішення здійснюється за
оптимістичною стратегією За песимістичною стратегією здійснюється пошук
Парето-оптимального розв’язку, одночасно допустимого при всіх можливих
значеннях неоднозначно заданих даних моделі. За оптимістичною стратегією
ведеться пошук оптимального розв’язку, який є допустимим принаймні для од-
ного набору значень даних задачі з області їх визначення. Можлива також
параметризація цих підходів.
Новим теоретичним підходом для розв’язання важливих задач економіки,
проектування складних систем, прийняття рішень за умов невизначеності та ін.
є застосування моделей і методів, що об’єднують багатокритеріальність альтер-
натив і комбінаторні властивості допустимої множини. Для розв’язання задач
комбінаторної оптимізації розроблені різні обчислювальні методи. Найбільш
перспективні з них складають окрему область поліедральної комбінаторики
[5 – 8]. Загальна ідея цих методів полягає у встановленні зв’язку екстремальних
комбінаторних задач з методами лінійного програмування: елементи допустимої
множини інтерпретуються як точки евклідового простору, функції критеріїв і
обмежень розглядаються як неперервні. Таким чином, розв’язується задача зна-
ходження екстремуму функції на опуклій оболонці заданих точок, тобто на
опуклому многограннику. Як відомо, екстремум лінійної функції на многогран-
нику досягається в одній з вершин, яка включається в множину комбінаторних
елементів, що розглядаються. Особливість розв’язування комбінаторних задач
при такому зведенні полягає у тому, що при знаходженні розв’язків можна об-
межуватися лише вершинами многогранника.
В.В. СЕМЕНОВ, Н.В. СЕМЕНОВА
Компьютерная математика. 2014, № 1 86
У даній роботі сформульовані та досліджені векторні задачі дискретної оп-
тимізації на комбінаторній множині за умов невизначеності та ризику. Описані
множини допустимих та оптимальних розв’язків, їх структурні властивості та за-
стосування до розв’язання таких задач. Запропоновано та обґрунтовано підхід з
розпаралелюванням процесу оптимізації до знаходження ефективних розв’язків,
який дозволяє не тільки розпаралелити процес оптимізації і тим самим приско-
рити обчислення, але і розв’язувати задачі значно більшої розмірності.
1. Математична постановка векторної задачі оптимізації за умов неви-
значеності та ризику на комбінаторній множині перестановок. Властивості
області допустимих розв’язків. Розглядаються векторні задачі дискретної оп-
тимізації вигляду: { }( , ) : max ( ) | ,iZ F X F x x X∈ 1( ,..., )F f f= l − векторний
критерій, 1 : n
jf R R→ , 1,...,j = l , iX – скінченна множина n-вимірних векторів,
1,2,i = 1 { | : }nX x R A H Ax b= ∈ ∀ ∈ ≤ , 2 { | : },nX x R A H Ax b= ∈ ∃ ∈ ≤
Песимістична стратегія щодо цих задач полягає у знаходженні Парето-
оптимального розв’язку задачі Z(F,X), одночасно допустимого для всіх можли-
вих значень A H∈ . Вона дає вектор ,z R∈ l мінімально гарантованих значень
оцінок критеріїв *( )z F x= і Парето-оптимальний розв’язок *
1x X∈ цієї задачі
тобто 1 :y X∃ ∈ * *( ) ( ), ( ) ( )F y F x F y F x≥ ≠ .
За оптимістичною стратегією здійснюється пошук оптимального розв’язку
задачі, що є допустимим для деяких (хоча б для однієї) матриці A H∈ . Такий
розв’язок є найкращим з усіх можливих розв’язків задачі Z(F, X). Оптимістична
стратегія дає верхню межу **( )z F x= всіх можливих значень критеріїв і Паре-
то-оптимальний розв’язок **
2x X∈ цієї задачі. Визначивши значення векторів z
і ,z можна охарактеризувати стійкість задачі до змін її вхідних даних.
Декомпозиційний підхід до розв’язання таких задач з одним критерієм
запропонований у роботах [1 – 3].
Побудуємо підхід з розпаралелюванням процесу оптимізації до знаходжен-
ня розв’язків векторних дискретних оптимізаційних задач на комбінаторній
множині перестановок з неточно заданими даними матриці обмежень на основі
принципу найкращого абсолютно гарантованого результату (песимістичної
стратегії). Математичне формулювання цього принципу для векторних задач з
лінійними функціями критеріїв приводить до задачі наступного вигляду:
{ }1( , ) : max | ,Z C X Cx x X∈ де 1 { | , }nX x R Ax b A H= ∈ ≤ ∀ ∈ , матриця nC R ×∈ l ,
1( ,..., ) n
i i inc c c R= ∈ , 1,..., .i = l
Для математичної постановки задачі Z(C, X) використовується також понят-
тя мультимножини 1{ ,..., }qA a a= [5, 7, 8].
РОЗПАРАЛЕЛЮВАННЯ ПРОЦЕСУ РОЗВ’ЯЗАННЯ ВЕКТОРНИХ ЗАДАЧ ...
Компьютерная математика. 2014, № 1 87
Упорядкованою n -вибіркою з мультимножини A називається набір
1
( , , ),
ni ia a a= K де
jia A∈ ,j ni N∀ ∈ nj N∀ ∈ , s ti i≠ , якщо s t≠ , .ns t N∀ ∈ Буде-
мо розглядати елементи множини перестановок з повтореннями як точки ариф-
метичного евклідового простору nR . У роботах [6 – 9] показано, що опуклою
оболонкою множини перестановок є многогранник ( ) conv ( ),nk nkA P AΠ = мно-
жина вершин якого збігається з множиною ( )nkP A перестановок:
vert ( ) ( )nk nkA P AΠ = , який описується наступною системою лінійних нерів-
ноcтей:
1 1 1
, ,
t
t
n n
i i t n i i
i i i j
x a N x a
ω
∈ω = = =
≥ ∀ω ⊂ =∑ ∑ ∑ ∑
де ,t tω = { }1,2,...t ∈ − кількість елементів множини індексів ω. При відобра-
женні множини ( )nkP A в евклідів простір nR кожній точці ( )nka P A∈ відпові-
дає ( )vert n
nkx A R∈ Π ⊂ . Нехай задача ( ),Z C X визначена на допустимій мно-
жині 1 vert ( )nkX X A= ΠI .
У роботах [5, 10] встановлено взаємозв’язок між задачею ( , )Z F X і задачею
( , )Z F G , визначеній на неперервній допустимій множині. Це дає можливість
застосовувати методи неперервної оптимізації до розв’язання векторних комбі-
наторних задач і на цій основі розвивати нові оригінальні методи розв’язання,
використовуючи властивості комбінаторних множин та їх опуклих оболонок.
2. Підхід до розв’язання векторних задач на комбінаторній множині пе-
рестановок за умов ризику та невизначеності. Продовжуючи дослідження і
розвиваючи результати робіт [1 – 3, 5], запропоновано підхід до розв’язання за-
дачі ( ),Z C X , оснований на лінійній згортці часткових критеріїв задачі [11]
і подальшому зведенні пошуку розв’язку початкової задачі до розв’язання
послідовності однокритеріальних лінійних підзадач, перевірки оптимальності
отриманих розв’язків. Методи розв’язання однокритеріальних підзадач заснова-
ні на ідеях декомпозиції, відтинаючих площин Келлі, релаксації. Далі
розглядається метод, при реалізації якого враховується той факт, що число об-
межень досить велике. Отже, доцільним є використання процедури релаксації,
тобто тимчасового відкидання деяких обмежень і розв’язання задачі на більш
широкій області, тобто за обмеженнями, що залишилися.
Введемо наступні позначення. Допустиму область задачі ( ),Z C G запишемо
у вигляді { | }nG x R Hx g= ∈ ≤ , 1( ,.., )qg g g= , q nH R ×∈ , H − матриця, яка
використовується для матрично-векторної форми запису обмежень задачі
( ),Z C G , де всі обмеження зведені до одного ( ≤ ) вигляду нерівностей. Позна-
чимо qN множину, елементами якої є номери обмежень задачі ( ),Z C G .
В.В. СЕМЕНОВ, Н.В. СЕМЕНОВА
Компьютерная математика. 2014, № 1 88
Введемо до розгляду задачу ( )( , ) : max{ | }s sZ f G f x x G∈ , яка розв’язується
на s-му кроці алгоритму, { }, ,s n
i i s qG x R h x g i Q N= ∈ ≤ ∈ ⊂ , де sQ – множина
номерів обмежень, що описують допустиму область цієї задачі, \s q sQ N R= ,
sR – множина номерів обмежень, які не були включені в задачу на s-му кроці.
Основна ідея методу розв’язання полягає у наступному.
1. Зводимо багатокритеріальну задачу ( ),Z C X до однокритеріальної задачі
( ),Z f X методом лінійної згортки. Вибираємо обмеження початкової системи,
що визначають область sG G⊂ .
2. Визначаємо обмеження допустимої області sG G⊂ , розв’язуємо задачу
лінійної оптимізації ( , )sZ f G і знаходимо оптимальний розв’язок sx .
3. Якщо отриманий оптимальний розв’язок є перестановкою, тобто верши-
ною переставного многогранника, то перевіряємо виконання обмежень у точці
,sx що не були враховані. Якщо додаткові обмеження не виконуються, то
будуємо відсікання, що проходить через суміжні вершини та відтинає вершину,
яка не є допустимою. Додаємо це обмеження до обмежень релаксованої задачі.
4. Розв’язуємо задачу ( , )sZ f G з доданими обмеженнями симплекс-
методом. Якщо отримали оптимальний розв’язок, що є елементом множини пе-
рестановок, тобто вершиною переставного многогранника, то перевіряємо об-
меження, які не були включені. Якщо знайдений розв’язок не задовольняє об-
меженням, тим, що залишилися, то додаємо найбільш порушене обмеження.
5. Будуємо суміжні вершини переставного многогранника, перевіряємо, чи
задовольняють вони нові обмеження. Якщо задовольняють обмеження, що за-
лишилися не включеними, то знаходимо значення цільової функції у цій точці
( )lf x . Додаємо до обмежень задачі ( , )sZ f G обмеження ( ) ( )lf x f x≥ .
6. Якщо значення ( )lf x зменшується, то відкидаємо неактивні обмеження в
точці lx . Покладаємо 1s s= + і переходимо до п. 2 алгоритму.
Та обставина, що жодне з обмежень не відкидається, якщо ( ) ,lf x f=
гарантує, що порівнюється тільки скінчене число задач ( , )sZ f G .
Загальна ідея запропонованого методу полягає у розв’язанні підзадач ліній-
ного програмування, послідовному включенні обмежень, що описують область
допустимих розв’язків цих підзадач, та відкиданні неактивних обмежень при
поточному розв’язку за деяких умов.
Теорема 1. Робота алгоритму після розв’язання скінченного числа підзадач
( , )sZ f G приводить до ефективного розв’язку задачі ( ),Z C X або до побудови
множини обмежень, при якій поточна підзадача ( , )sZ f G буде нерозв'язуваною.
РОЗПАРАЛЕЛЮВАННЯ ПРОЦЕСУ РОЗВ’ЯЗАННЯ ВЕКТОРНИХ ЗАДАЧ ...
Компьютерная математика. 2014, № 1 89
3. Розпаралелювання процесу оптимізації розв’язання підзадач лінійно-
го програмування великих розмірностей. Для підзадач лінійного програму-
вання, що розв’язуються за допомогою розробленого підходу, побудовані пара-
лельні алгоритми методу, що заснований на зведенні цих задач до задач безумо-
вної максимізації угнутої диференційовної кусково-квадратичної функції.
У роботах [12 – 14], запропоновано новий метод розв’язання задачі лінійно-
го програмування. Його застосування до двоїстої задачі дає можливість отрима-
ти точну проекцію заданої точки на множину розв’язків прямої задачі лінійної
оптимізації в результаті безумовної максимізації допоміжної кусково-
квадратичної функції при скінченному значенні коефіцієнта штрафу.
Дана робота присвячена розпаралелюванню цього методу, що дає можли-
вість розв’язувати підзадачі лінійної оптимізації з великим числом обмежень.
У роботі [15] викладено основні ідеї методу розв’язання задачі лінійної оптимі-
зації, при якому можливе отримання проекції заданої точки на множину
розв’язків прямої задачі, з числом обмежень, збільшеним до декількох сотень
тисяч. Наводяться формули для визначення граничного значення параметра до-
поміжної функції, починаючи з якого за одну безумовну максимізацію цієї фун-
кції за простими формулами обчислюється проекція точки на множину
розв’язків прямої задачі лінійної оптимізації. Повторна максимізація цієї функ-
ції, у яку підставлений розв’язок прямої задачі, дозволяє знайти розв’язки двоїс-
тої задачі лінійної оптимізації.
Нехай пряма і двоїста задачі лінійного програмування задані у вигляді:
( ) :min , {P : , 0},T n
x X
c x X x R Ax b x
∈
= ∈ = ≥
( ) :max , { : }.D T m T
u U
b u U u R A u c
∈
= ∈ ≤
Тут m nA R ×∈ , nc R∈ і mb R∈ . Нехай множина розв’язків *X прямої задачі
(Р) не порожня, отже, множина розв’язків *U двоїстої задачі (D) також не поро-
жня. Для знаходження проекції заданої точки x̂ на множину розв’язків *X пря-
мої задачі (Р) введемо допоміжну задачу безумовної максимізації:
21
ˆ ˆmax ( , , ) || ( ) ||
2m
T T
p R
S p x b p x A p c +
∈
β = − + − β
, (1)
де скаляр β – фіксований. Тут a+ – вектор, у якого i-та компонента збігається з
i-ою компонентою вектора a, якщо вона невід’ємна, і рівна нулю у протилежно-
му випадку. Скористаємось наступними теоремами [15].
Теорема 2. Існує таке число *,β що при кожному *,β ≥ β пара [ ( ), ]p β β ,
де ( )p β – розв’язок задачі безумовної максимізації (1) або, що те ж саме,
розв’язок системи ˆ( )TA x A p c b++ − β = , визначає проекцію *x̂ заданої точки x̂
на множину розв’язків *X прямої задачі (Р) за формулою
*ˆ ˆ( ( ) )Tx x A p c += + β − β .
В.В. СЕМЕНОВ, Н.В. СЕМЕНОВА
Компьютерная математика. 2014, № 1 90
Теорема 3. Нехай множина розв’язків *X задачі лінійного програмування
(Р) не порожня. Тоді для будь-яких 0β > і * *x̂ x X= ∈ розв’язок двоїстої задачі
(D) знаходиться за формулою * ( ) /u p= β β , де ( )p β – розв’язок задачі (1).
Отже, в результаті розв’язання двох задач безумовної максимізації угнутої
кусково-квадратичної функції від m змінних отримується проекція точки на
множину прямої задачі (Р) і розв’язок двоїстої задачі (D).
Для одночасного розв’язання прямої і двоїстої задач лінійного програму-
вання пропонується використовувати наступний ітераційний процес:
1 1( )T
s s sx x A p c+ + += + − β , (2)
де довільний параметр 0β > фіксований, а вектор 1sp + , визначається
з розв’язання наступної задачі максимізації:
2
1
1
arg max || ( ) || .
2m
T T
s s
p R
p b p x A p c+ +
∈
∈ − + − β
(3)
Теорема 4. При будь-якому 0β > й при будь-якій початковій точці 0x іте-
раційний процес (2), (3) збігається до * *x X∈ за скінченне число кроків ω .
Формула *
1 /u pω+= β дає точний розв’язок двоїстої задачі (D).
Цей ітераційний процес є скінченним і дає точні розв’язки прямої задачі (Р)
і двоїстої задачі (D). Розв’язання задачі безумовної максимізації (4) може вико-
нуватися будь-яким методом, наприклад методом спряженого градієнта. Але, як
показано в [14] для безумовної оптимізації кусково-квадратичної функції особ-
ливо ефективний узагальнений метод Ньютона.
4. Паралельний ітераційний алгоритм. Розглянемо паралельний алгоритм
методу (2)–(3) з використанням узагальненого методу Ньютона [15] у рамках
моделі розподіленої пам’яті. Вважаємо, що в кожного процесу (виконуваної
програми) є свій адресний простір, а обмін даними між процесами здійснюється
за допомогою бібліотеки Message Passing Interface (MPI), кожний процес вико-
нується на своєму процесорі (ядрі).
Розрахункові формули.
1. Задамо 0β > , точності, відповідно, для зовнішніх і внутрішніх операцій
1ε і ε , початкові наближення 0x і 0p .
2. Обчислюємо значення функції
21
( , , ) ( )
2
T T
k s k s kS p x b p x A p cβ = − + − β
та її градієнт: ( , , ) ( ) ,T
k k s s k
S
G p x b A x A p c
p +
∂= β = − + − β
∂
k – номер внутрішньої
ітерації методу Ньютона для розв'язання задачі (3), s – номер зовнішньої ітерації.
3. Використовуючи узагальнену матрицю Гессе функції ( , , )k sS p xβ , сфор-
муємо матрицю m m
kH R ×∈ : T
k kH I AD A= δ + . Діагональна матриця n n
kD R ×∈
задається рівностями ( ) 1,k iiD =
якщо ( ) 0,T i
s kx A p c+ − β > інакше
( ) 0.k iiD =
РОЗПАРАЛЕЛЮВАННЯ ПРОЦЕСУ РОЗВ’ЯЗАННЯ ВЕКТОРНИХ ЗАДАЧ ...
Компьютерная математика. 2014, № 1 91
4. Знайти напрямок максимізації pδ як розв’язок лінійної системи
.k kH p Gδ = − (4)
5. Визначити 1kp + за формулою 1k kp p p+ = − τδ , де ітераційний параметр
kτ знаходиться з розв’язання одновимірної задачі максимізації методом ділення
навпіл або методом Армихо:
max ( , , )k k sS p p x
τ
τ = − τδ β .
6. Якщо виконано критерій зупинки 1k kp p+ − ≤ ε для внутрішніх ітерацій
по k , то покласти 1kp p +=% й обчислити 1 ( )T
s sx x A p c+ += + − β% . Інакше перейти
до п. 2, поклавши 1k k= + .
7. Якщо виконано критерій зупинки 1 1s sx x+ − ≤ ε для зовнішніх ітерацій
по s , то обчислити розв’язок двоїстої задачі (D) * /u p= β% . Розв’язком прямої
задачі (Р) є *
1sx x += . Інакше покласти 0p p= % , 1s s= + і перейти до п. 2.
Основні операції паралельного алгоритму. В алгоритмі основними тру-
домісткими операціями є формування та розв’язання системи лінійних рівнянь
(4). Паралельна реалізація алгоритму вимагає розпаралелювання наступних ос-
новних операцій: множення матриць на вектор: Ax і TA p ; обчислення скаляр-
них добутків Tx y , x , ny R∈ і Tp q , p , ;mq R∈ формування узагальненої матри-
ці Гессе; множення її на вектор. Всі інші обчислення пунктів алгоритму є лока-
льними. Реалізовано декілька паралельних схем наведеного алгоритму в залеж-
ності від вигляду вхідної матриці А: стовпчикова схема, коли матриця A розби-
вається на блокові стовпці приблизно рівного розміру, рядкова схема – матриця
A розбивається на блоки по рядкам, клітинна схема, при якій матриця A розби-
вається на однакові прямокутні блоки, кількість яких рівна числу процесорів.
Кожна із запропонованих схем має свої переваги і недоліки, що і визначає об-
ласть їх застосування. Так стовпчикова схема досить ефективна при формуванні
системи лінійних рівнянь (4), рядкова – більш ефективна для паралельного ме-
тоду розв’язання системи лінійних рівнянь. В розроблених паралельних алгори-
тмах найкраще прискорення отримано для клітинної схеми. Однак, в залежності
від розмірності задачі та структури розрідженості матриці А, оптимальною може
виявитися як клітинна, так рядкова або стовпчикова схеми. Важливим фактором
у прискоренні обчислень є оптимізація операцій із щільними й розрідженими
матрицями. Для ефективної роботи із щільними матрицями використовувалися
функції з бібліотеки Lapack (Linear Algebra PACKage). Однак операції з розрі-
дженими матрицями дають додаткові можливості для оптимізації. Зокрема,
можна використовувати спеціальні способи подання розріджених матриць,
що поєднують переносимість і урахування характеристик кеш-пам'яті сучасних
процесорів і дозволяють істотно зменшити час на обчислення матрично-
векторних множень.
В.В. СЕМЕНОВ, Н.В. СЕМЕНОВА
Компьютерная математика. 2014, № 1 92
Висновки. В зв’язку з необхідністю створення нових оптимізаційних мето-
дів, які в повній мірі використовують можливості сучасних багатопроцесорних
комплексів, розроблено підхід до розпаралелювання процесу оптимізації до зна-
ходження розв’язків векторних дискретних оптимізаційних задач за умов неви-
значеності й ризику, який полягає у зведенні пошуку розв’язків вхідних задач до
розв’язання послідовності однокритеріальних підзадач лінійної оптимізації.
Методи розв’язання останніх ґрунтуються на ідеях декомпозиції, відсікаючих
площин, релаксації. Задачі лінійного програмування зводяться до задач безумо-
вної максимізації угнутих диференційовних кусково-квадратичних функцій, які
розв’язуються за допомогою паралельного алгоритму методу Ньютона. Розробка
ефективного паралельного алгоритму є досить складною задачею, отже для
кожного паралельного варіанта алгоритму слід шукати розумний компроміс між
обчислювальною масштабованістю й масштабованістю за пам’яттю. Розроблені
паралельні алгоритми розв’язання підзадач лінійного програмування засновані
на різних схемах розбиття даних успішно можна застосовувати для розв’язання
указаних підзадач великої розмірності при досить сильно заповнених матрицях
обмежень. Побудований підхід з розпаралелюванням процесу оптимізації дає
можливість розв’язувати векторні задачі дискретної оптимізації за умов неви-
значеності і ризику досить великої розмірності та відкриває перспективи по-
дальшої розробки ефективних алгоритмів розпаралелювання обчислень для
розв’язання нових класів векторних задач комбінаторної оптимізації.
В.В. Семенов, Н.В. Семенова
РАСПАРАЛЛЕЛИВАНИЕ ПРОЦЕССА РЕШЕНИЯ ВЕКТОРНЫХ ЗАДАЧ
КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ ПРИ УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ
И РИСКА
Разработан подход к распараллеливанию процесса решения векторных дискретных оптими-
зационных задач при условиях неопределенности и риска, который состоит в сведении поис-
ка решений исходной задачи к решению последовательности однокритериальных подзадач
линейной оптимизации. Методы решения последних основаны на идеях декомпозиции, отсе-
кающих плоскостей, релаксации и сводятся к задачам безусловной максимизации вогнутых
кусочно-квадратичных функций, которые решаются с помощью параллельного алгоритма
метода Ньютона.
V.V. Semenov, N.V. Semenova
PARALLELIZING THE SOLUTION PROCESS OF VECTOR COMBINATORIAL PROBLEMS
UNDER UNCERTAINTY AND RISK CONDITIONS
An approach to parallelizing the solution process of vector discrete optimization problems under
uncertainty and risk conditions is developed. This approach consists of the search of solution to
initial problem as a sequence of solutions to linear optimization scalar criteria subproblems. The
solution methods of linear optimization problems are based on the ideas of decomposition, cutting
planes and relaxation, and are reduced to the problems of maximization of concave piecewise qua-
dratic functions, which are solved with the use of the parallel algorithm of Newton method.
РОЗПАРАЛЕЛЮВАННЯ ПРОЦЕСУ РОЗВ’ЯЗАННЯ ВЕКТОРНИХ ЗАДАЧ ...
Компьютерная математика. 2014, № 1 93
1. Семенова Н.В. Методы поиска гарантирующих и оптимистических решений задач цело-
численной оптимизации в условиях неопределенности данных // Кибернетика и систем-
ный анализ. – 2007. – № 1. – С. 103 – 114.
2. Семенова Н.В., Мащенко О.С. Оптимізація на комбінаторній множині перестановок в
умовах неточно заданих даних // Вісник Київського університету. Серія фіз.-мат. науки. –
2009, вип. 3. – С. 184 – 189.
3. Семенова Н.В. Гарантирующие и оптимистические решения задач целочисленной опти-
мизации с выпуклыми квадратичными функциями ограничений // Теорія оптимальних
рішень. – К.: Ін-т кібернетики імені В.М. Глушкова НАН України, 2006. – № 5. –
С. 39 – 47.
4. Льюис Р.Д., Райфа Х. Игры и решения. – М.: Иностранная литература, 1961. – 642 с.
5. Семенова Н.В., Колєчкіна Л.М. Векторні задачі дискретної оптимізації на комбінаторних
множинах: методи дослідження та розв’язання. – К.: Наук. думка, 2009. – 266 с.
6. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. – М.:
Наука, 1981. – 342 с.
7. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. – К.: Ін-т
систематичних досліджень освіти. – 1993. – 188 с.
8. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометри-
ческого проектирования. – К.: Наук. думка, 1986. – 268 с.
9. Rado R. An inequality // J. London Math. Soc. – 1952. – 27 р.
10. Семенова Н.В. Условия оптимальности в векторных задачах комбинаторной оптимизации
// Теорія оптимальних рішень. – К.: Ін-т кібернетики імені В.М. Глушкова НАН України,
2008. – № 7. – С. 152 – 160.
11. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач.
– М.: Наука, 1982. – 256 с.
12. Голиков А.И., Евтушенко Ю.Г. Метод решения задач линейного программирования
большой размерности // Докл. РАН. – 2004. – 397, № 6. – С. 727 – 732.
13. Голиков А.И., Евтушенко Ю.Г., Моллаверди Н. Примеівазмерности // Вычислительная
математика и математическая физика. – 2004. – 44, № 9. – С. 1564 – 1573.
14. Mangasarian O.L. A Newton Method for Linear Programming // J. Optimizat. Theory and Appl.
– 2004. – Vol. 121. – P. 1 – 18.
15. Гаранжа В.А., Голиков А.И., Евтушенко Ю.Г., Нгуен M.X. Параллельная реализация ме-
тода Ньютона для решения больших задач линейного программирования // Вычислитель-
ная математика и математическая физика. – 2009. – 49, № 8. – С. 1369 – 1384.
Одержано 25.12.2013
Про автора:
Семенов Віктор Вікторович,
молодший науковий співробітник
Інституту кібернетики імені В.М. Глушкова НАН України.
Е-mail: hunt.semen@gmail.com
Семенова Наталія Володимирівна,
доктор фізико-математичних наук, провідний науковий співробітник
Інституту кібернетики імені В.М. Глушкова НАН України.
Е-mail: nvsemenova@meta.ua
|
| id | nasplib_isofts_kiev_ua-123456789-84813 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:15:08Z |
| publishDate | 2014 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Семенов, В.В. Семенова, Н.В. 2015-07-15T19:54:38Z 2015-07-15T19:54:38Z 2014 Розпаралелювання процесу розв’язання векторних задач комбінаторної оптимізації за умов невизначеності та ризику / В.В. Семенов, Н.В. Семенова // Компьютерная математика. — 2014. — № 1. — С. 83-92. — Бібліогр.: 15 назв. — укр. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84813 519.8 Розроблено підхід до розпаралелювання процесу розв’язання векторних дискретних оптимізаційних задач за умов невизначеності й ризику, який полягає у зведенні пошуку розв’язків вхідної задачі до розв’язання послідовності однокритеріальних підзадач лінійної оптимізації. Методи розв’язання останніх ґрунтуються на ідеях декомпозиції, відсікаючих площин, релаксації і зводяться до задач безумовної максимізації угнутих кусково-квадратичних функцій, які розв’язуються за допомогою паралельного алгоритму методу Ньютона. Разработан подход к распараллеливанию процесса решения векторных дискретных оптимизационных задач при условиях неопределенности и риска, который состоит в сведении поиска решений исходной задачи к решению последовательности однокритериальных подзадач линейной оптимизации. Методы решения последних основаны на идеях декомпозиции, отсекающих плоскостей, релаксации и сводятся к задачам безусловной максимизации вогнутых кусочно-квадратичных функций, которые решаются с помощью параллельного алгоритма метода Ньютона. An approach to parallelizing the solution process of vector discrete optimization problems under uncertainty and risk conditions is developed. This approach consists of the search of solution to initial problem as a sequence of solutions to linear optimization scalar criteria subproblems. The solution methods of linear optimization problems are based on the ideas of decomposition, cutting planes and relaxation, and are reduced to the problems of maximization of concave piecewise quadratic functions, which are solved with the use of the parallel algorithm of Newton method. uk Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Оптимизация вычислений Розпаралелювання процесу розв’язання векторних задач комбінаторної оптимізації за умов невизначеності та ризику Распараллеливание процесса решения векторных задач комбинаторной оптимизации при условиях неопределенности и риска Parallelizing the solution process of vector combinatorial problems under uncertainty and risk conditions Article published earlier |
| spellingShingle | Розпаралелювання процесу розв’язання векторних задач комбінаторної оптимізації за умов невизначеності та ризику Семенов, В.В. Семенова, Н.В. Оптимизация вычислений |
| title | Розпаралелювання процесу розв’язання векторних задач комбінаторної оптимізації за умов невизначеності та ризику |
| title_alt | Распараллеливание процесса решения векторных задач комбинаторной оптимизации при условиях неопределенности и риска Parallelizing the solution process of vector combinatorial problems under uncertainty and risk conditions |
| title_full | Розпаралелювання процесу розв’язання векторних задач комбінаторної оптимізації за умов невизначеності та ризику |
| title_fullStr | Розпаралелювання процесу розв’язання векторних задач комбінаторної оптимізації за умов невизначеності та ризику |
| title_full_unstemmed | Розпаралелювання процесу розв’язання векторних задач комбінаторної оптимізації за умов невизначеності та ризику |
| title_short | Розпаралелювання процесу розв’язання векторних задач комбінаторної оптимізації за умов невизначеності та ризику |
| title_sort | розпаралелювання процесу розв’язання векторних задач комбінаторної оптимізації за умов невизначеності та ризику |
| topic | Оптимизация вычислений |
| topic_facet | Оптимизация вычислений |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84813 |
| work_keys_str_mv | AT semenovvv rozparalelûvannâprocesurozvâzannâvektornihzadačkombínatornoíoptimízacíízaumovneviznačenostítariziku AT semenovanv rozparalelûvannâprocesurozvâzannâvektornihzadačkombínatornoíoptimízacíízaumovneviznačenostítariziku AT semenovvv rasparallelivanieprocessarešeniâvektornyhzadačkombinatornoioptimizaciipriusloviâhneopredelennostiiriska AT semenovanv rasparallelivanieprocessarešeniâvektornyhzadačkombinatornoioptimizaciipriusloviâhneopredelennostiiriska AT semenovvv parallelizingthesolutionprocessofvectorcombinatorialproblemsunderuncertaintyandriskconditions AT semenovanv parallelizingthesolutionprocessofvectorcombinatorialproblemsunderuncertaintyandriskconditions |