Conjugated function – Wikipedia

In mathematics, and more precisely in convex analysis, the conjugated function is a function built from a real function

${displaystyle f}$

Defined on a vector space

${displaystyle mathbb {E} }$

, which is useful:

The combined function of

${displaystyle f}$

is most often noted

${displaystyle f^{*}}$

. It is a convex function, even if

${displaystyle f}$

is not, defined on slopes , that is to say on the elements of the dual vector space of

${displaystyle mathbb {E} }$

. The definition is motivated and specified below.

L’application

${displaystyle fto f^{*}}$

is called transformation de Fenchel or Legendre transformation or Transformation de Legendre-Fnechel , the APRIIIIr Adrien-Mary Legendrere it Werner Fenchel.

Supposed knowledge : linear algebra, differential calculation, the bases of convex analysis (in particular the main concepts attached to convex sets and functions); The subdifferential of a convex function is only used to motivate the definition of combined function.

The apparent complexity of the concept of combined function requires motivating its definition.

Function convexification [ modifier | Modifier and code ]

By definition, a function is convex if its epigraph is convex. Convex a function

${displaystyle f:mathbb {E} to {bar {mathbb {R} }}}$

consists in determining the largest convex function, let’s say closed, reduced

${displaystyle f}$

. In terms of epigraph, this amounts to finding the smallest closed convex containing the epigraph of

${displaystyle f}$

, that is to say to take the closed convex envelope of the epigraph

${displaystyle operatorname {epi} ,fsubset mathbb {E} times mathbb {R} .}$

Like any closed convex envelope, that of

${displaystyle operatorname {epi} ,f}$

is the intersection of every closed half-space containing

${displaystyle operatorname {epi} ,f}$

, that is, sets of the form

${displaystyle H^{-}(xi ,tau ,t):={(x,alpha )in mathbb {E} times mathbb {R} :langle xi ,xrangle +tau alpha leqslant t},}$

Or

${displaystyle (xi ,tau ,t)in mathbb {E} times mathbb {R} times mathbb {R} }$

. It is easy to see that when

${Displaystyle h^{-} (xi, tau, t)}$

contains an epigraph, we must have

${displaystyle tau leqslant 0}$

. It is more thin to show that, in the expression of the closed convex envelope of

${displaystyle operatorname {epi} ,f}$

as an intersection of

${Displaystyle h^{-} (xi, tau, t)}$

, we can only keep half-spaces with

${displaystyle tau <0}$

. However, these are the epigraphs of the Minurants Affines de

${displaystyle f}$

of shape

${displaystyle xmapsto leftlangle {frac {-xi }{tau }},xrightrangle +{frac {t}{tau }}.}$

Summons. As you would expect, the closed convenience of

${displaystyle f}$

is the upper envelope of all the Minurant Affines of

${displaystyle f}$

. Parmi les diminishing affines

${displaystyle xmapsto langle s,xrangle +alpha }$

having a slope

${displaystyle sin mathbb {E} }$

fixed, one can also keep only the one that is the highest, that is to say the one that has the greatest

${displaystyle alpha }$

. We must therefore determine the greatest

${displaystyle alpha }$

such as

${displaystyle forall ,xin mathbb {E} ,:quad langle s,xrangle +alpha leqslant f(x)quad {mbox{ou}}quad langle s,xrangle -f(x)leqslant -alpha .}$

We clearly see that the smallest value of

${displaystyle -alpha }$

is given by

${displaystyle f^{*}(s):=sup _{xin mathbb {E} }{Bigl (}langle s,xrangle -f(x){Bigr )}.}$

It is the value of the combination of

${displaystyle f}$

in

${displaystyle s}$

. We are interested in

${displaystyle -alpha }$

rather than

${displaystyle alpha }$

to define

${displaystyle f^{*}}$

in order to obtain a conjugated conjugated function.

Access route to the subdifferential [ modifier | Modifier and code ]

In this section, we show the interest of the concept of combined function as a tool to calculate the subdifferential of a convex function.

The subdifferential

${displaystyle partial f(x)}$

of a convex function

${displaystyle f}$

in

${displaystyle x}$

is the set of slopes of minorating the affines of

${displaystyle f}$

(i.e., des fonctions affines that less

${displaystyle f}$

), which are accurate in

${displaystyle x}$

(i.e., who have the same value as

${displaystyle f}$

in

${displaystyle x}$

). For

${displaystyle x}$

given, it is not always easy to specify all the minor affins exact in

${displaystyle x}$

. It is sometimes easier to give yourself a slope

${displaystyle s}$

of Minurant Affine

${displaystyle xmapsto langle s,xrangle +alpha }$

and seek the points it may be exact by modifying

${displaystyle alpha }$

. From this point of view, we are looking for the largest

${displaystyle alpha }$

such as

${displaystyle forall ,xin mathbb {E} ,:quad langle s,xrangle +alpha leqslant f(x)quad {mbox{ou}}quad langle s,xrangle -f(x)leqslant -alpha .}$

We clearly see that the smallest value of

${displaystyle -alpha }$

is given by

${displaystyle f^{*}(s):=sup _{xin mathbb {E} }{Bigl (}langle s,xrangle -f(x){Bigr )}.}$

It is the value of the combination of

${displaystyle f}$

in

${displaystyle s}$

. We are interested in

${displaystyle -alpha }$

rather than

${displaystyle alpha }$

to define

${displaystyle f^{*}}$

in order to obtain a conjugated conjugated function. Let’s get back to the problem we were asking at the start of this paragraph: if

${displaystyle x}$

is solution of the maximization problem above, then

${DisplayStyle Langle S, Xrangle -F (x) Geqslant Langle S, Yrangle -F (Y)}$

for everything

${displaystyle yin mathbb {E} }$

or

${displaystyle forall ,yin mathbb {E} ,:quad f(y)geqslant f(x)+langle s,y-xrangle .}$

These inequalities show that

${displaystyle ymapsto f(x)+langle s,y-xrangle }$

is a minor refine

${displaystyle f}$

, Exact and

${displaystyle x}$

.

It is assumed in this section that the functions are defined in a euclidean vector space

${displaystyle mathbb {E} }$

(of finished dimension therefore), whose scalar product is noted

${displaystyle langle cdot ,cdot rangle }$

and the associated standard

${displaystyle |cdot |}$

.

On note

The combined and its properties [ modifier | Modifier and code ]

We chose to designate by

${displaystyle s}$

l’Argment of

${displaystyle f^{*}}$

to remember that this is a slope ( slope in English), that is to say an element of the dual space of

${displaystyle mathbb {E} }$

, here identified with

${displaystyle mathbb {E} }$

via the scalar product.

We are interested below in the convexity and the clean and closed character of the conjugated

${displaystyle f^{*}}$

. The convexity of

${displaystyle f^{*}}$

is a remarkable property of the combined, since it is remembered that

${displaystyle f}$

is not necessarily convex.

It will be remembered that a convex and clean function necessarily has an affine minor; It therefore checks the properties of point 1 above, so that

${displaystyle fin operatorname {Conv} (mathbb {E} )quad Longrightarrow quad f^{*}in operatorname {C{overline {onv}}} (mathbb {E} ).}$

The biconjugated and its properties [ modifier | Modifier and code ]

We can of course apply the transformation of Legendre-Fenchel to the combined function

${displaystyle f^{*}}$

; We thus obtain the biconjugated of

${displaystyle f}$

, noted

${displaystyle f^{**}}$

.

The convex, closed and clean character of the biconjugated is examined in the following result.

If the argument

${displaystyle s}$

of

${displaystyle f^{*}}$

is a slope (identified with an element of

${displaystyle mathbb {E} }$

), l’argument

${displaystyle x}$

of

${displaystyle f^{**}}$

is in the starting space

${displaystyle mathbb {E} }$

. We can then wonder if there is a link between

${displaystyle f}$

And

${displaystyle f^{**}}$

. The following proposal examines this question. We noted there

${displaystyle {bar {f}}}$

, the closure of

${displaystyle f}$

.

This result makes it possible to compare the values ​​of

${displaystyle f^{**}}$

And

${displaystyle f}$

.

If we take the combined of the biconjugated, we find the conjugated. There is therefore no concept of triconjuguée .

Conjugated rules for calculating [ modifier | Modifier and code ]

Inf-image under a linear application [ modifier | Modifier and code ]

Let us recall the definition of Inf-image of a function under a linear application . We give ourselves two Euclidian spaces

${displaystyle mathbb {E} }$

And

${displaystyle mathbb {F} }$

(we will need a scalar product here on

${displaystyle mathbb {E} }$

And

${displaystyle mathbb {F} }$

, while this structure is not necessary in the definition of

${displaystyle fveebar A}$

), a function

${displaystyle f:mathbb {E} to {bar {mathbb {R} }}}$

and a linear application

${displaystyle A:mathbb {E} to mathbb {F} }$

. Then the inf-image of

${displaystyle f}$

below

${displaystyle A}$

is the noted application

${displaystyle fveebar A:mathbb {F} to {bar {mathbb {R} }}}$

and defined in

${displaystyle yin mathbb {F} }$

about

${displaystyle (fveebar A)(y)=inf _{{xin mathbb {E} } atop {Ax=y}};f(x).}$

Pre-composition with a linear application [ modifier | Modifier and code ]

Examples [ modifier | Modifier and code ]

Rules [ modifier | Modifier and code ]

Either

${displaystyle f:mathbb {E} to mathbb {R} :xmapsto |x|}$

A standard on a Euclidean space

${displaystyle mathbb {E} }$

, not necessarily derived from the scalar product

${displaystyle langle cdot ,cdot rangle }$

of

${displaystyle mathbb {E} }$

. We introduce the dual standard

${displaystyle |s|_{_{D}}:=sup _{|x|leqslant 1};langle s,xrangle }$

and the closed duality ball

${Displaystyle {bar {b}} _ {_ {d}}: = {sin mathbb {e}: | S | _ {_ {d}} ledlant 1}.}$

The combined function

${displaystyle f^{*}:mathbb {E} to mathbb {R} }$

of

${displaystyle f}$

is the indicator of the dual unit ball; So she takes in

${displaystyle sin mathbb {E} }$

the following value

Now consider the power

${displaystyle p>1}$

${displaystyle f:mathbb {E} to mathbb {R} :xmapsto {frac {1}{p}},|x|^{p}.}$

Its conjugated function

${displaystyle f^{*}:mathbb {E} to mathbb {R} }$

Take in

${displaystyle sin mathbb {E} }$

the following value

Or

${displaystyle p’:=p/(p-1)>1}$

${displaystyle p}$

:

${displaystyle {frac {1}{p}}+{frac {1}{p’}}=1.}$

Distance to a convex [ modifier | Modifier and code ]

Maximum proper value [ modifier | Modifier and code ]

Elements of history [ modifier | Modifier and code ]

The combined function was introduced by Mandelbrojt (1939) for a function of a single real variable; Then specified and improved by Fenchel (1949) with convex functions depending on a finished number of variables. The latter introduces the notation

${displaystyle f^{*}}$

For the combined of

${displaystyle f}$

. Conjugation generalizes a function transformation introduced much earlier by Legendre (1787). The extension to topological vector spaces is due to Brønsted (1964), Moreau (1967) and Rockafellar.

Related articles [ modifier | Modifier and code ]

Bibliography [ modifier | Modifier and code ]

• (in) J. M. Borwein et A. S. Lewis, Convex Analysis and Nonlinear Optimization , New York, Springer, 2000 .
• (in) A. Brøndsted, ‘ Conjugate convex functions in topological vector spaces. » , Mathematical Physical Messages Published by the Royal Danish Society of Sciences , n ^O 34, 1964 , p. 1–26 .
• (in) W. Fenchel, ‘ On conjugate functions » , Canadian Journal of Mathematics , vol. 1, 1949 , p. 73–77 .
• (in) J.-B. Hiriart-Urrey et C. Lemaréchal, ‘ Convex Analysis and Minimization Algorithms » , Basics of mathematical Sciences , Springer-Verlag, 1993 , p. 305-306 .
• (in) J.-B. Hiriart-Urrey et C. Lemaréchal, Fundamentals of convex analysis , Berlin, Springer-Verlag, 2001 .
• (in) A.M. Legendre, Memory on the integration of some equations with partial differences , coll. «My. ACAD. Sciences », 1787 , p. 309–351 .
• (in) S. Mandelbrojt, ‘ On convex functions » , C. R. Acad. Sci. Paris , vol. 209, 1939 , p. 977-978 .
• J.J. Moreau, Convex functional , France secondary school, coll. “Seminar with partial drift equations”, 1967 .
• (in) R.T. Rockafellar, ‘ Convex Analysis » , Princeton Mathematics , Princeton, New Jersey, Princeton University Press,, 28 ^{It is} series, 1970 .