Combinatorial-analyticalmethod for maximizing of nonsmooth greatest lower boundary of the set of smooth concavefunctions depending on the parameter.pdf Задача максимизации точной нижней границы множества гладких функцийявляется частным случаем максиминной задачи, в которой максимизация идёт понепрерывной переменной, а минимизация − по дискретной. Такие непрерывно-дискретные максиминные задачи возникают в теории игр (нижняя цена «игры сприродой» [1]), в исследовании операций и теории принятия решений (осторож-ный критерий Вальда [2]), в математической экономике [3−5], в том числе в мате-матических моделях рынка [6, 7]), и вообще в теории любых динамических сис-тем, функционирующих по непрерывно-дискретному максиминному критерию(технических, экономических, биологических и др.).Во всех приложениях, где целевая функция задачи максимизации является по-точечной точной нижней гранью множества функций, приходится иметь дело снедифференцируемой (негладкой) оптимизацией, так как такая целевая функциядаже при гладких функциях множества оказывается не гладкой, а кусочно-гладкой, кусочно-дифференцируемой. Для численного решения задач выпуклойнегладкой (недифференцируемой) оптимизации в настоящее время разработанмощный математический аппарат субдифференциалов и субградиентов [8−10], наоснове которого построены эффективные итерационные вычислительные алго-ритмы оптимизации [11, 12]. Эти алгоритмы применимы и к решению задач чис-ленной максимизации точной нижней грани множества вогнутых функций, в томчисле зависящих от параметра.Однако задачи максимизации точной нижней грани конечного множества во-гнутых функций могут быть решены более простым методом. Метод состоит вприведении исходной негладкой максиминной задачи к эквивалентному наборузадач гладкой максимизации, обеспечивающих получение точек максимумов всехфункций, и задач отыскания всех точек пересечения этих гладких функций с по-следующим сравнением значений функций в точках максимумов и в точках пере-сечений и с комбинаторным отбором точного решения. В ряде случаев (например,при параболических функциях) эти задачи допускают точное аналитическое ре-шение. Использование такого комбинаторно-аналитического метода предпочти-тельно при построении и исследовании алгоритмов решения максиминных задач,зависящих от параметров.1. Математические модели систем, функционирующихпо максиминному критериюРассмотрим простейшую математическую модель динамической системы,функционирующей по максиминному критерию (см., например, [7]):( ) ( { ( ) ( ))}11 argsuXp inifm i , ,xt f u t x tƒ ≤ ≤+ = ƒ , t = 0,1, 2,... , x(0) = x0, (1)где вещественные функции fi(ƒ,u(t),x(t)), i= 1,m, непрерывны, дифференци-руемы и вогнуты по скалярным аргументам ƒ, x(t)  X = [xmin, xmax] и непрерывныи монотонны по скалярному аргументу u(t)  U = [umin, umax], а t = 0,1,2,… − дис-кретное время. Переменная x(t) описывает состояние системы в момент времени t,переменная u(t) − параметр системы или управляющая переменная.Поскольку интервал X − непустое компактное и выпуклое множество, то вслучае непрерывности отображения (1) в соответствии с теоремой Брауэра (см.,например, [13]) это отображение имеет неподвижную точку (точку равновесия)x (u) , к которой стремится состояние x(t) динамической системы (1) при t  .Опуская индекс t, получаем статическую модель, действующую на каждомшаге дискретного времени:* arg sxuXpinif{ i ( , ), 1, }x f xu i m= = . (2)2. Задача максимизации точной нижней границы конечного наборавогнутых гладких функцийЗадача (2) есть задача максимизации точной нижней границы конечного мно-жестваM ={fi (x,u),i=1,m}вогнутых гладких функций. Обозначив поточечную точную нижнюю грань этихфункций через( , ) inif{ i ( , ), 1, }f x u = f x u i= m ,представим задачу (2) как задачу максимизации функции f(x, u) по переменной xпри фиксированном значении параметра u:( ) sup ( , )x XJu fxu= .Нетрудно показать (см., например, [13]), что функция f (x, u) непрерывна и во-гнута по x. Однако, в отличие от исходных функций набора, эта функция в общемслучае не является гладкой.Теорема 1. Поточечная точная нижняя грань f (x, u) конечного множества Mвогнутых дифференцируемых функций переменной x непрерывна, вогнута и име-ет не более m(m − 1) точек разрыва производной первого рода при любом конеч-ном значении параметра u, то есть является непрерывной кусочно-дифферен-цируемой (кусочно-гладкой) функцией аргумента x.Доказательство. Непрерывность и вогнутость функции (4) известна [13].Точками разрыва производной функции f (x, u), очевидно, могут быть только точ-ки пересечения функций множества M. Каждая из вогнутых функций fi(x, u) мо-жет либо не иметь общих точек с любой другой вогнутой функцией fj(x, u), либоиметь одну точку пересечения (или касания), либо иметь две точки пересечения.Так, число пересечений первой функции с остальными m − 1 функциями не пре-вышает 2(m − 1). Число пересечений второй функции с оставшимися m − 2 функ-циями не превышает 2(m − 2), третьей функции с оставшимися m − 3 функциямине превышает 2(m − 3), и т.д. Число пересечений предпоследней функции с един-ственной оставшейся (последней) функцией не превышает 2. Следовательно, мак-симальное число возможных точек пересечения m вогнутых функций есть удво-енное число членов арифметической прогрессии 1 ( )1 1 /2 mi i m m −= ƒ = − , то естьm(m − 1). В каждой из точек пересечения скачок производной функции f(x, u) ко-нечен, так как он равен разности производных пересекающихся функций, котораявсегда ограничена вследствие дифференцируемости функций множества M. Тео-рема доказана.Таким образом, поточечная точная нижняя грань f(x, u) конечного множестваM дифференцируемых вогнутых функций является непрерывной вогнутой кусоч-но-дифференцируемой функцией с не более чем m(m − 1) точек изломов (скачковпроизводной). Поэтому оптимизационная задача (5) есть задача максимизациинепрерывной вогнутой кусочно-дифференцируемой функции.3. Комбинаторно-аналитический алгоритм решения задачимаксимизации вогнутой кусочно-дифференцируемой функцииПредположим, что часть N1, 0 ≤ N1 ≤ m, вогнутых дифференцируемых функциймножества M унимодальна, то есть на множестве вещественных чисел R имеетсяN1 точек {xi* (u),i1,m}, в которых выполняются необходимые и достаточныеусловия максимума:( * ( ), )0 fi xi u ux=,2 ( *( ) )2,0 fi xi u ux k1 сравниваем значение (12) точной нижней грани множествафункций M в точке (* ) ( )x k u с предыдущим значением (в точке (* ) ( )x k −1 u ). По-скольку f(x, u) вогнута по x, принимаем следующие решения: если ( (*) ( ) ) ( (* ) ( ) )f xk u,u f xk−1 u,u и k = k2, прекращаем процесс вычисле-ний значений функции f, полагаем *( ) (*) ( )x u =xk u и переходим на следующийшаг 5; в противном случае увеличиваем k на 1 и возвращаемся на шаг 3 (возможно-стью совпадения значений функции f в соседних точках упорядоченного множе-ства X* пренебрегаем, так как такое совпадение возможно лишь в том случае, есливо множестве функций M имеется функция-константа, не зависящая от x).Шаг 5. Конец.4. Пример: задача максимизации точной нижней границывогнутых квадратичных функций4 . 1 . К о м п ь ю т е р н о е м о д е л и р о в а н и е з а д а ч иВ качестве примера решения задачи максимизации точной нижней границынабора вогнутых гладких функций рассмотрим максиминную задачу для двух итрёх вогнутых квадратичных функций, зависящих от параметра u:( ) ( )2f1x,u = −a1x− x1 −u , ( ) ( )2f2 x,u = −a2 x− x2 +u ,( ) ( )2f3 x,u = −a3 x− x3. (13)Эти функции непрерывны и дифференцируемы по своим аргументам, вогнуты(выпуклы вверх) по x и монотонны по u. Задача (2) максимизации точной нижнейграницы этих функций на заданном интервале X = [xmin, xmax] принимает вид* arg sxuXpinif{ i ( , ), 1, }x f xu i m= = , m = 2,3. (14)Приведём сначала результаты компьютерного моделирования задачи (14) приследующих параметрах:a1 = 2, a2 = 1,5, a3 = 1, x1 = 5, x2 = 10, x3 = 15, (15)так что a1>a2>a3, x1

Скачать электронную версию публикации