Використання напіввизначеної оптимізації для моделювання складних систем
Розглядається напіввизначена релаксація для загальних задач квадратичного програмування та використовується новий узагальнений симплекс-метод для розв’язку цієї релаксації. Метод реалізований програмно і проведені численні експерименти, які свідчать, що напіввизначена релаксація є ефективною....
Gespeichert in:
| Datum: | 2012 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2012
|
| Schriftenreihe: | Математичні машини і системи |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/59996 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Використання напіввизначеної оптимізації для моделювання складних систем / А.І. Косолап ,А.С. Перетятько // Мат. машини і системи. — 2012. — № 1. — С. 174-179. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-59996 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-599962025-02-09T22:45:46Z Використання напіввизначеної оптимізації для моделювання складних систем Косолап, А.І. Перетятько, А.С. Моделювання і управління Розглядається напіввизначена релаксація для загальних задач квадратичного програмування та використовується новий узагальнений симплекс-метод для розв’язку цієї релаксації. Метод реалізований програмно і проведені численні експерименти, які свідчать, що напіввизначена релаксація є ефективною. Рассматривается полуопределенная релаксация для общих задач квадратического программирования и используется новый обобщенный симплекс-метод для решения этой релаксации. Метод реализован программно и проведены многочисленные эксперименты, которые свидетельствуют об эффективности полуопределенной релаксации. Semidefinite relaxation of general quadratic problems is regarded and a new generalized simplex-method for solving this relaxation is used. The method is implemented on practice and numerous experiments was performed. These experiments show that the semidefinite relaxation is effective. 2012 Article Використання напіввизначеної оптимізації для моделювання складних систем / А.І. Косолап ,А.С. Перетятько // Мат. машини і системи. — 2012. — № 1. — С. 174-179. — Бібліогр.: 7 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/59996 519.853 uk Математичні машини і системи application/pdf Інститут проблем математичних машин і систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Моделювання і управління Моделювання і управління |
| spellingShingle |
Моделювання і управління Моделювання і управління Косолап, А.І. Перетятько, А.С. Використання напіввизначеної оптимізації для моделювання складних систем Математичні машини і системи |
| description |
Розглядається напіввизначена релаксація для загальних задач квадратичного програмування та використовується новий узагальнений симплекс-метод для розв’язку цієї релаксації. Метод реалізований програмно і проведені численні експерименти, які свідчать, що напіввизначена релаксація є ефективною. |
| format |
Article |
| author |
Косолап, А.І. Перетятько, А.С. |
| author_facet |
Косолап, А.І. Перетятько, А.С. |
| author_sort |
Косолап, А.І. |
| title |
Використання напіввизначеної оптимізації для моделювання складних систем |
| title_short |
Використання напіввизначеної оптимізації для моделювання складних систем |
| title_full |
Використання напіввизначеної оптимізації для моделювання складних систем |
| title_fullStr |
Використання напіввизначеної оптимізації для моделювання складних систем |
| title_full_unstemmed |
Використання напіввизначеної оптимізації для моделювання складних систем |
| title_sort |
використання напіввизначеної оптимізації для моделювання складних систем |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2012 |
| topic_facet |
Моделювання і управління |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/59996 |
| citation_txt |
Використання напіввизначеної оптимізації для моделювання складних систем / А.І. Косолап ,А.С. Перетятько // Мат. машини і системи. — 2012. — № 1. — С. 174-179. — Бібліогр.: 7 назв. — рос. |
| series |
Математичні машини і системи |
| work_keys_str_mv |
AT kosolapaí vikoristannânapívviznačenoíoptimízacíídlâmodelûvannâskladnihsistem AT peretâtʹkoas vikoristannânapívviznačenoíoptimízacíídlâmodelûvannâskladnihsistem |
| first_indexed |
2025-12-01T12:42:43Z |
| last_indexed |
2025-12-01T12:42:43Z |
| _version_ |
1850309832049950720 |
| fulltext |
174 © Косолап А.І., Перетятько А.С., 2012
ISSN 1028-9763. Математичні машини і системи, 2012, № 1
УДК 519.853
А.І. КОСОЛАП, А.С. ПЕРЕТЯТЬКО
ВИКОРИСТАННЯ НАПІВВИЗНАЧЕНОЇ ОПТИМІЗАЦІЇ ДЛЯ МОДЕЛЮВАННЯ
СКЛАДНИХ СИСТЕМ
Анотація. Розглядається напіввизначена релаксація для загальних задач квадратичного програму-
вання та використовується новий узагальнений симплекс-метод для розв’язку цієї релаксації. Ме-
тод реалізований програмно і проведені численні експерименти, які свідчать, що напіввизначена
релаксація є ефективною.
Ключові слова: напіввизначена релаксація, квадратичне програмування, узагальнений симплекс-
метод, напіввизначена оптимізація.
Аннотация. Рассматривается полуопределенная релаксация для общих задач квадратического
программирования и используется новый обобщенный симплекс-метод для решения этой релакса-
ции. Метод реализован программно и проведены многочисленные эксперименты, которые свиде-
тельствуют об эффективности полуопределенной релаксации.
Ключевые слова: полуопределенная релаксация, квадратическое программирование, обобщенный
симплекс-метод, полуопределенная оптимизация.
Abstract. Semidefinite relaxation of general quadratic problems is regarded and a new generalized
simplex-method for solving this relaxation is used. The method is implemented on practice and numerous
experiments was performed. These experiments show that the semidefinite relaxation is effective.
Keywords: semidefinite relaxation, quadratic programming, generalized simplex-method, semidefinite
optimization.
1. Вступ
Як показали М. Месарович і Я. Такахара [1], довільна система може бути зведена до ціле-
направленої системи. Такі системи є оптимізаційними. Головною задачею оптимізації є
визначення оптимальних значень параметрів систем, при яких критерій якості системи
приймає найбільше або найменше значення. Оптимізаційна система складна, якщо вона
має безліч екстремальних значень параметрів. Знаходження значень цих параметрів, при
яких критерій якості системи приймає найбільше або найменше значення, є, як правило,
NP-складною проблемою, для якої не існує ефективних методів знаходження оптимальних
значень параметрів системи. В таких випадках складні системи зводяться до P-складних за
допомогою послаблення (релаксації) умов системи.
Велика кількість складних систем може бути описана за допомогою загальних ква-
дратичних функцій. Це комбінаторні задачі, задачі теорії графів, комп’ютерної геометрії та
багато інших. Використовуючи напіввизначену релаксацію, загальні квадратичні задачі
зводяться до напіввизначеної оптимізації. Тому в останні роки значна кількість робіт прис-
вячена напіввизначеній оптимізації: сучасному та ефективному напряму досліджень при
моделюванні та оптимізації складних систем. Існує багато причин для використання напів-
визначеної оптимізації (SDP). По-перше, додатно напіввизначені (або визначені) обмежен-
ня виникають у низці важливих практичних задач [2, 3]. По-друге, багато задач опуклої
оптимізації, наприклад, лінійне програмування або опукле квадратичне програмування,
можуть бути перетворені до задачі SDP. Таким чином, напіввизначене програмування
пропонує комплексний підхід для вивчення властивостей та виведення алгоритмів для ши-
рокого кола задач опуклої оптимізації. І, що найголовніше, задачі SDP можуть бути ефек-
тивно розв’язані чисельно.
Велика кількість досліджень присвячена теоретичному і практичному застосуванню
SDP-релаксації для складних задач оптимізації. Значне число комбінаторних задач NP-
ISSN 1028-9763. Математичні машини і системи, 2012, № 1 175
складності розв'язуються шляхом напіввизначеної релаксації [4]. У багатьох випадках оп-
тимальний розв’язок SDP-релаксації може бути перетворено до допустимого розв’язку
початкової задачі. Напіввизначена релаксація використовує перетворення квадратичного
виразу AxxT до скалярного добутку матриць TAxx або XA ⋅ , де Х – напіввизначена мат-
риця рангу одиниця. Таким чином, квадратичний вираз зводиться до лінійного.
Метою даної роботи є дослідження напіввизначеної релаксації для розв’язку квад-
ратичних задач, а також перевірка доцільності використання нового узагальненого симп-
лекс-методу для отриманої в результаті релаксації задачі напіввизначеної оптимізації.
2. Постановка задачі
Задача мінімізації квадратичної функції при квадратичних обмеженнях має ефективний
розв’язок, якщо цільова функція і обмеження – опуклі функції. Якщо ж принаймні одна з
функцій не є опуклою, то така задача стає достатньо складною і в загальному випадку ба-
гатоекстремальною. Загальній задачі квадратичної оптимізації останнім часом надається
значна увага [2, 3, 5]. Відмітимо, що комбінаторні задачі та багато задач теорії графів до-
сить легко звести до квадратичних задач. Так, якщо змінні системи ix приймають тільки
два значення: 0 і 1, то це рівносильно квадратичній умові 02 =− ii xx .
Розглянемо таку загальну задачу квадратичної оптимізації (QP):
{ } ..., ,1 | min mi,cxbxAxxdQxx i
T
ii
TTT =≤++ , (1)
де Q – симетрична матриця ( nn× ), iA – симетричні матриці )( nn× , cdb ,, – вектори ро-
змірності xm, – вектор змінних розмірності n .
У загальному випадку для розв’язання цієї задачі можуть використовуватися мето-
ди для розв’язання задач нелінійної оптимізації. Але вони не дають бажаної точності
розв’язку. Останнім часом наукова спільнота звернула увагу на напіввизначену релаксацію
для цього класу задач [3–5]. Напіввизначена релаксація розглядається як перспективний
метод не тільки для квадратичного програмування, а й для широкого класу неопуклих за-
дач оптимізації.
Використаємо напіввизначену релаксацію [6] для розв’язку квадратичної задачі (1).
Введемо матрицю змінних Y , яка може бути виражена через будь-який вектор x таким
чином [3]:
=
=
T
TT
xxx
x
xx
Y
111
. (2)
Таким чином, Y є симетричною та додатно напіввизначеною матрицею згідно з
правилом Шура [3]. Використовуючи матрицю Y , перепишемо цільову функцію та функ-
ції обмежень задачі (1):
Y
Q
d
d
xxx
x
Q
d
d
xdQxx
T
T
T
T
TT ⋅
=
⋅
=+
2
2
0
1
2
2
0
,
Y
A
b
b
c
xxx
x
A
b
b
c
cxbxAx
i
i
T
i
i
T
T
i
i
T
i
i
i
T
ii
T ⋅
−
=
⋅
−
=−+
2
2
1
2
2
.
176 ISSN 1028-9763. Математичні машини і системи, 2012, № 1
Рис. 1. Задача має 4 локальних мінімуми
Введемо позначення:
=
Q
d
d
Q
T
2
2
0~
,
=
i
i
T
i
i
i
A
b
b
-c
А
2
2
~
.
Тоді маємо таку задачу напіввизначеної оптимізації для задачі квадратичного про-
грамування (1):
{ }0 ,1 ,0
~
|
~
min fY,...,m iYAYQ i =≤⋅⋅ . (3)
Відмітимо, що задача (3) є опуклою незалежно від опуклості/ввігнутості задачі (1),
та її розв’язок співпадає з розв’язком задачі (1), якщо матриця Y має ранг одиниця [5].
Якщо ранг матриці Y більше одиниці, то буде отримано нижню оцінку розв’язку задачі
(1).
3. Методи розв’язку задач SDP
Для розв’язку задачі (3) використовують метод внутрішньої точки [2]. Він є популярним
серед наукової спільноти та реалізований у сучасному програмному забезпеченні для
розв’язку задач напіввизначеної оптимізації (CSDP, SP, SDPT3 та ін.). Але цей метод сут-
тєво залежить від вибору початкової точки й дозволяє отримати тільки наближений
розв’язок. Крім того, метод внутрішньої точки потребує виконання умови Слейтера (існує
допустимий розв’язок 0fX для задачи (1)), яка виконується не завжди. Більш ефективним
є новий узагальнений симплекс-метод [7], який шукає розв’язок задачі напіввизначеної
оптимізації у вигляді
∑= jjYaY ,
де jY – матриці рангу одиниця, число доданків у сумі більше розмірності Y та 0≥α . Ма-
триці jY є твірними конусу напіввизначених матриць і утворюють його початкову апрок-
симацію.
Тоді задача напіввизначеної оптимізації (3) зводиться до задачі лінійного програму-
вання:
{ }0 1 0,
~
|
~
min ≥=≤⋅⋅ ∑∑ α,...,m,iYaAYaQ jjijj . (4)
Алгоритм узагальненого симплекс-методу [7] для задачі (4) на кожній ітерації зна-
ходить нову матрицю kY рангу одиниця та kα , що зменшує значення цільової функції за-
дачі (4). Таким чином, на кожній ітерації уза-
гальненого симплекс-методу розв’я-зується
задача лінійного програмування та перевіря-
ється напіввизначеність матриці
,1∑ −⋅−= j
T
kk ABxxCCS
де B − базисна матриця оптимального
розв’язку задачі (4). Якщо такої матриці kY
не існує (це визначається перевіркою напів-
визначеності відповідної матриці, побудова-
ної по матрицях задачі (3)), то знайдений
ISSN 1028-9763. Математичні машини і системи, 2012, № 1 177
розв’язок задачі (3). Тоді визначаємо ранг матриці Y . Коли він дорівнює одиниці, одержу-
ємо точний розв’язок задачі (1), а якщо ранг матриці Y більше одиниці, то отримаємо ни-
жню границю розв’язку задачі (1). Якщо в задачі (4) знайти точки перетину осей коорди-
нат з границею допустимого многогранника і серед цих точок визначити точку з най-
меншим значенням цільової функції задачі (4), то буде отримана верхня границя розв’язку
задачі (1).
4. Результати чисельних експериментів
Узагальнений симплекс-метод для розв’язку задачі загальної квадратичної оптимізації був
реалізований програмно засобами VBA для Excel та проведені значні чисельні експериме-
нти.
На рис. 1 показана допустима множина задачі квадратичної оптимізації:
}042282 ,01424648|||min{|| 2121
2
2
2
12121
2
2
2
1
2 ≤+−−−−−≤−−+−+− xxxxxxxxxxxxx .
Ця множина є незв’язною і містить 4 локальних мінімуми. Після перетворення цієї
задачі до напіввизначеної була одержана така матриця
1 0,41399 2,15917
0,41399 0,17139 0,893883
2,15917 0,89388 4,662041
ранг якої дорівнює одиниці. Тому напіввизначена релаксація є точною, знайдено точку
глобального мінімуму даної квадратичної задачі x*=(0,41399; 2,15917).
Розглянемо приклад загальної квадратичної задачі з трьома обмеженнями (дані
представлені в табл. 1.)
Таблиця 1. Вхідні дані
Q
~
=
0 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 1
1
~
A =
1 -2 0 0 -2 -0,5 -0,5 0
-2 8 -1 3 4 2 1
0 -1 -4 -2 1 2 -3
0 3 -2 -1 2 -1 1
-2 4 1 2 8 1 -1
-0,5 2 2 -1 1 -3 2
-0,5 1 -3 1 -1 2 -8
2
~
A =
10 -2 0 -3 1 -0,5 -2 0
-2 -10 -1 1 4 2 1
0 -1 -6 -2 1 3 -3
-3 1 -2 6 2 -1 1
1 4 1 2 -6 1 -1
-0,5 2 3 -1 1 7 2
-2 1 -3 1 -1 2 8
3
~
A =
-20 -2 0 0 -2 -0,5 0,5 0
-2 -12 -1 3 4 2 1
0 -1 -10 -2 1 2 -3
0 3 -2 2 2 -1 1
178 ISSN 1028-9763. Математичні машини і системи, 2012, № 1
Продовж. табл. 1
-2 4 1 2 8 1 2
-0,5 2 2 -1 1 -10 2
0,5 1 -3 1 2 2 8
Результати розв’язку представлені в табл. 2.
Таблиця 2. Матриця розв’язку
Y=
1 0,508 0,3544 0,151 1E-11 7E-08 0,159
0,5079 0,372 0,2591 0,085 -0,08 -0,026 0,0872
0,3544 0,259 0,1806 0,059 -0,06 -0,018 0,0608
0,1515 0,085 0,0595 0,024 -0,01 -0,002 0,0246
1E-11 -0,08 -0,056 -0,01 0,056 0,018 -0,004
7E-08 -0,026 -0,018 -0 0,018 0,006 -0,001
0,159 0,087 0,0608 0,025 -0 -0,001 0,0257
Ранг матриці розв’язку (табл. 2) дорівнює 2, тому можна зробити висновок, що на-
ми була одержана нижня оцінка глобального мінімуму 0,664244, яка незначно відрізняєть-
ся від точного розв’язку 0,6724962.
У табл. 3 наведені результати чисельних експериментів по розв’язку загальних ква-
дратичних задач різної розмірності.
Таблиця 3. Результати чисельних експериментів
№п/п n ранг fSDP fmin
1 6 2 0,53 0,67017
2 6 3 0,769978 1,470926
3 10 2 0,453065 0,45308
4 10 3 0,375502 0,575855
5 10 3 9,883102 12,34698
6 10 3 0,375502 0,575855
7 12 2 1,38959 1,539229
8 15 2 0,6795 0,874392
Як бачимо, ранг матриці розв’язку задач незначно відрізняється від одиниці. Ці екс-
перименти показують, що напіввизначена релаксація може бути використана для наближе-
ного розв’язку загальних квадратичних задач.
5. Висновки
У даній роботі розв’язувалася загальна квадратична задача шляхом напіввизначеної релак-
сації, яка зводить початкову задачу (в загальному випадку – неопуклу) до задачі напіввиз-
наченого програмування, що завжди є опуклою, а, отже, й ефективно вирішуваною. Було
проведено значну кількість чисельних експериментів, які підтверджують ефективність об-
раного методу. Перспективу цього напрямку дослідження автори вбачають у використанні
отриманих нижніх та верхніх оцінок для пошуку оптимального розв’язку початкової квад-
ратичної задачі.
СПИСОК ЛІТЕРАТУРИ
1. Месарович М. Общая теория систем: математические основы / М. Месарович, Я. Такахара. – М.:
Мир, 1978. – 312 с.
ISSN 1028-9763. Математичні машини і системи, 2012, № 1 179
2. Freund R.M. Introduction to Semidefinite Programming / Freund R.M. – Massachusett: Massachusetts
Institute of Technology, 2004 – 54 p.
3. Helmberg C. Semidefinite Programming For Combinatorial Optimization / Helmberg C. – Berlin, 2000.
– 150 p.
4. Benson S.J. Parallel Semidefinite programming and combinatorial optimization / S.J. Benson // Parallel
combinatorial optimization. – Wiley-interscience, 2006. – P. 103 – 122.
5. Lasserre J.B. Convergent LMI relaxations for nonconvex quadratic programs / J.B. Lasserre // 39th
IEEE Conference on Decision and Control. – Sydney, 2000. – P. 5041 – 5046.
6. Шор Н.З. Квадратичные оптимизационные задачи / Н.З. Шор // Техническая кибернетика. –
1987. – № 1. – С. 128 – 139.
7. Косолап А.И. Обобщение симплекс-метода для решения задач полуопределенной оптимизации /
А.И. Косолап // Математичне та комп’ютерне моделювання. – 2010. – № 3. – C. 99 – 106.
Стаття надійшла до редакції 10.10.2011
|