Обобщенная теорема об обратной функции и экстремальные задачи с ограничениями
Автор: Магарил-Ильяев Георгий Георгиевич
Журнал: Владикавказский математический журнал @vmj-ru
Статья в выпуске: 4 т.6, 2004 года.
Бесплатный доступ
Используя метод Ньютона, доказывается некоторый вариант теоремы об обратной функции для функций, определенных на конусе. В качестве следствия выводится теорема о необходимых условия экстремума в задаче с ограничениями типа равенств, неравенств и включений.
Короткий адрес: https://sciup.org/14318129
IDR: 14318129
Текст научной статьи Обобщенная теорема об обратной функции и экстремальные задачи с ограничениями
Владикавказский математический журнал
Октябрь–декабрь, 2004, Том 6, Выпуск 4
ОБОБЩЕННАЯ ТЕОРЕМА ОБ ОБРАТНОЙ ФУНКЦИИ И
ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ С ОГРАНИЧЕНИЯМИ 1
Г. Г. Магарил-Ильяев
Дорогому Владимиру Михайловичу с благодарностью за дружбу
Используя метод Ньютона, доказывается некоторый вариант теоремы об обратной функции для функций, определенных на конусе. В качестве следствия выводится теорема о необходимых условия экстремума в задаче с ограничениями типа равенств, неравенств и включений.
Основная мотивировка получения необходимых условиях экстремума в конечномерной задаче с ограничениями типа равенств и неравенств для функций, определенных на выпуклом конусе, связана с необходимыми условиями экстремума в задаче оптимального управления, доказательство которых сводится именно к такой задаче (см. [1]). Ее бесконечномерный аналог доказан (при схожих предположениях) в работе [2], как следствие других, более общих утверждений. Приводимое здесь доказательство непосредственно и вполне элементарно: оно использует лишь классический метод Ньютона последовательных приближений и стандартную теорему отделимости для выпуклых множеств. Отметим, что доказанное утверждение приспособлено для получения необходимых условий экстремума в задаче оптимального управления в классе кусочно-непрерывных управлений. Для измеримых управлений требуется аналогичный результат, но при несколько более слабых предположениях. Он доказан, используя теорему Брауэра о неподвижной точке, в работе [3].
Для формулировки результатов и их доказательств необходимы некоторые определения. Мы будем иметь дело с функциями многих переменных, т. е. с функциями, определенными на подмножествах пространства n , которое рассматриваем как совокупность (x i
. I . Ради экономии места будем писать так: x = (xi,..., xn)T, xn где T означает транспонирование. Наряду с пространством n будем также рассматривать пространство (Rn)0, элементы которого суть вектор-строки (т. е. те же наборы из n действительных чисел, но расположенные в строку). Пусть a = (ai,..., an) G (Rn)0 и x = (xi,..., xn)T G Rn. Обозначим a • x = ^2П=1 aixi, т. е. — это матричное произведение
вектор-строки а на вектор-столбец x. Для каждого a Е (R n ) 0 отображение x ^ a • x, очевидно, есть линейная функция (функционал) на n .
Пусть x = (x 1 ,...,x n ) T Е Rn . Величина | x | = л/ x2 + ... + х П (или короче, | x | = x T · x) — это длина (или модуль, или евклидова норма) вектора x. Пусть x b ∈ n и 6 > 0. Открытый шар и замкнутый шар с центром в точке b радиуса 6 обозначаем соответственно U g ( b ; Rn) = { x Е Rn : | x — b| <6 } и B g (x; Rn) = { x Е Rn : | x — b| 6 6 } . Множество в n открыто, если с каждой своей точкой оно содержит и некоторый шар с центром в этой точке. Окрестность точки — любое открытое множество, содержащее данную точку.
Пусть Л: Rn ^ Rs — линейный оператор. Мы будем отождествлять его с его матрицей в стандартных базисах Rn и Rs, так что если x Е Rn, то Лx — произведение матрицы Л на вектор x. В частности, если s = 1, т. е. Л = l — линейный функционал, то l(x) = а • x, где а = (l(e i ),..., l(e n )) и e i ,..., e n — стандартный базис в Rn.
Норма оператора Л определяется обычным образом: || Л к = max |x| 6 i | Лx | .
Пусть M — подмножество Rn и b Е M. Будем говорить, что отображение F : M ^ Rs строго дифференцируемо в b относительно M, если найдется такой оператор Л: Rn ^ R s , что для любого е > 0 существует 6 > 0 такое, что всех x ' , x 00 Е U g (x; Rn) П M выполняется неравенство
| F(x 0 ) — F (x 00 ) — Л(x 0 — x 00 ) | 6 e | x ' — x 00 | . (1)
Оператор Л будем обозначать F 0 (x) и называть производной отображения F в точке x b относительно множества M. В частности, если s = 1, т. е. если задана функция f : M ^ R , то говорим о строгой дифференцируемости f в x относительно M и соответствующий линейный функционал (элемент (R n ) ' ) обозначаем f 0 ( b ).
Если M — окрестность точки x b , то (1) — стандартное определение строгой дифференцируемости отображения F в точке x b (см. [1], стр. 139). В этом случае, как легко видеть, F дифференцируемо в x b и Л = F 0 (x b ) — производная F в точке x b . В частности, если s = 1 (т. е. имеем дело с функцией f ), то ее производную обозначаем f 0 ( b ). Из дифференцируемости отображения F в точке x b не следует, вообще говоря, его строгая дифференцируемость в этой точке, но если F непрерывно дифференцируемо в некоторой окрестности x b , то оно строго дифференцируемо в x b (см. там же).
Покажем, что если отображение F : M ^ Rs строго дифференцируемо в b относительно M , то существует такая окрестность U 0 точки x b , что F непрерывно на U 0 ∩ M . Действительно, пусть 6 > 0 такое, что (1) выполняется с е = 1. Положим U o = U g/ 2 (x; Rn) и пусть x Е U o П M . Для е > 0 возьмем 6 o = min { 6/2, е/2, e/2 | F 0 ( b ) |} . Тогда, если x Е U g 0 ( b ; Rn) П M, то
| F (x) — F (x) | = | F (x) — F (x) — F' ( b )(x — x) + F 0 ( b )(x — x) |
6 | x — x| + k F? 0 ( b ) k| x — x| < е/2 + е/2 = е,
-
т. е. F непрерывно в x и тем самым на U 0 ∩ M .
Пусть C — выпуклый конус в Rn. Множество C * = { у Е (R n ) ' | у • x > 0, V x Е C } называется сопряженным конусом к C . Легко видеть, что C ∗ — выпуклый замкнутый конус.
Формулировка основных результатов
Мы начинаем с формулировки обобщенной теоремы об обратной функции
Теорема 1. Пусть C — выпуклый замкнутый конус в n , U — окрестность точки b E Rn , отображение F : U П ( b + C ) ^ Rs строго дифференцируемо в b относительно U П ( b + C) и F 0 ( b )(C) = Rs . Тогда существуют окрестность V точки F( b ) , отображение ^: V ^ U П (x + C ) и константа K > 0 такие, что F (^(y)) = y и | ^(y) - b| 6 K | y - F ( b ) | для всех y E V .
Эту теоремы мы применяем для получения необходимых условий локального экстремума (т. е. минимума или максимума) в следующей экстремальной задаче fо(x) ^extr, fi (x) 6 0, i = 1,...,m', fi(x) = 0, i = m' + 1,...,m, x E b+C. (2)
Здесь функции f i , i = 0, 1,... ,m, определены на множестве U П ( b + C ), где U — окрестность точки b E Rn и C — выпуклый замкнутый конус в Rn.
Свяжем с задачей (2) функцию Лагранжа L (x, А) = m L^ f А i f i (x), где А = (А о , А 1 ,..., Ат) — вектор множителей Лагранжа.
Теорема 2. Пусть в задаче (2) функции f i , 0 6 i 6 m, строго дифференцируемы в точке b относительно множества U П ( b + C ) . Тогда, если b — локальный экстремум в этой задаче, то найдется ненулевой вектор множителей Лагранжа А = (А о , А 1 ,..., А т ) такой, что А о > 0 (А о 6 0) , если задача на минимум (максимум) и при этом
-
(a) А i > 0, i = 1,..., m ' ;
-
(b) А i f ( b ) = 0, i = 1,... ,m ' ;
-
(c) L x (x,А) E C * . ■ p m =0 А i f i ( b ) E C ♦ .
Сформулируем теперь наиболее важные следствия этого результата.
-
1. Пусть U — окрестность точки b E R и функции f i , i = 0,1..., m, определены на U . Рассмотрим задачу
-
2. Пусть снова U — окрестность точки b E R и функции f i , i = 0,1..., m, определены на U . Рассмотрим задачу
f o (x) ^ extr, f i (x) = 0, i = 1,...,m. (3)
Следствие 1. Пусть в задаче (3) функции fi, 0 6 i 6 m строго дифференцируемы в точке xb. Тогда, если xb — локальный экстремум в этой задаче, то найдется ненулевой вектор множителей Лагранжа А = (Ао, А1,..., Ат) такой, что Ао > 0 (Ао 6 0), если задача на минимум (максимум) и m
L x ( b , А) = 0 . . X А i f ' ( b ) = 0.
i =0
Это классическое правило множителей Лагранжа, явно сформулированное Лагранжем в 1797 году, но которым он пользовался, начиная с середины XVIII века.
f о (x) ^ extr, f i (x) 6 0, i = 1,...,m', f i (x) = 0, B = m ' + 1,...,m. (4)
Следствие 2. Пусть в задаче (4) функции f i , 0 6 i 6 m, строго дифференцируемы в точке x b . Тогда, если x b — локальный экстремум в этой задаче, то найдется ненулевой вектор множителей Лагранжа А = (А о , А 1 ,..., А т ) такой, что А о > 0 (А о 6 0) , если задача на минимум ( максимум ) и при этом
-
(a) A i > 0, i = 1,..., m 0 ;
-
(b) A i f ( b ) = 0, i = 1,... ,m 0 ;
-
(c) L x ( b , A) = 0 .
-
3. Отметим, наконец, еще одну ситуацию. Пусть U — окрестность точки x b ∈ n и функции f i , i = 0,1,..., m, определены на множестве U П ( b + R+), где R+ = { x = (x i ,..., x n ) T E Rn : x i > 0, 1 6 i 6 n } . Рассмотрим задачу
Эта теорема была доказана в [4].
fo(x) ^ extr, fi(x) 6 0, i = 1,...,m', fi(x) = 0, i = m0 + 1,...,m, x E U П (x + R^). (5)
Следствие 3. Пусть в задаче (5) функции f i , 0 6 i 6 m , строго дифференцируемы в x относительно множества U П (x + R+) . Тогда, если x — локальный экстремум в этой задаче, то найдется ненулевой вектор множителей Лагранжа A = (A o , A i ,..., A m ) такой, что A o > 0 (A o 6 0) , если задача на минимум (максимум) и
-
(a) A i > 0, i = 1,..., m 0 ;
-
(b) A i f( b ) = 0, i = 1,... ,m 0 ;
-
(c) L x ( b + 0, A) > 0 . . P i =o A i f0 ( b + 0) > 0 ,
где f i0 ( b + 0) — производная справа функции f i в точке b, 0 6 i 6 m , и неравенство между векторами понимается покоординатно.
Именно к такого сорта задаче сводится доказательство необходимых условий экстремума в задаче оптимального управления (в классе кусочно-непрерывных управлений), стандартные требования к которой гарантируют выполнение условий следствия.
Доказательства
-
<1 [Доказательство теоремы 1] Как уже было сказано, доказательство основано на методе Ньютона, где роль обратного оператора к F 0 ( b ) играет правый обратный к F 0 ( b ), существование и нужные свойства которого вытекают из следующей леммы.
Лемма . Пусть C — выпуклый конус в Rn и Л: Rn ^ Rs — линейный оператор такой, что Л(С) = Rs . Тогда существуют отображение R: Rs ^ C и константа y > 0 такие, что Л(R(y)) = у и | R(y) | 6 y | y | для всех y E Rs .
-
< Пусть S — s-мерный симплекс в Rs, т. е. S — выпуклая оболочка некоторого набора аффинно независимых векторов e i ,..., e s +i . Тогда любой вектор у E S однозначно представляется в виде у = P s ^ ate i , где a i > 0, 1 6 i 6 s + 1 и P s +i a i = 1 (числа a i называют барицентрическими координатами y) и внутренность S не пуста (см. [5, стр. 27–29]). Можно считать, что нуль принадлежит внутренности S. Тогда для некоторого r > 0 шар B r (0; Rs) также принадлежит внутренности S. Так как Л(С) = Rs, то найдутся такие f i E C, 1 6 i 6 s + 1, что Лf i = e i , 1 6 i 6 s + 1. Для каждого у E Rs, у = 0, положим R(y) = ( | у | /r) P s +i a i; (r | у | -i у)^, где a i (r | y | -1 y), 1 6 i 6 s + 1, — барицентрические координаты вектора г | у | - 1 у , и пусть R(0) = 0. Ясно, что R(y) E C для любого y ∈ s . Далее имеем:
s +i
Л(R(y)) = ( | у | /г) X a i (r | y | -i y)e i = ( | у | /г)г | у | -1 у = у i =i
и
s +1
s +1
\ R(y) \ 6 ( | y | /r)
max 1 6 i 6 s +1
a i (r | y | 1 y) 52 f 6 ( | y | /r) 52 f = Y | y | ,
i =1
i =1
где y = r 1 P s +i 1 | f i | . B
Приступим теперь непосредственно к доказательству теоремы. Оператор F 0 (b) удовлетворяет условиям леммы. Возьмем соответствующие ему отображение R и число γ из этой леммы. Для Е = 1 / 2 y найдется (согласно определению строгой дифференцируемости F в b относительно множества U П (x + C ) и непрерывности F в некоторой окрестности b , пересеченной с b + C ) такое 6 > 0, что U g ( b ; Rn) С U , отображение F непрерывно на B g/ 2 ( b ; Rn) П (x + C ) и если x 0 , x 0 E U g ( b ; Rn) П (x + C ), то
\ F(x 0 ) - F (x 00 ) - F 0 (x)(x 0 - x 00 ) \ 6 — | x 0 - x,0\.
Положим V = U g/ 4 Y (F ( b ); Rs) и пусть y E V. Рассмотрим последовательность (итеративный процесс Ньютона)
x i = x i - 1 + R(y - F (x i- 1 )), i E N, x o = b .
Покажем, что x i E B g/ 2 ( b ; Rn ) П ( b + C ) (i = 0,1, 2,...). Доказываем по индукции. Ясно, что x o E B g/ 2 ( b ; Rn) П ( b + C ) и допустим x i E B g/ 2 ( b ; Rn) П ( b + C ), i = 0,1,..., m. Из (7) следует, что
Л(x i - x i- 1 ) = У - F (x i- 1 ), i = 0, 1,...,m. (8)
Воспользовавшись последовательно (7) с оценкой для отображения R, (8), (6) и затем итерируя процедуру, будем иметь
\x m +1 - x m \ 6 Y \y - F(x m ) | = y \ F (x m- 1 ) - F(x m ) + Л(X m - x m- 1 ) |
-
6 ^ \ x m x m - 1 \ 6 4 \ x m- 1 x m - 2 \ 6 • • • 6 ^ m \ x 1 x \ " (9)
Теперь по неравенству треугольника, (9) и (7)
\ x m +1 x \ 6 \ x m +1 x m \ + \ x m x m - 1 \ + ... + \ x 1 x \
-
6 ( 2 m + 2 m- r +...+ 1 ) \ x 1 - b \ 6 2 y \ у - F ( b ) \ < 2 y 4 y = 6,
т. е. x m +1 E B g/ 2 ( b ; Rn).
По предположению x m E b + C . Отсюда и из (7): x m +1 E x m + C С b + C + C = b + C (в силу выпуклости C ). Таким образом, x m +1 E B g/ 2 ( b , Rn ) П ( b + C ) и тем самым это включение выполняется для всех i = 0,1, 2,...
Так как для любых i и j (по неравенству треугольника и (9))
\ x i + j - x i \ 6 \ x i + j - x i + j - 1 \ + ... + \ x i +1 - x i \
-
6 ^2 i + j- 1 + ... + 2 i) \ x 1 x \
6 2 \ x 1 - x \ ^ 0
при i → ∞ , то последовательность { x i } фундаментальна и значит, сходится.
Обозначим ^(y) = lim i^^ x i . Ясно, что ^(y) E B ^/ 2 ( b ; Rn) П (x + C ). Далее в силу непрерывности F на В ^/ 2 ( ж ; Rn ) П (x + C ) и (8) имеем
|FМу)) - y| = lim |F(xi) - y| = lim |F0(b)(xi+1 - bi) | = 0 i→∞ i→∞ и, следовательно, F(^(y)) = y.
Поскольку (по неравенству треугольника и (7))
|xi - b| 6 |xi - xi-1| + ... + |xi - b| 6 2Y|y - F(b)|, то переходя здесь к пределу при i ^ го и обозначая К = 2y, получаем, что |^(y) - b| 6 K|y - F(b)|. B
Заметим, что если в теореме C = Rn, s = n, то F 0 ( b ) — обратимый оператор и в этом случае у: V ^ F -1 (V) — обратное отображение к F . Действительно, обозначим Л = F 0 (x), тогда R = Л -1 . Пусть y E V и F (x) = y. Имеем
| x - ^М = | Л 1 л(x - ^М ) 6 Y |N x - V ( У )) |
= Y | F (x) - F Му)) - Л(ж - ^y)) 6 Y2Y | x - УМ = 2 | x - ^Mh (10)
-
т. е. x = ^(y).
C [Доказательство теоремы 2] Пусть x b — локальный экстремум в задаче (2). Можно считать, что f i ( b ) = 0, 1 6 i 6 m 0 + 1 (и тем самым утверждение (b) теоремы выполнено). Действительно, отбросим те ограничения, для которых f i ( b ) < 0. Легко понять, что x b — локальный экстремум и в новой задаче. Если для нее будут доказаны условия (а) и (с), то (b) будет выполняется автоматически. Дополнив найденный набор множителей Лагранжа нулевыми компонентами (соответствующие тем номерам, где f ( b ) < 0), получим утверждения (a), (b), (с) для исходной задачи.
Пусть, для определенности, x b — локальный минимум. Рассмотрим отображение F : (U П ( ь + C )) х Rm4 1 ^ Rm +1 , определенное по правилу: F (x, u) = (f o (x) + u o , f 1 (x) + U 1 ,..., f m 0 (x) + U m O , f m +1 (x),..., f m (x)) T . Ясно, что F( b , 0) = (f o (b), 0). Из строгой дифференцируемости функций f i , 0 6 i 6 m, в точке b относительно множества U П ( ь + C) следует строгая дифференцируемость отображения F в точке ( ь , 0) относительно множества (U П ( ь + C)) х Rm +1 , где F 0 ( b , 0) — матрица, строки которой суть (f 0 ( b ), 1, 0,..., 0), (f 1 ( b ), 0, 1, 0,..., 0),..., (fm, ( b ), 0 0, 1), (f m 0 +1 ( b ), 0,..., 0),..., (f m ( b ), 0, . . . , 0).
Покажем, что F 0 ( b , 0)(C х Rm +1 ) = Rm +1 . Если это не так, то по теореме 1 (условия которой, очевидно, выполнены) найдутся окрестность V точки (f o ( b ), 0), отображение у: V ^ (U П ( ь + С)) хR m +1 и константа K > 0 такие, что | ^(y) - (x, 0) | 6 K | y - (f o (x), 0) | для всех y E V .В частности, для всех достаточно малых е > 0 вектор y e = (f o ( b ) - е, 0) принадлежит V и | ^(y e ) - (x, 0) | 6 Ке. Отсюда следует, что какова бы ни была окрестность U o точки ь найдутся такие x . E U o П (x + C) и u e = (u o e ,..., u m'e ) T E Rm +1 , что f o (x e )+ U o e = f o ( b ) - e, f 1 (b e )+ U 1 e = 0, . . . , f m 0 (b e )+ Um^. =0,f m 0 +1 (b e ) = 0, . . . , f m (b e ) = 0. Таким образом, точка x e допустима в задаче (2), но f o (x e ) 6 f o (x e ) + u o e = f o ( b ) - e < f o ( b ) в противоречии с тем, что ь — локальный минимум. Итак, F 0 ( b , 0)(C х Rm +1 ) = m +1 . 0
Множество Q = F 0 (x, 0)(C х Rm +1 ) есть выпуклый конус в Rm +1 как образ выпуклого конуса при линейном отображении. Множество Q \ { 0 } также выпуклый конус. По теореме отделимости (см., например, [5, стр. 37]) его можно отделить от точки 0, т. е.
существует такой ненулевой вектор А = (Aq, Ai,..., Am), что для всех y Е Q \ {0} справедливо неравенство А • у > 0, которое, очевидно, справедливо и для всех у Е Q. Но У = (fQ (b) • x + UQ,fi (b) • x + Ui, . . • ,fm 0 (b) • x + UmO ,fm>+1(X) • x, . . . , fm (b) • X)T и поэтому мы имеем mm
X Aif^i(cc) • X + X AiUi > 0 V (x,u) Е C x Rm0^, i=Q где u = (uq,Ui,... ,um0).
Полагая x = 0, получаем утверждение (a) теоремы, а полагая u = 0, получаем утверждение (с). Если b — локальный максимум, то в качестве первой компоненты F (x,u) надо взять f o (x) — u q . Все рассуждения остаются прежними, но и из (11) будет следовать, что A q 6 0. B
C [Доказательство следствия 1] В силу предположений f i (x) = f i0 ( b ), 0 6 i 6 m. Отсутствие ограничения типа включения можно трактовать так: C = Rn. Тогда утверждение (с) теоремы означает, что линейный функционал неотрицателен на всем Rn и, следовательно, он равен нулю. B
Отметим, что если не заботиться о знаке A q , то следствие 1 сразу вытекает из теоремы 1. Действительно, рассмотрим отображение F : U ^ Rm +i , F (x) = (f o (x),f i (x),..., f m (x)) T . Также как при доказательстве теоремы 2 проверяется, что F 0 ( b )(R n ) = Rm +i , т. е. строки матрицы F 0 ( b ) линейно зависимы, а это и есть утверждение следствия 1.
C [Доказательство следствия 2] Поскольку здесь также f i0 ( b ) = f i0 ( b ), 0 6 i 6 m, и C = Rn, то те же аргументы, что и выше приводят к требуемому утверждению. B
C [Доказательство следствия 3] Легко видеть, что f i ( b ) = f i0 ( b + 0), 0 6 i 6 m, и ясно, что сопряженный конус к R^ совпадает с R+. B
Список литературы Обобщенная теорема об обратной функции и экстремальные задачи с ограничениями
- Алесеев В. М., Тихомиров В. М., Фомин С. В. Оптимальное управление.-М.: Наука, 1979.-429 с.
- Дмитрук А. В., Милютин А. А., Осмоловский Н. П. Теорема Люстерника и теория экстремума//Успехи мат. наук.-1980.-Т. 35, вып. 6.-С. 11-40.
- Арутюнов А. В., Винтер Р. Б. Метод конечномерной аппроксимации в теории оптимального управления//Диф. уравнения.-2003.-Т. 39, № 11.-С. 1443-1451.
- John F. Extreme problems with inequalities as subsidery conditions//Studies and essays presented to R. Courant on his 60-th birthday, January 8.-New York: Intersociety, 1948.-P. 187-204.
- Магарил-Ильяев Г. Г., Тихомиров В. М. Выпуклый анализ и его приложения.-М.: Эдиториал УРСС, 2003.-176 с.