Выпуклое сопряжение функции — это обобщение преобразования Лежандра , которое применяется к невыпуклым функциям. Оно известно также как преобразование Лежандра — Фенхеля или преобразование Фенхеля (по именам Адриена Мари Лежандра и Вернера Фенхеля ). Сопряжение используется для преобразования задачи оптимизации в соответствующую двойственную задачу , которую, возможно, проще решить.
Пусть X {\displaystyle X} будет вещественным топологическим векторным пространством и пусть X ∗ {\displaystyle X^{*}} будет двойственным пространством для X {\displaystyle X} . Обозначим двойственную пару [англ.] через
⟨ ⋅ , ⋅ ⟩ : X ∗ × X → R . {\displaystyle \langle \cdot ,\cdot \rangle :X^{*}\times X\to \mathbb {R} .} Для функции
f : X → R ∪ { − ∞ , + ∞ } {\displaystyle f:X\to \mathbb {R} \cup \{-\infty ,+\infty \}} , принимающей значения на расширенной числовой прямой , выпуклое сопряжение
f ∗ : X ∗ → R ∪ { − ∞ , + ∞ } {\displaystyle f^{*}:X^{*}\to \mathbb {R} \cup \{-\infty ,+\infty \}} определено в терминах супремума по формуле
f ∗ ( x ∗ ) := sup { ⟨ x ∗ , x ⟩ − f ( x ) | x ∈ X } , {\displaystyle f^{*}\left(x^{*}\right):=\sup \left\{\left.\left\langle x^{*},x\right\rangle -f\left(x\right)\right|x\in X\right\},} или, эквивалентно, в терминах инфимума по формуле
f ∗ ( x ∗ ) := − inf { f ( x ) − ⟨ x ∗ , x ⟩ | x ∈ X } . {\displaystyle f^{*}\left(x^{*}\right):=-\inf \left\{\left.f\left(x\right)-\left\langle x^{*},x\right\rangle \right|x\in X\right\}.} Это определение можно интерпретировать как кодирование выпуклой оболочки надграфика функции в терминах её опорных гиперплоскостей [1] [2] .
Выпуклое сопряжение аффинной функции
f ( x ) = ⟨ a , x ⟩ − b , a ∈ R n , b ∈ R {\displaystyle f(x)=\left\langle a,x\right\rangle -b,\,a\in \mathbb {R} ^{n},b\in \mathbb {R} } равно
f ∗ ( x ∗ ) = { b , x ∗ = a + ∞ , x ∗ ≠ a . {\displaystyle f^{*}\left(x^{*}\right)={\begin{cases}b,&x^{*}=a\\+\infty ,&x^{*}\neq a.\end{cases}}} Выпуклое сопряжение степенной функции
f ( x ) = 1 p | x | p , 1 < p < ∞ {\displaystyle f(x)={\frac {1}{p}}|x|^{p},\,1<p<\infty } равно
f ∗ ( x ∗ ) = 1 q | x ∗ | q , 1 < q < ∞ {\displaystyle f^{*}\left(x^{*}\right)={\frac {1}{q}}|x^{*}|^{q},\,1<q<\infty } где 1 p + 1 q = 1. {\displaystyle {\tfrac {1}{p}}+{\tfrac {1}{q}}=1.}
Выпуклое сопряжение функции абсолютной величины
f ( x ) = | x | {\displaystyle f(x)=\left|x\right|} равно
f ∗ ( x ∗ ) = { 0 , | x ∗ | ⩽ 1 ∞ , | x ∗ | > 1. {\displaystyle f^{*}\left(x^{*}\right)={\begin{cases}0,&\left|x^{*}\right|\leqslant 1\\\infty ,&\left|x^{*}\right|>1.\end{cases}}} Выпуклое сопряжение показательной функции f ( x ) = e x {\displaystyle f(x)=\,\!e^{x}} равно
f ∗ ( x ∗ ) = { x ∗ ln x ∗ − x ∗ , x ∗ > 0 0 , x ∗ = 0 ∞ , x ∗ < 0. {\displaystyle f^{*}\left(x^{*}\right)={\begin{cases}x^{*}\ln x^{*}-x^{*},&x^{*}>0\\0,&x^{*}=0\\\infty ,&x^{*}<0.\end{cases}}} Выпуклое сопряжение и преобразование Лежандра показательной функции совпадают за исключением того, что область определения выпуклого сопряжения строго шире, поскольку преобразование Лежандра определено лишь для положительных вещественных чисел.
Пусть F означает интегральную функцию распределения случайной величины X . Тогда (интегрируя по частям),
f ( x ) := ∫ − ∞ x F ( u ) d u = E [ max ( 0 , x − X ) ] = x − E [ min ( x , X ) ] {\displaystyle f(x):=\int _{-\infty }^{x}F(u)\,du=\operatorname {E} \left[\max(0,x-X)\right]=x-\operatorname {E} \left[\min(x,X)\right]} имеет выпуклое сопряжение
f ∗ ( p ) = ∫ 0 p F − 1 ( q ) d q = ( p − 1 ) F − 1 ( p ) + E [ min ( F − 1 ( p ) , X ) ] = p F − 1 ( p ) − E [ max ( 0 , F − 1 ( p ) − X ) ] . {\displaystyle f^{*}(p)=\int _{0}^{p}F^{-1}(q)\,dq=(p-1)F^{-1}(p)+\operatorname {E} \left[\min(F^{-1}(p),X)\right]=pF^{-1}(p)-\operatorname {E} \left[\max(0,F^{-1}(p)-X)\right].} Конкретная интерпретация имеет преобразование
f inc ( x ) := arg sup t t ⋅ x − ∫ 0 1 max { t − f ( u ) , 0 } d u , {\displaystyle f^{\text{inc}}(x):=\arg \sup _{t}\,t\cdot x-\int _{0}^{1}\max\{t-f(u),0\}\,\mathrm {d} u,} как неубывающую перегруппировку начальной функции f. В частности, f inc = f {\displaystyle f^{\text{inc}}=f} для f {\displaystyle f} не убывает.
Выпуклое сопряжение замкнутой выпуклой функции [англ.] снова является замкнутой выпуклой функцией . Выпуклое сопряжение полиэдральной выпуклой функции (выпуклой функции с многогранным надграфиком ) снова является полиэдральной выпуклой функцией.
Выпуклое сопряжение обращает порядок — если f ⩽ g {\displaystyle f\leqslant g} , то f ∗ ⩾ g ∗ {\displaystyle f^{*}\geqslant g^{*}} . Здесь
( f ⩽ g ) : ⟺ ( ∀ x , f ( x ) ⩽ g ( x ) ) . {\displaystyle (f\leqslant g):\iff (\forall x,f(x)\leqslant g(x)).} Для семейства функций ( f α ) α {\displaystyle \left(f_{\alpha }\right)_{\alpha }} это следует из факта, что супремумы могут быть переставлены местами
( inf α f α ) ∗ ( x ∗ ) = sup α f α ∗ ( x ∗ ) , {\displaystyle \left(\inf _{\alpha }f_{\alpha }\right)^{*}(x^{*})=\sup _{\alpha }f_{\alpha }^{*}(x^{*}),} и из max–min неравенства [англ.]
( sup α f α ) ∗ ( x ∗ ) ⩽ inf α f α ∗ ( x ∗ ) . {\displaystyle \left(\sup _{\alpha }f_{\alpha }\right)^{*}(x^{*})\leqslant \inf _{\alpha }f_{\alpha }^{*}(x^{*}).} Выпуклое сопряжение функции всегда полунепрерывно снизу . Двойное сопряжение f ∗ ∗ {\displaystyle f^{**}} (выпуклое сопряжение выпуклого сопряжения) является также замкнутой выпуклой оболочкой , то есть наибольшей полунепрерывной снизу выпуклой функцией с f ∗ ∗ ⩽ f {\displaystyle f^{**}\leqslant f} . Для выпуклых собственных функций [англ.] f = f ∗ ∗ {\displaystyle f=f^{**}} тогда и только тогда, когда f выпукла и полунепрерывна снизу по теореме Фенхеля — Моро .
Для любой функции f и её выпуклого сопряжения f ∗ {\displaystyle f^{*}} неравенство Фенхеля (известное также как неравенство Фенхеля — Моро ) выполняется для любого x ∈ X {\displaystyle x\in X} и p ∈ X ∗ {\displaystyle p\in X^{*}} :
⟨ p , x ⟩ ⩽ f ( x ) + f ∗ ( p ) . {\displaystyle \left\langle p,x\right\rangle \leqslant f(x)+f^{*}(p).} Доказательство следует немедленно из определения выпуклого сопряжения: f ∗ ( p ) = sup x ~ { ⟨ p , x ~ ⟩ − f ( x ~ ) } ⩾ ⟨ p , x ⟩ − f ( x ) {\displaystyle f^{*}(p)=\sup _{\tilde {x}}\{\langle p,{\tilde {x}}\rangle -f({\tilde {x}})\}\geqslant \langle p,x\rangle -f(x)} .
Для двух функций f 0 {\displaystyle f_{0}} и f 1 {\displaystyle f_{1}} и числа 0 ⩽ λ ⩽ 1 {\displaystyle 0\leqslant \lambda \leqslant 1} выполняется
( ( 1 − λ ) f 0 + λ f 1 ) ∗ ⩽ ( 1 − λ ) f 0 ∗ + λ f 1 ∗ {\displaystyle \left((1-\lambda )f_{0}+\lambda f_{1}\right)^{*}\leqslant (1-\lambda )f_{0}^{*}+\lambda f_{1}^{*}} . Здесь операция ∗ {\displaystyle {*}} — это выпуклое отображение в себя.
Инфимальная конволюция двух функций f и g определяется как
( f ◻ g ) ( x ) = inf { f ( x − y ) + g ( y ) | y ∈ R n } . {\displaystyle \left(f\Box g\right)(x)=\inf \left\{f(x-y)+g(y)\,|\,y\in \mathbb {R} ^{n}\right\}.} Пусть f 1 , …, f m будут правильными выпуклыми полунепрерывными снизу функциями на R n {\displaystyle \mathbb {R} ^{n}} . Тогда инфимальная конволюция выпукла и полунепрерывна снизу (но не обязательно будет правильной функцией)[3] и удовлетворяет равенству
( f 1 ◻ ⋯ ◻ f m ) ∗ = f 1 ∗ + ⋯ + f m ∗ . {\displaystyle \left(f_{1}\Box \cdots \Box f_{m}\right)^{*}=f_{1}^{*}+\cdots +f_{m}^{*}.} Инфимальная конволюция двух функций имеет геометрическую интерпретацию — (строгий) надграфик инфимальной конволюции двух функций равен сумме Минковского (строгих) надграфиков этих функций[4] .
Если функция f {\displaystyle f} дифференцируема, то её производная является максимизирующим аргументом при вычислении выпуклого сопряжения:
f ′ ( x ) = x ∗ ( x ) := arg sup x ∗ ⟨ x , x ∗ ⟩ − f ∗ ( x ∗ ) {\displaystyle f^{\prime }(x)=x^{*}(x):=\arg \sup _{x^{*}}{\langle x,x^{*}\rangle }-f^{*}(x^{*})} и f ∗ ′ ( x ∗ ) = x ( x ∗ ) := arg sup x ⟨ x , x ∗ ⟩ − f ( x ) ; {\displaystyle f^{{*}\prime }(x^{*})=x(x^{*}):=\arg \sup _{x}{\langle x,x^{*}\rangle }-f(x);} откуда
x = ∇ f ∗ ( ∇ f ( x ) ) , {\displaystyle x=\nabla f^{*}(\nabla f(x)),} x ∗ = ∇ f ( ∇ f ∗ ( x ∗ ) ) , {\displaystyle x^{*}=\nabla f(\nabla f^{*}(x^{*})),} и, более того,
f ′ ′ ( x ) ⋅ f ∗ ′ ′ ( x ∗ ( x ) ) = 1 , {\displaystyle f^{\prime \prime }(x)\cdot f^{{*}\prime \prime }(x^{*}(x))=1,} f ∗ ′ ′ ( x ∗ ) ⋅ f ′ ′ ( x ( x ∗ ) ) = 1. {\displaystyle f^{{*}\prime \prime }(x^{*})\cdot f^{\prime \prime }(x(x^{*}))=1.} Если для некоторого γ > 0 {\displaystyle \gamma >0} g ( x ) = α + β x + γ ⋅ f ( λ x + δ ) {\displaystyle \,g(x)=\alpha +\beta x+\gamma \cdot f(\lambda x+\delta )} , то
g ∗ ( x ∗ ) = − α − δ x ∗ − β λ + γ ⋅ f ∗ ( x ∗ − β λ γ ) . {\displaystyle g^{*}(x^{*})=-\alpha -\delta {\frac {x^{*}-\beta }{\lambda }}+\gamma \cdot f^{*}\left({\frac {x^{*}-\beta }{\lambda \gamma }}\right).} В случае дополнительного параметра (скажем, α {\displaystyle \alpha } ), более того,
f α ( x ) = − f α ( x ~ ) , {\displaystyle f_{\alpha }(x)=-f_{\alpha }({\tilde {x}}),} где x ~ {\displaystyle {\tilde {x}}} где выбирается максимизирующим аргументом.
Пусть A будет ограниченным линейным оператором из X в Y . Для любой выпуклой функции f на X , имеем
( A f ) ∗ = f ∗ A ∗ {\displaystyle \left(Af\right)^{*}=f^{*}A^{*}} где
( A f ) ( y ) = inf { f ( x ) : x ∈ X , A x = y } {\displaystyle (Af)(y)=\inf\{f(x):x\in X,Ax=y\}} является прообразом f для A , а A * является сопряжённым оператором для A [5] .
Замкнутая выпуклая функция f симметрична для заданного множества G ортогональных линейных преобразований
f ( A x ) = f ( x ) , ∀ x , ∀ A ∈ G {\displaystyle f\left(Ax\right)=f(x),\;\forall x,\;\forall A\in G} тогда и только тогда, когда выпуклое сопряжение f * симметрично для G .
Следующая таблица даёт преобразования Лежандра для многих часто употребимых функций, а также для нескольких полезных свойств[6] .
g ( x ) {\displaystyle g(x)} dom ( g ) {\displaystyle \operatorname {dom} (g)} g ∗ ( x ∗ ) {\displaystyle g^{*}(x^{*})} dom ( g ∗ ) {\displaystyle \operatorname {dom} (g^{*})} f ( a x ) {\displaystyle f(ax)} (где a ≠ 0 {\displaystyle a\neq 0} ) X {\displaystyle X} f ∗ ( x ∗ a ) {\displaystyle f^{*}\left({\frac {x^{*}}{a}}\right)} X ∗ {\displaystyle X^{*}} f ( x + b ) {\displaystyle f(x+b)} X {\displaystyle X} f ∗ ( x ∗ ) − ⟨ b , x ∗ ⟩ {\displaystyle f^{*}(x^{*})-\langle b,x^{*}\rangle } X ∗ {\displaystyle X^{*}} a f ( x ) {\displaystyle af(x)} (где a > 0 {\displaystyle a>0} ) X {\displaystyle X} a f ∗ ( x ∗ a ) {\displaystyle af^{*}\left({\frac {x^{*}}{a}}\right)} X ∗ {\displaystyle X^{*}} α + β x + γ ⋅ f ( λ x + δ ) {\displaystyle \alpha +\beta x+\gamma \cdot f(\lambda x+\delta )} X {\displaystyle X} − α − δ x ∗ − β λ + γ ⋅ f ∗ ( x ∗ − β γ λ ) ( γ > 0 ) {\displaystyle -\alpha -\delta {\frac {x^{*}-\beta }{\lambda }}+\gamma \cdot f^{*}\left({\frac {x^{*}-\beta }{\gamma \lambda }}\right)\quad (\gamma >0)} X ∗ {\displaystyle X^{*}} | x | p p {\displaystyle {\frac {|x|^{p}}{p}}} (где p > 1 {\displaystyle p>1} ) R {\displaystyle \mathbb {R} } | x ∗ | q q {\displaystyle {\frac {|x^{*}|^{q}}{q}}} (где 1 p + 1 q = 1 {\displaystyle {\frac {1}{p}}+{\frac {1}{q}}=1} ) R {\displaystyle \mathbb {R} } − x p p {\displaystyle {\frac {-x^{p}}{p}}} (где 0 < p < 1 {\displaystyle 0<p<1} ) R + {\displaystyle \mathbb {R} _{+}} − ( − x ∗ ) q q {\displaystyle {\frac {-(-x^{*})^{q}}{q}}} (где 1 p + 1 q = 1 {\displaystyle {\frac {1}{p}}+{\frac {1}{q}}=1} ) R − {\displaystyle \mathbb {R} _{-}} 1 + x 2 {\displaystyle {\sqrt {1+x^{2}}}} R {\displaystyle \mathbb {R} } − 1 − ( x ∗ ) 2 {\displaystyle -{\sqrt {1-(x^{*})^{2}}}} [ − 1 , 1 ] {\displaystyle [-1,1]} − log ( x ) {\displaystyle -\log(x)} R + + {\displaystyle \mathbb {R} _{++}} − ( 1 + log ( − x ∗ ) ) {\displaystyle -(1+\log(-x^{*}))} R − − {\displaystyle \mathbb {R} _{--}} e x {\displaystyle e^{x}} R {\displaystyle \mathbb {R} } { x ∗ log ( x ∗ ) − x ∗ if x ∗ > 0 0 if x ∗ = 0 {\displaystyle {\begin{cases}x^{*}\log(x^{*})-x^{*}&{\text{if }}x^{*}>0\\0&{\text{if }}x^{*}=0\end{cases}}} R + {\displaystyle \mathbb {R} _{+}} log ( 1 + e x ) {\displaystyle \log \left(1+e^{x}\right)} R {\displaystyle \mathbb {R} } { x ∗ log ( x ∗ ) + ( 1 − x ∗ ) log ( 1 − x ∗ ) if 0 < x ∗ < 1 0 if x ∗ = 0 , 1 {\displaystyle {\begin{cases}x^{*}\log(x^{*})+(1-x^{*})\log(1-x^{*})&{\text{if }}0<x^{*}<1\\0&{\text{if }}x^{*}=0,1\end{cases}}} [ 0 , 1 ] {\displaystyle [0,1]} − log ( 1 − e x ) {\displaystyle -\log \left(1-e^{x}\right)} R {\displaystyle \mathbb {R} } { x ∗ log ( x ∗ ) − ( 1 + x ∗ ) log ( 1 + x ∗ ) if x ∗ > 0 0 if x ∗ = 0 {\displaystyle {\begin{cases}x^{*}\log(x^{*})-(1+x^{*})\log(1+x^{*})&{\text{if }}x^{*}>0\\0&{\text{if }}x^{*}=0\end{cases}}} R + {\displaystyle \mathbb {R} _{+}}
↑ Legendre Transform (неопр.) . Дата обращения: 14 апреля 2019. Архивировано 28 июля 2020 года. ↑ Frank Nielsen. Legendre transformation and information geometry (неопр.) . Дата обращения: 19 апреля 2019. Архивировано 11 ноября 2013 года. ↑ Phelps, 1991 , с. 42. ↑ Bauschke, Goebel, Lucet, Wang, 2008 , с. 766. ↑ Иоффе, Тихомиров, 1974 , с. утверждение 3.4.3. ↑ Borwein, Lewis, 2006 , с. 50–51. Robert R. Phelps. Convex Functions, Monotone Operators and Differentiability. — Springer, 1991. — ISBN 0-387-56715-1 . Heinz H. Bauschke, Rafal Goebel, Yves Lucet, Xianfu Wang. The Proximal Average: Basic Theory // SIAM Journal on Optimization. — 2008. — Т. 19 , вып. 2 . — doi :10.1137/070687542 . Иоффе А. Д., Тихомиров В. М. Теория экстремальных задач. — М. : «Наука», 1974. Jonathan Borwein, Adrian Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. — Springer, 2006. — ISBN 978-0-387-29570-1 . Владимир Игоревич Арнольд. Математические методы классической механики. — М. : «Наука», 1989. R. Tyrrell Rockafellar. Convex Analysis . — Princeton: Princeton University Press, 1970. — ISBN 0-691-01586-4 .