|
|
Статьи Соросовского Образовательного журнала в текстовом формате
Рассматриваются задачи негладкого анализа в двумерном случае. В классическом (гладком) математическом анализе основополагающую роль играет градиент. В негладком случае роль градиента играет производная по направлениям. Подробно обсуждается один класс дифференцируемых по направлениям функций - функции максимума.
НЕГЛАДКИЙ АНАЛИЗНА ПЛОСКОСТИ. Часть I
В. Ф. ДЕМЬЯНОВ
Санкт-Петербургский государственный университет
ВВЕДЕНИЕ
В [1] обсуждались вопросы негладкого анализа функций одной вещественной переменной. Как и в классическом гладком математическом анализе, основные особенности и трудности при переходе к функциям многих переменных хорошо просматриваются уже в случае двух переменных. Поэтому изложение проводится для функций двух переменных. Для понимания дальнейшего знакомство с материалом статьи [1] необязательно. Негладкие функции возникают естественным образом при построении математических моделей, описывающих различные практические задачи.
Рассмотрим простейшую задачу обработки экспериментальных данных. В точках xi , i = 0, 1, 2, 3, 4, заданы значения "наблюдений" yi :
Предполагая, что эти наблюдения описывают некоторую линейную зависимость, попробуем построить на двумерной плоскости xy прямую y = y (x) = = ax + b, которая соответствует полученным наблюдениям. Поскольку точки [xi , yi ] не лежат на одной прямой, то требуется найти прямую, в некотором смысле наилучшим образом соответствующую имеющимся данным. Что значит наилучшим? На этот вопрос должен ответить экспериментатор, это не математический вопрос. Обычно выбирают какую-нибудь функцию параметров a и b и пытаются ее минимизировать. Среди инженеров для этой цели весьма популярен метод наименьших квадратов. Суть его в том, что строится функция
и находятся коэффициенты a и b, ее минимизирующие. В нашем случае минимум функции F1 достигается при a = 0, b = 1, то есть прямая y1(x) = 1 является наилучшей (для функции F1).
Если в качестве минимизируемой функции выбрать суммарную ошибку
и найти минимум этой функции, то окажется, что F2 достигает наименьшего значения при y2(x) = x (то есть a = 1, b = 0).
Если же выбрать функцию наименьшего уклонения
и найти минимум этой функции, то ее минимум достигается при (то есть ). Решения y1(x), y2(x), y3(x) изображены на рис. 1 соответственно синим, красным и зеленым цветом.
Выбор конкретной функции в качестве критерия зависит от характера описываемого процесса. Так, если | axi + b - yi | есть штраф за нарушение графика, то, как следует из изложенного выше, выгоднее удовлетворить точки x0 , x1 , x2 , x3 и игнорировать точку x4 (и выбрать функцию F2). Если же желаем минимизировать максимальное уклонение от графика, то наилучшим является решение y3(x), минимизирующее функцию F3 .
Для нас здесь важно то, что, в то время как функция F1 является непрерывно дифференцируемой, функции F2 и F3 недифференцируемые.
1. КЛАССИЧЕСКИЙ МАТЕМАТИЧЕСКИЙ АНАЛИЗ - ТЕАТР ОДНОГО АКТЕРА
Множество всех точек вида z = [x, y] (где x и y - вещественные числа) называется двумерным пространством (или двумерной плоскостью) и обозначается R2. Точки пространства R2 также называются векторами и направлениями (в зависимости от той роли, которую им приходится играть). Пусть на R2 задана функция f (x, y) = f (z), принимающая вещественные значения.
Классический математический анализ имеет дело с дифференцируемыми функциями. Напомним
Определение. Функция f называется дифференцируемой в точке z0 = [x0 , y0], если существует вектор A = (a1 , a2) такой, что имеет место разложение
f (z) = f (x, y) = f (z0) + (A, z - z0) + o(|| z - z0 ||).
Здесь
(A, B ) обозначает скалярное произведение векторов A и B (если A = [a1 , a2], B = [b1 , b2], то (A, B ) = a1b1 + + a2b2), || z || - евклидова норма (длина) вектора z (если z = [x, y], то ).
Если имеет место (1), то
Величина a1 называется частной производной функции f в точке z0 по x, а величина a2 - частной производной функции f в точке z0 по y. Таким образом, если функция f дифференцируема в точке z0 , то она дифференцируема и по каждой из переменных x и y. К сожалению, существование частных производных еще не гарантирует дифференцируемости. Вектор называется градиентом функции f в точке z0 и обозначается или просто f '(z0). Негладкий анализ (НГА) имеет дело с функциями, которые не являются дифференцируемыми, а под гладким анализом теперь понимают (не совсем, строго говоря, обоснованно) классический математический анализ.
Пусть g = [g1 , g2] k R2. Говорят, что функция f дифференцируема в точке z0 по направлению g, если существует конечный предел
Здесь a + 0 означает, что a 0 и a > 0. Величина f '(z0 , g) называется производной функции f в точке z0 по направлению g.
Положим S1 = {g k R2 | || g || = 1}. Это единичная окружность. Пусть функция f дифференцируема по всем направлениям. Направление g0 k S1 называется направлением наискорейшего спуска функции f в точке z0 , если
Аналогично направление g0 k S1 называется направлением наискорейшего подъема, если
Без преувеличения можно сказать, что классический математический анализ - это театр одного актера и этим актером является градиент: понятие градиента (производной в одномерном случае) является наиболее важным понятием математического анализа. Отметим только некоторые задачи, которые решаются с использованием градиента. С его помощью можно:
1) найти производную функции f в точке z0 по любому направлению g
f '(z0 , g) = (f '(z0), g);
2) построить аппроксимацию функции f в окрестности точки z0 (см. (1))
f (z) = f (z0) + (f '(z0), z - z0) + o(|| z - z0 ||);
3) сформулировать необходимые условия минимума и максимума: для того чтобы в точке z* функция f достигала своего наименьшего значения, необходимо, чтобы
f '(z*) = [0, 0] = 02 ;
для того чтобы в точке z** функция f достигала своего наибольшего значения, необходимо, чтобы
f '(z**) = 02 .
Здесь 02 = [0, 0]. Отметим, что необходимые условия максимума и минимума совпадают. Условия (8) и (9) означают, что в точке максимума и минимума частные производные функции f обращаются в нуль. Если в точке z0 оказалось f '(z0) = 02 , то точка z0 называется стационарной точкой функции f ;
4) если точка z0 еще не является стационарной (то есть f '(z0) ? 02), то можно найти направления наискорейшего спуска и подъема:
Отметим, что направление наискорейшего спуска противоположно направлению наискорейшего подъема: g0 = - g0. Итак, существуют единственное направление наискорейшего спуска и единственное направление наискорейшего подъема. С помощью этих направлений можно построить численные методы для нахождения точек минимума или максимума. Из (6) и (7) вытекает также, что если f '(z0) ? 02, то прямая, проходящая через точку z0 и перпендикулярная вектору f '(z0), делит плоскость на две полуплоскости: для любого направления g из той полуплоскости, куда смотрит вектор f '(z0), функция f возрастает (то есть при достаточно малых a > 0 будет f (z0 + ag) > f (z0)), а для любого g из той полуплоскости, куда смотрит вектор - f '(z0), функция f убывает (рис. 2).
Принципиально важным является то, что указанные выше задачи решаются с использованием только трех чисел: значения функции f (z0) и двух частных производных и . Существенно также, что имеется хорошо разработанное исчисление (правила вычисления градиентов).
2. ДИФФЕРЕНЦИРУЕМЫЕ ПО НАПРАВЛЕНИЯМ ФУНКЦИИ
Негладкий анализ имеет дело с недифференцируемыми функциями. Мы здесь ограничимся рассмотрением функций, дифференцируемых по направлениям. Класс этих функций достаточно широкий. Производная по направлениям (см. определение (5)) позволяет решать многие задачи, которые в гладком случае решались с помощью градиента. Так, необходимое условие минимума имеет вид
f '(z*, g) $ 0 ;g k R2,
а необходимое условие максимума
f '(z**, g) # 0 ;g k R2.
Обратим внимание на то, что необходимые условия максимума (12) и минимума (11) оказались различными (в то время как в гладком случае необходимые условия минимума (8) и максимума (9) совпадали). Точка z*, удовлетворяющая условию (11), называется inf-стационарной, а точка z*, удовлетворяющая условию (12), называется sup-стационарной.
С помощью производной по направлениям можно построить аппроксимацию функции f в окрестности точки z0 :
f (z) = f (z0) + f '(z0, z - z0) + o(|| z - z0 ||).
В негладком случае может существовать несколько направлений наискорейшего спуска и несколько направлений наискорейшего подъема.
Пример 1. Пусть f (z) = f (x, y) = | x | - | y |, z0 = (0, 0). Эта функция не является дифференцируемой на прямых x = y и x = - y. Возьмем направление g = [g1 , g2]. По формуле (5) находим производную по направлению g :
f '(z0 , g) = | g1 | - | g2 |.
Прямыми g1 = g2 и g1 = - g2 плоскость делится на четыре области (сами эти прямые не входят ни в одну из областей). На рис. 3 видно, что в областях I и III | g1 | > | g2 |, то есть f '(z0 , g) > 0. Следовательно, направления из областей I и III являются направлениями подъема, в то время как в областях II и IV | g1 | < | g2 |, то есть f '(z0 , g) < 0, поэтому направления из областей II и IV являются направлениями спуска. При этом существуют два направления наискорейшего спуска: g0 = [0, 1] и = [0, -1] - и два направления наискорейшего подъема функции f в точке z0 : g0 = = [1, 0] и g0' = [-1, 0]. Вспомним, что в гладком случае существовало только одно направление наискорейшего спуска и одно направление наискорейшего подъема.
3. ПОЧЕМУ НЕ СГЛАЖИВАНИЕ?
Один из распространенных и общепринятых способов борьбы с негладкостью состоит в замене негладкой функции гладкой (так называемое сглаживание).
Пример 2. Пусть, как и в примере 1, f (x, y) = = | x | - | y |, z0 = [0, 0]. Зафиксируем произвольные отличные от нуля числа a, t, g, m и рассмотрим функцию
Здесь e ? 0. Очевидно, что для любого z fe(z) f (z) . Функция fe непрерывно дифференцируема, и ее градиент
При этом в точке z0 = [0, 0]
Здесь
Из (10) и (13) заключаем, что любое наперед заданное направление g k S1 может быть (при соответствующем выборе параметров a, t, g, m) либо направлением наискорейшего спуска, либо направлением наискорейшего подъема для функции fz в точке z0 .
Любое направление g из полуплоскости является направлением подъема, а любое направление g из полуплоскости является направлением спуска функции fz в точке z0 , что не имеет ничего общего со свойствами функции f (z).
Можно, конечно, возразить, что функция fe(z) неудачно подобрана. Однако никакая гладкая аппроксимация функции f не сможет обнаружить тот факт, что существуют два направления наискорейшего спуска и два направления наискорейшего подъема.
Следовательно, сглаживание не позволяет исследовать те свойства функции, которые связаны с понятием градиента. Тем не менее если построена гладкая аппроксимация, то ее можно использовать для исследования свойств исходной функции, не связанных с понятием градиента (например, если fe отличается от f не больше, чем на e, и если найдена точка минимума функции fe , то значение функции f в этой точке отличается от минимального значения функции f не больше, чем на e).
4. ФУНКЦИИ МАКСИМУМА
Из изложенного в разделе 2 следует, что в случае дифференцируемых по направлениям функций роль, аналогичную роли градиента в гладком анализе, выполняет производная по направлениям. Для решения многих теоретических задач это действительно так, однако при практическом использовании производных по направлениям возникают трудности, связанные с неконструктивным заданием производной по направлению: если в гладком случае мы находили только значения функции и ее частных производных в данной точке, то теперь необходимо уметь находить производную по любому направлению.
Для ряда классов дифференцируемых по направлениям функций удается описать производную по направлению более конструктивно. Одним из таких классов является класс функций максимума.
Пусть fi(z), i k {1, 2, _, N}, - непрерывно дифференцируемые функции. Положим
где I = {1, 2, _, N}. Функция f уже не является непрерывно дифференцируемой, но она является дифференцируемой по направлениям:
где R(z) = {i k I | fi(z) = f (z)}.
Выражение (14) можно переписать в виде
где ?f (z) = co{}. Здесь co{Ai | i k I } - выпуклая оболочка векторов {Ai } (в нашем случае выпуклый многоугольник, натянутый на точки {Ai }).
Обратим внимание на то, что в (14) и (15) множества R (z) и ?f (z) не зависят от направления g, то есть для вычисления производной по направлениям (как функции направления g) необходимо вычислить и хранить только градиенты функций fi (и то лишь для i k R (z)).
Необходимое условие минимума (11) в данном случае (с учетом (15)) эквивалентно условию
02 k ?f (z*),
а необходимое условие максимума (12) эквивалентно условию
Если в точке z0 необходимое условие минимума (16) еще не выполнено, то есть 02 s ?f (z0), то найдем
Направление (рис. 4)
является направлением наискорейшего спуска функции f в точке z0 . Такое направление единственно.
Если же в точке z0 не выполнено необходимое условие максимума (17), то найдем
Тогда направление
является направлением наискорейшего подъема функции f в точке z0 . Поскольку максимум в (19) может достигаться на нескольких индексах, то и направлений наискорейшего подъема тоже может оказаться несколько.
Пример 3. Пусть f (z) = max{x + y, x - y}. Положим f1(z) = x + y, f2(z) = x - y, I = {1, 2}. Имеем . Возьмем z0 = [0, 0]. Тогда f (z0) = = f1(z0) = f2(z0) = 0, то есть R (z0) = {1, 2} = I. Так как , то (рис. 5, а) ?f (z0) = = co{[1, 1], [1, - 1]}. Поскольку 02 s ?f (z0), то условие (17) не выполнено.
Найдем
где u0 = [1, 0]. Направление (см. (18)) g0 = [- 1, 0] является направлением наискорейшего спуска. Условие (17) тоже не выполнено в точке z0 . Поскольку достигается в двух точках и , то направления
являются направлениями наискорейшего подъема (рис. 5, б ).
Пример 4. Пусть f (z) = max {x + y, - x - y} = | x + + y |. Положим f1(z) = x + y, f2(z) = - x - y, I = {1, 2}. Имеем . Возьмем z0 = [0, 0]. Имеем f (z0) = f1(z0) = f2(z0) = 0, то есть R (z0) = {1, 2} = I. Так как , то ?f (z0) = = co {[1, 1], [- 1, - 1]}.
Поскольку (рис. 6) 02 k ?f (z0), то в точке z0 выполнено необходимое условие минимума, то есть точка z0 inf-стационарная (в действительности точка z0 является точкой минимума, но наша теория позволяет лишь утверждать, что z0 - inf-стационарная точка). Необходимое условие максимума (17) в точке z0 не выполнено. Направления
являются направлениями наискорейшего подъема.
ЗАКЛЮЧЕНИЕ
Для функции максимума в каждой точке z существует выпуклое множество (в данном случае многоугольник) ?f (z), которое позволяет описать необходимые условия максимума и минимума, найти направления наискорейшего спуска и подъема, построить аппроксимацию функции, вычислить производную по направлениям. Множество ?f (z) называется субдифференциалом функции f в точке z. Оно играет роль, которую в гладком случае выполняет градиент. Оказывается, что аналогичное множество ?f существует и для другого важного класса негладких функций - выпуклых функций.
ЛИТЕРАТУРА
1. Демьянов В.Ф. Обобщение понятия производной в негладком анализе // Соросовский Образовательный Журнал. 1996. ╧ 5. С. 121-127.
2. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972. 368 с.
3. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973. 472 с.
4. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.: Наука, 1980. 320 с.
* * *
Владимир Федорович Демьянов, доктор физико-математических наук, профессор, зав. кафедрой факультета прикладной математики - процессов управления Санкт-Петербургского государственного университета. Область научных интересов: оптимальное управление, математическое программирование, негладкий анализ, недифференцируемая оптимизация. Член редколлегии четырех международных математических журналов, автор более 100 работ, в том числе семи монографий, часть из которых переведена на английский, немецкий, польский и китайский языки.
