Вариационный принцип Экланда

В математическом анализе вариационный принцип Экланда , открытый Иваром Экландом , [1] [2] [3] представляет собой теорему, утверждающую, что существуют почти оптимальные решения некоторых задач оптимизации .

Принцип Экланда может быть использован, когда нижний уровень множества минимизационной задачи не является компактным , так что теорема Больцано–Вейерштрасса не может быть применена. Принцип основан на полноте метрического пространства . [4]

Было показано, что этот принцип эквивалентен полноте метрических пространств. [5] В теории доказательств он эквивалентен Π1
1CA 0 над RCA 0 , т.е. относительно сильный.

Это также приводит к быстрому доказательству теоремы Каристи о неподвижной точке . [4] [6]

История

Экеланд был связан с Университетом Париж-Дофин, когда он предложил эту теорему. [1]

Вариационный принцип Экланда

Предварительные определения

Функция, значение которой выражено в расширенных действительных числах, называется ф : Х → Р ∪ { − ∞ , + ∞ } {\displaystyle f:X\to \mathbb {R} \cup \{-\infty ,+\infty \}} Р ∪ { − ∞ , + ∞ } = [ − ∞ , + ∞ ] {\displaystyle \mathbb {R} \cup \{-\infty,+\infty \} = [-\infty,+\infty]} ограничен снизу, еслии это называется инф ф ( Х ) = инф х ∈ Х ф ( х ) > − ∞ {\displaystyle \inf _{}f(X)=\inf _{x\in X}f(x)>-\infty } правильно, если он имеет непустоеэффективная область , которая по определению является множеством и никогда не равнаДругими словами, отображение являетсяправильнымесли имеет значения ви не тождественно. Отображениеявляется правильным и ограниченным снизу тогда и только тогда, когдаили, что эквивалентно, тогда и только тогда, когда дом ⁡ ф   = определение   { х ∈ Х : ф ( х ) ≠ + ∞ } , {\displaystyle \operatorname {dom} f~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\{x\in X:f(x)\neq +\infty \},} − ∞ . {\displaystyle -\infty .} Р ∪ { + ∞ } {\displaystyle \mathbb {R} \cup \{+\infty \}} + ∞ . {\displaystyle +\infty .} ф {\displaystyle f} − ∞ < инф ф ( Х ) ≠ + ∞ , {\displaystyle -\infty <\inf _{}f(X)\neq +\infty ,} инф ф ( Х ) ∈ Р . {\displaystyle \inf _{}f(X)\in \mathbb {R} .}

Функция полунепрерывна снизу в заданной точке , если для каждого действительного числа существует окрестность такая , что для всех Функция называется полунепрерывной снизу , если она полунепрерывна снизу в каждой точке , что происходит тогда и только тогда, когда является открытым множеством для каждого или, что эквивалентно, тогда и только тогда , когда все ее множества нижнего уровня замкнуты . ф : Х → [ − ∞ , + ∞ ] {\displaystyle f:X\to [-\infty ,+\infty ]} х 0 ∈ Х {\displaystyle x_{0}\in X} у < ф ( х 0 ) {\displaystyle y<f\left(x_{0}\right)} У {\displaystyle U} х 0 {\displaystyle x_{0}} ф ( ты ) > у {\displaystyle f(u)>y} ты ∈ У . {\displaystyle u\in U.} Х , {\displaystyle X,} { х ∈ Х :   ф ( х ) > у } {\displaystyle \{x\in X:~f(x)>y\}} у ∈ Р , {\displaystyle y\in \mathbb {R} ,} { х ∈ Х :   ф ( х ) ≤ у } {\displaystyle \{x\in X:~f(x)\leq y\}}

Формулировка теоремы

Вариационный принцип Экланда [7]  — Пустьбудетполным метрическим пространствоми пустьбудет собственнойполунепрерывной снизуфункцией, которая ограничена снизу (так что). Выберитетакое, что(или, что эквивалентно,) и зафиксируйте любое действительное Существует некотороетакое, что и для любого, отличного от(то есть,), ( Х , г ) {\displaystyle (X,d)} ф : Х → Р ∪ { + ∞ } {\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}} инф ф ( Х ) ∈ Р {\displaystyle \inf _{}f(X)\in \mathbb {R} } х 0 ∈ Х {\displaystyle x_{0}\in X} ф ( х 0 ) ∈ Р {\displaystyle f(x_{0})\in \mathbb {R} } ф ( х 0 ) ≠ + ∞ {\displaystyle f(x_{0})\neq +\infty } ε > 0. {\displaystyle \varepsilon >0.} в ∈ Х {\displaystyle v\in X} ф ( в )   ≤   ф ( х 0 ) − ε г ( х 0 , в ) {\displaystyle f(v)~\leq ~f\left(x_{0}\right)-\varepsilon \;d\left(x_{0},v\right)} х ∈ Х {\displaystyle x\in X} в {\displaystyle v} х ≠ в {\displaystyle x\neq v} ф ( в )   <   ф ( х ) + ε г ( в , х ) . {\displaystyle f(v)~<~f(x)+\varepsilon \;d(v,x).}

Доказательство

Определим функцию , которая является полунепрерывной снизу, так как она является суммой полунепрерывной снизу функции и непрерывной функции , причем обозначим функции с одной фиксированной координатой , и определим множество , которое не является пустым, так как Элемент удовлетворяет заключению этой теоремы тогда и только тогда, когда Осталось найти такой элемент. Г : Х × Х → Р ∪ { + ∞ } {\displaystyle G:X\times X\to \mathbb {R} \cup \{+\infty \}} Г ( х , у )   = определение   ф ( х ) + ε г ( х , у ) {\displaystyle G(x,y)~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~f(x)+\varepsilon \;d(x,y)} ф {\displaystyle f} ( х , у ) ↦ ε г ( х , у ) . {\displaystyle (x,y)\mapsto \varepsilon \;d(x,y).} з ∈ Х , {\displaystyle z\in X,} з {\displaystyle z} Г з   = определение   Г ( з , ⋅ ) : Х → Р ∪ { + ∞ }  и  {\displaystyle G_{z}~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~G(z,\cdot ):X\to \mathbb {R} \cup \{+\infty \}\;{\text{ и }}} Г з   = определение   Г ( ⋅ , з ) : Х → Р ∪ { + ∞ } {\displaystyle G^{z}~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~G(\cdot ,z):X\to \mathbb {R} \cup \{+\infty \}} Ф ( з )   = определение   { у ∈ Х : Г з ( у ) ≤ ф ( з ) }   =   { у ∈ Х : ф ( у ) + ε г ( у , з ) ≤ ф ( з ) } , {\displaystyle F(z)~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\left\{y\in X:G^{z}(y)\leq f(z)\right\}~=~\{y\in X:f(y)+\varepsilon \;d(y,z)\leq f(z)\},} з ∈ Ф ( з ) . {\displaystyle z\in F(z).} в ∈ Х {\displaystyle v\in X} Ф ( в ) = { в } . {\displaystyle F(v)=\{v\}.}

Можно убедиться, что для каждого х ∈ Х , {\displaystyle x\in X,}

  1. Ф ( х ) {\displaystyle F(x)} замкнуто (поскольку полунепрерывно снизу); Г х = определение Г ( ⋅ , х ) : Х → Р ∪ { + ∞ } {\displaystyle G^{x}\,{\stackrel {\scriptscriptstyle {\text{def}}}{=}}\,G(\cdot ,x):X\to \mathbb {R} \cup \{+\infty \}}
  2. если тогда х ∉ дом ⁡ ф {\displaystyle x\notin \operatorname {dom} f} Ф ( х ) = Х ; {\displaystyle F(x)=X;}
  3. если тогда в частности, х ∈ дом ⁡ ф {\displaystyle x\in \operatorname {dom} f} х ∈ Ф ( х ) ⊆ дом ⁡ ф ; {\displaystyle x\in F(x)\subseteq \operatorname {dom} f;} х 0 ∈ Ф ( х 0 ) ⊆ дом ⁡ ф ; {\displaystyle x_{0}\in F\left(x_{0}\right)\subseteq \operatorname {dom} f;}
  4. если тогда у ∈ Ф ( х ) {\displaystyle y\in F(x)} Ф ( у ) ⊆ Ф ( х ) . {\displaystyle F(y)\subseteq F(x).}

Пусть , которое является действительным числом, поскольку предполагалось ограниченным снизу. Выберите такое, что Определив и пусть и выберите такое, что Для любого гарантирует, что и которое в свою очередь влечет и, таким образом, также Так что если тогда и которое гарантирует с 0 = инф х ∈ Ф ( х 0 ) ф ( х ) , {\displaystyle s_{0}=\inf _{x\in F\left(x_{0}\right)}f(x),} ф {\displaystyle f} х 1 ∈ Ф ( х 0 ) {\displaystyle x_{1}\in F\left(x_{0}\right)} ф ( х 1 ) < с 0 + 2 − 1 . {\displaystyle f\left(x_{1}\right)<s_{0}+2^{-1}.} с н − 1 {\displaystyle s_{n-1}} х н , {\displaystyle x_{n},} s n   = def   inf x ∈ F ( x n ) f ( x ) {\displaystyle s_{n}~{\stackrel {\scriptscriptstyle {\text{def}}}{=}}~\inf _{x\in F\left(x_{n}\right)}f(x)} x n + 1 ∈ F ( x n ) {\displaystyle x_{n+1}\in F\left(x_{n}\right)} f ( x n + 1 ) < s n + 2 − ( n + 1 ) . {\displaystyle f\left(x_{n+1}\right)<s_{n}+2^{-(n+1)}.} n ≥ 0 , {\displaystyle n\geq 0,} x n + 1 ∈ F ( x n ) {\displaystyle x_{n+1}\in F\left(x_{n}\right)} s n ≤ f ( x n + 1 ) {\displaystyle s_{n}\leq f\left(x_{n+1}\right)} F ( x n + 1 ) ⊆ F ( x n ) , {\displaystyle F\left(x_{n+1}\right)\subseteq F\left(x_{n}\right),} s n + 1 ≥ s n {\displaystyle s_{n+1}\geq s_{n}} f ( x n + 2 ) ≥ s n + 1 ≥ s n . {\displaystyle f\left(x_{n+2}\right)\geq s_{n+1}\geq s_{n}.} n ≥ 1 {\displaystyle n\geq 1} x n + 1 ∈ F ( x n ) = def { y ∈ X : f ( y ) + ε d ( y , x n ) ≤ f ( x n ) } {\displaystyle x_{n+1}\in F\left(x_{n}\right){\stackrel {\scriptscriptstyle {\text{def}}}{=}}\left\{y\in X:f(y)+\varepsilon \;d\left(y,x_{n}\right)\leq f\left(x_{n}\right)\right\}} f ( x n + 1 ) ≥ s n − 1 , {\displaystyle f\left(x_{n+1}\right)\geq s_{n-1},} ε d ( x n + 1 , x n )   ≤   f ( x n ) − f ( x n + 1 )   ≤   f ( x n ) − s n − 1   <   1 2 n . {\displaystyle \varepsilon \;d\left(x_{n+1},x_{n}\right)~\leq ~f\left(x_{n}\right)-f\left(x_{n+1}\right)~\leq ~f\left(x_{n}\right)-s_{n-1}~<~{\frac {1}{2^{n}}}.}

Из этого следует, что для всех положительных целых чисел , что доказывает, что является последовательностью Коши. Поскольку является полным метрическим пространством, существует некоторое такое, что сходится к Для любого, поскольку является замкнутым множеством, содержащим последовательность, оно должно также содержать предел этой последовательности, который, таким образом , и в частности, n , p ≥ 1 , {\displaystyle n,p\geq 1,} d ( x n + p , x n )   ≤   2 ε − 1 2 n , {\displaystyle d\left(x_{n+p},x_{n}\right)~\leq ~2\;{\frac {\varepsilon ^{-1}}{2^{n}}},} x ∙ := ( x n ) n = 0 ∞ {\displaystyle x_{\bullet }:=\left(x_{n}\right)_{n=0}^{\infty }} X {\displaystyle X} v ∈ X {\displaystyle v\in X} x ∙ {\displaystyle x_{\bullet }} v . {\displaystyle v.} n ≥ 0 , {\displaystyle n\geq 0,} F ( x n ) {\displaystyle F\left(x_{n}\right)} x n , x n + 1 , x n + 2 , … , {\displaystyle x_{n},x_{n+1},x_{n+2},\ldots ,} v ; {\displaystyle v;} v ∈ F ( x n ) {\displaystyle v\in F\left(x_{n}\right)} v ∈ F ( x 0 ) . {\displaystyle v\in F\left(x_{0}\right).}

Теорема будет следовать, как только будет показано, что Итак, пусть и остается показать , что Поскольку для всех следует, как и выше, что влечет за собой то, что сходится к Поскольку также сходится к и пределы в метрических пространствах единственны, ЧТЭ F ( v ) = { v } . {\displaystyle F(v)=\{v\}.} x ∈ F ( v ) {\displaystyle x\in F(v)} x = v . {\displaystyle x=v.} x ∈ F ( x n ) {\displaystyle x\in F\left(x_{n}\right)} n ≥ 0 , {\displaystyle n\geq 0,} ε d ( x , x n ) ≤ 2 − n , {\displaystyle \varepsilon \;d\left(x,x_{n}\right)\leq 2^{-n},} x ∙ {\displaystyle x_{\bullet }} x . {\displaystyle x.} x ∙ {\displaystyle x_{\bullet }} v {\displaystyle v} x = v . {\displaystyle x=v.} ◼ {\displaystyle \blacksquare }

Например, если и такие, как в формулировке теоремы, и если является точкой глобального минимума, то вектор из заключения теоремы равен f {\displaystyle f} ( X , d ) {\displaystyle (X,d)} x 0 ∈ X {\displaystyle x_{0}\in X} f , {\displaystyle f,} v {\displaystyle v} v := x 0 . {\displaystyle v:=x_{0}.}

Следствия

Следствие [8]  —  Пусть — полное метрическое пространство , и пусть — полунепрерывный снизу функционал на , который ограничен снизу и не равен тождественно Fix , и точка такая, что Тогда для каждого существует точка такая, что и для всех ( X , d ) {\displaystyle (X,d)} f : X → R ∪ { + ∞ } {\displaystyle f:X\to \mathbb {R} \cup \{+\infty \}} X {\displaystyle X} + ∞ . {\displaystyle +\infty .} ε > 0 {\displaystyle \varepsilon >0} x 0 ∈ X {\displaystyle x_{0}\in X} f ( x 0 )   ≤   ε + inf x ∈ X f ( x ) . {\displaystyle f\left(x_{0}\right)~\leq ~\varepsilon +\inf _{x\in X}f(x).} λ > 0 , {\displaystyle \lambda >0,} v ∈ X {\displaystyle v\in X} f ( v )   ≤   f ( x 0 ) , {\displaystyle f(v)~\leq ~f\left(x_{0}\right),} d ( x 0 , v )   ≤   λ , {\displaystyle d\left(x_{0},v\right)~\leq ~\lambda ,} x ≠ v , {\displaystyle x\neq v,} f ( x ) + ε λ d ( v , x )   >   f ( v ) . {\displaystyle f(x)+{\frac {\varepsilon }{\lambda }}d(v,x)~>~f(v).}

Принцип можно представить следующим образом: для любой точки , которая почти реализует инфимум, существует другая точка , которая по крайней мере так же хороша, как , она близка к и возмущенная функция , имеет единственный минимум в . Хорошим компромиссом является принятие предыдущего результата. [8] x 0 {\displaystyle x_{0}} v {\displaystyle v} x 0 {\displaystyle x_{0}} x 0 {\displaystyle x_{0}} f ( x ) + ε λ d ( v , x ) {\displaystyle f(x)+{\frac {\varepsilon }{\lambda }}d(v,x)} v {\displaystyle v} λ := ε {\displaystyle \lambda :={\sqrt {\varepsilon }}}

Смотрите также

Ссылки

  1. ^ ab Экеланд, Ивар (1974). «О вариационном принципе». J. Math. Anal. Appl . 47 (2): 324–353. doi : 10.1016/0022-247X(74)90025-0 . ISSN  0022-247X.
  2. ^ Экланд, Ивар (1979). «Невыпуклые задачи минимизации». Бюллетень Американского математического общества . Новая серия. 1 (3): 443–474. doi : 10.1090/S0273-0979-1979-14595-6 . MR  0526967.
  3. ^ Экеланд, Ивар; Темам, Роджер (1999). Выпуклый анализ и вариационные задачи . Классика прикладной математики. Том 28 (Исправленное переиздание (1976) издания North-Holland). Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM). стр. 357–373. ISBN 0-89871-450-8. МР  1727362.
  4. ^ ab Kirk, William A.; Goebel, Kazimierz (1990). Темы в метрической теории неподвижных точек . Cambridge University Press. ISBN 0-521-38289-0.
  5. ^ Салливан, Фрэнсис (октябрь 1981 г.). «Характеристика полных метрических пространств». Труды Американского математического общества . 83 (2): 345–346. doi : 10.1090/S0002-9939-1981-0624927-9 . MR  0624927.
  6. ^ Ok, Efe (2007). "D: Continuity I". Реальный анализ с экономическими приложениями (PDF) . Princeton University Press. стр. 664. ISBN 978-0-691-11768-3. Получено 31 января 2009 г. .
  7. ^ Залинеску 2002, стр. 29.
  8. ^ ab Zalinescu 2002, стр. 30.

Библиография

  • Экланд, Ивар (1979). «Невыпуклые задачи минимизации». Бюллетень Американского математического общества . Новая серия. 1 (3): 443–474. doi : 10.1090/S0273-0979-1979-14595-6 . MR  0526967.
  • Кирк, Уильям А.; Гебель, Казимеж (1990). Темы в метрической теории неподвижных точек . Cambridge University Press. ISBN 0-521-38289-0.
  • Залинеску, С (2002). Выпуклый анализ в общих векторных пространствах . River Edge, NJ London: World Scientific. ISBN 981-238-067-1. OCLC  285163112.
  • Zălinescu, Constantin (30 июля 2002 г.). Выпуклый анализ в общих векторных пространствах . River Edge, NJ London: World Scientific Publishing . ISBN 978-981-4488-15-0. MR  1921556. OCLC  285163112 – через Интернет-архив .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Ekeland%27s_variational_principle&oldid=1201956193"