Портал | Содержание | О нас | Авторам | Новости | Первая десятка | Дискуссионный клуб | Чат Научный форум --> Первая десятка "Русского переплета" Темы дня:

Президенту Путину о создании Института Истории Русского Народа. |Нас посетило 40 млн. человек | Чем занимались русские 4000 лет назад?

| Кому давать гранты или сколько в России молодых ученых?

Вводится и обсуждается понятие квазидифференциала - одного из понятий негладкого анализа. Описываются элементы квазидифференциального исчисления, являющегося обобщением классического дифференциального исчисления. Формулируются необходимые и достаточные условия минимума и максимума. Приводятся численные примеры.

НА ПЛОСКОСТИ. Часть 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 работ, в том числе семи монографий, часть из которых переведена на английский, немецкий, польский и китайский языки.