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

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2024
Автори:	Лебєдєва, Т.Т., Семенова, Н.В., Сергієнко, Т.І.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Видавничий дім "Академперіодика" НАН України 2024
Назва видання:	Доповіді НАН України
Теми:	Інформатика та кібернетика
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/202368
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Регуляризація частково цілочислової задачі векторної оптимізації з квадратичними функціями критеріїв / Т.Т. Лебєдєва, Н.В. Семенова, Т.І. Сергієнко // Доповіді Національної академії наук України. — 2024. — № 5. — С. 38-43. — Бібліогр.: 6 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-202368
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-2023682025-07-31T00:09:11Z Регуляризація частково цілочислової задачі векторної оптимізації з квадратичними функціями критеріїв Regularization of partially integer vector optimization problems with quadratic criteria Лебєдєва, Т.Т. Семенова, Н.В. Сергієнко, Т.І. Інформатика та кібернетика Представлено нові результати, пов’язані з регуляризацією частково цілочислових задач оптимізації за Парето за умов можливих збурень вхідних даних векторного критерію, який складається з квадратичних функцій. Розроблена процедура регуляризації ґрунтується на використанні властивості стійкості відносно збурень коефіцієнтів критеріїв векторної задачі оптимізацїі за Слейтером. The article is devoted to the question of regularization of partially integer Pareto-optimization problems with vector criterion input perturbations. New results are obtained for the case when the vector problem is partially integer with quadratic functions as criteria. The developed regularization procedure is based on the use of the Slater stability property with respect to perturbations of criterion coefficients of the vector optimization problem. The obtained results - the conditions of stability to possible perturbations of vector criterion input data and the developed procedure of regularization of vector optimization problems — are related to the solution of problems of correct modeling of economic, ecological, technological, social processes in conditions of effective accounting of incompleteness and uncertainty of input information. 2024 Article Регуляризація частково цілочислової задачі векторної оптимізації з квадратичними функціями критеріїв / Т.Т. Лебєдєва, Н.В. Семенова, Т.І. Сергієнко // Доповіді Національної академії наук України. — 2024. — № 5. — С. 38-43. — Бібліогр.: 6 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/202368 519.8 DOI: doi.org/10.15407/dopovidi2024.05.038 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	2024
topic_facet	Інформатика та кібернетика
url	https://nasplib.isofts.kiev.ua/handle/123456789/202368
citation_txt	Регуляризація частково цілочислової задачі векторної оптимізації з квадратичними функціями критеріїв / Т.Т. Лебєдєва, Н.В. Семенова, Т.І. Сергієнко // Доповіді Національної академії наук України. — 2024. — № 5. — С. 38-43. — Бібліогр.: 6 назв. — укр.
series	Доповіді НАН України
work_keys_str_mv	AT lebêdêvatt regulârizacíâčastkovocíločislovoízadačívektornoíoptimízacíízkvadratičnimifunkcíâmikriteríív AT semenovanv regulârizacíâčastkovocíločislovoízadačívektornoíoptimízacíízkvadratičnimifunkcíâmikriteríív AT sergíênkotí regulârizacíâčastkovocíločislovoízadačívektornoíoptimízacíízkvadratičnimifunkcíâmikriteríív AT lebêdêvatt regularizationofpartiallyintegervectoroptimizationproblemswithquadraticcriteria AT semenovanv regularizationofpartiallyintegervectoroptimizationproblemswithquadraticcriteria AT sergíênkotí regularizationofpartiallyintegervectoroptimizationproblemswithquadraticcriteria
first_indexed	2025-11-26T23:09:45Z
last_indexed	2025-11-26T23:09:45Z
_version_	1849896298955669504
fulltext	38 ОПОВІДІ НАЦІОНАЛЬНОЇ АКАДЕМІЇ НАУК УКРАЇНИ ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2024. No. 5: 38—43 Ц и т у в а н н я: Лебєдєва Т.Т., Семенова Н.В., Сергієнко Т.І. Регуляризація частково цілочислової задачі вектор- ної оптимізації з квадратичними функціями критеріїв. Допов. Нац. акад. наук Укр. 2024. № 5. С. 38—43. https:// doi.org/10.15407/dopovidi2024.05.038 © Видавець ВД «Академперіодика» НАН України, 2024. Стаття опублікована за умовами відкритого доступу за ліцензією CC BY-NC-ND (https://creativecommons.org/licenses/by-nc-nd/4.0/) ІНФОРМАТИКА ТА КІБЕРНЕТИКА INFORMATICS AND CYBERNETICS https://doi.org/10.15407/dopovidi2024.05.038 УДК 519.8 Т.Т. Лебєдєва, https://orcid.org//0000-0002-0041-2174 Н.В. Семенова, https://orcid.org// 0000-0001-5808-1155 Т.І. Сергієнко, https://orcid.org//0000-0003-0396-3315 Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна E-mail: lebedevatt@gmail.com, nvsemenova@meta.ua, taniaser62@gmail.com Регуляризація частково цілочислової задачі векторної оптимізації з квадратичними функціями критеріїв Представлено академіком НАН України І.В. Сергієнком Представлено нові результати, пов’язані з регуляризацією частково цілочислових задач оптимізації за Па- рето за умов можливих збурень вхідних даних векторного критерію, який складається з квадратичних функцій. Розроблена процедура регуляризації ґрунтується на використанні властивості стійкості віднос- но збурень коефіцієнтів критеріїв векторної задачі оптимізацїі за Слейтером. Ключові слова: задача частково цілочислової оптимізації за Парето, векторний критерій, квадратичні функції, збурення вхідних даних, стійкість, регуляризація, множина Слейтера. Вступ. Багато проблем прийняття багатоцільових рішень в управлінні, плануванні та про- єктуванні можуть бути сформульовані як багатокритерійні (векторні) задачі дискретної оптимізації. Характерною особливістю таких задач, що виникають на практиці, є неточ- ність вхідної інформації, яка зумовлена впливом різних факторів невизначеності та випад- ковості: неадекватністю математичних моделей реальним процесам, помилками округлен- ня, похибками вимірювань тощо. За таких умов математична задача не може бути корек- тно поставлена та розв’язана без хоча б неявного використання результатів теорії стійкості та регуляризації можливо нестійкої задачі [1—3]. Мета роботи — розробка та обґрунтування процедури регуляризації можливо нестій- кої за векторним критерієм частково цілочислової задачі оптимізації за Парето з квадра- тичними цільовими функціями і множиною допустимих розв’язків, яка є компактом. У 39ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2024. № 5 Регуляризація частково цілочислової задачі векторної оптимізації з квадратичними функціями критеріїв межах цього підходу регуляризація полягає у перетворенні нестійкої за векторним крите- рієм вхідної задачі на завідомо стійку збурену спеціальним чином задачу. Постановка задачі. Означення та основні твердження. Розглянемо векторну задачу частково цілочислової оптимізації такого вигляду: max{ ( ) },F x x X (1) де X  , 1 2n n nX R Z R   , 1 2n n n  , 11 n n , nR — n -вимірний дійсний про- стір, 2nZ — множина всіх цілочислових векторів з 2nR , 1 2( ) ( ( ), ( ), ..., ( ))F x f x f x f x  — векторний критерій, 1 2 1: n n if R Z R  — квадратичні критеріальні функції ви- гляду ( ) , ,i i if x x D x c x      , [ ]i n n i jkD d R   , 1( , ..., ) n i i inc c c R  , {1, ..., }i N   , , {1, ..., }nj k N n  . Задачу (1) позначатимемо ( , )PQ F X , якщо її множиною оптимальних розв’язків будемо вважати множину Парето P (F, X) = {x  X\| π(x, F, X) = , де ( , , ) { ( ) ( ), ( ) ( )}x F X y X F y F x F y F x    , (2) Якщо оптимальними будемо вважати всі допустимі розв’язки задачі, які належать множині Слейтера ( , ) { ( , , ) }S F X x X x F X    , де ( , , ) { ( ) ( )}x F X y X F y F x    , (3) тоді задачу (1) позначатимемо ( , )SlQ F X . Для задачі (1) як вхідні дані, що можуть зазнавати збурень, будемо розглядати коефіці- єнти векторного критерію F , який складається з квадратичних функцій. Набір таких вхід- них даних позначимо ( , ) n n nu D C U R R       , де 1( , ..., ) ,n nD D D R      [ ] n ijC c R    , U — простір вхідних даних задачі, які необхідні для подання векторного критерію. З ме- тою уточнення, який саме набір вхідних даних u U відповідає задачі, що розглядається, будемо користуватися також позначеннями 1( ) ( ( ), ..., ( ))u u uF x f x f x  . Далі для будь-якого натурального числа q дійсний векторний простір qR розгляда- тимемо як нормований. Норму в qR задамо формулою q i i N z z    , де 1( , ..., ) q qz z z R  . Під нормою деякої матриці [ ] m k ijB b R   будемо розуміти норму вектора 11 12, ...,( , )mkb b b . Враховуючи, що у скінченно-вимірному просторі qR будь-які дві норми еквівалентні [4], викладені далі результати справедливі й для інших норм, введених у такому просторі. Для набору вхідних даних u U і будь-якого числа 0  визначимо множину збуре- них вхідних даних як такий  -окіл: ( ) { ( ) ( ) }O u u U u u        . Задача зі збуреними вхідними даними для векторного критерію матиме вигляд: ( )max{ ( ) },uF x x X  де ( ) ( ),u O u  1 2 ( ) ( ) ( ) ( )( ) { ( ), ( ), .., ( )}u u u uF x f x f x f x     . 40 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2024. No 5 Т.Т. Лебєдєва, Н.В. Семенова, Т.І. Сергієнко Означення 1. Задачу ( , )P uQ F X ( ( , ))Sl uQ F X , де u U , назвемо стійкою за век- торним критерієм, якщо 0  0  , таке, що ( ) ( )u O u   виконується умова ( )( , ) ( ( , ))u uP F X O P F X  (відповідно ( )( , ) ( ( , ))u uSl F X O Sl F X  . Тут і далі ε-окіл будь-якої множини nB R будемо визначати за формулою ( ) infn y B O B x R x y           . Відмітимо, що стійкість за векторним критерієм задачі ( , )P uQ F X ( ( , ))Sl uQ F X , де u U , означає, що точково-множинне відображення : 2 , ( ) ( , )X uP U u P u P F X   (відповідно відображення : 2 , ( ) ( , )X uSl U u Sl u Sl F X   ) є напівнеперервним зверху за Хаусдорфом у точці u U . У роботі [5] доведено таку достатню умову стійкості до збурень коефіцієнтів векторно- го критерію для задачі на відшукання розв’язків, оптимальних за Слейтером. Теорема 1. Якщо допустима множина X є компактом, то задача ( , )Sl uQ F X , де u U , є стійкою за векторним критерієм. Достатні умови стійкості задачі ( , )P uQ F X , де u U , на відшукання Парето-оптималь- них розв’язків, сформульовано в наступному твердженні, доведеному в роботі [6]. Теорема 2. Якщо допустима множина X є компактом і, крім того, виконується рів- ність ( , ) cl( ( , )),u uS F X P F X (4) де clB — замикання будь-якої множини nB R , то задача ( , )P uQ F X , де u U , є стійкою за векторним критерієм. Враховуючи цю теорему і виходячи з означення 1, робимо висновок, що розв’язуючи векторну задачу ( , )P uQ F X за умов обмеженості і замкненості допустимої множини X , а також виконання співвідношення (4), яке пов’язує множини Слейтера і Парето, отримаємо розв’язки, близькі до істинних, навіть у випадку, коли можливі достатньо малі збурення у вхідних даних для векторного критерію. Проте згідно з означенням 1 для нестійкої до збурень вхідних даних векторного кри- терію частково цілочислової задачі ( , )P uQ F X існує 0  таке, що 0  знайдеться набір збурених вхідних даних ( ) ( )u O u  , для якого множина ( )( , ) ( , )u uP F X O P F X \ не є по- рожньою. Таким чином, за умови збурень вхідних даних, необхідних для подання вектор- ного критерію, існує можливість отримання результатів розв’язання задачі ( , )P uQ F X , які не є її шуканими Парето-оптимальними розв’язками і навіть не є достатньо близькими до множини Парето. Для уникнення таких помилкових результатів необхідна розробка та обґрунтування процедури регуляризації, застосування якої дозволить отримати шукані розв’язки з множини ( , )uP F X або близькі до неї, здійснивши для цього, наприклад, як це буде запропоновано далі, перехід від безпосереднього розв’язання можливо нестійкої задачі ( , )P uQ F X оптимізації за Парето до розв’язання напевно стійкої задачі ( , )Sl uQ F X оптимізації за Слейтером зі спеціальним чином збуреними (зміненими) вхідними даними u , де τ — параметр збурення. 41ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2024. № 5 Регуляризація частково цілочислової задачі векторної оптимізації з квадратичними функціями критеріїв Відмітимо, що у випадку, коли критерій uF складається з лінійних функцій ( ) ,i if x c x   , i N  , підхід до регуляризації можливо нестійкої за векторним критерієм задачі ( , )P uQ F X запропоновано у статті [5]. Далі опишемо процедуру регуляризації можливо нестійкої за векторним критерієм частково цілочислової задачі ( , )P uQ F X оптимізації за Парето з квадратичними цільовими функціями і множиною допустимих розв’язків X , яка є компактом. Крок 1. Змінимо спеціальним чином векторний критерій ( )uF x . Змінений кри- терій буде мати вигляд 1 2( ) { ( ), ( ), .., ( )}u u u uF x f x f x f x     , де ( , )u D C U    , 0 < , ( ) , ,i i iuf x x D x c x        , n n i i k k k N D D D R         , i i k k k N c c c       — вектори-рядки зміненої матриці nC R   , 0i  , i N  . Крок 2. Перейдемо від можливо нестійкої за векторним критерієм задачі ( , )P uQ F X оптимізації за Парето до стійкої зміненої задачі ( , )Sl uQ F X оптимізації за Слейтером. Об- ґрунтуванням такого переходу слугують наступні дві теореми, які встановлюють зв’язок між множинами оптимальних розв’язків цих двох задач, у тому числі за можливості збу- рень коефіцієнтів критеріальних функцій. Теорема 3. Для будь-якого значення 0 < параметра збурень вхідних даних векторного критерію задачі ( , )Sl uQ F X справджується включення ( , ) ( , )uuS F X P F X  . (5) Доведення. Якщо ( , )uX P F X \ , тоді справедливість включення (5) стає оче- видною. Проте у протилежному випадку, коли не всі точки множини X є Па- рето-оптимальними розв’язками задачі ( , )P uQ F X , для доведення включен- ня (5) розглянемо будь-яку точку ( , )uz X P F X \ . Для неї з урахуванням форму- ли (2) маємо ( , , ) { ( ) ( ) 0, ( ) ( )}u u u u uz F X y X F y F z F y F z      . Покажемо, що 0  справедливе включення ( , , ) ( , , )u uz F X z F X   , де згідно з формулою (3) ( , , ) { ( ) ( ) 0}u u uz F X y X F y F z      > . Для цього, вибравши довільну точку ( , , )uy z F X і будь-яке 0  , оцінимо різницю значень кожної i -ї критеріальної функції i uf  ( i N  ) у точках y і z : ( ) ( ) , , , , , ( )i i i i i i i k ku u k N f y f z y D y c y z D z c z y D D y                            , , ( ) ,i k k i k k i k k k N k N k N c c y z D D z c c z                           ( ) ( ) ( ( ) ( ))i i i i u u k u u k N f y f z f y f z         > 0 . Отримана додатна оцінка вказаної різниці означає, що ( , , )uy z F X  . Отже, ( , )uz X Sl F X \ і, більше того, ( , ) ( , )u uX P F X X Sl F X\ \ . Останнє включення еквіва- лентне в нашому випадку включенню (5). Доведення теореми завершено. З врахуванням теорем 1 і 3 приходимо також до такого висновку. 42 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2024. No 5 Т.Т. Лебєдєва, Н.В. Семенова, Т.І. Сергієнко Теорема 4. Нехай допустима множина X задачі ( , )P uQ F X , де u U , є компактом. Тоді 0  і 0  0  таке, що ( ) ( )u O u     має місце включення ( ) ( , ) ( , )uuS F X O P F X   . Висновки. Запропоновано та обґрунтовано процедуру регуляризації можливо нестій- кої за векторним критерієм частково цілочислової задачі ( , )P uQ F X оптимізації за Паре- то з квадратичними цільовими функціями і допустимою множиною X , яка є компактом. У межах розробленого підходу регуляризація полягає у перетворенні можливо нестійкої за векторним критерієм задачі ( , )P uQ F X на стійку збурену спеціальним чином задачу ( , )Sl uQ F X оптимізації за Слайтером, розв’язки якої близькі до шуканих Парето-опти- мальних розв’язків навіть у випадку, коли існують достатньо малі збурення у вхідних да- них векторного критерію. ЦИТОВАНА ЛІТЕРАТУРА 1. Сергиенко И.В., Козерацкая Л.Н., Лебедева Т.Т. Исследование устойчивости и параметрический анализ дискретных оптимизационных задач. Киев: Наук. думка, 1995. 170 с. 2. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы решения, исследова- ния. Киев: Наук. думка, 2003. 264 с. 3. Emelichev V.A., Girlich E., Nikulin Yu.V., Podkopaev D.P. Stability and regularization of vector problems of integer linear programming. Optimization. 2002. 51, № 4. P. 645—676. https://doi.org/10.1080/ 0233193021000030760 4. Ляшко І.І., Ємельянов В.Ф., Боярчук О.К. Математичний аналіз. Частина 1. Київ: Вища школа. 1992. 495 с. 5. Лебєдєва Т.Т., Семенова Н.В., Сергієнко Т.І. Стійкість і регуляризація частково цілочислових задач век- торної оптимізації за можливих збурень критеріїв. Допов. Нац. акад. наук Укр. 2022. № 5. С. 16—22. https://doi.org/10.15407/dopovidi2022.05.016 6. Лебєдєва Т.Т., Семенова Н.В., Сергієнко Т.І. Стійкість за векторним критерієм задачі частково цілочис- лової оптимізації з квадратичними критеріальними функціями. Допов. Нац. акад. наук Укр. 2020. № 10. С. 15—21. https://doi.org/10.15407/dopovidi2020.10.015 Надійшло до редакції 09.07.2024 REFERENCES 1. Sergienko, I. V., Kozeratskaya, L. N. & Lebedeva, Т. Т. (1995). Stability Analysis and Parametric Analysis of Discrete Optimization Problems. Kyiv: Naukova Dumka (in Russian) 2. Sergienko, I. V. & Shilo, V. P. (2003). Discrete optimization. Problems: challenges, methods, solutions. Kyiv: Naukova Dumka (in Russian) 3. Emelichev, V. A., Girlich, E., Nikulin, Yu. V. & Podkopaev, D. P. (2002). Stability and regularization of vector problems of integer linear programming. Optimization, 51, No. 4, pp. 645-676. https://doi.org/10.1080/ 0233193021000030760 4. Lyashko, I. I., Yemelyanov, V. F. & Boyarchuk, O. K. (1992). Mathematical analysis. Part 1. Kyiv: Visha shcola (in Ukrainian) 5. Lebedeva, Т. Т., Semenova, N. V. & Sergienko, T. I. (2022). Stability and regularization of partially integer problems of vector optimization with possible perturbations of criteria. Dopov. Nac. akad. nauk Ukr., No. 5, pp. 16-22. (in Ukrainian). https://doi.org/10.15407/dopovidi2022.05.016 6. Lebedeva, Т. Т., Semenova, N. V. & Sergienko, T. I. (2020). Stability by the vector criterion of a mixed integer optimization problem with quadratic criterial functions. Dopov. Nac. akad. nauk Ukr., No. 10, pp. 15-21. (in Ukrainian). https://doi.org/10.15407/dopovidi2020.10.015 Received 09.07.2024 43ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2024. № 5 Регуляризація частково цілочислової задачі векторної оптимізації з квадратичними функціями критеріїв Т.Т. Lebedeva, https://orcid.org//0000-0002-0041-2174 N.V. Semenova, https://orcid.org//0000-0001-5808-1155 T.I. Sergienko, https://orcid.org//0000-0003-0396-3315 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv, Ukraine E-mail: lebedevatt@gmail.com, nvsemenova@meta.ua, taniaser62@gmail.com REGULARIZATION OF PARTIALLY INTEGER VECTOR OPTIMIZATION PROBLEMS WITH QUADRATIC CRITERIA The article is devoted to the question of regularization of partially integer Pareto-optimization problems with vector criterion input perturbations. New results are obtained for the case when the vector problem is partially integer with quadratic functions as criteria. The developed regularization procedure is based on the use of the Slater stability property with respect to perturbations of criterion coefficients of the vector optimization problem. The obtained results - the conditions of stability to possible perturbations of vector criterion input data and the developed procedure of regularization of vector optimization problems — are related to the solution of problems of correct modeling of economic, ecological, technological, social processes in conditions of effective accounting of incompleteness and uncertainty of input information. Keywords: partially integer problem, Pareto optimization, vector criterion, quadratic functions, perturbations of input data, stability, regularization, set of Slater.

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

Репозитарії

Схожі ресурси