Методи негладкої оптимізації: теорія та практичне застосування (стенограма доповіді на засіданні Президії НАН України 1 листопада 2023 р.)

У доповіді розглянуто окремі найважливіші результати проведених в Інституті кібернетики імені В.М. Глушкова НАН України досліджень у галузі чисельних методів негладкої оптимізації та наведено приклади їх застосування для розв’язання широкого кола актуальних практичних задач. Сучасним напрямом, як...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2024
Автор: Стецюк, П.І.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Видавничий дім "Академперіодика" НАН України 2024
Назва видання:Вісник НАН України
Теми:
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/201721
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Методи негладкої оптимізації: теорія та практичне застосування (стенограма доповіді на засіданні Президії НАН України 1 листопада 2023 р.) / П.І. Стецюк // Вісник Національної академії наук України. — 2024. — № 1. — С. 49-55. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-201721
record_format dspace
spelling irk-123456789-2017212025-01-29T18:51:13Z Методи негладкої оптимізації: теорія та практичне застосування (стенограма доповіді на засіданні Президії НАН України 1 листопада 2023 р.) Стецюк, П.І. З кафедри Президії НАН України У доповіді розглянуто окремі найважливіші результати проведених в Інституті кібернетики імені В.М. Глушкова НАН України досліджень у галузі чисельних методів негладкої оптимізації та наведено приклади їх застосування для розв’язання широкого кола актуальних практичних задач. Сучасним напрямом, який активно розвивається в Інституті, є розроблення методів штучного інтелекту з використанням спеціалізованих моделей та алгоритмів негладкої оптимізації для нейронних мереж та машинного навчання, а також для аналізу і проєктування логістичних, транспортних та енергетичних мереж. The report presents some of the most important results of research conducted at the V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine in the field of numerical methods of non-smooth optimization and gives examples of their application for solving a wide range of relevant practical problems. A modern direction that is actively evolving at the Institute is the development of artificial intelligence methods using specialized models and non-smooth optimization algorithms for neural networks and machine learning, as well as for the analysis and design of logistics, transport, and energy networks. 2024 Article Методи негладкої оптимізації: теорія та практичне застосування (стенограма доповіді на засіданні Президії НАН України 1 листопада 2023 р.) / П.І. Стецюк // Вісник Національної академії наук України. — 2024. — № 1. — С. 49-55. — укр. 1027-3239 DOI: doi.org/10.15407/visn2024.01.049 http://dspace.nbuv.gov.ua/handle/123456789/201721 uk Вісник НАН України Видавничий дім "Академперіодика" НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Ukrainian
topic З кафедри Президії НАН України
З кафедри Президії НАН України
spellingShingle З кафедри Президії НАН України
З кафедри Президії НАН України
Стецюк, П.І.
Методи негладкої оптимізації: теорія та практичне застосування (стенограма доповіді на засіданні Президії НАН України 1 листопада 2023 р.)
Вісник НАН України
description У доповіді розглянуто окремі найважливіші результати проведених в Інституті кібернетики імені В.М. Глушкова НАН України досліджень у галузі чисельних методів негладкої оптимізації та наведено приклади їх застосування для розв’язання широкого кола актуальних практичних задач. Сучасним напрямом, який активно розвивається в Інституті, є розроблення методів штучного інтелекту з використанням спеціалізованих моделей та алгоритмів негладкої оптимізації для нейронних мереж та машинного навчання, а також для аналізу і проєктування логістичних, транспортних та енергетичних мереж.
format Article
author Стецюк, П.І.
author_facet Стецюк, П.І.
author_sort Стецюк, П.І.
title Методи негладкої оптимізації: теорія та практичне застосування (стенограма доповіді на засіданні Президії НАН України 1 листопада 2023 р.)
title_short Методи негладкої оптимізації: теорія та практичне застосування (стенограма доповіді на засіданні Президії НАН України 1 листопада 2023 р.)
title_full Методи негладкої оптимізації: теорія та практичне застосування (стенограма доповіді на засіданні Президії НАН України 1 листопада 2023 р.)
title_fullStr Методи негладкої оптимізації: теорія та практичне застосування (стенограма доповіді на засіданні Президії НАН України 1 листопада 2023 р.)
title_full_unstemmed Методи негладкої оптимізації: теорія та практичне застосування (стенограма доповіді на засіданні Президії НАН України 1 листопада 2023 р.)
title_sort методи негладкої оптимізації: теорія та практичне застосування (стенограма доповіді на засіданні президії нан україни 1 листопада 2023 р.)
publisher Видавничий дім "Академперіодика" НАН України
publishDate 2024
topic_facet З кафедри Президії НАН України
url http://dspace.nbuv.gov.ua/handle/123456789/201721
citation_txt Методи негладкої оптимізації: теорія та практичне застосування (стенограма доповіді на засіданні Президії НАН України 1 листопада 2023 р.) / П.І. Стецюк // Вісник Національної академії наук України. — 2024. — № 1. — С. 49-55. — укр.
series Вісник НАН України
work_keys_str_mv AT stecûkpí metodinegladkoíoptimízacííteoríâtapraktičnezastosuvannâstenogramadopovídínazasídanníprezidíínanukraíni1listopada2023r
first_indexed 2025-07-17T09:04:02Z
last_indexed 2025-07-17T09:04:02Z
_version_ 1837884289890385920
fulltext ISSN 1027-3239. Вісн. НАН України, 2024, № 1 49 МЕТОДИ НЕГЛАДКОЇ ОПТИМІЗАЦІЇ: ТЕОРІЯ ТА ПРАКТИЧНЕ ЗАСТОСУВАННЯ Стенограма доповіді на засіданні Президії НАН України 1 листопада 2023 року У доповіді розглянуто окремі найважливіші результати проведених в Ін- ституті кібернетики імені В.М. Глушкова НАН України досліджень у галузі чисельних методів негладкої оптимізації та наведено приклади їх застосування для розв’язання широкого кола актуальних практичних задач. Сучасним напрямом, який активно розвивається в Інституті, є розроблення методів штучного інтелекту з використанням спеціалізованих моделей та алгоритмів негладкої оптимізації для нейронних мереж та машинного навчання, а також для аналізу і проєктування логістичних, транспортних та енергетичних мереж. Шановний Анатолію Глібовичу! Шановні члени Президії! Шановні присутні! Сьогодні я хотів би привернути вашу увагу до розвитку теорії та чисельних методів негладкої оптимізації — напряму, який в останні десятиліття викликає особливий інтерес завдяки ши- рокому колу його практичних застосувань. Методи негладкої оптимізації — це методи, що працюють з неперервними функціями, які не всюди є дифереційовними, тобто існують такі точки, в яких у функції немає похідної. Ці точки називають точками негладкості, і для них визначено по- няття узагальненого градієнта. Якщо функція є опуклою, уза- гальнений градієнт називають субградієнтом. У доповіді я часто буду вживати термін «субградієнтний ме- тод». Його слід розуміти як градієнтний метод, який розшире- но на клас негладких опуклих функцій. Методи негладкої оптимізації з кожним роком стають деда- лі більш актуальними. Останнім часом у світі спостерігається значний розвиток теорії і методів негладкої оптимізації, що на- самперед зумовлено такими чотирма факторами: 1) у сучасному математичному моделюванні технологічних, екологічних та економічних процесів усе частіше доводиться мати справу з негладкими функціями; СТЕЦЮК Петро Іванович — доктор фізико-математичних наук, завідувач відділу методів негладкої оптимізації Інституту кібернетики імені В.М. Глушкова НАН України doi: https://doi.org/10.15407/visn2024.01.049 50 ISSN 1027-3239. Visn. Nac. Acad. Nauk Ukr. 2024. (1) З КАФЕДРИ ПРЕЗИДІЇ НАН УКРАЇНИ 2) наявність добре розвинених теорій і чи- сельних алгоритмів — на сьогодні у світі є ба- гато відомих наукових шкіл негладкої оптимі- зації; 3) поява нових прикладних галузей, таких як нейронні мережі, машинне навчання, великі дані тощо, актуалізує розроблення ефектив- них алгоритмів для них; 4) прогрес сучасної обчислювальної тех- ніки (кластерні архітектури, grid- та cloud- обчислення) відкриває нові можливості для розвитку цього напряму. Починаючи з 1962 р. в Інституті кіберне- тики імені В.М. Глушкова НАН України під керівництвом академіка НАН України Наума Зуселевича Шора розроблялися оригінальні методи негладкої оптимізації. Досягнення за- снованої ним наукової школи здобули широке світове визнання. Так, у 1962 р. Н.З. Шор розробив перший субградієнтний метод; у 1969 р. — вперше ви- користав оператор розтягу простору для при- скорення субградієнтних методів; у 1985 р. — розпочав роботи з розроблення техніки дво- їстих оцінок для квадратичних екстремальних задач, яка дає змогу обґрунтовувати оптималь- ні розв’язки в багатоекстремальних задачах. Отримані результати Наум Зуселевич деталь- но представив у двох англомовних монографі- ях: «Minimization Methods for Non-Differentia- ble Functions»1 і «Nondifferentiable Optimiza- tion and Polymomial Problems»2. Загалом субградієнтні алгоритми з пере- творенням простору мають велике теоретич- не та прикладне значення і є «ключем» для розв’язання задач математичного програму- вання великих розмірностей. Вони вирізня- ються простотою реалізації, зручністю для розпаралелювання, розвиненою методикою налаштування параметрів з урахуванням спе- 1 Shor N.Z. Minimization Methods for Non-Differentiable Functions. Springer-Verlag Berlin, Heidelberg, 1985. https://doi.org/10.1007/978-3-642-82118-9 2 Shor N.Z. Nondifferentiable Optimization and Polymo- mial Problems. Springer Science+Business Media Dor- drecht, 1998. https://doi.org/10.1007/978-1-4757- 6015-6 цифіки задачі. Алгоритми забезпечують висо- ку швидкість збіжності для мінімізації яруж- них функцій, тобто функцій з витягнутими поверхнями рівня. Добре відомими окремими випадками суб- градієнтних алгоритмів з розтягом простору є r-алгоритми, розроблені в 1970 р., та метод еліпсоїдів, запропонований у 1977 р. За часом обчислення і точністю результатів програмні реалізації r-алгоритмів виявилися конкурен- тоспроможними порівняно з найбільш ефек- тивними методами розв’язання гладких пога- но обумовлених задач (задач із сингулярними особливостями), але при цьому r-алгоритми мають вагому перевагу — їх можна використо- вувати для задач негладкої оптимізації. Швидкість збіжності методу еліпсоїдів не залежить від властивостей функції, вона зале- жить тільки від розмірності простору. Це дало можливість отримати перший поліноміальний алгоритм для задачі лінійного програмування та низку поліноміальних алгоритмів для спеці- альних задач комбінаторної оптимізації. Нині в Інституті кібернетики імені В.М. Глушкова НАН України продовжуються роботи з розвитку субградієнтних алгоритмів та їх застосування в багатьох прикладних галу- зях. Розроблено нові модифікації r-алгоритмів: r(σ)-алгоритми з автоматичним вибором кое- фіцієнтів розтягу простору та r(n)-алгоритми з використанням операторів розтягу простору по різниці нормованих субградієнтів, а також узагальнене сімейство методів еліпсоїдів, нові субградієнтні методи з перетворенням просто- ру, які використовують апріорну інформацію про мінімальне значення функції, що мінімі- зується. За допомогою цих методів отримано нові результати в теорії двоїстості для неопуклих квадратичних оптимізаційних задач. Розро- блені алгоритми мають прискорену збіжність для яружних функцій, і їх програмні реалізації із застосуванням процедури регулювання ма- триць перетворення простору можна викорис- товувати як оптимізаційні ядра для побудови ефективних методів розв’язання прикладних задач. ISSN 1027-3239. Вісн. НАН України, 2024, № 1 51 З КАФЕДРИ ПРЕЗИДІЇ НАН УКРАЇНИ Рис. 1. Порівняння збіжності алгоритмів субградієнтного методу (а) і субградієнтного методу з перетворенням простору (б) На прикладі кусково-лінійної функції від двох змінних 1 2 1 2( , ) 10f x x x x  продемонструємо, що саме означає така «при- скорена збіжність алгоритмів». На рис. 1а на- ведено траєкторію субградієнтного методу, яка починається в стартовій точці і закінчується в точці мінімуму. Ця траєкторія є зигзагоподіб- ною, і ще більш зигзагоподібною вона буде, якщо для функції коефіцієнт 10 замінити на більший. На рис. 1б можна бачити траєкторію одного з розроблених нами методів з перетво- ренням простору, який з тієї самої стартової точки збігається до точки мінімуму всього за дві ітерації. І це буде так незалежно від того, наскільки великим ми візьмемо коефіцієнт при модулі х2. Тому розроблені алгоритми з вико- ристанням операторів перетворення простору змінних дають можливість будувати ефектив- ні алгоритми для розв’язання оптимізаційних задач із сингулярними особливостями. Тепер від теорії методів негладкої оптиміза- ції перейдемо до прикладів оптимізаційних за- дач, у яких було використано розроблені нами методи. За браком часу розповім лише про п’ять таких застосувань, хоча їх, звісно, більше. Отже, це: 1) відмовостійкі мережі; 2) сопло Лаваля з центральним тілом; 3) дефекти в регулярних структурах; 4) збалансоване пакування 2D- і 3D-об’єктів; 5) міжгалузеві моделі планування структур- но-технологічних змін. Роботи над задачами відмовостійких мереж та міжгалузевих моделей планування струк- турно-технологічних змін розпочалися ще при Наумі Зуселевичі Шорі, тобто над ними ми працюємо вже понад 20 років. Над іншими трьома задачами ми разом з їх замовниками почали працювати в останні роки. Для розв’язання задач про відмовостійкі ме- режі в Інституті кібернетики імені В.М. Глуш- кова НАН України розроблено математичні моделі, методи та програмне забезпечення для визначення та модернізації пропускних спро- можностей дуг відмовостійких мереж. Такі мо- делі описуються блочними задачами з сотнями мільйонів змінних та сотнями тисяч обмежень, і для них методи негладкої оптимізації у поєд- нанні зі схемами декомпозиції є ефективними. Специфіку цих задач характеризує рис. 2, на якому показано, що мережі повинні функціо- нувати навіть тоді, коли дуга або шлях вияв- ляться несправними, тобто «відмовлять». На початку цього року ми почали працю- вати над задачами відмовостійких мереж для операторів систем розподілу електроенергії. Замовником цих робіт є Навчально-науковий інститут енергетики, автоматики і енергозбе- реження Національного університету біоре- сурсів та природокористування. Спільно ми 52 ISSN 1027-3239. Visn. Nac. Acad. Nauk Ukr. 2024. (1) З КАФЕДРИ ПРЕЗИДІЇ НАН УКРАЇНИ Рис. 3. Схема задачі адресності потоків у багатовузлових регіональних енергосистемах для забезпечення опти- мальних сценаріїв диспетчеризації регіональних енергосистем в умовах дефіциту потужності (квадратики — по- стачальники, кружечки — споживачі): а — розподіл потоків у мережі в разі, якщо всі постачальники поставляють електроенергію; б — перерозподіл потоків у разі, якщо постачальник А1 не зможе поставляти електроенергію в систему Рис. 2. Схема за- дачі про відмово- стійкі мережі розробили алгоритм і програмне забезпечення для розв’язання задачі адресності потоків у багатовузлових регіональних енергосистемах для забезпечення оптимальних сценаріїв дис- петчеризації регіональних енергосистем в умо- вах дефіциту потужності. Схему цих задач наведено на рис. 3. Клю- чове питання полягає в тому, як у разі немож- ливості постачання електроенергії одним або кількома постачальниками перерозподілити потоки в мережі так, щоб споживачі постраж- дали якнайменше. Може так статися, що ці за- дачі виявляться дуже актуальними цієї зими. У другому прикладі застосувань ми вико- ристали модифікації r-алгоритмів для побу- дови профілів зовнішнього та внутрішнього контурів поверхонь сопла Лаваля з централь- ним тілом та аеродинамічних профілів і по- верхонь пера лопатки для авіадвигунів. Ці роботи ми виконували в 2018—2020 рр. спіль- но з ДП «Запорізьке машинобудівне кон- структорське бюро «Прогрес» імені академіка О.Г. Івченка». Зміст задачі про сопло Лаваля з централь- ним тілом показано на рис. 4. Потрібно так побудувати контури поверхонь сопла та цен- трального тіла, щоб вони задовольняли задані закони зміни площ для крайнього лівого, край- нього правого та кількох проміжних положень центрального тіла. ISSN 1027-3239. Вісн. НАН України, 2024, № 1 53 З КАФЕДРИ ПРЕЗИДІЇ НАН УКРАЇНИ Рис. 4. Задача про сопло Лаваля з центральним тілом: а — крайнє ліве положення центрального тіла; б — крайнє праве положення центрального тіла На основі отриманих результатів було роз- ширено функціональні можливості розро- блених у ДП «Івченко-Прогрес» пакетів при- кладних програм «Поверхня» і «Сопло». Нові версії пакетів прикладних програм дозволяють скоротити терміни проєктування аеродина- мічних поверхонь та поверхонь сопла Лаваля з центральним тілом і поліпшити їх газодина- мічні характеристики. Це має важливе значен- ня для створення сучасної авіаційної техніки. Третій приклад — дослідження щодо знахо- дження місць розміщення та границь дефек- тних областей у зображеннях, отриманих за допомогою методів ширографії для тонкостін- них багатошарових композиційних матеріалів. Ці роботи ми виконували спільно з Інститу- том електрозварювання ім. Є.О. Патона НАН України. Так, було розроблено алгоритми пошуку де- фектів у регулярних структурах з використан- ням методу найменших модулів, який опису- ється негладкою функцією. Деформації вимі- рювали за допомогою розробленої в Інституті електрозварювання методики неруйнівного контролю якості металевих і композиційних матеріалів (рис. 5), а створене нами алгорит- Рис. 5. Результати вимірювання деформацій у зображеннях, отриманих за допомогою методів ширографії для тонкостінних багатошарових композиційних матеріалів: а — тришарова панель з дефектом зварювання; б — ком- позиційна пластина з трьома внутрішніми дефектами 54 ISSN 1027-3239. Visn. Nac. Acad. Nauk Ukr. 2024. (1) З КАФЕДРИ ПРЕЗИДІЇ НАН УКРАЇНИ боти ми проводимо ще з 1998 р., коли Михайло Володимирович Михалевич звернувся до нас з проханням виконати за допомогою методів негладкої оптимізації розрахунки для однієї з його економічних задач. Упродовж десяти ро- ків ми активно розвивали методи розв’язання таких задач, після чого ними зацікавилися швейцарські вчені з Університету м. Фрібург, спільно з якими ми виконували такі міжнарод- ні проєкти, як грант Швейцарської національ- ної наукової фундації (SNSF) IZ73ZO_127962 «Аналіз інституційних і технологічних змін у ринкових та перехідних економіках на тлі сучасної фінансової кризи» (2010—2012), а також гранти SNSF IZ63ZO_147586 (2013— 2014) і SNSF IZ63ZO_160605 (2015—2016). Результати цих робіт узагальнено в монографії «Институциональные и технологические из- менения в странах с рыночной и переходной экономикой» (2015). Отже, актуальність подальшого розвитку методів негладкої оптимізації визначається доведеною ефективністю їх практичного за- стосування. Ці методи дозволяють побудувати адекватні моделі оптимізації для багатьох при- кладних задач. Методи негладкої оптимізації можна ви- користовувати для різноманітних класів за- дач (оптимальне планування, проєктування, управління), що відкриває широкі перспекти- ви для розширення співпраці в різних сферах науки і техніки. На сьогодні є необхідність по- силення інформаційної обізнаності та зв’язків із потенційними замовниками для побудови прийнятних математичних моделей. Особливого значення набуває розроблення спеціалізованих алгоритмів негладкої оптимі- зації для нейронних мереж та машинного на- вчання. Сьогодні в Інституті кібернетики імені В.М. Глушкова НАН України розробляються також методи штучного інтелекту із застосу- ванням моделей та алгоритмів негладкої опти- мізації (спеціалізовані алгоритми негладкої оптимізації для нейронних мереж та машин- ного навчання), методи негладкої оптимізації для аналізу та проєктування логістичних, тран- мічне та програмне забезпечення дозволяє автоматизувати процес визначення місцезна- ходження дефектів у стільникових панелях, що мають періодичну структуру, та зменшити вплив людського фактора під час неруйнівно- го контролю якості методом ширографії. Наступний приклад пов’язаний із розв’я- зан ням задач оптимального пакування геоме- тричних об’єктів у контейнери різних форм за умови балансу (рівновага, інерційність та ін.). Паралельні алгоритми для деяких задач па- кування реалізовано на суперкомп’ютерному комплексі СКІТ Інституту кібернетики імені В.М. Глушкова НАН України. Ці роботи ми проводимо ще з 2011 р. спільно з професорами Юрієм Григоровичем Стояном і Тетяною Євге- нівною Романовою, які представляють відділ математичного моделювання і оптимального проєктування Інституту проблем машинобу- дування ім. А.М. Підгорного НАН України. Метод φ-функцiй, розроблений у цьому відділі, на сьогодні високо оцінено світовою науковою спільнотою фахівців з досліджен- ня операцій (operational research). Цей метод визнано найбільш потужним засобом матема- тичного моделювання відношень геометрич- них об’єктів, що відкрило шлях до можливості застосування методів математичного програ- мування для розв’язання NP-складних задач геометричного проєктування. У загальному випадку кожна φ-функція є негладкою, тому методи негладкої оптимізації є вкрай важли- вими для пошуку найкращих локально-опти- мальних рішень. За цей час ми виконали кілька спільних міжнародних проєктів, зокрема грант Україн- ського науково-технологічного центру (2014— 2015) і грант Volkswagen Foundation, який роз- почався 2021 р. і нині ще продовжується. Задачі збалансованого пакування мають широкий спектр застосувань — це і космічна інженерія, і адитивне виробництво (3D-друк), і матеріалознавство та багато інших галузей. І останній приклад — використання міжга- лузевих моделей планування структурно-тех- нологічних змін для виявлення диспропорцій в економіці та аналізу шляхів їх усунення. Ці ро- ISSN 1027-3239. Вісн. НАН України, 2024, № 1 55 З КАФЕДРИ ПРЕЗИДІЇ НАН УКРАЇНИ спортних та енергетичних мереж. Потенцій- ними їх користувачами є кафедра медичної ін- форматики Тернопільського національного ме- дичного університету імені І.Я. Горбачевського, якій вони потрібні для вирішення завдань реа- білітаційної та телереабілітаційної медицини, асоціація «Український логістичний альянс», Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України, Інститут елек- тродинаміки НАН України та інші організації, зацікавлені в дослідженнях за цим напрямом. Дякую за увагу! За матеріалами засідання підготувала О.О. Мележик Petro I. Stetsyuk V.M. Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine, Kyiv, Ukraine ORCID: https://orcid.org/0000-0003-4036-2543 METHODS OF NON-SMOOTH OPTIMIZATION: THEORY AND PRACTICAL APPLICATION Transcript of scientific report at the meeting of the Presidium of NAS of Ukraine, November 1, 2023 The report presents some of the most important results of research conducted at the V.M. Glushkov Institute of Cyber- netics of the NAS of Ukraine in the field of numerical methods of non-smooth optimization and gives examples of their application for solving a wide range of relevant practical problems. A modern direction that is actively evolving at the Institute is the development of artificial intelligence methods using specialized models and non-smooth optimization algorithms for neural networks and machine learning, as well as for the analysis and design of logistics, transport, and energy networks. Cite this article: Stetsyuk P.I. Methods of non-smooth optimization: theory and practical application. Visn. Nac. Akad. Nauk Ukr. 2024. (1): 49—55. https://doi.org/10.15407/visn2024.01.049