Алгоритм знаходження двоїстої оцінки для квадратичної екстремальної задачі
Дано опис алгоритму знаходження двоїстої оцінки глобального екстремуму квадратичної екстремальної задачі, що базується на r-алгоритмі з адаптивним регулюванням кроку. Дано описание алгоритма нахождения двойственной оценки глобального экстремума квадратичной экстремальной задачи, базирующийся на r-ал...
Gespeichert in:
| Veröffentlicht in: | Компьютерная математика |
|---|---|
| Datum: | 2018 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/161893 |
| 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: | Алгоритм знаходження двоїстої оцінки для квадратичної екстремальної задачі / О.А. Березовський // Компьютерная математика. — 2018. — № 2. — С. 129-134. — Бібліогр.: 7 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-161893 |
|---|---|
| record_format |
dspace |
| spelling |
Березовський, О.А. 2019-12-25T19:35:55Z 2019-12-25T19:35:55Z 2018 Алгоритм знаходження двоїстої оцінки для квадратичної екстремальної задачі / О.А. Березовський // Компьютерная математика. — 2018. — № 2. — С. 129-134. — Бібліогр.: 7 назв. — укр. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/161893 519.85 Дано опис алгоритму знаходження двоїстої оцінки глобального екстремуму квадратичної екстремальної задачі, що базується на r-алгоритмі з адаптивним регулюванням кроку. Дано описание алгоритма нахождения двойственной оценки глобального экстремума квадратичной экстремальной задачи, базирующийся на r-алгоритме с адаптивной регулировкой шага. We describe the algorithm for finding a dual bound of the global extremum of a quadratic extremal problem based on the r-algorithm with adaptive step regulation. uk Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации Алгоритм знаходження двоїстої оцінки для квадратичної екстремальної задачі Алгоритм нахождения двойственной оценки для квадратичной экстремальной задачи Algorithm to find a dual bound in quadratic extremal problem Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Алгоритм знаходження двоїстої оцінки для квадратичної екстремальної задачі |
| spellingShingle |
Алгоритм знаходження двоїстої оцінки для квадратичної екстремальної задачі Березовський, О.А. Теория и методы оптимизации |
| title_short |
Алгоритм знаходження двоїстої оцінки для квадратичної екстремальної задачі |
| title_full |
Алгоритм знаходження двоїстої оцінки для квадратичної екстремальної задачі |
| title_fullStr |
Алгоритм знаходження двоїстої оцінки для квадратичної екстремальної задачі |
| title_full_unstemmed |
Алгоритм знаходження двоїстої оцінки для квадратичної екстремальної задачі |
| title_sort |
алгоритм знаходження двоїстої оцінки для квадратичної екстремальної задачі |
| author |
Березовський, О.А. |
| author_facet |
Березовський, О.А. |
| topic |
Теория и методы оптимизации |
| topic_facet |
Теория и методы оптимизации |
| publishDate |
2018 |
| language |
Ukrainian |
| container_title |
Компьютерная математика |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Алгоритм нахождения двойственной оценки для квадратичной экстремальной задачи Algorithm to find a dual bound in quadratic extremal problem |
| description |
Дано опис алгоритму знаходження двоїстої оцінки глобального екстремуму квадратичної екстремальної задачі, що базується на r-алгоритмі з адаптивним регулюванням кроку.
Дано описание алгоритма нахождения двойственной оценки глобального экстремума квадратичной экстремальной задачи, базирующийся на r-алгоритме с адаптивной регулировкой шага.
We describe the algorithm for finding a dual bound of the global extremum of a quadratic extremal problem based on the r-algorithm with adaptive step regulation.
|
| issn |
2616-938Х |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/161893 |
| citation_txt |
Алгоритм знаходження двоїстої оцінки для квадратичної екстремальної задачі / О.А. Березовський // Компьютерная математика. — 2018. — № 2. — С. 129-134. — Бібліогр.: 7 назв. — укр. |
| work_keys_str_mv |
AT berezovsʹkiioa algoritmznahodžennâdvoístoíocínkidlâkvadratičnoíekstremalʹnoízadačí AT berezovsʹkiioa algoritmnahoždeniâdvoistvennoiocenkidlâkvadratičnoiékstremalʹnoizadači AT berezovsʹkiioa algorithmtofindadualboundinquadraticextremalproblem |
| first_indexed |
2025-11-25T22:57:33Z |
| last_indexed |
2025-11-25T22:57:33Z |
| _version_ |
1850576459989516288 |
| fulltext |
ISSN 2616-938X. Компьютерная математика. 2018, № 2 129
Теория и методы
оптимизации
Дано опис алгоритму знаходжен-
ня двоїстої оцінки глобального
екстремуму квадратичної екстре-
мальної задачі, що базується на
r-алгоритмі з адаптивним регу-
люванням кроку.
О.А. Березовський, 2018
УДК 519.85
О.А. БЕРЕЗОВСЬКИЙ
АЛГОРИТМ ЗНАХОДЖЕННЯ ДВОЇСТОЇ
ОЦІНКИ ДЛЯ КВАДРАТИЧНОЇ
ЕКСТРЕМАЛЬНОЇ ЗАДАЧІ
Під квадратичною екстремальною задачею
розуміють задачу математичного програму-
вання, у якої цільова функція та всі функції
обмежень квадратичні:
*
0sup ( )
nx T R
f f x
, (1)
де
{ : ( ) 0, , ( ) 0, }LQ EQ
i iT x f x i I f x i I ,
( ) T T
i i i if x x A x b x c , {0} LQ EQi I I –
квадратичні функції з симетричними
n n -матрицями iA , векторами n
ib R і кон-
стантами 1
ic R ; 1 | |LQm I і 2 | |EQm I –
кількість обмежень у вигляді нерівностей та
рівностей відповідно, 1 2m m m . В загаль-
ному випадку квадратична екстремальна
задача належить до класу NP-складних задач.
У зв’язку з цим виникає необхідність
у різних прийомах для дослідження задач
цього класу, серед яких найбільш пошире-
ним є знаходження оцінок глобального
екстремуму шляхом використання різних
опуклих релаксацій: лагранжеві релаксації,
SDP-релаксації, SOCP-релаксації, LP-релак-
сації та інші. В цій роботі розглядається
двоїста оцінка * [1] для квадратичної задачі
(1), яка отримується в результаті лагранжевої
релаксації цієї задачі за усіма обмеженнями:
* *
,
inf ( )
u V
u U
u f
, (2)
де
( ) sup ( , )
nx R
u L u x
, (3)
О.А. БЕРЕЗОВСЬКИЙ
ISSN 2616-938X. Компьютерная математика. 2018, № 2130
( , ) ( ) ( ) ( )T TL u x x A u x b u x c u – функція Лагранжа для задачі (1), в якій
0
1
( )
m
i i
i
A u A u A
, 0
1
( )
m
i i
i
b u b u b
, 0
1
( )
m
i i
i
c u c u c
; { : 0, }LQ
iU u u i I ;
: ( ) 0V u A u ( { : ( ) 0}V u A u ) – множина точок двоїстих змінних u , при
яких гесіан функції Лагранжа недодатньо (від’ємно) визначений.
При u V внутрішня задача (3) – безумовна задача максимізації строго
ввігнутої квадратичної функції, розв'язок якої ( ) arg max ( , )
x
x u L u x однозначно
визначається з невиродженої системи рівностей ' ( , ) 2 ( ) ( ) ( ) 0xL u x A u x u b u ,
наприклад, використовуючи розкладання Холецького для матриці ( )A u
(враховуючи, що вона – симетрична і додатно визначена). Тобто в будь-якій
точці u V двоїста функція має обмежене значення ( ) ( , ( ))u L u x u ,
а її градієнт дорівнює '
1 2( ( )), ( ( )), , ( ( )) T
u mf x u f x u f x u (в усіх внутрішніх
точках області недодатної визначеності матриці ( )A u функція ( )u
диференційовна).
Зовнішня задача (2) визначення двоїстої оцінки – задача мінімізації опуклої
двоїстої функції ( )u на опуклих обмеженнях двох типів:
a) : 0, LQ
iU u u i I – недодатність двоїстих змінних, що відповідають
обмеженням-нерівностям;
b) : ( ) 0V u A u – недодатна визначеність матриці ( )A u функції
Лагранжа, що можна замінити, наприклад, еквівалентною умовою недодатності
її максимального власного числа max ( ( )) 0A u (функція max ( ( ))A u – недифе-
ренційовна та опукла).
Для розв’язання задачі (2) можна використовувати будь-який з чисельних
методів розв’язання задачі негладкої опуклої оптимізації. Описаний у даній
роботі алгоритм знаходження двоїстої оцінки для задачі квадратичної оптиміза-
ції базується на застосуванні для цих цілей r-алгоритму з адаптивним регулю-
ванням кроку [1 – 4], який має швидку практичну збіжність і добре протистоїть
яружності цільової функції, що доведено майже п’ятидесятилітнім досвідом
його використання для розв’язання різних практичних оптимізаційних задач.
r-алгоритм вже неодноразово використовувався як базовий у програмних реалі-
заціях різних алгоритмів для знаходження двоїстої оцінки [1, 3, 5 – 7].
Різноманітність цих варіантів пояснюється тим, що зробивши вибір стосовно
базового алгоритму розв’язання задачі (2) опуклого програмування, різні
алгоритми можна отримувати в залежності від способів перевірки й ураху-
вання обмежень а) і b) цієї задачі. Наприклад, в [3] обмеження b) врахо-
вувалися за допомогою штрафної функції
max
( ), ( ) 0
( )
( ( )),
u if A u
u
A u else
,
АЛГОРИТМ ЗНАХОДЖЕННЯ ДВОЇСТОЇ ОЦІНКИ ДЛЯ КВАДРАТИЧНОЇ ЕКСТРЕМАЛЬНОЇ ЗАДАЧІ
ISSN 2616-938X. Компьютерная математика. 2018, № 2 131
а обмеження в) – за рахунок заміни двоїстих змінних у функції Лагранжа ( , )L x u
на їхній модуль із знаком мінус – ( , )L x u . В роботі [7] запропоновано підхід,
що базується на зведенні задачі (1) загального вигляду до квадратичної
однорідної (без лінійних членів) задачі (доведено, що двоїста оцінка при цьому
не змінюється), знаходження двоїстої оцінки якої зводиться до безумовної задачі
мінімізації опуклої недиференційовної функції за допомогою точної штрафної
функції у вигляді функції максимуму. Обидва наведені приклади вимагають
досить трудомістких обчислень максимальних власних чисел та відповідних їм
власних векторів матриці ( )A u , що навіть при середніх розмірностях ( 410n )
задачі стає певною проблемою. Далі наведемо один з варіантів, що не потребує
цих обчислень – обмеження задачі (2) (як типу а), так і b)) враховуються за
рахунок дроблення кроку r-алгоритму таким чином, щоб ітераційний процес не
виходив за межі допустимої області. Цей алгоритм можна розглядати як
узагальнення на загальний випадок задач квадратичної оптимізації алгоритму,
що використовувався для дослідження двоїстої оцінки у задачі про максимальну
зважену стійку множину графа [1, 5].
В роботі [1] зазначалося, що функція ( ) max{0, }
LQ
i
i I
u S u
(в цьому варіанті
алгоритму обмеження а) враховувалися шляхом введення негладкого штрафу; S
– досить велике додатнє число) як би «самоекранується» від виходу за межі
області V при використанні алгоритмів монотонного спуску, тобто відпадає
необхідність у застосуванні бар’єрних штрафних функцій для урахування
обмеження типу в). Таким чином, вихід за межі області V (обмеження b))
можна контролювати довільною процедурою перевірки матриці ( )A u
на від’ємну визначеність: якщо на даному кроці має місце вихід за межі області
,V то шаг дробиться до тих пір, поки не буде отримано допустиме значення.
Покажемо, що така ж процедура може буди застосована і для урахування
обмежень а). Насправді, умова : 0, LQ
iu U u u i I певною мірою
еквівалентна умові від’ємної визначеності матриці ( )A u в задачі (2).
За допомогою допоміжних змінних задачу (1) можна звести до еквівалентної
квадратичної задачі виключно з обмеженнями-рівностями
1
*
0sup ( )
n mx T R
f f x
, (4)
де
2{ : ( ) 0, , ( ) 0, }LQ EQ
i i iT x f x y i I f x i I , 1n mx
x R
y
, nx R , 1my R .
Причому двоїсті оцінки задачі (1) та (4), як доведено в [7], збігаються. Для задачі
(4) функція Лагранжа
О.А. БЕРЕЗОВСЬКИЙ
ISSN 2616-938X. Компьютерная математика. 2018, № 2132
1 2 1
2
0
1 1 1
( , ) ( ) ( ) ( ) ( , )
m m m
i i i i i i
i i i
L u x f x u f x u f x L u x u y
,
відрізняється від функції Лагранжа ( , )L x u для задачі (1) додатковим доданком,
що залежить від допоміжних змінних. При цьому у визначенні двоїстої оцінки
для задачі (4) будуть вже відсутні обмеження ,u U які автоматично
випливають з умови недодатньої визначеності гессіана ( )A u функції ( , )L u x
1
1 1
( ) 0
( ) 0
0 ( , 1, )
n m
T
m n
A u
A u
diag u i m
,
де ( )A u – гессіан функції Лагранжа для задачі (1). Власні вектори матриці ( )A u
( ( ))
( ( ))
0
i
i
A u
A u
, 1,i n , ( ( ))n i n iA u e , 11,i m , а власні числа
( ( )) ( ( ))i iA u A u , 1,i n , ( ( ))i iA u u , 11,i m , де 0 – нульовий вектор
відповідної розмірності (у даному випадку його розмірність 1m ) , ie – нульовий
вектор відповідної розмірності (у даному випадку 1m m ), i -а компонента якого
дорівнює 1.
Таким чином при знаходженні двоїстої оцінки в обох випадках (задачі (1) та
(4)) маємо однакові зовнішні задачі, за вийнятком, що для задачі (4) обмеження
недодатності змінних заміщується обмеженням на недодатність власних чисел
розширеної матриці. Тобто можна говорити про рівноправність обмежень обох
типів а) і b), яка дозволяє застосовувати одні й ті ж прийоми для їх урахування.
Підсумовуючи, можна запропонувати такий алгоритм обчислення двоїстої
оцінки для квадратичної екстремальної задачі загального вигляду (1):
1) для мінімізації функції ( )u (задача (2)) використовується r-алгоритм
з адаптивним регулюванням кроку;
2) початкова точка 0
mu R вибирається таким чином, щоб виконувалися
умови 0( ) 0A u та 0 .u U Таку точку можна визначити в багатьох випадках
просто проаналізувавши початкову задачу (1). Наприклад, якщо всі змінні задачі
бінарні (0,1) та/або ( 1,1) , що в квадратичній постановці враховується завдяки
обмеженням 2 0i ix x та/або 2 1 0ix відповідно, то при досить великих
від’ємних значеннях двоїстих змінних, які відповідають цим обмеженням,
та нульових значеннях інших двоїстих змінних завжди можна отримати від’ємно
визначену матрицю ( )A u у функції Лагранжа. Але у загальному випадку для її
знаходження необхідно розв’язати допоміжну задачу, наприклад,
*
max maxmin ( ( )).
u U
A u
АЛГОРИТМ ЗНАХОДЖЕННЯ ДВОЇСТОЇ ОЦІНКИ ДЛЯ КВАДРАТИЧНОЇ ЕКСТРЕМАЛЬНОЇ ЗАДАЧІ
ISSN 2616-938X. Компьютерная математика. 2018, № 2 133
Звернемо увагу на те, що немає необхідності знаходити *
max – досить
у результаті ітераційного процесу розв’язання даної задачі опуклої оптимізації
отримати деякий вектор ku U , при якому max ( ( )) 0.kA u Зазначимо, що це
не єдиний спосіб знайти допустиму точку 0u . Наприклад, навіть розв’язання
запропонованої задачі можна замінити на знаходження локального мінімуму
задачі безумовної оптимізації
*
max maxmin ( ( )),
mu R
A u
яка є багатоекстремальною, але всі значення її локальних мінімумів збігаються;
3) для урахування як обмежень а), так і обмежень б), використовується одна
й та ж процедура. Після кожного кроку r-алгоритму у визначеному напрямі
перевіряємо обмеження 0, LQ
iu i I , якщо на даному кроці має місце вихід
за межі області U , то крок дробиться до тих пір, поки не буде отримано
допустиме значення. Після отримання u U переходимо до перевірки обме-
ження ( ) 0A u (використовуємо процедуру розкладання матриці ( )kA u
методом Холецького), якщо на даному кроці ( )kA u не є додатно визначеною
матрицею, то крок дробиться до тих пір, поки не буде отримано допустиме
значення;
4) для обчислення градієнта і значення двоїстої функції ( )u в отриманій
допустимій точці ku спершу знаходиться ( )kx u (розв'язок задачі (3)) з неви-
родженої системи ' ( , ) 2 ( ) ( ) ( ) 0xL u x A u x u b u , використовуючи результати
факторизації матриці ( ) ( ) ( )T
k k kA u M u M u методом Холецького, що отримані
при перевірці обмеження б). Для цього розв’язується система лінійних рівнянь
2 ( ) ( ) ( ) 0T
k k kM u M u x b u щодо змінних x методом прогонки:
( ) ( )T
k kM u z b u ,
( ) ( )k kM u x u z .
Визначивши ( )kx u обчислюємо
( ) ( , ( )) ( ) ( ) ( ) ( ) ( ) ( ),T T
k k k k k k k k ku L u x u x u A u x u b u x u c u
1 1 2( ( )), ( ( )), , ( ( )) T
k k k m kg f x u f x u f x u .
На завершення слід зауважити, що регулювання кроку, яке використову-
ється в описаному алгоритмі, може призводити до «прилипання» до границі
допустимої області. В цьому випадку можна, наприклад, при малих значеннях
кроку збурювати значення поточної точки та збільшувати крок.
О.А. БЕРЕЗОВСЬКИЙ
ISSN 2616-938X. Компьютерная математика. 2018, № 2134
О.А. Березовский
АЛГОРИТМ НАХОЖДЕНИЯ ДВОЙСТВЕННОЙ ОЦЕНКИ ДЛЯ КВАДРАТИЧНОЙ
ЭКСТРЕМАЛЬНОЙ ЗАДАЧИ
Дано описание алгоритма нахождения двойственной оценки глобального экстремума квадра-
тичной экстремальной задачи, базирующийся на r-алгоритме с адаптивной регулировкой
шага.
O.A. Berezovskyi
ALGORITHM TO FIND A DUAL BOUND IN QUADRATIC EXTREMAL PROBLEM
We describe the algorithm for finding a dual bound of the global extremum
of a quadratic extremal problem based on the r-algorithm with adaptive step regulation.
Список літератури
1. Шор Н.З., Стеценко С.И. Квадратичные экстремальные задачи и недифференцируемая
оптимизация. К.: Наук. думка, 1989. 208 с.
2. Шор Н.З., Журбенко Н.Г. Метод минимизации, использующий операцию растяжения
пространства в направлении разности двух последовательных градиентов. Кибернетика.
1971. № 3. C. 51 – 59.
3. Шор Н.З., Стецюк П.И. Использование модификации r-алгоритма для нахождения
глобального минимума полиномиальных функций. Кибернетика и системный анализ.
1997. № 4. С. 28 – 49.
4. Стецюк П.И. Субградиентные методы ralgb5 и ralgb4 для минимизации овражных
выпуклых функций. Вычислительные технологии. 2017. Т. 22, № 2. С. 127 – 149.
5. Shor N.Z., Stetsenko S.I. Quadratic Boolean problems and Lovasz bounds. 12th IFIP Conf. on
System Modeling and Optimization, Abstracts. Budapest, 1985. Р. 302 – 304.
6. Шор Н.З., Березовский О.А. Новые алгоритмы решения задачи о максимальном взвешен-
ном разрезе графа. Кибернетика и системный анализ. 1995. № 2. С. 100 – 106.
7. Березовский О.А., Стецюк П.И. Об одном способе нахождения двойственных квадра-
тичных оценок Шора. Кибернетика и системный анализ. 2008. № 2. С. 89 – 99.
Одержано 19.10.2018
Про автора:
Березовський Олег Анатолійович,
кандидат фізико-математичних наук,
старший науковий співробітник
Інституту кібернетики імені В.М. Глушкова НАН України.
E-mail: o.a.berezovskyi@gmail.com
|