Convex conjugate

In mathematics and mathematical optimization, the convex conjugate of a function is a generalization of the Legendre transformation which applies to non-convex functions. It is also known as Legendre–Fenchel transformation, Fenchel transformation, or Fenchel conjugate (after Adrien-Marie Legendre and Werner Fenchel). The convex conjugate is widely used for constructing the dual problem in optimization theory, thus generalizing Lagrangian duality.

Definition

Let

X

{\displaystyle X}

be a real topological vector space and let

X

∗

{\displaystyle X^{*}}

be the dual space to

X

{\displaystyle X}

. Denote by

⟨

⋅

,

⋅

⟩

:

X

∗

×

X

→

R

{\displaystyle \langle \cdot ,\cdot \rangle :X^{*}\times X\to \mathbb {R} }

the canonical dual pairing, which is defined by

⟨

x

∗

,

x

⟩

=

x

∗

(

x

)

.

{\displaystyle \left\langle x^{*},x\right\rangle =x^{*}(x).}

For a function

f

:

X

→

R

∪

{

−

∞

,

+

∞

}

{\displaystyle f:X\to \mathbb {R} \cup \{-\infty ,+\infty \}}

taking values on the extended real number line, its convex conjugate is the function

f

∗

:

X

∗

→

R

∪

{

−

∞

,

+

∞

}

{\displaystyle f^{*}:X^{*}\to \mathbb {R} \cup \{-\infty ,+\infty \}}

whose value at

x

∗

∈

X

∗

{\displaystyle x^{*}\in X^{*}}

is defined to be the supremum:

f

∗

(

x

∗

)

:=

sup

{

⟨

x

∗

,

x

⟩

−

f

(

x

)

:

x

∈

X

}

,

{\displaystyle f^{*}\left(x^{*}\right):=\sup \left\{\left\langle x^{*},x\right\rangle -f(x)~\colon ~x\in X\right\},}

or, equivalently, in terms of the infimum:

f

∗

(

x

∗

)

:=

−

inf

{

f

(

x

)

−

⟨

x

∗

,

x

⟩

:

x

∈

X

}

.

{\displaystyle f^{*}\left(x^{*}\right):=-\inf \left\{f(x)-\left\langle x^{*},x\right\rangle ~\colon ~x\in X\right\}.}

This definition can be interpreted as an encoding of the convex hull of the function's epigraph in terms of its supporting hyperplanes.

Examples

For more examples, see § Table of selected convex conjugates.

The convex conjugate of an affine function

f

(

x

)

=

⟨

a

,

x

⟩

−

b

{\displaystyle f(x)=\left\langle a,x\right\rangle -b}

is

f

∗

(

x

∗

)

=

{

b

,

x

∗

=

a

+

∞

,

x

∗

≠

a

.

{\displaystyle f^{*}\left(x^{*}\right)={\begin{cases}b,&x^{*}=a\\+\infty ,&x^{*}\neq a.\end{cases}}}

The convex conjugate of a power function

f

(

x

)

=

1

p

|

x

|

p

,

1

<

p

<

∞

{\displaystyle f(x)={\frac {1}{p}}|x|^{p},1<p<\infty }

is

f

∗

(

x

∗

)

=

1

q

|

x

∗

|

q

,

1

<

q

<

∞

,

where

1

p

+

1

q

=

1.