Достатня умова точної двоїстої оцінки для сепарабельної квадратичної оптимізаційної задачі: Fìz.-mat. model. ìnf. tehnol. 2021, 32:42-45
The paper considers nonconvex separable quadratic optimization problems subject to inequality constraints. A sufficient condition is given for finding the value and the point of the global extremum of a problem of this type by calculating the Lagrange dual bound. The peculiarity of this condition is...
Збережено в:
| Дата: | 2021 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2021
|
| Теми: | |
| Онлайн доступ: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/157 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
Репозитарії
Physico-mathematical modeling and informational technologies| _version_ | 1867479462071762944 |
|---|---|
| author | Berezovskyi, Oleg |
| author_facet | Berezovskyi, Oleg |
| author_institution_txt_mv | [
{
"author": "Oleg Berezovskyi",
"institution": "Інститут кібернетики імені В.М. Глушкова НАН України, проспект Академіка Глушкова, 40, Київ"
}
] |
| author_sort | Berezovskyi, Oleg |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2021-09-06T07:59:01Z |
| description | The paper considers nonconvex separable quadratic optimization problems subject to inequality constraints. A sufficient condition is given for finding the value and the point of the global extremum of a problem of this type by calculating the Lagrange dual bound. The peculiarity of this condition is that it is easily verified and requires from the Hessian matrix of the Lagrange function only that its region of positive definiteness is not empty. The result obtained for the dual bound also holds for the bound obtained using SDP relaxation.
References
Shor, N. Z., Stetsenko, S. I. (1989). Quadratic extremal problems and nondifferentiable optimization. Naukova Dumka, Kiev.
Berezovskyi, O. A. (2017). Zero duality gap in quadratically constrained quadratic programming. Mathematical and computer modelling. Series: Physical and mathematical sciences, 15, 20-25.
Nesterov, Y., Wolkowicz, H., Ye, Y. (2000). Semidefinite programming relaxations of nonconvex quadratic optimization. Handbook of semidefinite programming, Springer, New York, 361-419. DOI doi.org/10.1007/978-1-4615-4381-7_13
Berezovskyi, O. A. (2016). Exactness criteria for SDP-relaxations of quadratic extremum problems. Cybernetics and Systems Analysis, 52(6), 915-920. DOI doi.org/10.1007/s10559-016-9893-3
|
| doi_str_mv | 10.15407/fmmit2021.32.071 |
| first_indexed | 2026-06-09T01:06:39Z |
| format | Article |
| fulltext | |
| id | oai:ojs2.www.fmmit.lviv.ua:article-157 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:06:39Z |
| publishDate | 2021 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-1572021-09-06T07:59:01Z The sufficient condition to find an exact dual bound in a separable quadratic optimization problem: Fìz.-mat. model. ìnf. tehnol. 2021, 32:42-45 Достатня умова точної двоїстої оцінки для сепарабельної квадратичної оптимізаційної задачі: Fìz.-mat. model. ìnf. tehnol. 2021, 32:42-45 Berezovskyi, Oleg сепарабельна квадратична оптимізаційна задача глобальний екстремум двоїста оцінка додатно визначена матриця нульовий розрив двоїстості separable quadratic optimization problem global extremum dual bound positively defined matrix zero duality gap The paper considers nonconvex separable quadratic optimization problems subject to inequality constraints. A sufficient condition is given for finding the value and the point of the global extremum of a problem of this type by calculating the Lagrange dual bound. The peculiarity of this condition is that it is easily verified and requires from the Hessian matrix of the Lagrange function only that its region of positive definiteness is not empty. The result obtained for the dual bound also holds for the bound obtained using SDP relaxation. References Shor, N. Z., Stetsenko, S. I. (1989). Quadratic extremal problems and nondifferentiable optimization. Naukova Dumka, Kiev. Berezovskyi, O. A. (2017). Zero duality gap in quadratically constrained quadratic programming. Mathematical and computer modelling. Series: Physical and mathematical sciences, 15, 20-25. Nesterov, Y., Wolkowicz, H., Ye, Y. (2000). Semidefinite programming relaxations of nonconvex quadratic optimization. Handbook of semidefinite programming, Springer, New York, 361-419. DOI doi.org/10.1007/978-1-4615-4381-7_13 Berezovskyi, O. A. (2016). Exactness criteria for SDP-relaxations of quadratic extremum problems. Cybernetics and Systems Analysis, 52(6), 915-920. DOI doi.org/10.1007/s10559-016-9893-3 В роботі розглядаються неопуклі сепарабельні квадратичні оптимізаційні задачі при обмеженнях-нерівностях. Наведено достатню умову знаходження значення і точки глобального екстремуму задачі даного типу шляхом обчислення лагранжевої двоїстої оцінки. Особливість цієї умови полягає в тому, що вона легко перевіряється і вимагає від матриці гессіана функції Лагранжа лише, щоб її область додатної визначеності була не порожньою. Отриманий для двоїстої оцінки результат має місце і для оцінки, отриманої за допомогою SDP-релаксації. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2021-07-06 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/157 10.15407/fmmit2021.32.071 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 32 (2021): Physico-mathematical modeling and informational technologies, 2021, Issue 32; 42-45 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 32 (2021): Фізико-математичне моделювання та інформаційні технології, 2021, Вип. 32; 42-45 2617-5258 1816-1545 10.15407/fmmit2021.32 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/157/147 Авторське право (c) 2021 Oleg Berezovskyi (Автор) |
| spellingShingle | сепарабельна квадратична оптимізаційна задача глобальний екстремум двоїста оцінка додатно визначена матриця нульовий розрив двоїстості Berezovskyi, Oleg Достатня умова точної двоїстої оцінки для сепарабельної квадратичної оптимізаційної задачі: Fìz.-mat. model. ìnf. tehnol. 2021, 32:42-45 |
| title | Достатня умова точної двоїстої оцінки для сепарабельної квадратичної оптимізаційної задачі: Fìz.-mat. model. ìnf. tehnol. 2021, 32:42-45 |
| title_alt | The sufficient condition to find an exact dual bound in a separable quadratic optimization problem: Fìz.-mat. model. ìnf. tehnol. 2021, 32:42-45 |
| title_full | Достатня умова точної двоїстої оцінки для сепарабельної квадратичної оптимізаційної задачі: Fìz.-mat. model. ìnf. tehnol. 2021, 32:42-45 |
| title_fullStr | Достатня умова точної двоїстої оцінки для сепарабельної квадратичної оптимізаційної задачі: Fìz.-mat. model. ìnf. tehnol. 2021, 32:42-45 |
| title_full_unstemmed | Достатня умова точної двоїстої оцінки для сепарабельної квадратичної оптимізаційної задачі: Fìz.-mat. model. ìnf. tehnol. 2021, 32:42-45 |
| title_short | Достатня умова точної двоїстої оцінки для сепарабельної квадратичної оптимізаційної задачі: Fìz.-mat. model. ìnf. tehnol. 2021, 32:42-45 |
| title_sort | достатня умова точної двоїстої оцінки для сепарабельної квадратичної оптимізаційної задачі: fìz.-mat. model. ìnf. tehnol. 2021, 32:42-45 |
| topic | сепарабельна квадратична оптимізаційна задача глобальний екстремум двоїста оцінка додатно визначена матриця нульовий розрив двоїстості |
| topic_facet | сепарабельна квадратична оптимізаційна задача глобальний екстремум двоїста оцінка додатно визначена матриця нульовий розрив двоїстості separable quadratic optimization problem global extremum dual bound positively defined matrix zero duality gap |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/157 |
| work_keys_str_mv | AT berezovskyioleg thesufficientconditiontofindanexactdualboundinaseparablequadraticoptimizationproblemfizmatmodelinftehnol2021324245 AT berezovskyioleg dostatnâumovatočnoídvoístoíocínkidlâseparabelʹnoíkvadratičnoíoptimízacíjnoízadačífizmatmodelinftehnol2021324245 AT berezovskyioleg sufficientconditiontofindanexactdualboundinaseparablequadraticoptimizationproblemfizmatmodelinftehnol2021324245 |