Minimum principle of pontryagin

Thesis Overview

<p> </p><p>Preliminaries<br>1.1 Linear maps<br>In this part we dene linear map and present some basic results concerning<br>them.<br>Denition :Let X and linear spaces over a scalar eld K.A mapping T : X ô€€€!<br>Y is said to be a linear map if:<br>T(x + y) = T(x) + T(y) (1.1)<br>for arbitrary x; y 2 X and arbitrary scalars ; 2 K.Some authors use the term<br>linear operator or linear transformation instead of linear map.Condition (1.1) is<br>equivalent to the following two conditions:<br>(i)T(x + y) = T(x) + T(y)8x; y 2 X<br>(ii)T(x) = T(x)8x 2 X and for each scalar, .<br>1.1.1 A basic result concerning linear maps<br>We remark rst that since linear functionals are special forms of linear maps,any<br>result proved for linear map holds for linear functionals.<br>Proposition 1.1.1 Let X and Y be two linear spaces over a scalar eld, K, and<br>let T : X ô€€€! Y be a linear map.Then<br>1. T(0) = 0<br>2. The rang of T, R(T) = fy 2 Y : T(x) = y for some x 2 Xg is a linear<br>subspace of Y<br>3. T is one to one if and only if T(x) = 0 implies that x = 0<br>4. If T is one to one , then Tô€€€1 exist on R(T) and Tô€€€1 : R(T) ô€€€! X is also<br>a linear map.<br>8<br>Proof. (1) Since T is linear,we have, T(x) = T(x) for each x 2 X and each<br>scalar . Take = 0 and (1) follows immediately.<br>(2)We need to show that for y1; y2 2 R(T) and ; scalars, y1 + y2 2 R(T).<br>Now, y1; y2 2 R(T) implies that there exists x1; x2 2 X such that T(x1) =<br>y1; T(x2) = y2. Moreover, x1 + x2 2 X(since X is a linear space). Further-<br>more, by the linearity of T,we have<br>T(x1 + x2) = T(x1) + T(x2)<br>Hence y1 + y2 2 R(T), and so R(T) is a linear subspace of Y .<br>(3)())Assume that T is one to one. Clearly T(x) = 0 ) T(x) = T(0) since T<br>is linear (and so T(0) = 0). But T is one-to-one.So,x = 0.<br>(()Assume that whenever T(u) = 0 then u must be 0. We want to prove that<br>T is one-to-one.So,let T(x) = T(y). Then T(x) ô€€€ T(y) = 0 and by the linearity<br>of T; T(x ô€€€ y) = 0.By hypothesis, x ô€€€ y = 0 which implies x = y. Hence T is<br>one to-one.<br>(4)Assume that T is one-to-one,since the restriction of T on R(T) is always<br>onto, then T is bijective from X into R(T).So Tô€€€1 exists on R(T). For the<br>linearity, let y1; y2 2 R(T) and a scalar. Then there exists x1; x2 2 X such<br>that y1 = T(x1); y2 = T(x2). so<br>Tô€€€1(y1 + y2) = Tô€€€1(T(x1) + T(x2)<br>which is equivalent to:<br>Tô€€€1(y1 + y2) = Tô€€€1(T(x1 + x2)) by using the linearity of T;<br>which is also equivalent to<br>Tô€€€1(y1 + y2) = x1 + x2 = Tô€€€1(y1) + Tô€€€1(y2)<br>Therefore Tô€€€1 is linear<br>1.1.2 Bounded Linear Maps<br>Denition : Let X and Y be normed linear spaces over a scalar eld K, and<br>let T : X ô€€€! Y be a linear map. Then T is said to be bounded if there exists<br>some constant K 0 such that for each x 2 X,<br>kT(x)k Kkxk;<br>the constant K is called a bound for T and in this case, T is called a bounded<br>linear map. We denote by B(X; Y ), the family of all bounded linear maps from<br>X into Y .<br>We now turn our attention to linear maps that are continuous. The notion of<br>continuity can be state, for linear maps in several useful equivalent forms. We<br>state these equivalent forms in the following theorem.<br>Theorem 1.1.1 Let X and Y be normed linear space and let T : X ô€€€! Y be a<br>linear map.Then the following are equivalent:<br>1. T is continuous;<br>9<br>2. T is continuous at the origin(in the sense that if fxng is a sequence of X<br>such that xn ! 0 as n ! +1,then T(xn) ! 0 as n ! +1)<br>3. T is Lipschitz, ie , there exists a constant K 0 such that,for each x 2 X,<br>kT(x)k Kkxk<br>;<br>4. If D = fx 2 X : kxk 1g is the closed unit disc in X, then T(D)<br>is bounded(in the sense that there exists a constant M 0 such that<br>kT(x)k M for all x 2 D)<br>1.2 Banach spaces<br>Denition Let X be a real linear space, and k:kX a norm on X , and dX the<br>corresponding metric dened by dX(x; y) = kxô€€€ykX8x; y 2 X. The norm linear<br>space (X; k:kX) is a real Banach space if the metric space (X; dX) is complete,<br>ie if any Cauchy sequence of elements of space (X; k:kX) converges in (X; k:kX:)<br>That is every sequence satisfying the the following Cauchy criterion:<br>8 &gt; 0; 9n0 2 N : p; q &gt; n0 ) dX(xp; xq) &lt;<br>Denition Given any vector space V over a vector eld F (where F = R or C),<br>the topological dual space(or simply) dual space of V is the linear space of all<br>bounded linear functionals. We shall denote it by V .<br>Remark 1.2.1 1. The dual space V has a canonical norm dened by<br>kfk = sup<br>x2V;kxk6=0<br>jf(x)j<br>kxk<br>; 8f 2 V : (1.2)<br>2. The dual of every real normed linear space, endowed with its canonical<br>norm is a Banach space.<br>In order to dene other useful topologies on dual spaces, we recall the following:<br>Denition (Initial topology) Let X be an nonempty set, fYigi2I be a family<br>of topological spaces(where I is an arbitrary index set)and i : X ô€€€! Y ; i 2 I<br>a family of maps.<br>The smallest topology on X such that the map i; i 2 I are continuous is called<br>the initial topology.<br>Next, we dene the weak topology of a normed vector space X and the weak<br>star topology of its dual space X which are special initial topologies.<br>Denition (weak topology) Let X be a real normed linear space, and let us<br>associate to each f 2 X the map f : X ô€€€! R given by f (x) = f(x)8x 2 X<br>The weak topology on X is the smallest topology on X for which all the f are<br>continuous.<br>We write !-topology for the weak topology.<br>10<br>Denition (weak star topology) Let X be a real normed linear space and X<br>its dual. Let us associate to each x 2 X the map x : X ô€€€! R given by<br>x(f) = f(x)8f 2 X.<br>The weak star topology on X is the smallest topology on X for which all the<br>x are continuous. We write !-topology for the weak star topology<br>Proposition 1.2.1 Let X be a real normed linear space and X its dual space.<br>Then, there exists on X three standard topologies, the strong topology given<br>by the canonical norm k:kx , the weak topology(!-topology) and the weak star<br>topology ((!-topology) such that:<br>(X; !) ,! (X; !) ,! (X; k:kX ):<br>The following part of this section is devoted to reexive spaces. For any normed<br>real linear space X; the space X of all bounded linear functionals on X is a<br>Banach space and as a linear space, it has its own corresponding . Let X be<br>a Banach space, there exists a natural mapping J : X ô€€€! X of X into X<br>dened, for each x 2 X by J(x) = x where x : X ô€€€! R is given by<br>x(f) = hf; xi, for each f 2 X. Thus,<br>hJ(x); fi = hf; xi for each ; f 2 X<br>We verify the following properties of J:<br>(i)J is linear(which is trivial);<br>(ii)kJ(x)k = kxk for all x 2 X;ie J is an isometry.In fact, for each f 2<br>X; kJ(x)k = sup<br>kfk=1;f2X<br>jhf; xij = kxk.<br>In general, the map J need not to be onto. Consequently, we always identify X<br>as a subspace of X. Since an isometry is always injective, it follows that J is<br>an isomorphism onto J(X) X. The mapping J dened above is called the<br>canonical map(or canonical embedding) of X into X, and the space X is said<br>to be embedded in X. This leads to the following denition.<br>Denition Let X be a norm linear space and let J be the canonical embedding<br>of X into X. If J is onto, then X is called reexive. Thus, a reexive Banach<br>space is one in which the canonical embedding is onto.<br>We now state the following important theorem.<br>Theorem 1.2.1 (Eberlein-Smul’yan theorem)<br>A real Banach space X is reexive if and only if every ( norm ) bounded sequence<br>in X has a subsequence which converges weakly to an element of X.<br>1.3 Hilbert Spaces<br>Denition 1. A map : E E ô€€€! C is Sesquilinear if<br>(i)(x + y; z + w) = (x; z) + (x;w) + (y; z) + (y;w)<br>(ii)(ax; by) = ab(x; y) , where the “bar” indicates the complex conjuga-<br>tion<br>11<br>for all x; y; z;w 2 E and for all a; b 2 C.<br>2. AHermitian form is a sesquilinear form : E E ô€€€! C such that<br>(x; y) = (y; x)<br>3. A positive Hermitian form is a Hermitian form such that (x; x) 0<br>for all x 2 E.<br>4. A denite Hermitian form is a Hermitian form such that (x; x) =<br>0 ) x = 0<br>5. An inner product on E is a positive denite Hermitian form and<br>will be denoted h:; :i := (:; :). The pair(E; h; i) is called an inner prod-<br>uct space.<br>We shall simply write E for the inner product space (E, h; i) when the<br>inner product h; i) is known.<br>In the case where we are using more than one inner product spaces, spec-<br>ication will be made by writing h; h; iE when talking about the inner<br>product space (E; h; i)<br>Denition Two vectors x and y in an inner product space E are said to be<br>orthogonal if hx; yi = 0. For a subset F of E, we have x is orthogonal to F if x<br>is orthogonal to y for all y in F.<br>Proposition 1.3.1 Let E be an inner product space andx; y 2 E: Then<br>khx; yik (hx; xi)<br>1<br>2 (hy; yi)<br>1<br>2<br>For an inner product space (E; h; i),the function k:k : E ô€€€! R dened by<br>kxkE =<br>p<br>hx; xiE<br>is a norm on E<br>Thus, (E; k:kE ) is a normed vector space, hence a metric space endowed with<br>the distance<br>dE : E E ô€€€! R dened by dE(x; y) = kx ô€€€ ykE.<br>Denition (Hilbert Space). An inner product space E is called a Hilbert<br>space if it is complete.<br>Remark 1.3.1 1. Hilbert spaces are thus a special class of Banach spaces.<br>2. Every nite dimension inner product space is complete and simply called<br>Euclidian Space.<br>Proposition 1.3.2 : Let H be a Hilbert space. Then,<br>for all u 2 H; Tu(v) := hu; vi denes a bounded linear functional,ie Tu 2 H.<br>Furthermore kukH = kTukH<br>Theorem 1.3.1 (Riesz Representation theorem) Let H be a Hilbert space and<br>let f be a bounded linear functional on H: Then,<br>12<br>1. There exists a unique vector y0 2 H such that<br>f(x) = hx; y0i for each ; x 2 H<br>2. Moreover, kfk = ky0k.<br>Remark 1.3.2 The map T : H ô€€€! H dened by T(u) = Tu is linear,(anti-<br>linear in the complex case) and isometric. Therefore the canonical embedding<br>is an isometry showing that “any Hilbert space is reexive”.<br>At the end of this part, we state this important proposition which is just a<br>corollary of Eberlein-Smul’yan theorem.<br>Proposition 1.3.3 Let H be a Hilbert space, then any bounded sequence in H<br>has a subsequence which converges weakly to an element of H<br>1.4 Dierential Calculus in Banach spaces<br>In this section we dene the derivative of a map dened between real Banach<br>spaces.<br>Denition ( Directional Dierentiability) Let f be a function dened from a<br>real linear space X into a real normed linear space Y and let x0 in X and v in<br>X/{0}. The function f is said to be dierentiable at x0 in the direction v if the<br>function t 7ô€€€! f(x0 + tv) is dierentiable at t = 0. i.e.<br>t 7ô€€€!<br>f(x0 + tv) ô€€€ f(x0)<br>t<br>; t 6= 0<br>has a limit in Y when t tends to 0.This,when it exists is denoted f0(xo; v) or<br>@f<br>@v (x0)<br>Denition ( Gateau Dierentiability) A function f dened from a real linear<br>space X into a real normed linear space Y is Gateaux Dierentiable at a point<br>x0 in X if :<br>1. f is dierentiable at x0 in every direction v<br>2. there exists a bounded linear map A : X ô€€€! Y such that f0(x0; v) =<br>A(v);in others words,the mapv 7ô€€€! f0(x0; v) is a bounded linear map<br>from X into Y<br>In this case the map f0(x0; <img alt="" src="https://s.w.org/images/core/emoji/11/svg/1f642.svg">&nbsp;is called the Gateaux dierential of f at x0<br>and is denoted by DGf(x0; <img alt="" src="https://s.w.org/images/core/emoji/11/svg/1f642.svg">&nbsp;or f0G<br>(x0).<br>Denition (Frechet Dierentiability) A map f : U X ô€€€! Y whose domain<br>U is an open set of a real Banach space X and whose range is a real Banach<br>space Y is (Frechet) dierentiable at x 2 U if there exists a bounded linear map<br>A : X ô€€€! Y such that<br>lim<br>kuk!0<br>k<br>f(x + u) ô€€€ f(x) ô€€€ Au<br>kuk<br>k = 0<br>or equivalently to<br>f(x + u) ô€€€ f(x) ô€€€ Au = o(kuk)<br>13<br>Proposition 1.4.1 : If f : U X ô€€€! Y is Frechet Dierentiable, then f is<br>Gateaux Dierentiable.<br>Proof. Indeed by taking u = tv; in the denition of Frechet Dierentiability we<br>have:f(x + tv) ô€€€ f(x) = A(tv) + o(ktvk). Simplifying by t and using the fact<br>that A is linear,we have:<br>f(x + tv) ô€€€ F(x)<br>t<br>= (A(v) +<br>(oktvk)<br>t<br>)<br>by the Frechet Dierentiability of f And since as t ! 0; u ! 0 so we have<br>lim<br>t!0<br>f(x + tv) ô€€€ f(x)<br>t<br>= Av<br>Proposition 1.4.2 Let X be a real Banach space and Y be a real normed linear<br>space. Then<br>1. The set of Gateaux dierentiable mappings from X into Y is a linear sub-<br>space of the linear space of all the mappings dened from X into Y space<br>is contained in B(X; Y );<br>2. The set of Frechet Dierentiable mappings from X into Y is also a sub-<br>space of B(X; Y )<br>1.5 Convex sets and convex functions<br>Let us recall rst the following basic notions of optimization.<br>Denition Let V be a norm linear space, and let F : V ô€€€! R [ f+1g.<br>1. A point u 2 K is a minimizer of F on K if<br>F(u) F(v)8v 2 K<br>2. A point u 2 K is a local minimizer of F on K if there exists r &gt; 0 such that<br>F(u) F(v)8v 2 K B(u; r)<br>3. A point u 2 K is a strict minimizer of F on K if<br>F(u) &lt; F(v)8v 2 K; v 6= u<br>4. A point u 2 K is a strict local minimizer of F on K if there exists r &gt; 0 such<br>that<br>F(u) &lt; F(v)8v 2 K B(u; r); v 6= u<br>Denition Let X be a norm linear space.A set C X is convex if and only if:<br>8x; y 2 C; 8 2 (0; 1), we have x + (1 ô€€€ )y 2 C<br>ie [x; y] C ; 8x; y 2 C<br>14<br>Denition Let C be a convex subset of a norm linear space X. A function<br>f : X ô€€€! R [ f+1g is convex on C if 8x; y 2 C; 8 2 (0; 1)<br>f(x + (1 ô€€€ )y) f(x) + (1 ô€€€ )f(y) (1.3)<br>If (1.3) is strict for x; y 2 C, with x 6= y and f(x); f(y) nite then f is strictly<br>convex.<br>f linear functional implies that f is convex and concave<br>Theorem 1.5.1 (Slope Inequality) Let I be an interval of R and let f : I ô€€€!<br>R [ f+1g convex. Let r1; r2; r3 2 I : r1 &lt; r2 &lt; r3;with f(r1); f(r2) nite then:<br>f(r1) ô€€€ f(r2)<br>r2 ô€€€ r1</p><p>f(r3) ô€€€ f(r1)<br>r3 ô€€€ r1</p><p>f(r3) ô€€€ f(r2)<br>r3 ô€€€ r2<br>Proof. Set =<br>r2 ô€€€ r1<br>r3 ô€€€ r1<br>2 (0; 1). We have 1 ô€€€ =<br>r3 ô€€€ r2<br>r3 ô€€€ r1<br>2 (0; 1) and<br>r2 = (1 ô€€€ )r1 + r3. Using the convexity of f, it follows that f(r2)<br>f(r3) + (1 ô€€€ )f(r1) =<br>r3 ô€€€ r2<br>r3 ô€€€ r1<br>f(r1) +<br>r2 ô€€€ r1<br>r3 ô€€€ r1<br>f(r3). Adding ô€€€f(r1) in both<br>sides,we get f(r2) ô€€€ f(r1)<br>r1 ô€€€ r2<br>r3 ô€€€ r1<br>f(r1) +<br>r2 ô€€€ r1<br>r3 ô€€€ r1<br>f(r3). Which implies that<br>f(r2) ô€€€ f(r1)<br>r2 ô€€€ r1</p><p>f(r3) ô€€€ f(r1)<br>r3 ô€€€ r1<br>. This prove rst inequality. Replacing ô€€€f(r1)<br>by ô€€€f(r3) in this rst inequality and using the same argument, we get the<br>second inequality.<br>Corollary 1.5.1 Let f : I ô€€€! R derivable on I, then The following are equiva-<br>lent:<br>1. f is convex<br>2. f0 is increasing<br>3. f(y) f(x) + f0(x)(y ô€€€ x)8x; y 2 I<br>If f is twice derivable on I the f is convex if and only if f0(x) 08x 2 I<br>Proof.<br>(1) ) (2). Let r &lt; t.By the rst inequality of the slope inequality we have<br>f(s) ô€€€ f(r)<br>s ô€€€ r</p><p>f(t) ô€€€ f(r)<br>t ô€€€ r<br>, for r &lt; s &lt; t. So we have, f0(r) = lim<br>s&amp;r<br>f(s) ô€€€ f(r)<br>s ô€€€ r</p><p>f(t) ô€€€ f(r)<br>t ô€€€ r<br>. By taking s % t, and by using the second inequality of the slope<br>inequality, we have<br>f(t) ô€€€ f(r)<br>t ô€€€ r<br>lim<br>s%t<br>f(s) ô€€€ f(t)<br>s ô€€€ t<br>= f0(t). Therefore we have<br>f0(r) f0(t)8r &lt; t. Thus f0 is increasing.<br>(2)) (3)<br>Let x 2 I, let us dene g(y) = f(y) ô€€€ f(x) ô€€€ f0(x)(y ô€€€ x). We have that<br>g is dierentiable and g0(y) = f0(y) ô€€€ f0(x). this give us:g0(y) 0 if and<br>only if f0(y) f0(x), if and only if y x since f0 is increasing. And also<br>we have,g0(y) 0if and only if y x. So by studding the function g, we<br>have that x is a minimizer of this function. So we have g(y) g(x)8y. Since<br>g(x) = 0,this implies that g(y) 0 which implies f(y)ô€€€f(x)ô€€€f0(x)(yô€€€x) 0,<br>15<br>ie f(y) f(x) + f0(x)(y ô€€€ x), ie (3)<br>(3)) (1)<br>We have by assumption that f(y) f(x) + f0(x)(y ô€€€ x)8x 2 I, which implies<br>that f(y) sup<br>x2I<br>[f(x) + f0(x)(y ô€€€ x)],which is equivalent to f(y) sup<br>x2I<br>hx(y),<br>where hx(y) = f(x)+f0(x)(yô€€€x) = f0(x):y+f(x)ô€€€f0(x):x. Since for x = y we<br>have equality on the previous inequality,then we have: f(y) = sup<br>x2I<br>hx(y), which<br>give us that f is convex.<br>Theorem 1.5.2 Let X a norm linear space, U X; is open, convex, nonempty.<br>Let f : U ô€€€! R dierentiable, then the following are equivalent:<br>1. f is convex<br>2. f0 : U ô€€€! X is monotone increasing, ie hf0(y)ô€€€f0(x); yô€€€xi 08x; y 2 U<br>3. f(y) f(x) + hf0(x); y ô€€€ xi8x; y 2 U<br>If f is twice dierentiable then f is convex if and only if f”(x) is positive<br>semi-denite ie:<br>hf0(x):y; yi 08y 2 X; 8x 2 U<br>Proof.<br>Let x; y 2 U, dene I = fs 2 R : x + s(y ô€€€ x) 2 Ug<br>Claim:I is an interval of R such that 0; 1 2 I<br>Let s1; s2 2 I; t 2 (0; 1), then we have: x + s1(y ô€€€ x) 2 U and x + s2(y ô€€€ x) 2<br>U. Our aim is to show that x + (ts1 + (1 ô€€€ t)s2)(y ô€€€ x) 2 U to get that<br>ts1 + (1 ô€€€ t)s2(y ô€€€ x) 2 I, which is equivalent to say that I is an interval. For<br>that, we have x + (ts1 + (1 ô€€€ t)s2)(y ô€€€ x) = x + ts1(y ô€€€ x) + (1 ô€€€ t)s2(y ô€€€ x)<br>= tx + (1 ô€€€ t)x + ts1(y ô€€€ x) + (1 ô€€€ t)s2(y ô€€€ x)<br>= t(x + s1(y ô€€€ x)) + (1 ô€€€ t)(x + s2(y ô€€€ x))<br>Since x + s1(y ô€€€ x) 2 U and x + s2(y ô€€€ x) 2 U and U is convex, t 2 (0; 1), we<br>have = t(x+s1(y ô€€€x))+(1ô€€€t)(x+s2(y ô€€€x)) 2 U. Which is equivalent to say<br>x + (ts1 + (1 ô€€€ t)s2)(y ô€€€ x) 2 U, ie I is an interval.<br>Assume that (1) is true, we want to show (2), ie f0 is monotone. Let us dene<br>h : I ô€€€! R by h(s) = f(x + s(y ô€€€ x))<br>We have that:<br>i)h is derivable on I<br>ii)h is convex if and only if f is convex on U<br>f convex implies that h is convex. so according to the previous theorem, we<br>have h0 is increasing, which give us that h0(1) h0(0)<br>Buy dierentiating h, we have h0(s) = hf0(x + s(y ô€€€ x)); y ô€€€ xi. So h0(0) =<br>hf0(x); y ô€€€ xi and h0(1) = hf0(y); y ô€€€ xi. So using our inequality h0(1) h0(0),<br>we have hf0(y); y ô€€€ xi hf0(x); y ô€€€ xi, which is equivalent to f0 is monotone.<br>we assume (2), ie a dire f is monotone, we have to prove rst that f0 monotone<br>implies that h0 is increasing. For that, let us evaluate the dierence (h0(s2) ô€€€<br>h0(s1))(s2 ô€€€ s1). We have that<br>(h0(s2)ô€€€h0(s1))(s2 ô€€€s1) = (hf0(x+s2(yô€€€x)ô€€€f0(y+s1(yô€€€x); yô€€€xi)(s2 ô€€€s1)<br>= hf0(x + s2(y ô€€€ x) ô€€€ f0(y + s1(y ô€€€ x); y ô€€€ x; (s2 ô€€€ s1)(y ô€€€ x)i<br>16<br>= hf0(z2) ô€€€ f0(z1); z2 ô€€€ z1i<br>By using the monotony of f0, we have that hf0(z2) ô€€€ f0(z1); z2 ô€€€ z1i 0,which<br>implies that (h0(s2) ô€€€ h0(s1))(s2 ô€€€ s1) 0, which means that h0 is increasing.<br>So buy using our previous theorem, we have:h(s) h(r)+h0(r)(sô€€€r)8s; r 2 I.<br>So h(1) h(0)+h0(0), which implies that f(y) f(x)+hf0(x); yô€€€xi8x; y 2 U,<br>ie (3)<br>we assume (3) and we have to (1), ie f is convex. We have by hypothesis that<br>) f(y) f(x) + hf0(x); y ô€€€ xi, which implies that<br>f(y) = sup<br>x2U<br>(f(x) + hf0(x); y ô€€€ xi) = sup<br>x2U<br>fx(y)<br>where fx(y) = f(x) + hf0(x); y ô€€€ xi.<br>Therefore f is convex.<br>Denition (Domain of a Function) Let F : X ô€€€! R [ f+1g be a map. The<br>domain of F is the set dened by<br>dom(F) := fx 2 X : F(x) &lt; +1g<br>Domain of F is sometimes called the eective domain of F. The map F is called<br>Proper if D(F) 6= ;.Recall that this means there exists at least one x0 2 D(F)<br>such that F(x0) 2 R or F is not identically +1<br>1.5.1 Notation and Further denitions<br>Let X be a real normed space and D X is a convex subset of X. Let<br>f : D ô€€€! R be a convex function. We dene the convex extension of f,<br>F : X ô€€€! R [ f+1g by<br>F(x) =</p><p>f(x); if x 2 D<br>+1; if x 2 XnD<br>(1.4)<br>We observe that f is convex on D if and only if F is convex on X. Moreover<br>dom(f) = dom(F).<br>Denition The epigraph of F is the subset of X] R denoted by epi(F) and<br>dened by<br>epi(F) = f(x; ) 2 X R : x 2 dom(F) and; F(x) g:<br>Denition Let 2 R. We have the following denitions:<br>SF; = fx 2 X : F(x) g = fx 2 D(F) : F(x) g<br>Proposition 1.5.1 F is convex if and only if epi(F) is convex<br>Proof.<br>))Assume that F is convex. Let (x1; 1) 2 epi(F); (x2; 2) 2 epi(F); t 2 (0; 1).<br>Now F(x1) 1; F(x2) 2. Hence F(tx1+(1ô€€€t)x2) tF (x1)+(1ô€€€t)F(x2)<br>t1 + (1 ô€€€ t)2:<br>17<br>Thus (tx1 + (1 ô€€€ t)x2; t1 + (1 ô€€€ t)2) 2 epi(F). But<br>(tx1 + (1 ô€€€ t)x2; t1 + (1 ô€€€ t)2) = t(x1; 1) + (1 ô€€€ t)(x2; 2). Hence, epi(F) is<br>convex.<br>(() Assume that epi(F) is convex. We show that F is convex. Let x1; x2 2<br>D(F); t 2 (0; 1). Then x1; x2 2 D(F) implies that F(x1) 2 R; F(x2) 2 R.<br>Thus (x1; F(x1)) 2 epi(F) and (x2; F(x2) 2 epi(F). But epi(F) is convex,thus<br>t(x1; F(x1) + (1 ô€€€ t)(x2; F(x2)) 2 epi(F) if and only if F(tx1 + (1 ô€€€ t)x2)<br>tF (x1) + (1 ô€€€ t)F(x2) if and only if f is convex.<br>1.6 Lower Semi-Continuous Functions<br>Let V be a real norm linear space, let F : V ô€€€! R [ f+1g be a map.<br>Denition : We says that F is lower semi-continuous(lsc)at x0 2 Dom(F) if:<br>Given; &gt; 0; 9 &gt; 0 : kx ô€€€ x0k &lt; ) F(x0) ô€€€ &lt; F(x):<br>Denition One says that F is lsc if and only if epi(F) is closed in X R<br>Proposition 1.6.1 : Let F : V ô€€€! R [ f+1g. F is lower semi-continuous if<br>and only if for all sequence (xn) of V converging to x 2 V , we have F(x)<br>lim inf F(xn:)<br>Proof. Assume that F is lsc and xn ! x in V . We take a subsequence (xnk)<br>of (xn) such that lim<br>k<br>F(xnk) = lim inf<br>n<br>F(xn). It follows that(xnk; F(xnk) is a<br>sequence of epi(F) converging to (x; lim inf<br>n<br>F(xn)). Since epi(F) is closed, then<br>(x; lim inf<br>n<br>F(xn)) 2 epi(F). Thus<br>F(x) lim inf<br>n<br>F(xn)<br>Reversely suppose that(xn ! xin V ) ) F(x) lim inf<br>n<br>F(xn). Let (an; xn) be<br>a sequence of epi(F) converging to (x; a) in V R. Then xn ! x and an ! a.<br>So by hypothesis we have F(x) lim inf<br>n<br>F(xn) lim inf an = limn an = a<br>therefore (x; a) 2 epi(F)<br>Proposition 1.6.2 : A function F : V ô€€€! R [ f+1g is lsc if and only if for<br>all a 2 R; Sa;F = fx 2 V : F(x) ag is closed.<br>Proof. Assume that F is lsc. Let a 2 R and let (xn) be a sequence of Sa;F<br>converges to x 2 V .<br>Since F(xn) a8n,then lim inf<br>n<br>F(xn) a. So according to proposition 1,<br>F(x) lim inf<br>n<br>F(xn) a.<br>Thus x 2 Ca, which means that Ca is closed.<br>Reversely assume that Sa;F is closed for each a 2 R. Let xn be a sequence of V<br>converging to x 2 V . There exists a subsequence xnk of xn such that<br>lim<br>k<br>F(xnk) = lim inf<br>n<br>F(xn)<br>Assume that F(x) &gt; lim inf<br>n<br>F(xn). Then there exists a 2 R such that<br>lim inf<br>n<br>F(xn) &lt; a &lt; F(x): (1.5)<br>18<br>So there exists N 2 IN such that F(xnk &lt; a for all k N. So xnk 2 Sa;F 8k<br>N. Since xnk ! x and Sa;F is closed then x 2 Sa;F or equivalent to say that<br>F(x) a which contradict (2.1) Thus F(x) lim inf<br>n<br>F(xn)<br>Proposition 1.6.3 Let F : V ô€€€! R [ f+1g be a l.s.c. function on a compact<br>set K. Then there exists x 2 K such that:<br>F(x) = inf<br>x2K<br>F(x)<br>.<br>Proof. Let fxng be a minimizing sequence of F on K. Since K is compact,there<br>exists a subsequence (xnk) of (xn) such that xnk ! x 2 K. From Proposition 2<br>we have:<br>F(x) lim inf<br>k<br>F(xnk) = lim<br>k<br>F(xnk) = inf<br>x2K<br>F(x):<br>Therefore F(x) = inf<br>x2K<br>F(x).<br>1.7 Existence Result<br>A concept that will be needed in the proof of one of our fundamental theorems<br>of optimization is that of coercivity. We introduce this concept now<br>Denition : Let X be a topological space. Let K be a subset of X. The set<br>K is said to be sequentially compact if every sequence in K has a subsequence<br>which converges to an element of K. The subset K is called Weakly sequentially<br>compact if every sequence in K has a subsequence which converges weakly to<br>an element of K.<br>Denition : Let X be a topological space. A function F : X ô€€€! R[f+1g is<br>called (weakly, respectively) sequentially coercive if the closure of every section<br>S;F is (weakly, respectively) sequentially compact in X<br>Denition :let X be a real reexive.A function F : X ô€€€! R [ f+1g is called<br>coercive if:<br>lim<br>kxk!+1<br>F(x) = +1<br>In fact, we have the following Proposition:<br>Proposition 1.7.1 : Let X be a real reexive space. Then F : X ô€€€! R[f+1g<br>is weakly sequentially coercive if and only if lim<br>kxk!+1<br>F(x) = +1<br>Proof. ()) Let F be weakly sequentially coercive. We prove that<br>limkxk!+1F(x) = +1 i.e. , 8M 2 R; 9N0 2 R :if kxk &gt; N0; then F(x) &gt; M.<br>Assume by contradiction that this is not the case. Then there exists a sequence<br>fxng such that lim<br>n!+1<br>kxnk = +1and fF(xn)g is bounded. Let 2 R be such<br>that jF(xn)j 8n 1:Since F is weakly sequentially coercive, the section<br>19<br>S;F X is weakly sequentially compact. Hence the sequence fxng which is<br>in the section S;F = fx 2 X : F(x) g, has a subsequence fxnjg which<br>converges weakly to an element of S;F ; F(xnj) whereas lim kxnjk = +1.<br>This subsequence is therefore bounded(Since every weakly convergent sequence<br>is bounded), which is a contradiction.<br>(()We assume that lim<br>kxk!+1<br>F(x) = +1<br>we want to prove that F is weakly sequentially coercive, ie for arbitrary 2<br>R; S;F is weakly sequentially compact, or that any sequence in S;F has a<br>weakly convergent subsequence. So let fxng be an arbitrary sequence in S;F<br>for arbitrary 2 R.<br>Then fxng is bounded. Since X is reexive, fxng has a subsequence fxnkg<br>converges weakly to an element of S;F . Thus F is weakly sequentially coercive.<br>Remark 1.7.1 If X is reexive and if lim<br>kxk!+1<br>F(x) = +1, we simply say that<br>F is coercive. This condition actually implies that<br>8A &gt; 0; 9B &gt; 0 : 8x 2 X; kxk &gt; B ) F(x) &gt; A<br>Equivalently,this means that F(x) A ) kxk B, i.e. ,if the range of F is<br>bounded, then the domain of F is also bounded.<br>Theorem 1.7.1 (Existence of minimum in nite dimension)<br>Let K be a nonempty closed subset of Rn and F a continuous real value appli-<br>cation on K satisfying the following property:<br>8(un) K; lim<br>n!1<br>kunk = +1 ) lim<br>n!1<br>F(un) = +1 (1.6)<br>Then there exists a least one minimum point of F over K. Moreover for any<br>minimizing sequence of F over K,one can take a subsequence converging to a<br>minimum point.<br>Proof.<br>Let (un) be a minimizing sequence of F over K. The condition (1:3) implies<br>that (un) is bounded since (F(un)) is a bounded real sequence. So by Bonzano-<br>weistrass there exists a subsequence (unk) of(un) converging to a point u of Rn.<br>But u is in K since K is closed,and F(unk) converges to F(u) by the continuity<br>of F, thus F(U) = inf<br>v2K<br>F(v)<br>Theorem 1.7.2 (Existence in innite dimension)<br>Let K be a closed,convex and nonempty subset of a reexive real Banach space<br>V . Let F : V ô€€€! R [ f+1g convex and lsc.<br>If K is bounded or if F is coercive, then there exists u 2 K such that F(u) =<br>min<br>v2K<br>F(v)<br>Moreover if F is strictly convex, then u is unique<br>Proof. Assume that F 6= +1, ie a there exists at least x0 2 V : F(x0) 6= +1.<br>In the case where F = +1, we obviously have inf<br>v2K<br>F(v) = +1<br>K is nonempty,let (vn) be a minimizing sequence of F on K. K bounded or<br>20<br>F coercive implies that (vn) is bounded. Indeed, if K is bounded,then vn is<br>bounded as a sequence of K, if F is coercive,assume by contradiction that vn is<br>not bounded,then vn has a subsequence vnk : vnk ! +1 as k ! +1. Since F<br>is coercive,then lim<br>k!+1<br>F(vnk) = +1. But since (vn) is a minimizing sequence of<br>F, we have that lim<br>k!+1<br>F(vnk) = inf<br>v2K<br>F(v) which implies that inf<br>v2K<br>F(v) = +1.<br>Therefore we have F(x) = +1 which is a contradiction,thus vn is bounded.<br>V reexive implies that there exists (vnk) subsequence of vn such that vnk<br>converges weakly to u in V . K convex and closed implies that K is weakly<br>closed,which implies that u 2 K So in one hand we have lim<br>k!+1<br>F(vnk) =<br>inf<br>v2K<br>F(v),and in a other hand, we have F convex and lsc implies that epi(f) is<br>convex and closed, which implies that F is weakly lsc.Or vnk converges weakly<br>to u,so we have F(u) lim inf F(vnk) = inf<br>v2K<br>F(v). Thus F(u) = inf<br>v2K<br>F(v).<br>but we have u 2 K,which implies that F(u) = min<br>v2K<br>F(v) For the uniqueness,<br>assume that F is strictly convex. Let u and w two minimum of F over K<br>Assume by contradiction that u 6= w. K convex implies that 1<br>2 u + 1<br>2 w 2 K.<br>So we have min<br>v2K<br>F(v) F( 1<br>2 u + 1<br>2 w). Using the strict convexity of F,we have<br>min<br>v2K<br>F(v) &lt; 1<br>2F(u) + 1<br>2F( w), which is equivalent that<br>min<br>v2K<br>F(v) &lt; min<br>v2K<br>F(v)<br>which is a contradiction, therefore u = w, ie the minimum is unique<br>Corollary 1.7.1 Let A be an (n n) positif dened matrix. Then there exists<br>&gt; 0 such that<br>hAx; xi kxk28x 2 Rn<br>Proof. Consider the following problem<br>8&lt;<br>:<br>min J(x) := hAx; xi<br>kxk = 1<br>(1.7)<br>-J is continuous<br>-dim(Rn) &lt; 1<br>-Dene K = fx 2 Rn : kxk = 1g is compact<br>Then by Weistrass theorem there exists x 2 K : x = arg min J(x).<br>ie 9x 2 K : J(x) J( x<br>kxk )8x 6= 0. Taking = J(x) &gt; 0,we have<br>1<br>kxk2 hAx; xi ,<br>which implies that hAx; xi kxk2<br>1.8 Optimality condition:<br>-Convex case<br>In this section, we will try to get the necessary condition,and sometimes su-<br>cient, for minimizer. Our aim is now in one hand more practical than the last<br>section, since these condition will more often be useful for computing a mini-<br>mizer.<br>21<br>These conditions will be achieved by using the rst derivative(necessary condi-<br>tions of rst order) or second(necessary conditions of second order)<br>Theorem 1.8.1 : Let K be a nonempty convex set of norm linear space V . Let<br>F : V ô€€€! R derivable (in the sens of Gateaux).<br>If u is a local minimum of F over K then<br>F0(u)(v ô€€€ u) 08v 2 K (1.8)<br>Moreover if u 2 Int(K) then (1.8) become<br>F0(u) = 0 EULER EQUATION ;<br>ie u is a critical point.<br>Proof.<br>u minimum local implies that there exists r 0 such that F(u) F(v); 8v 2<br>K B(u; r). Let v 2 K; v 6= u, let t 2]0; 1[, let wt = u + t(v ô€€€ u) =<br>(1 ô€€€ t)u + tv 2 K. For wt to be in B(u; r), it suces to have kwt ô€€€ uk &lt; r,<br>ie 0 &lt; t &lt;<br>r<br>kv ô€€€ uk<br>. let 0 &lt; t &lt; minf<br>r<br>kv ô€€€ uk<br>; 1g = , for all t 2]0; [, we<br>have wt 2 K B(u; r), which implies that F(u) F(u + t(v ô€€€ u)); which<br>gives that<br>F(u) ô€€€ F(u + t(v ô€€€ u))<br>t<br>08t 2]0; [. Letting t goes to 0, we get<br>F0(u)(v ô€€€ u) 0<br>Assume u 2 int(K), so 9r &gt; 0;B(u; r) K. we already know that 8u 2<br>K; F0(u)(v ô€€€ u) 0, let h 6= 0. Consider for all t 2 R; u + th. So for all<br>tsuch that jtj &lt;<br>r<br>krk<br>,we have u + th 2 K,which implies that for all t such that<br>jtj &lt;<br>r<br>krk<br>, we have tF 0(u):h 0. this give us tF 0(u):(ô€€€h) = 0, which implies<br>that F0(u):h = 08h 6= 0, which means that F0(u) = 0<br>-General case<br>Denition : Let K be a nonempty subset of a norm linear space V . Let u 2 K,<br>let d 2 V; d 6= 0.<br>One says that d is an admissible direction of K on U if it exists &gt; 0 such<br>that u + td 2 K, for all t 2]o; [. We denote by Dad(u) the set of admissible<br>direction on the point u.<br>Theorem 1.8.2 Consider</p><p>MinF (v)<br>v 2 K 6= ;<br>(1.9)<br>If F is dierentiable and if F is a local minimum of F over K, then F0(u):d<br>08d 2 Dad(u)<br>In particular if u 2 int(K), then F0(u) = 0<br>Proof.<br>u minimum local of F implies that there existsr 0 : F(u) F(v), for all<br>v 2 K B(u; r). Let d 2 Dad(u), it follows that : u + td 2 K; 8t 2]0; [.So for<br>22<br>u+td to be on B(u; r),it suces to have 0 &lt; t &lt;<br>r<br>kdk<br>. Now let displaystyle =<br>minf; r<br>kdkg, so for all t 2]0; [, we have u + td 2 K B(u; r), therefore F(u +<br>td) F(u); 8t 2]0; [ implies that<br>F(u + td) ô€€€ F(u)<br>t<br>0; 8t 2]0; [, letting t<br>goes to 0, we have F0(u):d 0<br>If u 2 int(K),then Dad = V=f0g implies that F0(u):d 0; 8d 2 V=f0g, which<br>implies that F0(u):d 0; 8d 2 V=f0g, which implies that F0(u) = 0<br>Theorem 1.8.3 (necessary and sucient condition of second order)<br>One assume that K is nonempty, F is of class C2.<br>If u 2 K is a local minimum of F on K then:<br>1) F0(u):d 08d 2 Dad(U)<br>2) If d 2 Dad(u) and F0(u):d = 0 then F00(u):d:d 0<br>3) If F0(u):d = 0 and F00(u):d:d kdk2; 8d 6= 0; &gt; 0, then u is strict local<br>minimum of F over K<br>Proof.<br>(1)Let d 2 Dad(u) : F0(u):d = 0, let &gt; 0 : 8t 2]0; [; u + td 2 K B(u; r). We<br>have by Taylor expansion that:<br>F(u + td) = F(u) + tF 0(u):d +<br>t2<br>2<br>F00(u):d:d + t2kdk2″(t)<br>where “(t) ! 0 as t ! 0. This implies that t2[ 1<br>2F00(u):d:d + kdk2″(t) 0. By<br>simplifying the last inequality by t2 and bu letting t goes to 0 we have:F0(u):d<br>0<br>(2) Let v 2 V; v 6= u,we have also by the Taylor expansion of F that<br>F(v) ô€€€ F(u) = F0(u)(v ô€€€ u) +<br>1<br>2<br>:(v ô€€€ u)(v ô€€€ u) + kv ô€€€ uk2″(v)<br>where “(v) ! 0 as v ! 0. This implies that F(v) ô€€€ F(u) kv ô€€€ uk2[</p><p>2<br>+ “(v)]<br>But<br>2 &gt; 0 and varepsilon(v) ! 0 as v ! 0 implies that there exists r &gt; 0 :<br>kv ô€€€ uk &lt; r implies that “(v)j &lt;<br>2 . This implies that for kv ô€€€ uk &lt; r,we have<br>ô€€€</p><p>2<br>&lt; “(v) &lt;</p><p>2<br>,which implies that for all v 2 B(u; r),we have</p><p>2<br>+ “(v) &gt; 0,<br>which give us: for all v 2 B(u; r); v 6= u, we have F(v) &gt; F(u)<br>Therefore u is a strict local minimum If F is convex, then F0(u):(v ô€€€ u) 0<br>is a (Necessary and sucient condition)<br>1.9 Optimization with equality constrains<br>In this part we are interested with optimization problem with equality constrains<br>in Rn. Given<br>an open set of Rn; F and F1; cdots; Fp functions dened on</p><p>taking value on R. One consider the following problem:<br>inf<br>v2K<br>F(v) (1.10)<br>with<br>fv 2<br>; gi(v) = 0; 1 i mg (1.11)<br>23<br>The function F is called objective or cost.The function gi dene the equality<br>constrains,the elements of K are called the admissible elements. Obviously the<br>rst question we have to ask is the one on the existence of solution of (1.10), for<br>that we use our last results. Indeed they have been obtained in spaces which<br>are more general, they are applicable in particularly in Rn. It is preferable in<br>the following to denote in a more synthetic form the constrains. For that, one<br>pose.<br>G(x) = (g1(x); ; gm(x))8x 2</p><p>Hence the set of the constrains is written K = Gô€€€1f0g.<br>Consider the following optimization problem<br>8&gt;&gt;&gt;&gt;&lt;<br>&gt;&gt;&gt;&gt;:<br>min F(x)<br>gi(x) = 0; i = 1; :::p<br>x 2 RN(p N)<br>(1.12)<br>where F; gi : Rn ô€€€! R<br>Set C = fx 2 RN : gi(x) = 0; 8i = 1; ; pg<br>So our problem (1.4) become:<br>8&lt;<br>:<br>min F(x)<br>x 2 C<br>(1.13)<br>Denition A point x satises the qualication condition (QC) or we can say<br>x is regular if rgi(x); i = 1; :::p are linearly independant<br>If p = 1; x is regular if rg1(x) 6= 0<br>G : RN ô€€€! Rp<br>x 7! G(x) = (rg1(x); ;rgp(x))<br>C = fx 2 RN=G(x) = 0g<br>x is regular if and only if JG(x) has rank p<br>Theorem 1.9.1 (Lagrange)<br>Assume that x 2 C is regular. If x is an extremum then:<br>91; ; p 2 R :<br>8&gt;&gt;&gt;&lt;<br>&gt;&gt;&gt;:<br>rF(x) +<br>Xp<br>i=1<br>irgi(x) = 0<br>gi(x) = 0; i = 1; ; p<br>(1.14)<br>The real 1; ; p are called the Lagrange multipliers associated with the<br>constrains of the problem and the minimum local point. The uniqueness of these<br>reals is assured by the qualication condition(QC)<br>24<br>Proposition 1.9.1 Let<br>be an open convex subset of Rn. Let F :<br>! R be a<br>convex dierentiable function on<br>and gi :<br>! R be ane. Let x 2 K such<br>that there exists 1; 2; ; p 2 R such that<br>rF(x) +<br>Xp<br>i=1<br>irgi(x) = 0: (1.15)<br>Then, x is a minimizer of F on K.<br>Proof. Let x 2 K,by convexity of F we have:<br>F(x) ô€€€ F(x) rF(x)(x ô€€€ x) (1.16)<br>Using (1.15) it follows that:<br>F(x) ô€€€ F(x) ô€€€<br>Xp<br>i=1<br>irgi(x)(x ô€€€ x) (1.17)<br>Since gi are ane and gi(x) = gi(x) = 0,we have also the identities<br>gi(x) ô€€€ gi(x) = rgi(x):(x ô€€€ x) = 0<br>By replacing in (1.17),we obtain F(x) F(x)</p> <br><p></p>