Effective computational procedure of the alternance optimization method

Full Text

Постановка задачи. В современной промышленности широко используется оптимальное управление различными технологическими процессами. Разработка алгоритмов оптимального управления и автоматических систем, их реализующих, непосредственно связана с решением экстремальных задач. Не касаясь вопросов параметризации подобных задач, рассмотренных, например, в работах [1-5], можно, однако, констатировать, что для обширного круга прикладных задач экономики, обработки информации, управления разнообразными техническими и технологическими процессами проблема параметрической оптимизации сводится в постановочном аспекте к задаче полубесконечной оптимизации или полубесконечного программирования [1, 2, 6-10] в евклидовом пространстве как одного из вариантов общей задачи математического программирования: () > min, ; () 6 0. (1) (2) Здесь = (1 , 2 , . . . , ) - -мерный аргумент (параметры); () - условия связи, ограничивающие область поиска экстремума функционала () в евклидовом пространстве . В технологически содержательной постановке задача (1), (2) интерпретируется как минимизация целевой функции (функционала) (), отражающей отклонение от заданного уровня распределения 0 (, ()) некоторой управляемой с помощью параметризованного управления () субстанции - температуры, давления, концентрации и др. К задаче (1), (2) сводятся задачи минимизации времени 0 протекания технологического процесса () = 0 () и другие разнообразные задачи оптимального управления. В отличие от большинства постановочных концепций, особенностью рассматриваемой в статье постановки является бесконечное число ограничений (2) и невыпуклый негладкий вид функционала (1), к которому приводят задачи робастной оптимизации, игровые стратегии, а также технологически обоснованные [1, 3, 4, 11-15] проблемы в производственных процессах промышленной теплофизики - различных видах нагрева, химико-термической обработки и т.п. В силу наличия конечного числа неизвестных параметров и бесконечного числа ограничений (2) такие задачи получили свое название - задачи полубесконечной оптимизации или полубесконечного программирования [1, 2, 6-10]. В связи с изложенным задачу полубесконечной оптимизации как частную форму общей постановки (1), (2) для широко распространенного в технологической практике требования минимизации максимума функции 0 (, ()) при заданном или минимальном значении бесконечного числа () ограничений на уровне 0 или min , соответственно, будем формулировать так же, как в работах [1, 2, 16]: } { () = max 0 (, ()) : , > 1 > min, (3) () , , > 1; { } () = max (, ()) : , > 1 6 0 > 0, (4) { } () 0 > min = inf () : ; () = (1 (), . . . , (), . . . , ()) . (5) Здесь () - критерий оптимальности; () - параметризованная векторфункция управления, определенная на множестве своих значений ; - замкнутое непустое компактное множество параметров в ; и - компактные множества в и соответственно; функции 0 (, ()) и (, ()) - гладкие функции своих переменных на пересечениях и . При этом задача (3), (4) для заданной функции (, ()) не выходит за рамки общей постановки (1), (2), так как { } { } max (, ()) 0 : = max (, ()) : 0 (см. [1, 2]), а ограничения (2) эквивалентны условию (4): { } () = max (, ()) : , [ ] max = (1 , . . . , , . . . , ) , min , (6) (7) в случае бесконечного числа функциональных ограничений в форме неравенств (, ()) 6 0, , , () . (8) Отметим, что переменные и в прикладных задачах могут совпадать, не совпадать, совпадать частично, быть взаимозависимыми и т.п. Например, может иметь физический смысл температуры, а - смысл термонапряжений в определенном сечении нагреваемой детали. К экстремальной задаче полубесконечной оптимизации (3), (4) сводятся, как показано в [1], многочисленные прикладные проблемы оптимизации объектов с распределенными и сосредоточенными параметрам и другие задачи управления. Частным случаем задачи (3), (4) является известная [1, 11] задача оптимального по Чебышевской норме индукционного нагрева достаточно длинного стержня единичного радиуса : (, ) = max (, 0 ) * () > min; [0, 1] 0 = () . (9) =1 Для этого процесса 2 1 (, ())= = 2 (, )(), (10) (0, 1), (0, 0 ], а бесконечное число ограничений (6) принимает безразмерную форму краевой задачи при краевых условиях () = 0, (0, ) = 0, (, 0 ) = 0 ; (11) = Bi [ () (1, )] и является отражением того, что в бесконечном числе точек радиуса стержня относительная температура (, ) в любой момент относительного времени должна быть связана уравнением теплопроводности (10), (11). Здесь Bi - критерий Био (Bi = const); () - безразмерная температура окружающей стержень среды; (, ) - распределение теплоисточников по радиусу стержня ; зависящее от параметра , связанного с частотой питающего индуктор тока; - относительное время (критерий Фурье); () () - мощность () внутренних индуцированных теплоисточников, = { }=1,, - парамет=1, ры оптимального управления, подлежащие определению в ходе решения за() дачи; < , < . В рассматриваемом примере [0, 0] - продолжительность периода включения ( = 1, 3, 5, . . . ) и отключения ( = 2, 4, 6, . . . ) индуктора от питающей сети; - количество циклов включения-отключения в каждом -ом классе управлений. Подробно пример описан в работе [11], а здесь приведен как частная содержательная иллюстрация общей постановки задачи (3), (7), (8). Поставленная задача (3), (7), (8) в общем случае представляет собой с вычислительной точки зрения сложную нелинейную негладкую минимаксную задачу математического программирования, хотя для решения конкретных прикладных проблем ее удается модифицировать к более простым вариантам с конкретного вида функциями (, ()), (), 0 (, ()), () и областями , , , . При этом поставленную задачу (3), (7), (8) в условиях { } () 0 > min = inf () : в частных случаях можно интерпретировать } { () как задачу быстродействия, а в условиях 0 = min = inf () : - как задачу максимальной точности [1]. Для решения подобных задач используются варианты и модификации генетических алгоритмов [17], методов случайного поиска [18-21], симплексметодов [22, 23] и другие прямые численные методы [24-26]. По нашему мнению, наиболее эффективным является метод сведения экстремальной задачи (3)-(5) к решению системы нелинейных уравнений. Этот метод для широкого круга задач разработан в трудах Э. Я. Рапопорта [1, 2] и получил название «альтернансный метод оптимизации» (АМО). Однако вычислительная процедура АМО, хотя и проще исходной, но все же достаточно затруднительна в силу того, что сводится к решению, как правило, трансцендентной системы определяющих уравнений эффективным и достаточно универсальным вычислительным методом. Рассмотрим возможности снижения вычислительной сложности поисковой процедуры для решения задачи (3)-(5) безотносительно к ее содержательной технологической постановке. В любом случае, как в ходе использования прямых вычислительных процедур решения задачи (3)-(5) поиска экстремума функционала (3), так и для численного решения системы соответ ствующих нелинейных уравнений АМО, проблема сводится к минимизации, в общем случае, невыпуклого негладкого функционала () > min в условиях ограничений в форме неравенств (2) или эквивалентных им соотношений (6) [1]. Предлагаемый алгоритм эффективен по вычислительной сложности, если параметры = (1 , 2 , . . . , ) удовлетворяют следующим условиям: () 0 = = () , (12) =1 () (1 , . . . , () ), = (1 , . . . , , . . . , ), = (13) , (14) =1 () () 0 [min , () max ], , (15) () где 0 - точка завершения, - одномерное замкнутое множество (отрезок) на оси , а параметры внутри группы имеют смысл величины интервалов () () внутри отрезка [min , 0 ] , при этом каждая -тая группа параметров независима от других членов . Здесь с учетом (12)-(15) ограничимся рассмотрением алгоритма для = 1. (16) Адаптировать предлагаемый алгоритм для > 1 можно, например, с использованием рекурсии, что не представляет особой сложности. Функцию управления (5) представим в форме простой борелевской векторфункции: () = (1 (), . . . , (), . . . , ()) . (17) При этом каждая компонента () * , в свою очередь, является простой борелевской функцией, определенной на счетном ограниченном множестве значений * , = 1, . Таким образом, по определению, представляет собой счетное ограниченное множество значений функции управления (): ( ) 1* 2* · · · * (1) , ...., () , (18) () () () = (1 , . . . , ), = 1, . Задача (3)-(5) в условиях (12)-(18) сводится к определению значений параметров и их количества = 1, . Поиск оптимального управления осуществляется в соответствии с процедурой АМО [1] последовательно для каждого -го числа параметров. При этом решение последовательности задач максимальной точности для различных позволяет сформировать ряд неравенств: (1) (2) ( ) ( +1) min > min > · · · > min > 0 > min () > · · · > min = { } = inf = inf () : , обеспечивающих выбор минимально необходимого количества параметров для достижения абсолютной минимальной погрешности inf или заданной погрешности 0 при < . ( ) Согласно АМО, вектор ( ) , достижимая погрешность min и дополнительные параметры, например минимальное время при заданной погрешности , определяются из замкнутой системы соотношений [1]: ) () = , (19) (, 0 , (( ) ) = ( ) () , 0 , (( ) ) = = 0, (20) которые трансформируются в )замкнутую систему уравнений для конкретно( го вида функции , (( ) ) в практических приложениях. Здесь { = 1, , = 1, , = ( 1) ( ) , min > > min , ( ) + 1, = min , { } , = 2, = 1, = . (21) (22) Система соотношений (19), (20) отражает установленные АМО специальные свойства решения задачи (3)-(5). Максимумы модуля функции ( ) ( ) () , (( ) ) = , 0 , (( ) ) () в ограничениях (4) с учетом (6) в точке завершения 0 во внутренних точ( ) () ках области , где функция , 0 , (( ) ) достигает экстремума (20), и в граничных точках этой области равны допустимой или предельно достижимой в норме погрешности . Следует отметить, что в некоторых ( ) () прикладных задачах экстремумы функции , 0 , (( ) ) (20) достигаются на границе области , что отражают соотношения (21), (22). При этом общее количество этих экстремумов равно числу искомых параметров в задаче (3)-(5), что делает систему уравнений на базе соотношений (19), (20) замкнутой. Это также отражается в соотношениях (21), (22). Получить аналитическое решение системы (19), (20) затруднительно, поэтому ее решение ищется с применением численных методов путем минимизации невязок ( , ( ) , ), ( , ( ) , ) [3, 12]: ( ) = ( , ( ) , ), , (( ) ) = ( ) , (( ) ) = ( , ( ) , ). = Для этого введем оценку невязок в форме штрафной функции [12]: ( , ( ) , ) = big ( , ( ) , ) + small ( , ( ) , ) = = ( ) ( , ( ) , , ), (23) где 1/2 2 big ( , ( ) , ) = abs , small ( , ( ) , ) = abs , ( ) abs = ( , , ) + ( , ( ) , ) , =1 =1 - коэффициент масштабирования. Оценка (23) всегда положительна, но в зависимости ( ) от оптимизируемого ( ) процесса из-за формальной зависимости ( ) может быть невыпуклой. Однако если система (19), (20) имеет решение, то оценка (23) имеет глобальный минимум ( ) inf = inf ( ) ( , ( ) , , ) = 0. Таким образом, для решения поставленной задачи необходимо определить координаты глобального минимума inf = 0 оценки (23), определенной в многомерной области 1 = ( : , ( ) : , ), ( ) 1 = dim 1 = ( + 1)( + 1), = dim , (24) для чего следует решить нелинейную невыпуклую задачу математического программирования: ( ) ( , ( ) , , ) > inf ( ) ( , ( ) , , ). (25) 1 2. Минимизация вычислительной сложности АМО. Для решения подобных задач применяют современные и достаточно эффективные алгоритмы случайного поиска глобального в замкнутой области экстремума многомерных нелинейных невыпуклых функций, которые позволяют с некото( ) рой вероятностью попасть в область, максимально приближенную к inf [18, 24, 27-29]. Введем обозначения: ( ) ( , ( ) , , ) = ( ) ( ( ) , ), ( ) = ( , ( ) , ), ( ) ( ) , (( ) ) = ( , (( ) ), ( ) ), = ( , ( ) ) = ( , 0 ). За основу возьмем вычислительную процедуру решения задачи (25), построенную на комбинации алгоритма -преобразования (алгоритм случайного поиска), предложенного В. К. Чичинадзе [18], и метода Дж. Недлера и Р. Мида [22], который представляет собой улучшенный вариант симплексметода. Метод -преобразования, не будучи методом прямого случайного поиска, обладает всеми общими свойствами алгоритмов случайного поиска, поэтому выводы, полученные ниже, применимы для широкого круга вычислительных процедур, основанных на алгоритмах случайного поиска. Сущность процедуры сводится к преобразованию минимизируемой многомерной функции (23) в одномерную непрерывную, монотонно убывающую численно за( ) ( ) данную метрику (), нуль которой соответствует значению ( , ), ( ) ( ) лежащему в области, максимально приближенной к inf . Точка затем используется как опорная для построения симплекса в методе Недлера-Ми( ) ( ) да, который применяется для улучшения результата поиска к inf (inf , ). Основные вычислительные затраты при применении процедуры имеют место на этапе подготовки данных для алгоритма -преобразования, на котором производят вычисление ( ) ( ( ) , ) в случайно либо регулярно, но обязательно равномерно распределенных в области 1 точках: ( ) 1 , = 1, , ( ) ( ) которые используются как базис для поиска. Плотность точек в области 1 напрямую влияет на погрешность алгоритма поиска экстремума. ( ) ( ) ( ) ( ) При > , ( ) > inf с координатами inf = arg min ( ) ( , ). ( ) ( ) Из (24) видно, что размерность 1 области 1 возрастает при увеличении количества параметров управления . При этом погрешность алгоритма поиска экстремума не должна увеличиваться, иначе говоря: ( ) ( 1) > . (26) ( ) В случае регулярного и равномерного распределения точек сти 1 плотность (v ) ( ) ( ) = 1 ( ) , в обла- где ( ) - количество отрезков, на которые разделяются диапазоны аргументов в области 1 . Таким образом, ( ) = ( 1) . Это означает, что с увеличением количество точек (для сохранения точности вычислений) должно возрастать в соответствии с формулой ) ( ( 1) )( v 1 ( ) 1 ( 1) . = () Для вычисления оценки (23) в каждой точке из множества мы долж( ) ны вычислить ( ( ) ) 2(1 1) раз, т.е. количество обращений к модели (3)-(8) для однократного решения задачи оптимального управления при определении параметров ( ) составит величину, равную ( ) 2(1 ) ( ( 1) )( v 1 1 ( 1) 1) , а общее количество обращений к модели (3)-(8) для достижения inf составит величину be = (1) 2(1 1) (1) + +1 =2 ( ) 2(1 ) )( ( ( 1) v 1 1) 1 ( 1) , ( ) при этом = = const. Вычислительная сложность [30] процедуры АМО ( ( )) be = , (( ) ) · be . (27) Очевидно, что вычислительная сложность определяется в основном необходимостью рассматривать заведомо не используемые в процедуре оптимизации точки при обращении к условиям связи (8) - математической модели объекта оптимизации. В условиях бесконечного числа ограничений, особенно при численном моделировании, это обстоятельство существенно осложняет и затягивает процесс поиска экстремума функционала (25), который и без того сложный в силу негладкости и невыпуклости функционала. Однако процесс обращения к модели можно упорядочить, если использовать параметрический характер управления (14) и свойства результирующих распределений управляемой субстанции, установленные АМО [1]. Присваивая точкам дискретизации (, ()) в (4) соответствующие этим параметрам и свойствам общие признаки, удается подготовить условия связи (8) к использованию в многократном обращении в процедуре оптимизации и тем самым сэкономить вычислительные ресурсы. Для снижения вычислительных затрат рассмотрим (, (( ) )) с учетом представления функции управления в форме (17), (18). Изначально вектор параметров ( ) неизвестен, однако известно, что в любой заданной точке значения функций управления () принадлежат множеству = = ((1) , . . . , () ), а значит, (, (( ) )) принимает одно из значений (, (( ) )) ( (, 1 ), . . . , (, )) = = (1 ( ), . . . , ( )) = * ( ), (28) которые могут быть вычислены без определения конкретного значения вектора ( ) . Тогда с учетом (28) выполним вычислительную процедуру АМО по следующему алгоритму. 1. Подготовим точек = (, 0 ), = 1, , которые распределим в области = ( , 0 ), =vdim равномерно и регулярно: 1.1) выберем и вычислим = ; 1.2) диапазоны аргументов (7) в области разбиваем на равных отрезков с шагом = (max min )/ , = 1, ; 1.3) диапазон аргумента 0 (12) в области разбиваем на равных отрезков с шагом 0 = (max min )/ ; 1.4) формируем упорядоченные счетные множества = {1 , 2 , . . . , , . . . , } , где 1 = min , = (1) + , = 1, ; 1.5) формируем множество = (1calc , . . . , calc , . . . , calc ) векторов calc , . . . , calc ) , calc = аргументов : calc = (calc , . . . , 1 , = 1, , = ; 1.6) формируем упорядоченное счетное множество 0 = {1 , . . . , , . . . , } , где 1 = min , = 1 + 0 , = 1, 2, . . . , ; 1.7) готовим точек = ( , 0 0 ), = (, ), = 1, , = 1, . 2. Вычисляем * ( ) по (28) в каждой точке и ставим в соответствие этой точке массив = [ * ( ), ], = 1, , = 1, . 3. Приступаем к решению задачи оптимального управления: 3.1) устанавливаем = 1; ( ) ( ) 3.2) задаем точки = , ( ) , таким образом, что = calc и ( ) 0 , фиксируем индексы = (1 , . . . , ), с учетом ( ) 0 условия (12) определяем индекс вхождения 0 = =1 ( ) и создаем массивы = [ , , ]. Тогда на основе множеств ( ) , 0 получим количество возможных точек ( ) = ( : ) ( ( 1)) , (29) =1 которое возрастает по мере увеличения количества параметров управления в (14) с учетом (16). Таким образом, требование (26) к точности выполняется. Однако следует учитывать, что при > ( ) 6 0, т.е. алгоритм вырождается и выполнить процедуру минимизации становится невозможным. Поэтому следует выбирать такие , при которых + 1 , что позволит гарантировать возможность минимизации оценки (23) даже в случае неверной первоначальной оценки ; 3.3) по имеющимся индексам , из получаем набор массивов , из которых получаем множества = (1 , . . . , , . . . , ), = ( )/ , 3.4) 3.5) 3.6) 3.7) 370 = (1 , . . . , , . . . , ), , = 1, , = 1, , соответствующие каждому . Вычислительная сложность формирования множеств ( ) = + + 2 , ( ) = 4( ) [30]; подставляем члены множеств и в (23) и получаем значения ( ) ( ) ( , ); решаем задачу (25) и получаем параметры -го класса управления ( ) и максимальную достижимую в этом классе погреш( ) ность min ; если = 1, то присваиваем новое значение переменной = 2 и переходим к пункту 3.2; ( 1) ( ) если min > min , то увеличиваем на 1 и переходим к пункту 3.2; Эффективная вычислительная процедура альтернансного метода оптимизации ( 1) ( ) ( 1) 3.8) если min 6 min , то min = inf и вычислительная процедура АМО завершена. ( ) точек оценки (23). Теперь При этом получим не более = +1 =1 вычислительная сложность [30] процедуры АМО составляет ( ( )) aft = 2 · , (( ) ) + · ( + + 4 + 5 + 5 + 5 2 ). (30) Таким образом, с учетом (27) и (30) вычислительная сложность процедуры АМО уменьшается в пропорции = be = aft 2 be . · ( + + 4 + 5 + 5 + 5 2 ) ( ( )) + , (( ) ) 3. Пример применения вычислительного алгоритма АМО. В качестве тестовой задачи выбрана известная задача оптимального управления процессом индукционного нагрева бесконечного цилиндрического стержня (9)-(11) [11]. При условиях 0 () 0 = = const, Bi = 0.7, * () = = * = 0.5 решение краевой задачи (9)-(11) принимает вид (, ) (, ) = 0 + max =1 где (, ) = max +1 (1) ( ) , , = 2 ()( ) 2 (1 ); 2 2 2 ( + Bi )1 ( ) =1 ( ) = 0 ( ), 1 ( ) = 1 ( ) - функции Бесселя нулевого и первого порядка; 1 2 2 ber () + bei () () = * (, )( ), * (, ) = ; ber() ber () + bei() bei () 0 ber(), ber (), bei(), bei () - функции Кельвина и их первые производные; () (, () )= = (, 0 , () ) * (), [0, 1]. Решение задачи (9)-(11) с заданными выше условиями при = 4 извест(1) (2) (2) но [11]: 1 = 0.349, 1 = 0.35, 2 = 0.04. (1) (2) (2) Численное решение 1 = 0.3475, 1 = 0.3506, 2 = 0.0403, основанное на комбинации алгоритма -преобразования [18] и алгоритма Дж. Недлера и Р. Мида [22], получено на компьютере с процессором Intel Core i7 2го поколения, ОЗУ 6 Gb, за 37 минут. Всего рассчитано 1 070 067 значений (, ) = (, ). После минимизации вычислительной сложности процедуры АМО по пред(1) лагаемому алгоритму на том же компьютере получено то же решение 1 = (2) (2) = 0.3475, 1 = 0.3506, 2 = 0.0403 всего за 4 минуты. Всего было рассчитано 267 значений (, ) = (, ). Таким образом, для типовой тестовой задачи (9)-(11) достигнут 9-кратный выигрыш в производительности алгоритма по времени исполнения. Из (29) видно, что при большей сложности модели и мощности множества параметров управления эффективность предложенного алгоритма повышается. В обоих случаях 67 значений (, ) были рассчитаны при выполнении алгоритма Недлера-Мида [22]. Вычисление дополнительных значений (, ) оказалось необходимым для уточнения значения оценки (23) глобального ми( ) нимума (25) при удовлетворении длины ребра симплекса условию ( ) 2 < 0 + 2 . =1 Заключение. Использование предложенного алгоритма снижения вычислительной сложности процедуры АМО: 1) существенно сокращает вычислительные затраты на поиск оптимального управления за счет минимизации количества обращений к модели объекта управления и многократного повторного использования точек и массивов ; 2) позволяет выполнять процедуру АМО на сравнительно небольшом количестве заданных точек модели объекта управления без дополнительных обращений к модели, что особенно важно для численно заданных математических моделей; 3) применение предлагаемого алгоритма не увеличило погрешность решения задачи оптимального управления по процедуре АМО; 4) эффективность предлагаемого алгоритма повышается с увеличением вычислительной сложности модели объекта управления и мощности множества параметров управления .

About the authors

Mikhail Yur'evich Livshits

Samara State Technical University

Email: mikhaillivshits@gmail.com
Doctor of technical sciences, Professor 244, Molodogvardeyskaya st., Samara, 443100, Russian Federation

Alexey Vladimirovich Nenashev

Samara State Technical University

Email: alexvlnenashev@gmail.com
without scientific degree, no status 244, Molodogvardeyskaya st., Samara, 443100, Russian Federation

References

Supplementary files