Convex analysis explained

Convex analysis is the branch of mathematics devoted to the study of properties of convex functions and convex sets, often with applications in convex minimization, a subdomain of optimization theory.

Convex sets

See main article: Convex set.

A subset

C\subseteqX

of some vector space

X

is if it satisfies any of the following equivalent conditions:
  1. If

0\leqr\leq1

is real and

x,y\inC

then

rx+(1-r)y\inC.

  1. If

0<r<1

is real and

x,y\inC

with

x ≠ y,

then

rx+(1-r)y\inC.

See main article: Convex function.

Throughout,

f:X\to[-infty,infty]

will be a map valued in the extended real numbers

[-infty,infty]=R\cup\{\pminfty\}

with a domain

\operatorname{domain}f=X

that is a convex subset of some vector space. The map

f:X\to[-infty,infty]

is a if

holds for any real

0<r<1

and any

x,y\inX

with

x ≠ y.

If this remains true of

f

when the defining inequality is replaced by the strict inequality

then

f

is called .

Convex functions are related to convex sets. Specifically, the function

f

is convex if and only if its is a convex set. The epigraphs of extended real-valued functions play a role in convex analysis that is analogous to the role played by graphs of real-valued function in real analysis. Specifically, the epigraph of an extended real-valued function provides geometric intuition that can be used to help formula or prove conjectures.

The domain of a function

f:X\to[-infty,infty]

is denoted by

\operatorname{domain}f

while its is the set

The function

f:X\to[-infty,infty]

is called if

\operatorname{dom}f ≠ \varnothing

and

f(x)>-infty

for

x\in\operatorname{domain}f.

Alternatively, this means that there exists some

x

in the domain of

f

at which

f(x)\inR

and

f

is also equal to

-infty.

In words, a function is if its domain is not empty, it never takes on the value

-infty,

and it also is not identically equal to

+infty.

If

f:Rn\to[-infty,infty]

is a proper convex function then there exist some vector

b\inRn

and some

r\inR

such that

f(x)\geqx ⋅ b-r

for every

x

where

x ⋅ b

denotes the dot product of these vectors.

Convex conjugate

See main article: Convex conjugate. The of an extended real-valued function

f:X\to[-infty,infty]

(not necessarily convex) is the function

f*:X*\to[-infty,infty]

from the (continuous) dual space

X*

of

X,

and

f*\left(x*\right)=\supz\left\{\left\langlex*,z\right\rangle-f(z)\right\}

where the brackets

\left\langle ⋅ , ⋅ \right\rangle

denote the canonical duality

\left\langlex*,z\right\rangle:=x*(z).

The of

f

is the map

f**=\left(f*\right)*:X\to[-infty,infty]

defined by

f**(x):=

\sup
z*\inX*

\left\{\left\langlex,z*\right\rangle-f\left(z*\right)\right\}

for every

x\inX.

If

\operatorname{Func}(X;Y)

denotes the set of

Y

-valued functions on

X,

then the map

\operatorname{Func}(X;[-infty,infty])\to\operatorname{Func}\left(X*;[-infty,infty]\right)

defined by

f\mapstof*

is called the .

Subdifferential set and the Fenchel-Young inequality

If

f:X\to[-infty,infty]

and

x\inX

then the is

\begin{alignat}{4} \partialf(x):&=\left\{x*\inX*~:~f(z)\geqf(x)+\left\langlex*,z-x\right\rangleforallz\inX\right\}&&(“z\inX''canbereplacedwith:“z\inXsuchthatz ≠ x'')\\ &=\left\{x*\inX*~:~\left\langlex*,x\right\rangle-f(x)\geq\left\langlex*,z\right\rangle-f(z)forallz\inX\right\}&&\\ &=\left\{x*\inX*~:~\left\langlex*,x\right\rangle-f(x)\geq\supz\left\langlex*,z\right\rangle-f(z)\right\}&&Therighthandsideisf*\left(x*\right)\\ &=\left\{x*\inX*~:~\left\langlex*,x\right\rangle-f(x)=f*\left(x*\right)\right\}&&Takingz:=xinthe\sup{}givestheinequality\leq.\\ \end{alignat}

For example, in the important special case where

f=\| ⋅ \|

is a norm on

X

, it can be shown[1] that if

0 ≠ x\inX

then this definition reduces down to:

\partialf(x)=\left\{x*\inX*~:~\left\langlex*,x\right\rangle=\|x\|and\left\|x*\right\|=1\right\}

and

\partialf(0)=\left\{x*\inX*~:~\left\|x*\right\|\leq1\right\}.

For any

x\inX

and

x*\inX*,

f(x)+f*\left(x*\right)\geq\left\langlex*,x\right\rangle,

which is called the . This inequality is an equality (i.e.

f(x)+f*\left(x*\right)=\left\langlex*,x\right\rangle

) if and only if

x*\in\partialf(x).

It is in this way that the subdifferential set

\partialf(x)

is directly related to the convex conjugate

f*\left(x*\right).

Biconjugate

The of a function

f:X\to[-infty,infty]

is the conjugate of the conjugate, typically written as

f**:X\to[-infty,infty].

The biconjugate is useful for showing when strong or weak duality hold (via the perturbation function).

For any

x\inX,

the inequality

f**(x)\leqf(x)

follows from the . For proper functions,

f=f**

if and only if

f

is convex and lower semi-continuous by Fenchel–Moreau theorem.

Convex minimization

See main article: Convex optimization. A is one of the form

find

infxf(x)

when given a convex function

f:X\to[-infty,infty]

and a convex subset

M\subseteqX.

Dual problem

See main article: Duality (optimization). In optimization theory, the states that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem.

In general given two dual pairs separated locally convex spaces

\left(X,X*\right)

and

\left(Y,Y*\right).

Then given the function

f:X\to[-infty,infty],

we can define the primal problem as finding

x

such that

infxf(x).

If there are constraint conditions, these can be built into the function

f

by letting

f=f+Iconstraints

where

I

is the indicator function. Then let

F:X x Y\to[-infty,infty]

be a perturbation function such that

F(x,0)=f(x).

The with respect to the chosen perturbation function is given by

\sup
y*\inY*

-F*\left(0,y*\right)

where

F*

is the convex conjugate in both variables of

F.

The duality gap is the difference of the right and left hand sides of the inequality

\sup
y*\inY*

-F*\left(0,y*\right)\leinfxF(x,0).

This principle is the same as weak duality. If the two sides are equal to each other, then the problem is said to satisfy strong duality.

There are many conditions for strong duality to hold such as:

F=F**

where

F

is the perturbation function relating the primal and dual problems and

F**

is the biconjugate of

F

;

Lagrange duality

For a convex minimization problem with inequality constraints,

min{}xf(x)

subject to

gi(x)\leq0

for

i=1,\ldots,m.

the Lagrangian dual problem is

\sup{}uinf{}xL(x,u)

subject to

ui(x)\geq0

for

i=1,\ldots,m.

where the objective function

L(x,u)

is the Lagrange dual function defined as follows:

L(x,u)=f(x)+

m
\sum
j=1

ujgj(x)

References

Notes and References

  1. The conclusion is immediate if

    X=\{0\}

    so assume otherwise. Fix

    x\inX.

    Replacing

    f

    with the norm gives

    \partialf(x)=\left\{x*\inX*~:~\left\langlex*,x\right\rangle-\|x\|\geq\left\langlex*,z\right\rangle-\|z\|forallz\inX\right\}.

    If

    x*\in\partialf(x)

    and

    r\geq0

    is real then using

    z:=rx

    gives

    \left\langlex*,x\right\rangle-\|x\|\geq\left\langlex*,rx\right\rangle-\|rx\|=r\left[\left\langlex*,x\right\rangle-\|x\|\right],

    where in particular, taking

    r:=2

    gives

    x*(x)\geq\|x\|

    while taking

    r:=

    1{2}
    gives

    x*(x)\leq\|x\|

    and thus moreover, if in addition

    x ≠ 0

    then because
    *\left(x
    \|x\|
    x

    \right)=1,

    it follows from the definition of the dual norm that

    \left\|x*\right\|\geq1.

    Because

    \partialf(x)\subseteq\left\{x*\inX*~:~x*(x)=\|x\|\right\},

    which is equivalent to

    \partialf(x)=\partialf(x)\cap\left\{x*\inX*~:~x*(x)=\|x\|\right\},

    it follows that

    \partialf(x)=\left\{x*\inX*~:~x*(x)=\|x\|and\|z\|\geq\left\langlex*,z\right\rangleforallz\inX\right\},

    which implies

    \left\|x*\right\|\leq1

    for all

    x*\in\partialf(x).

    From these facts, the conclusion can now be reached. ∎

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Convex analysis".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.