|
|
Статьи Соросовского Образовательного журнала в текстовом формате
Вводится и обсуждается понятие квазидифференциала - одного из понятий негладкого анализа. Описываются элементы квазидифференциального исчисления, являющегося обобщением классического дифференциального исчисления. Формулируются необходимые и достаточные условия минимума и максимума. Приводятся численные примеры.
НЕГЛАДКИЙ АНАЛИЗНА ПЛОСКОСТИ. Часть II
В. Ф. ДЕМЬЯНОВ
Санкт-Петербургский государственный университет
ВВЕДЕНИЕ
В первой части статьи [1] мы выяснили, что в случае дифференцируемых по направлениям функций производная по направлениям выполняет роль, которую в гладком случае играл градиент. На примере функций максимума мы видели, что производная по направлениям имеет вид
где ? f (z) - выпуклый многоугольник (в общем случае выпуклое множество). Множество ? f (z) называется субдифференциалом функции f в точке z. Задача нахождения и хранения субдифференциала сводится к разысканию (по определенным правилам) вершин многоугольника. При этом необходимые условия максимума и минимума формулируются в терминах ? f (z). Оказывается, что производная по направлениям имеет вид (1) не только в случае функций максимума, но и для многих других функций. Функция, у которой производная по направлениям имеет вид (1), называется субдифференцируемой. К сожалению, произведение, частное и разность субдифференцируемых функций уже не являются субдифференцируемыми функциями.
Рассмотрим функцию минимума. Пусть fi(x, y), i k I = 1, 2, _, N, - непрерывно дифференцируемые функции. Положим
Как и в случае функции максимума, получим, что f является дифференцируемой по направлениям, причем
где . Нетрудно видеть, что
где . Напомним, что co A обозначает выпуклую оболочку, натянутую на множество A, следовательно, - выпуклый многоугольник, натянутый на точки . Из (3) и необходимых условий минимума и максимума дифференцируемых по направлениям функций вытекают необходимые условия минимума и максимума функции (2):
Для того чтобы функция (2) достигала своего наименьшего значения в точке z*, необходимо, чтобы
Для того чтобы функция (2) достигала своего наибольшего значения в точке z**, необходимо, чтобы
Изучение суммы функции максимума и функции минимума привело к понятию квазидифференцируемой функции [2].
1. КВАЗИДИФФЕРЕНЦИРУЕМЫЕ ФУНКЦИИ
Функция f (z) = f (x, y) называется квазидифференцируемой в точке z, если функция f дифференцируема в точке z по всем направлениям и если существуют выпуклые ограниченные замкнутые множества ? f (z) и (для простоты будем предполагать, что ? f (z) и - выпуклые многоугольники), такие, что
Пара множеств называется квазидифференциалом функции f в точке z.
Оказывается, что множество квазидифференцируемых функций является достаточно богатым.
Из (6) и необходимых условий минимума и максимума для дифференцируемых по направлениям функций можно получить необходимые условия для квазидифференцируемых функций.
Для того чтобы квазидифференцируемая функция f достигала своего наименьшего значения в точке z*, необходимо, чтобы
Для того чтобы функция f достигала своего наибольшего значения в точке z**, необходимо, чтобы
Точка z*, удовлетворяющая (7), называется inf-стационарной точкой функции f, а точка z**, удовлетворяющая (8), называется sup-стационарной.
Для негладких функций можно сформулировать и достаточные условия минимума и максимума.
Если функция f липшицева в окрестности точки z* (мы не обсуждаем здесь понятие липшицевости, это естественное обобщение понятия непрерывности) и при этом оказалось, что
(то есть множество находится строго внутри множества ), то точка z* является точкой строгого локального минимума функции f, то есть найдется такое e > 0, что
f (z) > f (z*) "z ? z*, || z - z* || # e.
Аналогично, если функция f липшицева в окрестности точки z* и при этом
то точка z** является точкой строгого локального максимума, то есть найдется такое e > 0, что
f (z) < f (z*) "z ? z**, || z - z** || # e.
В гладком случае с помощью градиента никаких достаточных условий сформулировать мы не могли, условия (9) и (10) справедливы лишь для негладких функций.
Гладкая функция тоже является квазидифференцируемой. Действительно, если f - дифференцируемая функция, то ее производная по направлению имеет вид
f '(z, g) = (f '(z), g).
Ясно, что если взять
то f '(z) будет представлено в виде (6). Таким образом, гладкая функция - это такая квазидифференцируемая функция, у которой в качестве квазидифференциала можно взять пару множеств, каждое из которых содержит по одной точке. Так как одна точка не может быть строго внутри другой точки, то в гладком случае соотношения (9) и (10) невозможны.
С помощью квазидифференциала мы можем не только проверить необходимые и достаточные условия минимума и максимума, но также и найти направления наискорейшего спуска и подъема. Пусть в точке z0 (рис. 1)
где m, n $ 1.
Для каждого найдем ближайшую точку многоугольника , то есть найдем
Если cj = 0 "j k 1, 2, _, n, то это значит, что , то есть , и точка z0 является inf-стационарной. Если при этом все вершины лежат строго внутри многоугольника , то точка z0 является точкой строгого локального минимума.
Если же
то направление является направлением наискорейшего спуска функции f в точке z0 .
Конечно, может оказаться, что существует несколько j0 , удовлетворяющих (13), тогда каждому из этих j0 соответствует свое направление наискорейшего спуска.
Аналогично для проверки выполнения необходимого условия максимума для каждого ai найдем
Если di = 0 "i k 1, 2, _, m, то , то есть , или, что то же самое, , и точка z0 является sup-стационарной. Если при этом оказалось, что все вершины ai лежат строго внутри многоугольника , то точка z0 является точкой строгого локального максимума.
Если же
то направление является направлением наискорейшего подъема функции f в точке z0 . Если существует несколько i0 , удовлетворяющих (15), то каждому из них соответствует свое направление наискорейшего подъема.
Замечание 1. Выше требуется уметь решать задачи (12) и (14) (то есть находить точку многоугольника, ближайшую к заданной точке). Эти задачи на плоскости не представляют трудностей.
2. ИСЧИСЛЕНИЕ КВАЗИДИФФЕРЕНЦИАЛОВ
Для практического применения изложенной в разделе 1 теории надо уметь вычислять вершины многоугольников и . К счастью, для этого имеется хорошо разработанное квазидифференциальное исчисление, то есть исчисление квазидифференциалов, к изложению которого мы и переходим.
Нам понадобится ввести операции сложения пар многоугольников и умножение на вещественное число.
Пусть D1 = [A1 , B1], D2 = [A2 , B2] - пары выпуклых многоугольников, где A1 , A2 , B1 и B2 - выпуклые многоугольники. Положим
D1 + D2 = [A, B],
где A = A1 + A2 , B = B1 + B2 . Здесь, как обычно,
C1 + C2 = {c = c1 + c2 | c1 k C1 , c2 k C2}.
Если
C1 = co {c1i | i k I }, C2 = co {c2j | j k J },
то
C1 + C2 = co {c = c1i + c2j | i k I, j k J }.
Пусть D = [A, B], l - вещественное число. Положим
Если
A = co {ai | i k A }, B = co {bj | j k J },
то
Теперь мы можем сформулировать основные формулы квазидифференциального исчисления.
1. Если j1(z) и j2(z) - квазидифференцируемые в точке z0 функции и Dj1(z0) и Dj2(z0) - их квазидифференциалы в этой точке, то и функции
f1(z) = l1j1(z) + l2j2(z), f2(z) = j1(z)j2(z),
(если j2(z0) ? 0)
тоже являются квазидифференцируемыми в точке z0 , при этом
Df1(z0) = l1Dj1(z0) + l2Dj2(z0),
Df2(z0) = j2(z0)Dj1(z0) + j1(z0)Dj2(z0),
Формулы (16)-(18) представляют собой обобщение формул дифференциального исчисления (если в (16)-(18) операцию Df (z0) заменить операцией f ', то получим формулы классического математического анализа).
Следующие две формулы не имеют аналога в гладком случае.
2. Если ji(z), i k I, - квазидифференцируемые в точке z0 функции, I = 1, 2, _. n, Dji(z0) - их квазидифференциалы в этой точке, то и функции
тоже являются квазидифференцируемыми в точке z0 , при этом
где
Здесь
R (z0) = {i k I | ji(z0) = f1(z0)},
Q(z0) = { j k J | jj(z0) = f2(z0)}.
Тот факт, что операции взятия максимума и минимума сохраняют свойство квазидифференцируемости, является важнейшим свойством квазидифференцируемых функций.
Пример 1. Пусть f (z) = f (x, y) = | x | - | y |, z = [0, 0]. Положим f1(z) = x, f2(z) = - x, f3(z) = y, f4(z) = - y, f5(z) = | x |, f6(z) = | y |. Функции f1 , f2 , f3 , f4 гладкие, поэтому по формуле (11)
где
где
где
где
Поскольку , то по формуле (19)
где
Аналогично поскольку f6(z) = max {f3(z), f4(z)}, то
Так как f(z) = f5(z) - f6(z), то по формуле (16)
где
Имеем (рис. 2)
где a1 = [1, 0], a2 = [-1, 0], b1 = [0, 1], b2 = [0, -1]. Поскольку , то
где u1 = [0, 0], u2 = [0, 0]. Так как c1 = c2 = 1, то из (13) заключаем, что направления g0 = [0, 1] и являются направлениями наискорейшего спуска функции f в точке z0 .
Аналогично направления g0 = [1, 0] и g0' = [-1, 0] являются направлениями наискорейшего подъема.
Замечание 2. Этот пример мы уже рассматривали в [1], где непосредственными вычислениями были найдены направления наискорейшего спуска и подъема. Здесь эти же результаты были получены с помощью теории квазидифференциалов.
Пример 2. Пусть f (z) = f (x, y) = max {| x | - | y |, | x + y |}, z = [0, 0]. Положим j1(z) = | x | - | y |, j2(z) = = | x + y |, j3(z) = x + y, j4(z) = - x - y. Тогда j2(z) = = max {j3(z), j4(z)}, f (z) = max {j1(z), j2(z)}.
Функция j1(z) рассматривалась в примере 1. Там было установлено, что
где
Функции j3 и j4 гладкие, поэтому можно взять
где
Так как j2(z) = max {j3(z), j4(z)}, то по правилам квазидифференциального исчисления (см. (19))
где
Поскольку f (z) = max {j1(z), j2(z)}, то из (19)
где
Отсюда
В данном примере .
На рис. 3 видно, что
то есть точка z0 является inf-стационарной (в действительности она уже точка минимума, но это не следует из необходимого условия минимума, а достаточное условие (9) в данном случае не выполнено).
Условие максимума не выполнено. Для каждой из вершин многоугольника найдем ближайшую точку отрезка . Наиболее удаленными от множества вершинами являются a2 = [1, 2] и a3 = [- 1, - 2], при этом
где b1 = [0, 1] и b2 = [0, - 1]. Поэтому (см. (15)) направлениями наискорейшего подъема функции f в точке z0 являются
ЗАКЛЮЧЕНИЕ
Из изложенного следует, что если функция является квазидифференцируемой, то исследование этой функции на экстремум можно проводить с помощью квазидифференциала. Существует хорошо разработанное квазидифференциальное исчисление, являющееся обобщением классического дифференциального исчисления (а сам квазидифференциал - обобщением понятия градиента). Все сказанное переносится на случай функций многих переменных.
Мы описали только одно из направлений в негладком анализе, который сейчас находится в стадии становления. Здесь еще остается много интересных и важных нерешенных задач, имеющих не только теоретическое, но и сугубо практическое значение. Мы ставили перед собой следующие цели:
1) показать, что математика (и, в частности, математический анализ) интенсивно развивается в настоящее время;
2) ознакомить с некоторыми результатами в негладком анализе, чтобы даже неспециалист мог при необходимости применить эти результаты в своей деятельности;
3) привлечь пытливого читателя к ведущимся сейчас исследованиям и заинтересовать его.
ЛИТЕРАТУРА
1. Демьянов В.Ф. Негладкий анализ на плоскости. Часть I // Соросовский Образовательный Журнал. 1997. ╧ 8. С. 122-127.
2. Демьянов В.Ф., Васильев Л.В. Недифференцируемая оптимизация. М.: Наука, 1981. 384 с.
3. Кларк Ф. Оптимизация и негладкий анализ. М.: Наука, 1988. 280 с.
* * *
Владимир Федорович Демьянов, доктор физико-математических наук, профессор, зав. кафедрой факультета прикладной математики - процессов управления Санкт-Петербургского государственного университета. Область научных интересов: оптимальное управление, математическое программирование, негладкий анализ, недифференцируемая оптимизация. Член редколлегии четырех международных математических журналов, автор более 100 работ, в том числе семи монографий, часть из которых переведена на английский, немецкий, польский и китайский языки.
