A course in Convex Analysis

几何,凸集,凸多面体国外文献

ICM, Warsaw, June 2003

Lecture notes compiled thanks to the support of

the Interdisciplinary Centrum for Mathematical and Computational Modelling (ICM),Warsaw University

http://www.icm.edu.pl/eng/

and

the Institute of Mathematics of the Polish Academy of Sciences (IM PAN),Warsaw

http://www.impan.gov.pl/

acting as a Stefan Banach Centre of Excellence

http://www.impan.gov.pl/Excellence/

The author:

Alain Bossavit

LGEP (CNRS)

11 Rue Joliot-Curie

91192 Gif-sur-Yvette CEDEX (France)

bossavit@lgep.supelec.fr

http://wendang.chazidian.com.tut.fi/~bossavit/ [as of Nov. 2011]To G.A course in©Alain Bossavit1986-2003Convex Analysis

几何,凸集,凸多面体国外文献

Contents

First part: Basic notions

1. Functions, minima, maxima

1. Functions

1.1 Sets, relations 1.2 Functions

2. Real-valued functions

2.1 Functions of a single variable2.2 Functions of two variables.

Additional exercises HintsSolutions

2. Functional spaces

1. Affine notions2. Complete spaces

2.1 Sequences and series2.2 Compactness 2.3 Completeness

3. Some complete functional spaces

3.1 The space L2 3.2 Prolongation

3.3 Prolongation of grad, and the space H11

0 3.4 The space HHintsSolutions

3. Hilbert spaces

1. "Strong" topology

1.1 Pre-Hilbert spaces

1.2 Projection on a convex set

1.3 Consequences of the projection theorem1.4 Hilbertian "bases" and Fourier series

2. "Weak" topology

2.1 The Baire lemma, and a few consequences.2.2 Weak convergence in Hilbert space 2.3 Weak topology

2.4 Weak topology and convexity 2.5 Weak compactness

Additional exercises HintsSolutions

Second part: Convex analysis

4. Convex functions, and their minimization

11. Semi-continuity

11.1 Definitions and criteria

11.2 Minimization of an l.s.c. function

2. Convex functions.

2.1 Minimum of a convex l.s.c. function 52.2 Convexity and continuity

3. Minimization of convex functions

3.1 The Kuhn and Tucker theorem

83.2 The Arrow–Hurwicz–Uzawa algorithm

9Additional exercises 9HintsSolutions

95. Separating convex sets

910

1. Separation theorems

1.1 Separating hyperplanes1.2 Support hyperplanes1.3 Separating convex sets

14

2. Affine minorization of convex functions

2.1 Prolongation of an affine minorizer2.2 Sub-gradient

Additional exercises Hints16Solutions

166. Convex functions in duality

181. The duality relation

18

1.1 An example1.2 Second example

1.3 Definition and properties

`

2. The conjugation operator

2.1 Conjugation, or "Fenchel transform"21

2.2 Fenchel involution

2.3 Relations with the Legendre transform

Additional exercises HintsSolutions

24References24Index25

262628303233333636

384242424343

47

494949

5152

几何,凸集,凸多面体国外文献

calls section of R by x the following part of Y (Fig. 1):

Chapter 1

Functions, minima, maxima

1. Functions

The point of what follows is not to start anew with Mathematics, but to motivate andmake precise some notational conventions. One of the fields of application ofconvex analysis is optimization, meaning, the search for maxima or minima of somefunctions, and for points at which such extrema are reached. So we need a precisedefinition of these concepts, and an adequate notation, which it will be our first taskto make explicit, because it departs a little from current usage.1.1 Sets, relations

We'll take as primitive notions those of set theory: If X is a set, P(X) denotes theset of all its parts, ? is the empty set. The Cartesian product is denoted X × Y, itselements are the ordered pairs {x, y}. We shall also consider as primitive thenotion of "predicate", that is, of a statement that can assume the values true orfalse. Statements such as, for instance, x ∈ X, or x ≠ y, or A ? B, or elsex ∈ A and y ? B, etc., make as many predicates. If p is a predicate, one usesthe construct

{x ∈ X : p}

to denote the part of X composed of all elements x for which p is true. Givena predicate p, not-p is another, which by definition is true when p is false,and the other way round. Predicates can be combined at will: p and q, p or q,p and (q or r), etc., with truth values as dictated by the well known rules ofBoolean algebra. Especially important among such constructs is q or not-p,which is false when p = true and q = false, and true in all other cases.It's frequent enough to deserve a dedicated notation: p ? q.

Remark. All of this applies of course to propositions: The semantic differencebetween "proposition" and "predicate" is that the latter can incorporate variables, thevalue of which may determine that of the predicate. ?

By way of example, let X and Y be two sets, and R a part of X × Y. One

Rx = {y ∈ Y : {x, y} ∈ R},

which is therefore characterized by the x-parameterized predicate {x, y} ∈ R, aproperty of y, which may be true or false depending on the value of x. Onedefines in the same manner the sections Ry. Another example: if A ? X and B ?Y, one may define the following set, called brick generated by the parts A and B:

A × B = {{x, y} ∈ X × Y : x ∈ A and y ∈ B},

One will check that (A × B)x is either B or ?, and this property of sections (thatnon-empty ones are all the same, for both factors) characterizes bricks among allparts of X × Y. (Do not confuse the section of R by x with the projection of Ralong X, which is the set

pX(R) = {y ∈ Y : Ry ≠ ?

}.)

Figure 1. Notions of "section" and "projection".

If {A ∈ P(X) : p} is a family of subsets of X, that is, a part of P(X),composed of all parts A of X which share a definite property p, one denotes theirunion and intersection by ∪ {A : p} and ∩ {A : p} — only a notational pattern,this, to be adapted to the context. The notion of relation, now coming, will give usa host of examples.

- 1 -

几何,凸集,凸多面体国外文献

A relation r is a triple {X, Y, R}, where X and Y are two sets and R a

part of X

× Y. One calls R the graph of the relation, and Rx is denoted by r(x).If y ∈ r(x), one says that x and y are linked by the relation r. This is anassertion, true or false, and hence a predicate, that one may as well denote x r y. Ifs = {X, Y, S} is another relation, and if R ? S, one says that r is

stronger thans, or that r implies s, which one may denote by r ? s.

Fx

cod(f)

Y

cod(r) = {y ∈ Y : r?1(y) ≠ ?}.

The image of a part A of X by r is the set-union ∪ {r(x) : x ∈ A}. (So thecodomain of r is the image of X by r.) The inverse image of a part B of Y byr is the image of B by r?1, that is to say the set {x ∈ dom(r) : r(x) ∈ B}.If r = {X, Y, R} and s = {X, Y, S} are two relations over the same sets, itseems natural to define the relations associated with the union and intersection oftheir respective graphs:(3)(4)

r and s = {X, Y, R ∩ S},r or s = {X, Y, R ∪ S}.

As one sees, (r and s) ? r, as well as r ? (r or s), and so forth. If now r ={X, Y, R} and s = {Y, Z, S}, the composition of r and s, denoted "r ; s", willbe the relation

r ; s = {X, Z, ∪ {r?1(y) × s(y) : y ∈ Y}}.

Composition is obviously associative. (Exercise 1: Which predicate characterizesthe graph of r ; s ?)

The case when X = Y generates other notions, all well known, which weshall work out anew for practice. One calls diagonal of X × X the set

? = ∪{{x, x} : x ∈ X} ≡ {{x, y} ∈ X × X : x = y}.

The relation id = {X, X, ?} is the identity. A relation r is reflexive if its graphcontains ?, i.e., if id ? r, symmetric if r?1 = r, antisymmetric if

(r and r?1) ? id,

and transitive if (r ; r) ? r. A reflexive and transitive relation is a preorder. Ifmoreover it is symmetric (resp. antisymmetric), it's an equivalence relation (resp.an order). An order r is total if r ∪ r?1 = {X, X, X × X}, i.e., if the predicatex ∈ r(y) or y ∈ r?1(x) always assumes the value true. If r = {X, X, R} is anorder (like, e.g., the relation ≤ over IR), one calls {X, X, R ? ?} the strictassociated relation (example: < over IR is thus associated with ≤). Be aware thatthis associated relation is not an order.

Figure 2. Domain, codomain. Right, the case of a functional graph.

The domain of a relation r is the following part of X:(1)

dom(r) = {x ∈ X : r(x) ≠ ?}.

Its codomain, denoted cod(r), also called range, is the union of all parts A of Ywhich share the property "A = r(x) for at least one x ∈ X", which authorizes us towrite(2)

cod(r) = ∪ {r(x) : x ∈ X}.

Domain and codomain are empty if and only if R is the empty set. If r ={X, Y, R} is a relation, and if one sets

R?1 = {{y, x} ∈ Y × X : {x, y} ∈ R},

then r?1 will be the relation {X, Y, R?1}, called the inverse of r. According to (1)and (2), cod(r?1) = dom(r). As one sees, an alternative to (1) is thus

dom(r) = ∪ {r?1(y) : y ∈ Y},

and (2) can also be written like this:

- 2 -

几何,凸集,凸多面体国外文献

1.2 Functions

The graph F of a relation f = {X, Y, F} is said to be functional if no section Fxcontains more than one element of Y. The relation f is then called a function "fromX to Y", or "Y-valued". Function f is surjective if cod(f) = Y, injective if f?1also is a function (the inverse of f), bijective if both f and f–1 are surjective. Theset of all functions from X to Y will be denoted X → Y, and one will refer tothem all as "functions of type X → Y". Let us stress that if f is thus of type X →Y, the equality dom(f) = X does not hold, in general. So what we call functions,here, are so-called "partial" functions, not necessarily "defined over all X". Thecomposition f ; g of two functions is again a function (of type X → Z, if f ∈ X →Y and g ∈ Y → Z). We shall prefer this notation to the more common1 g ο f.

We shall often use "map" instead of "function", with exactly the same meaning.2

The set or sets which play a role in any specific question are in general structuredby the existence of some relations, then called, most often, operations. For instance,on the real field IR, the relation ≥, or the operation +, or the multiplication ? (allfunctions of type IR × IR → IR with domain IR × IR), or the division /, withdomain IR × (IR ? {0}). Or else, on the set composed of the two elements trueand false, the operations and and or, defined by the equalities true andfalse = false, true or false = true, etc., which confer to this set the structureof Boolean algebra.

By the interplay of composition and of operations (3) and (4), one may thendefine new functions. For instance, the set {{x, y} ∈ IR × IR : y = x2 + 2x + 1}defines a relation, let's call it f, of type IR × IR, with domain IR and codomain{y ∈ IR : y ≥ 0}, which is a function. One can denote it by the construct(5)

x → x2 + 2x + 1.

repeat this, with all due generality: in such constructions as (6), of the form3 f =x → expr(x), where expr is some arithmetic expression, it's x → expr(x), notexpr(x), that denotes the function f.

Remark. On first encounter, (6) may look confusing, but this impression shoulddissipate as soon as the precedence rules about parsing such a construct, i.e.,finding its logical structure, are understood. Multiplication and exponentiation takeprecedence over addition, the arrow is weaker than all operational symbols, and =is the weakest link of all. The nested boxes below show how this applies to (6):

2

→

. ?

Now, the set

{{x, y} ∈ IR × IR : x ≥ 0 and x = y}

defines a relation (a functional one), say r. The composition r ; f is a new

function, say g, which can be denoted by either(7)

g = x → if x ≥ 0 then x2 + 2x + 1,

or, in a more cumbersome manner,

(8) g = x ∈ {x ∈ IR : x ≥ 0} → x2 + 2x + 1,

thus stressing the fact that dom(g) = {x ∈ IR : x ≥ 0}. It should be clear here thatf and g, though defined by the same arithmetic expression, are not equal, for theyhave different domains.

One calls constants those functions the graph of which is of the form X × {a},where a is a special element of Y. One may denote such a function by x → a.Let rA be the relation with graph RA = {{x, x} ∈ X × X : x ∈ A}. Thecomposition of rA and of the function x → 0 (of type X → IR) is denoted by χA,and called the indicatrix of A. Its domain is A, and its codomain is the part {0} ofIR. It should not be confused with the characteristic function of A, which is (pay

3

Be aware that it's (5) in its entirety, not the expression on the right side of thearrow, that denotes f. It's therefore illegitimate to write f = x2+ 2x + 1. On theother hand, one may write(6)

f = x → x2 + 2x + 1

since the expressions on both sides of the equal sign denote the same object. Let's

1

This use of the semi-colon is borrowed from programming practice. Cf. Meyer (1990), fromwhich some of the above "innovations" come.

Some insist on calling maps only those functions with maximal domain (all of X).

2

One more often meets "f : x → expr(x)" in the mathematical literature, but our use of an equalsign instead of this colon is just a matter of preference in syntactic sugar's flavors. The underyingmechanism is the same.

- 3 -