Використання r-алгоритму Шора в лінійних задачах робастної оптимізації

Cтаття присвячена опису нового підходу до побудови алгоритмів розв’язання задач лінійного програмування (ЛП-задач), у яких кількість обмежень є значно більшою за кількість змінних. Він базується на використанні модифікації r-алгоритму для розв`язання задачі мінімізації негладкої функції, яка є еквів...

Full description

Saved in:

Bibliographic Details
Date:	2021
Main Authors:	Стецюк, П.І., Стецюк, М.Г., Брагін, Д.О., Молодик, М.О.
Format:	Article
Language:	Ukrainian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2021
Series:	Кібернетика та комп’ютерні технології
Subjects:	Методи оптимізації та екстремальні задачі
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/179351
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Використання r-алгоритму Шора в лінійних задачах робастної оптимізації / П.І. Стецюк, М.Г. Стецюк, Д.О. Брагін, М.О. Молодик // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2021. — № 1. — С. 29-42. — Бібліогр.: 12 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-179351
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1793512025-02-09T21:17:41Z Використання r-алгоритму Шора в лінійних задачах робастної оптимізації Использование r-алгоритма Шора в линейных задачах робастной оптимизации Use of the Shor’s r-algorithm in linear robust optimization problems Стецюк, П.І. Стецюк, М.Г. Брагін, Д.О. Молодик, М.О. Методи оптимізації та екстремальні задачі Cтаття присвячена опису нового підходу до побудови алгоритмів розв’язання задач лінійного програмування (ЛП-задач), у яких кількість обмежень є значно більшою за кількість змінних. Він базується на використанні модифікації r-алгоритму для розв`язання задачі мінімізації негладкої функції, яка є еквівалентною ЛП-задачі. Переваги підходу продемонстровані на лінійній задачі робастної оптимізації та задачі робастної оцінки параметрів за допомогою методу найменших модулів. Розроблені octave-програми призначені для розв’язання ЛП-задач з дуже великою кількістю обмежень, для яких використання стандартного програмного забезпечення з лінійного програмування є або неможливим або недоцільним, адже вимагає значних обчислювальних ресурсів. Статья посвящена описанию нового подхода к построению алгоритмов решения задач линейного программирования (ЛП-задач), в которых количество ограничений значительно больше числа переменных. Он базируется на использовании модификации r-алгоритма для решения задачи минимизации негладкой функции, эквивалентной ЛП-задаче. Преимущества подхода продемонстрированы на линейной задаче робастной оптимизации и задаче робастной оценки параметров с помощью метода наименьших модулей. Разработанные octave-программы предназначены для решения ЛП-задач с очень большим количеством ограничений, для которых использование стандартного программного обеспечения линейного программирования является или невозможным или нецелесообразным, так как требует значительных вычислительных ресурсов. The paper is devoted to the description of a new approach to the construction of algorithms for solving linear programming problems (LP-problems), in which the number of constraints is much greater than the number of variables. It is based on the use of a modification of the r-algorithm to solve the problem of minimizing a nonsmooth function, which is equivalent to LP problem. The advantages of the approach are demonstrated on the linear robust optimization problem and the robust parameters estimation problem using the least moduli method. The developed octave programs are designed to solve LP problems with a very large number of constraints, for which the use of standard software from linear programming is either impossible or impractical, because it requires significant computing resources. 2021 Article Використання r-алгоритму Шора в лінійних задачах робастної оптимізації / П.І. Стецюк, М.Г. Стецюк, Д.О. Брагін, М.О. Молодик // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2021. — № 1. — С. 29-42. — Бібліогр.: 12 назв. — укр. DOI: https://doi.org/10.34229/2707-451X.21.1.3 2707-4501 https://nasplib.isofts.kiev.ua/handle/123456789/179351 519.85 uk Кібернетика та комп’ютерні технології application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Методи оптимізації та екстремальні задачі Методи оптимізації та екстремальні задачі
spellingShingle	Методи оптимізації та екстремальні задачі Методи оптимізації та екстремальні задачі Стецюк, П.І. Стецюк, М.Г. Брагін, Д.О. Молодик, М.О. Використання r-алгоритму Шора в лінійних задачах робастної оптимізації Кібернетика та комп’ютерні технології
description	Cтаття присвячена опису нового підходу до побудови алгоритмів розв’язання задач лінійного програмування (ЛП-задач), у яких кількість обмежень є значно більшою за кількість змінних. Він базується на використанні модифікації r-алгоритму для розв`язання задачі мінімізації негладкої функції, яка є еквівалентною ЛП-задачі. Переваги підходу продемонстровані на лінійній задачі робастної оптимізації та задачі робастної оцінки параметрів за допомогою методу найменших модулів. Розроблені octave-програми призначені для розв’язання ЛП-задач з дуже великою кількістю обмежень, для яких використання стандартного програмного забезпечення з лінійного програмування є або неможливим або недоцільним, адже вимагає значних обчислювальних ресурсів.
format	Article
author	Стецюк, П.І. Стецюк, М.Г. Брагін, Д.О. Молодик, М.О.
author_facet	Стецюк, П.І. Стецюк, М.Г. Брагін, Д.О. Молодик, М.О.
author_sort	Стецюк, П.І.
title	Використання r-алгоритму Шора в лінійних задачах робастної оптимізації
title_short	Використання r-алгоритму Шора в лінійних задачах робастної оптимізації
title_full	Використання r-алгоритму Шора в лінійних задачах робастної оптимізації
title_fullStr	Використання r-алгоритму Шора в лінійних задачах робастної оптимізації
title_full_unstemmed	Використання r-алгоритму Шора в лінійних задачах робастної оптимізації
title_sort	використання r-алгоритму шора в лінійних задачах робастної оптимізації
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2021
topic_facet	Методи оптимізації та екстремальні задачі
url	https://nasplib.isofts.kiev.ua/handle/123456789/179351
citation_txt	Використання r-алгоритму Шора в лінійних задачах робастної оптимізації / П.І. Стецюк, М.Г. Стецюк, Д.О. Брагін, М.О. Молодик // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2021. — № 1. — С. 29-42. — Бібліогр.: 12 назв. — укр.
series	Кібернетика та комп’ютерні технології
work_keys_str_mv	AT stecûkpí vikoristannâralgoritmušoravlíníinihzadačahrobastnoíoptimízacíí AT stecûkmg vikoristannâralgoritmušoravlíníinihzadačahrobastnoíoptimízacíí AT bragíndo vikoristannâralgoritmušoravlíníinihzadačahrobastnoíoptimízacíí AT molodikmo vikoristannâralgoritmušoravlíníinihzadačahrobastnoíoptimízacíí AT stecûkpí ispolʹzovanieralgoritmašoravlineinyhzadačahrobastnoioptimizacii AT stecûkmg ispolʹzovanieralgoritmašoravlineinyhzadačahrobastnoioptimizacii AT bragíndo ispolʹzovanieralgoritmašoravlineinyhzadačahrobastnoioptimizacii AT molodikmo ispolʹzovanieralgoritmašoravlineinyhzadačahrobastnoioptimizacii AT stecûkpí useoftheshorsralgorithminlinearrobustoptimizationproblems AT stecûkmg useoftheshorsralgorithminlinearrobustoptimizationproblems AT bragíndo useoftheshorsralgorithminlinearrobustoptimizationproblems AT molodikmo useoftheshorsralgorithminlinearrobustoptimizationproblems
first_indexed	2025-11-30T22:14:13Z
last_indexed	2025-11-30T22:14:13Z
_version_	1850255191351230464
fulltext	МЕТОДИ ОПТИМІЗАЦІЇ ТА ЕКСТРЕМАЛЬНІ ЗАДАЧІ ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.1 29 КІБЕРНЕТИКА та КОМП'ЮТЕРНІ ТЕХНОЛОГІЇ Робота присвячена опису нового підходу до побудови алгоритмів розв’язання задач ліній- ного програмування, у яких кількість обме- жень є значно більшою за кількість змінних. Він базується на використанні r-алгоритмів для розв`язання задачі мінімізації негладкої функції, яка є еквівалентною задачі лінійного програмування. Переваги підходу продемон- стровані на лінійній задачі робастної опти- мізації та задачі робастної оцінки парамет- рів за допомогою методу найменших модулів. Розроблені octave-програми призначені для розв’язання задач лінійного програмування, для яких використання стандартного про- грамного забезпечення є або неможливим, або недоцільним, адже вимагає значних об- числювальних ресурсів. Ключові слова: робастна оптимізація, зада- ча лінійного програмування, негладка штра- фна функція, r-алгоритм, метод найменших модулів, GNU Octave.   П.І. Стецюк, М.Г. Стецюк, Д.О. Брагін, М.О. Молодик, 2021 УДК 519.85 DOI:10.34229/2707-451X.21.1.3 П.І. СТЕЦЮК, М.Г. СТЕЦЮК, Д.О. БРАГІН, М.О. МОЛОДИК ВИКОРИСТАННЯ r-АЛГОРИТМУ ШОРА В ЛІНІЙНИХ ЗАДАЧАХ РОБАСТНОЇ ОПТИМІЗАЦІЇ Вступ. Задачі робастної оптимізації (задачі з невизна- ченістю у даних) є звичайними задачами математич- ного програмування, де цільова функція та обмеження залежать від невизначеної величини [1, 2]. Оптималь- ний розв’язок робастної задачі є «абсолютно надій- ним» у тому сенсі, що він вимагає виконання обме- жень при умові, що невизначені дані  не виходять за межі множини U (множини невизначеності). У статті розглянемо окремий випадок лінійної задачі робаст- ної оптимізації [3], яка має такий вигляд: max n T x c c x   R , (1)   ,A x b U   (2) 0,x  (3) де матриця обмежень  A  залежить від lU  R . Задача (1) – (3) – задача лінійного програмування (ЛП-задача) з нескінченною системою обмежень, як- що множина U є нескінченною. Якщо множина U – скінченна та містить сотні тисяч або мільйони реалізацій вектора  , то ЛП-задача (1) – (3) буде характеризуватися невеликою кількістю змінних та дуже великою кількістю обмежень (від сотень тисяч до декількох мільйонів). Для розв’язання таких задач використання стандартного програмного забезпечен- ня з ЛП є або неможливим, або недоцільним, адже вимагає значних обчислювальних ресурсів. У статті обговоримо спосіб побудови алгоритмів розв’язання ЛП-задач, у яких кількість обмежень значно більша за кількість змінних. Цей спосіб описа- ний у розділі 2 та базується на негладкій штрафній функції, та виборі параметра штрафу, який забезпечує еквівалентність ЛП-задачі і задачі мінімізації штраф- ної функції, яка розв’язується за допомогою модифі- кації r-алгоритму Шора [4, 5] (описана у розділі 1). Ця модифікація використана в статті для Octave- реалізації методу найменших модулів, який є робаст- ним до аномальних спостережень або «викидів» (розділ 3). https://doi.org/10.34229/2707-451X.21.1.3 П.І. СТЕЦЮК, М.Г. СТЕЦЮК, Д.О. БРАГІН, М.О. МОЛОДИК 30 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 1 1. Модифікація r(α)-алгоритму з адаптивним кроком. Розглядається задача пошуку точки мінімуму опуклої функції ( )f x , nxR . Мінімальне значення функції позначимо * ( )f f x , де x X . Нехай 1  – коефіцієнт розтягу простору. Означення. ( )r  -алгоритмом мінімізації функції ( )f x називається ітеративна процедура знаходження послідовності n -вимірних векторів 0{ }k kx   та послідовності n n -матриць 0{ }k kB   за таким правилом: 1 1, ( ), 0,1,2, ,k k k k k k k kx x h B B B R k         (4) де 0 ( ) , arg min ( ), ( ) T k f k k k k k k kT h k f k B g x h h f x hB B g x        (5) 1, ( ) ( ). T k k k k f k f kT k k B r r g x g x B r     (6) Тут 0x – стартова точка, 0 nB I – одинична n n -матриця1, * kh – величина кроку до точки мінімуму функції ( )f x , ( ) ( 1) T nR I       – оператор стиснення простору субградієнтів у нормованому напрямку  з коефіцієнтом 1 1  , ( )f kg x і 1( )f kg x  – субградієнти функції ( )f x у точках kx та 1kx  . Якщо на ітерації k процесу (4) – (5) виконані критерії (умови) зупинки, то вважаємо k k , k kx x і закінчуємо роботу алгоритму. Коментар. На кожній ітерації r -алгоритмів реалізується субградієнтний спуск для опуклої функції ( ) ( )ky f B y  у перетвореному просторі змінних ky A x , де 1 k kA B . Дійсно, якщо обидві частини формули 1k k k k kx x h B    домножити зліва на матрицю kA , то отримаємо 1 1 ( ) ( ) , ( )( ) T k f k k k k k k k k k k k k kT kk f k B g x g y y A x A x h y h y h g yB g x             (7) де вектор ( ) ( )T k k f kg y B g x  є субградієнтом функції ( ) ( )ky f B y  у точці k k ky A x простору змінних ky A x . Сімейство ( )r  -алгоритмів визначається коефіцієнтом розтягу простору 1  і послідовністю величин кроків 0{ }k kh   , які визначають ті два послідовні субградієнти ( )f kg x і 1( )f kg x  , розтягу- вання за різницею яких (див. формули (6), (7)) зменшує ступінь витягнутості функції у перетворе- ному просторі змінних. Вибір коефіцієнта 1  та адаптація величин 0{ }k kh   до критеріїв зупинки визначають ті чи інші варіанти ( )r  -алгоритмів. Кількість ітерацій ( )r  -алгоритму, необхідна для знаходження точки k x , для якої ( ) k f x f   , емпірично оцінюється як ( log(1 ))k O n  , де n – кількість змінних. 1 Як матрицю 0B часто вибирають діагональну матрицю nD з додатними коефіцієнтами на діагоналі, за допомогою якої здійснюється масштабування змінних. ВИКОРИСТАННЯ r-АЛГОРИТМУ ШОРА В ЛІНІЙНИХ ЗАДАЧАХ РОБАСТНОЇ ОПТИМІЗАЦІЇ ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.1 31 В практичних реалізаціях ( )r  -алгоритмів зазвичай використовують адаптивний спосіб регу- лювання кроку. Він полягає у тому, що величина kh налаштовується (адаптується) у процесі вико- нання одновимірного спуску, який завершується, як тільки знайдено субградієнт, що утворює негострий кут з субградієнтом, що визначає напрямок одновимірного спуску (умова завершення спуску за напрямом). Налаштування величини kh здійснюється за допомогою чотирьох парамет- рів: 0 0h  – величина початкового кроку (використовується на першій ітерації, а на кожній насту- пній – уточнюється), 1q ( 1 1q  ) – коефіцієнт зменшення кроку (якщо умова завершення спуску за напрямком виконується за перший крок), 2q ( 2 1q  ) – коефіцієнт збільшення кроку. Через кожні hn кроків одновимірного спуску ( 1hn  ) величина кроку збільшується в 2q раз. Якщо множина мінімумів X – обмежена, то після скінченної кількості кроків адаптивного спуску в напрямку нормованого антисубградієнта обов’язково виконується умова завершення спуску за напрямом. Для зупинки ітераційного процесу використовуються параметри x і g – алгоритм закінчує роботу в точці 1[ , ]k kk x x x  , якщо 1k k xx x    (зупинка за аргументом), або ( )f gk g x   (зупинка за нормою градієнта, яка використовується для гладких функцій). Використовуються також стандартна зупинка, якщо перевищено задану максимальну кількість ітерацій maxitn, та аварійна зупинка, яка сигналізує про те, що або функція ( )f x не є обмеженою знизу, або початко- вий крок 0h занадто малий, і його потрібно збільшити. Програмна реалізація ( )r  -алгоритму з адаптивним регулюванням кроку за формулами (4) – (6) виконана двома оctave-функціями: ralgb5a [6] та ralgb5 [7]. Тут абревіатура "b5" означає, що в їх основу покладено r -алгоритм у B -формі, де коректується n n -матриця B , а кожна ітерація вимагає 25n арифметичних операцій множення, які визначають обчислювальну трудоєм- ність однієї ітерації. Функція ralgb5a – спрощена (для зручності використання) версія ralgb5, для якої зафіксовані два найбільш часто вживані параметри 2 1.1q  і 3hn  . Окрім цього, у функції ralgb5a також використовується параметр intp (interval for print), який забезпечує друк інформації про хід процесу мінімізації через кожні intp ітерацій. Цей параметр дозволяє скоротити протокол роботи програми при мінімізації функції для сотень і тисяч змінних, коли кількість ітерацій оцінюється тисячами і десятками тисяч. Якщо ітераційний процес запускається зі стартової точки 0x , то параметри ( )r  -алгоритму рекомендується вибирати наступними: [2,4] , 1 1.0q  (для негладких функцій), 1 0.8 0.95q   (для гладких функцій), 0 0h x x  – оцінка відстані від стартової точки 0x до точки мінімуму x . Як правило, використовуються такі параметри зупинки: 610x   , 1210g   , maxitn 20n . Тут параметр g використовується для гладких функцій, а параметр x – для негладких функцій. При правильному виборі параметрів  , 0h та 1q можна значно скоротити кількість ітерацій для виконання одних і тих самих критеріїв зупинки x та g . Це залежить від конкретного виду функції, що мінімізується, ступеня її яружності та масштабу змінних. У статті Octave-функція ralgb5a доповнена параметром im: якщо im=1, то rx – наближення до точки мінімуму опуклої функції ( )f x , якщо im=-1, то rx – наближення до точки максимуму увігнутої функції ( )f x . Вона використовує Оctave-функцію function [f, g] = calcfg (x), яка обчислює значення функції ( )f f x та її субградієнта (суперградієнта) ( )fg g x в точці x . Ця функція готується користувачем та може мати довільне ім'я, яке підтримує синтаксис Оctave. П.І. СТЕЦЮК, М.Г. СТЕЦЮК, Д.О. БРАГІН, М.О. МОЛОДИК 32 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 1 Код модернізованої Octave-функції ralgb5a, який включає короткі англомовні коментарі для вхідних та вихідних параметрів, наведено далі. # Octave-function ralgb5a (Petro Stetsyuk, 07 February 2021) #rowc01 # Input parameters: #rowc02 # calcfg -- name of the function calcfg(x) for calculation #rowc03 # of f(x) and its sub(super)gradient g(x), #rowc04 # im -– minimize(im = 1), maximize(im = -1), #rowc05 # x -- starting point (it is modified in the program), x(1:n) #rowc06 # alpha -- coefficient of space dilation (alpha = 2:4) #rowc07 # h0, q1 -- parameters of the adaptive step adjustment, #rowc08 # recommend: h0=1, q1=1.0 - nonsmooth, q1=0.8:0.95 - smooth #rowc09 # epsx, epsg, maxitn -- stop parameters #rowc10 # intp -- print information for every intp iteration #rowc11 # Output parameters: #rowc12 # xr -- record point (with the best function value), xr(1:n) #rowc13 # fr -- the value of the function f at the point xr #rowc14 # itn -- the number of iterations #rowc15 # nfg -- the number of function calcfg calls #rowc16 # ist -- exit code: 2-epsg, 3-epsx, 4-maxitn, 5-warning #rowc17 # For more details see: Stetsyuk, P.I. Theory and Software #rowc18 # Implementations of Shor's r-Algorithms. Cybernetics and #rowc19 # Systems Analysis 53, 692-703 (2017) #rowc20 # function [xr,fr,itn,nfg,ist] = ralgb5a(calcfg,im,x,alpha,h0,q1, #row001 epsg,epsx,maxitn,intp), #row002 itn = 0, B = eye(length(x)), hs = h0, lsa = 0, lsm = 0, #row003 xr = x, [fr,g0] = calcfg(xr), nfg = 1, #row004 if (intp>0) #row005 printf("itn%5d f%15.6e fr%15.6e nfg%5d\n",itn,fr,fr,nfg), #row006 endif #row007 if(norm(g0) < epsg) ist = 2, return, endif #row008 for (itn = 1:maxitn) #row009 dx = B (g1 = B' * g0)/norm(g1), #row010 d = 1, ls = 0, ddx = 0, #row011 while (d > 0) #row012 x -= imhs dx, ddx += hs * norm(dx), #row013 [f, g1] = calcfg(x), nfg ++, #row014 if (imf < imfr) fr = f, xr = x, endif #row015 if(norm(g1) < epsg) ist = 2, return, endif #row016 ls ++, (mod(ls,3) == 0) && (hs = 1.1), #row017 if(ls > 500) ist = 5, return, endif #row018 d = dx' g1, #row019 endwhile #row020 (ls == 1) && (hs = q1), lsa=lsa+ls, lsm=max(lsm,ls), #row021 if(mod(itn,intp)==0) #row022 if (intp>0) #row023 printf("itn %4d f %14.6e fr %14.6e", itn, f, fr), #row024 printf(" nfg %4d lsa %3d lsm %3d\n", nfg, lsa, lsm), #row025 endif #row026 lsa=0, lsm=0, #row027 endif #row028 if(ddx < epsx) ist = 3, return, endif #row029 xi = (dg = B' (g1 - g0) )/norm(dg), #row030 B += (1 / alpha - 1) * B * xi * xi', #row031 g0 = g1, #row032 endfor #row033 ist = 4, #row034 endfunction #row035 ВИКОРИСТАННЯ r-АЛГОРИТМУ ШОРА В ЛІНІЙНИХ ЗАДАЧАХ РОБАСТНОЇ ОПТИМІЗАЦІЇ ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.1 33 2. r(α)-алгоритм для ЛП-задачі ( m n ). Розглянемо ЛП-задачу, яка полягає у максимізації лінійної функції ( ) Tс x c x при лінійних нерівностях Ax b та 0x  , де ncR – вектор коефіціє- нтів цільової функції, nxR – вектор невідомих (змінних),   m n ijA a  R – матриця обмежень, mbR – вектор правих частин. За допомогою цієї ЛП-задачі можна розв’язувати лінійні робастні задачі вигляду (1) – (3), якщо множина U – скінченна та містить сотні тисяч або мільйони реаліза- цій вектора  . Зауважимо, що для розв’язання таких ЛП-задач використання стандартного програ- много забезпечення з лінійного програмування є або неможливим або недоцільним, адже вимагає значних обчислювальних ресурсів. У загальній формі формулювання нашої ЛП-задачі має такий вигляд: знайти 1 ( ) max n n j j x j с с x c x R при обмеженнях 1 , 1, , , 0, 1, , , n ij j i j j a x b i m x j n        (8) де с – максимальне значення цільової функції, nx X R – точка максимуму, X – непорож- ня множина максимумів. Формулювання ЛП-задачі (8) у матричній формі має такий вигляд: знайти max n T x с c x R при обмеженнях , 0.Ax b x  (9) Особливістю ЛП-задач (8) та (9) будемо вважати те, що для них m n , тобто кількість лінійних обмежень у цих задачах значно більша за кількість невід’ємних змінних. За допомогою методу негладких штрафних функцій для задачі (8), а також і для задачі (9), побудуємо еквівалентну допоміжну задачу, яка є задачею безумовної максимізації негладкої увігнутої функції. Для врахування лінійних обмежень Ax b та 0x  будемо використовувати штрафну функцію у формі функції максимуму. Нехай 0P – штрафний коефіцієнт. Розглянемо штрафну функцію   1,... 1,... 1 ( ) max 0, max , max n T P ij j i j i m j n j с x c x P a x b x                        (10) та відповідну їй задачу оптимізації ( ) max ( ) nP P P P x R с c x c x     , (11) де Pс – максимальне значення функції ( )Pс x , P Px X  – точка максимуму, n PX   R – множина максимумів функції ( )Pс x . Задача (11) – задача безумовної максимізації увігнутої кусочно-лінійної функції ( )Pс x , суперградієнт якої у точці x обчислюється за формулою: 1 2 * * 1 2 11 * * 2 1 2 0, якщо 0 та 0, ( ) ( ,..., ) , якщо та 0, , якщо та 0, P T с i i n j t t g x c P a a t t t e t t t                      (12) де j e  – j -ий орт, а індекси i та j визначаються за наступним правилом: 1 1 1 : , 1,..., n n j ij j ii j i j j i t a x b a x b i m             , 2: , 1,...,jj j t x x j n         . П.І. СТЕЦЮК, М.Г. СТЕЦЮК, Д.О. БРАГІН, М.О. МОЛОДИК 34 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 1 Розглянемо пару взаємно двоїстих ЛП-задач, де пряма ЛП-задача має вигляд: знайти min n T x с c x R при обмеженнях , 0,Ax b x   (13) а двоїста ЛП-задача має такий вигляд: знайти , 0 1 max ( ) m m i i j с b R при обмеженнях 1 , 0, 1, , . m ij i j j j i a c j n         (14) Зауважимо, що задача (13) має таку ж множину оптимальних розв’язків, як і задачі (8) та (9), а оптимальні значення цільових функцій у цих задачах зв’язані співвідношенням c c   . Припустимо, що ЛП-задача (8) має множину оптимальних розв’язків nX  R , а для задач (13) та (14) відомі оптимальні множники Лагранжа * * 1 0,..., 0m    , які відповідають обмеженням Ax b , та множники Лагранжа * * 1 0,..., 0n    , які відповідають обмеженням 0x  . Теорема 1. Якщо * * 1 1 m n i i i i P P         , то * * Pc c . Якщо P P , то тоді довільна точка P Px X X    , тобто Px – оптимальний розв'язок задачі (8). Дана теорема – наслідок застосування теореми 27 [8, стор. 23] до ЛП-задачі (13), для якої штрафна функція є опуклою кусково-лінійною функцією та має вигляд   1,... 1,... 1 ( ) max 0, max , max , n T P ij j i j i m j n j с x c x P a x b x                         (15) де штрафний коефіцієнт 0P . Враховуючи, що ( ) ( )P Pc x с x  , отримуємо увігнуту кусково- лінійну штрафну функцію ( )Pc x вигляду (10). Теорема 1 встановлює нижню границю P на значення штрафного коефіцієнта, при якому задача (11) – еквівалентна ЛП-задачі (8), а значить еквівалентна і ЛП-задачі (9). Якщо значення штрафного коефіцієнта P вибрати більшим за P та розв’язати допоміжну задачу (11), то отрима- ємо розв’язок задачі (8). Той чи інший метод розв’язання задачі (11), яка є задачею безумовної максимізації негладкої увігнутої функції, забезпечує розв’язання ЛП-задачі (8). Допоміжну задачу (11) від декількох сотень змінних можна ефективно розв’язувати за допомогою r-алгоритму Шора, що означає, що використання Octave-функції ralgb5a забезпечить ефективне розв’язання ЛП-задач, у яких кількість обмежень m є значно більшою за кількість змінних 100n . Далі покажемо, що за 10 – 15 хвилин на сучасних ПЕОМ реалістично розв’язувати ЛП-задачі, в яких щільно заповнена матриця A містить 500 мільйонів елементів та вимагає 4 ГБ оперативної пам’яті для їх зберігання, якщо один елемент матриці займає 8 байт. Octave-функція ralgb5a використовує оракул, який для заданої точки x знаходить максималь- но порушене обмеження ЛП-задачі (8) і визначає значення функції ( )Pс x та її суперградієнта ( ) Pсg x . Обчислення ( )Pс x за формулою (10) та ( ) Pсg x за формулою (12) реалізує оctave-функція fgLP8(x), для якої n -вимірний вектор x – вектор змінних задачі (8) передається як формальний параметр, а вхідні дані задачі (8) передаються через загальну пам’ять як глобальні змінні. Код оctave-функції fgLP8 є таким: ВИКОРИСТАННЯ r-АЛГОРИТМУ ШОРА В ЛІНІЙНИХ ЗАДАЧАХ РОБАСТНОЇ ОПТИМІЗАЦІЇ ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.1 35 function [f,g] = fgLP8(x) global c A b n m P f = sum(c.x), g = c, tmp1 = Ax, tmp2 = [tmp1 - b, -x ], [tmpmax imax] = max(tmp2), if (tmpmax > 0.d0) if (imax <= m) f = f - Ptmpmax, g = g - PA(imax,1:n)', else f = f - Ptmpmax, itemp = imax-m, g(itemp,1) = g(itemp,1) + P, endif endif endfunction #fgLP8 Вхідні дані задачі (8) для octave-функції fgLP8 – наступні: c – вектор коефіцієнтів цільової функції, A – матриця обмежень, b – вектор правих частин, n – кількість змінних, m – кількість обмежень, P – штрафний коефіцієнт. Далі опишемо два обчислювальні експерименти для розв’язання тестових ЛП-задач з великою кількістю обмежень (від двохсот тисяч до п’ятдесяти мільйонів) та невеликою кількістю змінних (від десяти до п’ятдесяти). Умовимось називати їх ЛП-експериментами. Обидва ЛП-експерименти проводились на комп’ютері з процесором Intel Core i5-9400f з тактовою частотою 2,9 ГГц та 16 ГБ оперативної пам’яті. Мета першого ЛП-експерименту – порівняння результатів роботи r-алгоритму з результатами, отриманими за допомогою octave-функції glpk [9], яка для розв’язання ЛП-задач використовує відому бібліотеку GLPK [10]. Тут для програми ralgb5a використовувалася стартова точка 0 0x  , параметри ( )r  -алгоритму: 4  , 1 1.0q  , 0 20.0h  та параметри зупинки: 610x   , 810g   , maxitn =1500, intp =100. Вхідні дані для ЛП-задач вигляду (8) генерувалися випадковим чином з стандартним рівномірним розподілом (0,1)U за наступними формулами: c = rand(n,1), A = ones(m,n) + rand(m,n), b = Aones(n,1). ЛП-задачі характеризуються малою кількістю змінних 10; 20; 50n та дуже великою кількістю обмежень 200.000; 500.000;1.000.000m . Штрафний коефіцієнт P вибирався на одиницю більшим за його нижню межу (див. теорему 1), для чого розв’язувалася ЛП-задача (14) за допомогою octave-функції glpk. Затрати часу glpk (« 1t ») та ralgb5a (« 2t ») на розв’язання задач (8) та (11), абсолютна величина відхилень * Pdc с с  для отриманих розв’язків (« dc »), затрачена ralgb5a кількість ітерацій (« itn ») і обчислень функції та суперградієнта (« nfg ») при вибраних значеннях штрафного коефіці- єнта (« P ») наведені в табл. 1. П.І. СТЕЦЮК, М.Г. СТЕЦЮК, Д.О. БРАГІН, М.О. МОЛОДИК 36 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 1 ТАБЛИЦЯ 1. Перший ЛП-експеримент: затрати для функцій glpk ( 1t ) та ralgb5 ( 2t , itn , nfg ) n m 1t (сек) 2t (сек) 1 2t t dc itn nfg P 10 200000 1.27 0.83 1.53 1.41e-07 152 282 2.22 500000 3.13 3.96 0.79 2.32e-07 194 513 2.89 1000000 6.12 4.29 1.43 7.06e-08 159 273 2.93 20 200000 2.88 2.40 1.20 3.19e-08 387 662 4.45 500000 7.08 6.60 1.07 9.26e-08 393 709 4.61 1000000 14.41 10.34 1.39 4.37e-08 343 553 4.63 50 200000 9.77 17.10 0.57 2.94e-08 1946 3120 15.06 500000 25.87 32.48 0.80 3.04e-08 1553 2383 13.25 1000000 52.40 59.45 0.88 9.66e-08 1411 2155 13.80 З даної таблиці видно, що для розв'язання відповідних ЛП-задач за допомогою glpk вимагаєть- ся приблизно стільки ж часу, як і для розв’язання допоміжної задачі (11) за допомогою ralgb5a. Результати колонки « dc » показують, що відхилення між розв’язками ЛП-задачі та допоміжної задачі є дуже малими, що означає, що обидві програми збігаються до одного і того ж єдиного розв’язку для кожної з тестових ЛП-задач. Мета другого ЛП-експерименту – оцінка часу програми ralgb5a для розв’язання таких же ЛП-задач, як і в першому експерименті, де матриця A містить 500 мільйонів елементів. Враховуючи, що для зберігання такої матриці потрібно 4 ГБ оперативної пам’яті (вважається, що один елемент мат- риці займає 8 байт), то цю ЛП-задачу умовимось називати «4ГБ-задачею». Параметри ( )r  -алгоритма для другого ЛП-експерименту вибиралися такими ж як і для першого, за винятком 3  . Штрафний коефіцієнт P вибирався рівним 50. Другий експеримент реалізує наведений далі Octave -код. # Code for time of ralgb5a for 4Gb-problems global c A b n m P printf("\n"), # set parameters for r-algorithm alpha = 3.0, h0 = 20.0, q1 = 1.0, epsx = 1.e-6, epsg = 1.e-8, maxitn = 1500, intp = 200, nmtest = [ 50 10000000, 20 25000000, 10 50000000], P = 50, rand("seed", 2020), time12 = fopt = itna = [], for itest = 1:rows(nmtest) printf("\n"), # set test example n = nmtest(itest,1), m = nmtest(itest,2), c = rand(n,1), A = ones(m,n)+rand(m,n), x0 = ones(n,1), b = Ax0, # set start point and run r-algorithm im = -1, x0 = zeros(n,1), tstart = time(), [xr,fr,itn,nfg,ist]=ralgb5a(@fgLP8,im,x0,alpha,h0,q1, epsg,epsx,maxitn,intp), time1=time()-tstart, printf("..itn %4d fr %23.15e ist %d nfg %4d\n",itn,fr,ist,nfg), fr, ctxr = c'xr, time1, time12 = [time12, time1], fopt = [ fopt, c'xr fr], itna = [itna, itn nfg ist], endfor nmtest, fopt, # print of results printf("\n n m .t1.. ist .itn. .nfg."), for itest = 1:rows(nmtest) n = nmtest(itest,1), m = nmtest(itest,2), t1 = time12(itest,1), printf("\n %3d %6d %7.2f",n,m,t1), itn = itna(itest,1), nfg = itna(itest,2), ist = itna(itest,3), printf(" %2d %5d %5d",ist,itn,nfg), endfor printf("\n"), ВИКОРИСТАННЯ r-АЛГОРИТМУ ШОРА В ЛІНІЙНИХ ЗАДАЧАХ РОБАСТНОЇ ОПТИМІЗАЦІЇ ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.1 37 Результати розрахунків для 50, 20,10n та 10.000.000,25.000.000,50.000.000m наведено в табл. 2, де ist – код завершення роботи програми ralgb5a. ТАБЛИЦЯ 2. Другий ЛП-експеримент: затрати ralgb5a для розв’язання 4ГБ-задач n m time (сек.) itn nfg ist 50 10.000.000 625.75 1500 2310 4 20 25.000.000 479.05 575 1028 3 10 50.000.000 858.45 368 1104 3 З даної таблиці (колонка « time ») видно, що за 10 – 15 хвилин на сучасних ПЕОМ реалістично розв’язувати ЛП-задачі з 10 50n , в яких щільно заповнена матриця A містить 500 мільйонів елементів та вимагає 4 ГБ оперативної пам’яті для їх зберігання. Зауважимо, що Octave-реалізація ralgb5a не претендує на ефективну за часом розв’язання задачі (11). Для неї витрати за часом мож- на зменшити в десятки разів, якщо програму переписати мовою python, для якої бібліотека NumPy працює значно швидше і реалізована на С і Fortran (переважно матричні операції) й спирається на коди бібліотек BLAS, ATLAS та LAPACK. 3. Метод найменших модулів ( m n ). Нехай для оцінки n невідомих параметрів 1,.., nx x використовується m спостережень 1 ,,.. my y причому ці величини пов'язані співвідношенням: 1 , 1,..., n i ij j i j y a x u i m     , (16) де ija – відомі коефіцієнти, iu – невідомі випадкові величини, що мають (приблизно) однакові функції розподілу. Рівняння (16) можна записати в матричній формі: y Ax u  , (17) де  1,.., T m my y y R і  1,.., T m mu u u R – m -вимірні вектори, A – матриця розміру m n ,  1,.., T n nxxx  R – m -вимірний вектор параметрів, які потрібно оцінити. У класичній постановці метод найменших модулів (відповідає знаходженню невідомого вектора x згідно з критерієм найменших модулів) – задача математичного програмування:     1 1 min n m n LMM LMM LMM i ij j x i j xf f y xaxf                  R , (18) де  – модуль (абсолютна величина) числа. Задача (18) – безумовна задача мінімізації опуклої кусково-лінійної функції. Зауважимо, що метод найменших модулів є робастним до аномальних спостережень або «викидів» [11, 12]. Задача (18) – безумовна задача мінімізації опуклої кусково-лінійної функції  LMMf x , субградієнт якої у точці x обчислюється за такою формулою: 1 2 1 1 1 1 1 1 ( ) , , , . LMM T m n m n m n f ij j i i ij j i i ij j i in i j i j i j x xg x sign a y a sign a y a xsign a y a                                             (19) П.І. СТЕЦЮК, М.Г. СТЕЦЮК, Д.О. БРАГІН, М.О. МОЛОДИК 38 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 1 Знаходження найкращого за критерієм найменших модулів вектора x , де x – розв’язок задачі (18), можна звести до розв’язання наступної ЛП-задачі: знайти , 10 min n m LMM i z iz f z       R при обмеженнях 1 1 , , 1, , . n n i ij j i ij j j j i iy a y ax z x z i m          (20) Для розв’язання ЛП-задачі (20) можна використовувати відповідні стандартні програми ліній- ного програмування. При цьому паралельно зі знаходженням самого вектора x знаходяться і оптимальні значення вектора   * * 1 ,.., T mz z z , компоненти якого задають оцінки для незалежної випадкової величини , 1,.., .iu i m Далі наведемо результати двох обчислювальних експериментів для розв’язання тестових задач (18) з невеликою кількістю невідомих параметрів (від десяти до ста), де кількість спостережень m n . Будемо їх називати МНМ-експериментами. Обидва МНМ-експерименти проводились на тому ж комп’ютері, що і ЛП-експерименти із розділу 2. Мета першого МНМ-експерименту – порівняння результатів роботи програми ralgb5a з результатами, отриманими за допомогою octave-функції glpk для розв’язання ЛП-задач (20). Для програми ralgb5a використовувалася стартова точка 0 0x  , параметри ( )r  -алгоритму: 3  , 1 0.95q  , 0 5.0h  та параметри зупинки: 810x   , 810g   , maxitn=1500, intp=100. Вхідні дані для задачі (18) генерувалися випадковим чином з стандартним рівномірним розподілом (0,1)U за наступними формулами: A = rand(m,n), b = Aones(n,1), b(m,1) = b(m,1) + 1. Для заданої точки x обчислення  LMMf x та її субградієнта ( ) LMMfg x за формулою (19) реа- лізує оctave-функція fgLMM(x), для якої n -вимірний вектор x передається як формальний пара- метр, а вхідні дані задачі (18) передаються через загальну пам’ять як глобальні змінні. Код оctave- функції fgLMM є таким: function [f,g] = fgLMM(x) global A y n m tmp = Ax - y, f = sum(abs(tmp)), A1 = A.(sign(tmp)ones(1,n)), g1 = sum(A1,1), g = g1', endfunction #fgLMM Вхідні дані задачі (18) для octave-функції fgLMM є наступними: A – матриця відомих коефіці- єнтів, y – вектор результатів спостережень, n – кількість параметрів, m – кількість спостережень. Результати першого МНМ-експерименту – затрати часу glpk (« 1t », « 2t ») на розв’язання задач (19) відповідно прямим та двоїстим симплекс-методами, затрати ralgb5a (« 3t », « itn », « nfg ») на розв’язання задач (18), rx x – норма відхилення знайденого за допомогою ralgb5a наближення до точки мінімуму від відомої точки мінімуму (1,1, ,)Tx наведені в табл. 3. ВИКОРИСТАННЯ r-АЛГОРИТМУ ШОРА В ЛІНІЙНИХ ЗАДАЧАХ РОБАСТНОЇ ОПТИМІЗАЦІЇ ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.1 39 ТАБЛИЦЯ 3. Перший МНМ-експеримент: затрати для функцій glpk ( 1t , 2t ) та ralgb5 ( 3t , ,itn nfg ) n m 1t (сек) 2t (сек) 3t (сек) rx x itn nfg 100 20000 78.65 142.65 10.59 7.59e-09 481 651 10000 16.09 22.29 5.33 6.36e-09 449 584 50 20000 51.81 92.47 4.18 3.26e-09 382 508 10000 5.59 10.40 1.86 4.92e-09 358 456 20 20000 52.89 101.91 1.22 5.72e-09 236 320 10000 4.28 8.54 0.68 2.48e-09 230 305 10 20000 33.87 74.28 0.63 5.82e-09 149 214 10000 4.07 8.17 0.12 5.44e-09 142 188 З даної таблиці видно, що для розв'язання відповідних ЛП-задач за допомогою glpk вимагаєть- ся в десятки разів більше часу, ніж для розв’язання задачі (18) за допомогою ralgb5a. Результати колонки « rx x » показують, що відхилення між знайденим розв’язком задачі (18) та її точкою мінімуму є дуже малим та відповідає параметру 810x   для зупинки r-алгоритма. Мета другого обчислювального МНМ-експерименту – оцінка часу програми ralgb5a для розв’язання задачі (18) з малою кількістю змінних 10; 20; 50;80;100n , де матриця A містить 50 мільйонів елементів, тобто в 10 раз менше, ніж це мало місце для другого ЛП-експерименту. Вра- ховуючи, що для зберігання такої матриці потрібно 400 МБ оперативної пам’яті, то такі задачі для методу найменших модулів будемо називати «4ГБ-задачами». Вхідні дані для задачі (18) генеру- валися за формулами: A = rand(m,n), b = Aones(n,1). Параметри ( )r  -алгоритма для другого МНМ-експерименту вибиралися такими ж як і для першого, за винятком 1 1.0q  та 610x   . Четвертий експеримент реалізує наведений нижче Octave -код. # Code for time of ralgb5a for 400Mb-problems global A y n m printf("\n"), # set parameters for r-algorithm alpha = 3.0, h0 = 5.0, q1 = 1.0, epsx = 1.e-6, epsg = 1.e-8, maxitn = 1500, intp = 100, nmtest = [ 100 500000, 80 625000, 50 1000000, 20 2500000, 10 5000000], rand("seed", 2020), time12 = fopt = itna = [], for itest = 1:rows(nmtest) printf("\n"), # set test example n = nmtest(itest,1), m = nmtest(itest,2), A = ones(m,n)+rand(m,n), x0 = ones(n,1), y = Ax0, # set start point and run r-algorithm im = 1, x0 = zeros(n,1), tstart = time(), [xr,fr,itn,nfg,ist]=ralgb5a(@fgLMM,im,x0,alpha,h0,q1, epsg,epsx,maxitn,intp), time1=time()-tstart, printf("..itn %4d fr %23.15e ist %d nfg %4d\n",itn,fr,ist,nfg), fr, time1, time12 = [time12, time1], fopt = [ fopt, fr norm(xr-ones(n,1))], itna = [itna, itn nfg ist], endfor nmtest, fopt, printf("\n n m .t1.. dx ist .itn. .nfg."), for itest = 1:rows(nmtest) n = nmtest(itest,1), m = nmtest(itest,2), t1 = time12(itest,1), fr = fopt(itest,2), printf("\n %3d %8d %7.2f %9.2e ",n,m,t1,fr), itn = itna(itest,1), nfg = itna(itest,2), ist = itna(itest,3), printf(" %2d %5d %5d",ist,itn,nfg), endfor printf("\n"), П.І. СТЕЦЮК, М.Г. СТЕЦЮК, Д.О. БРАГІН, М.О. МОЛОДИК 40 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 1 Результати розрахунків для 10 100n та 500.000 5.000.000m наведено в табл. 4, де ist – код завершення роботи програми ralgb5a, rx x – норма відхилення знайденого наближення до точки мінімуму від самої точки мінімуму (1,1, ,)Tx . ТАБЛИЦЯ 4. Другий МНМ-експеримент: затрати ralgb5a для розв’язання 400MБ-задач n m time (сек.) itn nfg ist rx x 100 500.000 754.45 1500 1831 4 3.18e-06 80 625.000 689.47 1343 1670 3 6.26e-07 50 1.000.000 441.08 829 1055 3 3.68e-07 20 2.500.000 178.07 312 409 3 5.66e-07 10 5.000.000 96.01 147 198 3 6.60e-07 З колонки « time » даної таблиці видно, що за допомогою сучасних ПЕОМ за десять-двадцять хвилин можна розв’язувати оптимізаційні задачі для методу найменших модулів з невеликою кіль- кістю параметрів ( 10 100n ), якщо матриця A вимагає 400 МБ оперативної пам’яті для збері- гання коефіцієнтів. Зауважимо, що такі розміри матриці A не дозволяють використати стандартне програмне забезпечення з ЛП, так як воно вимагає значних обчислювальних ресурсів із-за збіль- шення кількості змінних в ЛП-задачах вигляду (19). За аналогічною схемою, як і для ЛП-задач у розділі 2, для методу найменших модулів витрати за часом можна значно зменшити, якщо Octave- програми ralgb5a та fgLMM переписати мовою python з використанням бібліотеки NumPy. Затрати програми ralgb5a на розв’язання першої та другої задач з табл. 4 можна суттєво зменшити за рахунок регулювання параметрів r-алгоритму. Так наприклад, якщо замість 1 1.0q  використати 1 0.95q  , то для задачі з 100n та 500.000m затрати програми ralgb5a складають 239.71time  , itn = 411 та nfg = 578, а для задачі з 80n та 625.000m вони складають 258.09time  , itn = 422 та nfg = 626. Висновки. У статті описано новий підхід до побудови алгоритмів розв’язання задач лінійного програмування, у яких кількість обмежень є значно більшою за кількість змінних. Він заснований на використанні r-алгоритмів для розв`язання безумовної задачі мінімізації негладкої штрафної функції, яка є еквівалентною задачі лінійного програмування. Переваги запропонованого підходу продемонстровані на лінійній задачі робастної оптимізації та задачі знаходження робастної оцінки параметрів за допомогою методу найменших модулів. Розроблені octave-програми призначені для розв’язання задач лінійного програмування з дуже великою кількістю обмежень, для яких використання стандартного програмного забезпечення є або неможливим або недоцільним, адже вимагає значних обчислювальних ресурсів. Це дозволить забезпечити розв`язання на сучасних ПЕОМ лінійних задач робастної оптимізації вигляду (1) – (3), у яких множина U – скінченна та містить сотні тисяч або мільйони реалізацій вектора  . Моделі робастних ЛП-задач вигляду (1) – (3) мають місце в економічних застосуваннях. В роботі [3] розглядається задача оптимізації доходу малого підприємства, де цільова функція відображає максимальний дохід підприємства при ресурсних обмеженнях, або інших технологіч- них обмеженнях (наприклад, кількість працівників, кількість робочих годин і т. д). Робастний підхід дає можливість прогнозування розвитку підприємства навіть тоді, коли вхідні параметри мають невизначенi збурення (в роботі [3] збурення сягали 20 % вiд своїх номiнальних значень). ВИКОРИСТАННЯ r-АЛГОРИТМУ ШОРА В ЛІНІЙНИХ ЗАДАЧАХ РОБАСТНОЇ ОПТИМІЗАЦІЇ ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.1 41 В книзі [1] описано приклад максимізації прибутку підприємства, яке виготовляє ліки. На виготовлення партії ліків можна використовувати два види сировини, які мають різну кількість активної речовини і різну вартість. Для виконання плану (визначається кількість упаковок, щоб укомплектувати партію) при застосуванні лінійної оптимізації перевага буде повністю віддана «дешевшій» сировині. Проте, якщо активна речовина видобувається з деяким збуренням з кожного екземпляру сировини (в задачі розглядаються збурення 0,5 % для першого виду і 2 % для другого), то за стратегією лінійної оптимізації, у найгіршому випадку можна отримати не тільки збитки, але й недоукомлектувати партію. Тому при робастному підході буде надаватися перевага «надійності розв’язку» і максимізації доходу і розв’язок може включати не тільки дешевшу «ризиковану» сировину, але дорожчу більш «надійну». Список літератури 1. Ben-Tal A., El Ghaoui L., Nemirovski A. Robust Optimization. Princeton: Princeton Univ. Press, 2009. 576 p. 2. Горяшко А.П., Немировский А.С. Оптимизация стоимости энергии в системах водоснабжения в условиях неопределенности потребления. Автоматика и телемеханика. 2014. Выпуск 10. С. 52–72. 3. Алєксєєва І.В., Перевознюк Т.І. Застосування робастної оптимізації для лінійної моделі функціонування малого підприємства. Mathematics in Modern Technical University. 2018. 1. P. 61–73. https://doi.org/10.20535/mmtu-2018.1-061 4. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979. 200 с. 5. Стецюк П.И. Теория и программные реализации r-алгоритмов Шора. Кибернетика и системный анализ. 2017. № 5. С. 43–57. 6. Стецюк П.И., Фишер А. r–Алгоритмы Шора и octave-функция ralgb5a. Тези міжнародної наукової конференції «Сучасна інформатика: проблеми, досягнення та перспективи розвитку», що присвячена 60-річчю заснуван- ня Інституту кібернетики імені В.М. Глушкова НАН України (Київ, 13–15 грудня 2017). К.: Ін-т кібернетики імені В.М. Глушкова НАН України. 2017. С. 143–146. 7. Стецюк П.И. Субградиентные методы ralgb5 и ralgb4 для минимизации овражных выпуклых функций. Вычис- лительные технологии. 2017. Т. 22, № 2. С. 127–149. 8. Shor N.Z. Non-Differentiable Optimization and Polуnomial Problems. Kluwer Academic Publishers, Boston, Dor- drecht, London. 1998. 412 p. 9. Eaton J.W., Bateman D., Hauberg S. GNU Octave Manual Version 3. Network Theory Ltd. 2008. 568 p. 10. GNU Linear Programming Kit (GLPK). http://www.gnu.org/software/glpk/glpk.html (звернення 12.03.2021) 11. Хьюбер Дж. П. Робастность в статистике. М.: Мир, 1984. 304 с. 12. Стецюк П.И., Колесник Ю.С., Лейбович М.М. О робастности метода наименьших модулей. Компьютерная математика. 2002. С. 114–123. Одержано 12.03.2021 Стецюк Петро Іванович, доктор фізико-математичних наук, завідувач відділу методів негладкої оптимізації Інституту кібернетики імені В.М. Глушкова НАН України, Київ, stetsyukp@gmail.com https://orcid.org/0000-0003-4036-2543 Стецюк Марія Григорівна, інженер-математик відділу методів дискретної оптимізації, математичного моделювання та аналізу складних систем Інституту кібернетики імені В.М. Глушкова НАН України, Київ, danilyukm5@gmail.com Брагін Данііл Олександрович, студент Московського фізико-технічного інституту, Долгопрудний, Московська область, bragin.da@phystech.edu Молодик Микола Олександрович, студент Московського фізико-технічного інституту, Долгопрудний, Московська область. molodyk.na@phystech.edu https://doi.org/10.20535/mmtu-2018.1-061 http://www.gnu.org/software/glpk/glpk.html mailto:stetsyukp@gmail.com https://orcid.org/0000-0003-4036-2543 mailto:danilyukm5@gmail.com П.І. СТЕЦЮК, М.Г. СТЕЦЮК, Д.О. БРАГІН, М.О. МОЛОДИК 42 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 1 UDC 519.85 P.I. Stetsyuk 1 , М.G. Stetsyuk 1, D.А. Bragin 2, N.А. Мolodyk 2 Use of the Shor’s r-Algorithm in Linear Robust Optimization Problems 1 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv 2 Moscow Institute of Physics and Technology, Dolgoprudny, Moscow Region Correspondence: stetsyukp@gmail.com The paper is devoted to the description of a new approach to the construction of algorithms for solving linear programming problems (LP-problems), in which the number of constraints is much greater than the number of variables. It is based on the use of a modification of the r-algorithm to solve the problem of mini- mizing a nonsmooth function, which is equivalent to LP problem. The advantages of the approach are demon- strated on the linear robust optimization problem and the robust parameters estimation problem using the least moduli method. The developed octave programs are designed to solve LP problems with a very large number of constraints, for which the use of standard software from linear programming is either impossible or imprac- tical, because it requires significant computing resources. The material of the paper is presented in three sections. In the first section for the problem of minimizing a convex function we describe a modification of the r-algorithm with a constant coefficient of space dilation in the direction of the difference of two successive subgradients and an adaptive method for step size adjustment in the direction of the antisubgradient in the transformed space of variables. The software implementation of this modification is presented in the form of Octave function ralgb5a, which allows to find or approximation of the minimum point of a convex function, or approximation of the maximum point of the concave function. The code of the ralgb5a function is given with a brief description of its input and output parameters. In the second section, a method for solving the LP problem is presented using a nonsmooth penalty func- tion in the form of maximum function and the construction of an auxiliary problem of unconstrained minimiza- tion of a convex piecewise linear function. The choice of the finite penalty coefficient ensures equivalence be- tween the LP-problem and the auxiliary problem, and the latter is solved using the ralgb5a program. The results of computational experiments in GNU Octave for solving test LP-problems with the number of constraints from two hundred thousand to fifty million and the number of variables from ten to fifty are presented. The third section presents least moduli method that is robust to abnormal observations or "outliers". The method uses the problem of unconstrained minimization of a convex piecewise linear function, and is solved using the ralgb5a program. The results of computational experiments in GNU Octave for solving test problems with a large number of observations (from two hundred thousand to five million) and a small number of un- known parameters (from ten to one hundred) are presented. They demonstrate the superiority of the developed programs over well-known linear programming software such as the GLPK package. Keywords: robust optimization, linear programming problem, nonsmooth penalty function, r-algorithm, least modulus method, GNU Octave. mailto:stetsyukp@gmail.com

Використання r-алгоритму Шора в лінійних задачах робастної оптимізації

Institution

Similar Items