Cinlar.&.Vanderbei. .Mathematical.Methods.of.Engineering.Analysis.[sharethefiles.com]

[ Pobierz całość w formacie PDF ]

81
We proceed to show that T is a contraction on C∗, which will complete the proof via
Theorem 16.3.
First, we show that T x ∈ C∗ for x ∈ C∗. For such x, it is clear that T x is a
continuous function, and
t
d(T x(t), x0) = max |
vi(s, x(s))ds| ≤ cδ
i
for t in [t0 - δ, t0 + δ] in view of the boundedness of vi by c. Thus, T x ∈ C∗ if x ∈ C∗.
Moreover, for x, y ∈ C∗,
T x - T y =
max d(T x(t), T y(t))
t
t
=
max max |
[vi(s, x(s)) - vi(s, y(s))]ds|
t
i
t
≤
max
d(v(s, x(s)) - v(s, y(s)))ds
t0
t
≤
max
Kd(x(s), y(s))ds
t0
≤
Kδ x - y ,
¯
t
T x(t) = x0 +
v(s, x(s))ds,
t0
t0
t0
t
t
x(0)(t)
=
x(n+1)(t)
=
=
t ∈ [t0 - δ, t0 + δ]
x0,
T x(n)(t)
82
DIFFERENTIAL AND INTEGRAL EQUATIONS
which follows from the Lipschitz condition 19.11 on v. Since Kδ 1, this shows that
T is a contraction on C∗.
The preceding theorem ensures the existence and uniqueness of a solution x to the
system 19.8 of differential equations. Successive approximations to x can be obtained
as follows. Define
t ∈ [t0 - δ, t0 + δ].
Then, the sequence x(n) of functions converges to the solution x.
Exercises:
19.1 Solve the system
for smooth b and initial condition x(0) = x0. How does the method of
successive approximations work?
t
x0 +
v(s, x(n)(s))ds,
t0
n
=
aijxj(t) + bi(t),
i = 1, 2, . . . , n
j=1
dxi(t)
dt
Convex Analysis
The aim of this chapter is to discuss basic concepts in convex analysis.
20
Convex Sets and Convex Functions
20.1 DEFINITION. A set C ⊂ Rn is called a convex set if
tx + (1 - t)y ∈ C
for all x, y ∈ C and 0 t 1.
20.2 DEFINITION. An R ∪ {∞}–valued function f defined on Rn is called a convex
function if
tf(x) + (1 - t)f(y) ≥ f(tx + (1 - t)y)
for all x, y ∈ Rn and 0 t 1.
An example of a convex set and function are shown in Figure 15. An example of a
nonconvex set and function are shown in Figure 16. There are two important sets that
one associates with functions defined on R ∪ {∞}.
20.3 DEFINITION. The epigraph of an R ∪ {∞}–valued function f, denote epi (f),
is defined by
epi (f) = {(x, r) ∈ Rn × R : f(x) ≤ r}.
20.4 DEFINITION. Given a convex function f, The effective domain of an R ∪ {∞}–
valued function f, denote dom (f), is defined by
dom (f) = {x ∈ Rn : f(x) ∞}.
83
84
CONVEX ANALYSIS
y
x
x
y
Figure 15: (a) A convex set. (b) A convex function.
20. CONVEX SETS AND CONVEX FUNCTIONS
85
y
x
x
y
Figure 16: (a) A nonconvex set. (b) A nonconvex function.
86
CONVEX ANALYSIS
The notions of set convexity and function convexity are closely related:
20.5 THEOREM. A function is convex if and only if its epigraph is convex.
PROOF. First suppose that f is convex. Fix (x, r) and (y, s) in epi (f) and fix 0
t 1. Then
f(tx + (1 - t)y)
≤
tf(x) + (1 - t)f(y)
≤
tr + (1 - t)s.
Therefore, (tx + (1 - t)y, tr + (1 - t)s) ∈ epi (f). That is, epi (f) is convex.
Now, suppose that epi (f) is convex. Fix x, y in Rn and fix 0 t 1. Then,
t(x, f(x)) + (1 - t)(y, f(y)) ∈ epi (f).
Therefore, tf(x) + (1 - t)f(y) ≥ f(tx + (1 - t)y). That is, f is convex.
21
Projection
Given a point x in Rn and a convex set C, the following theorem establishes the exis-
tence and uniqueness of a point in C closest to the point x. Such a point is called the
projection of x on C.
21.1 THEOREM. Let C be a nonempty closed convex set in Rn and let x be a point in
Rn. Then, there exists a unique solution to
min z - x 2.
z∈C
PROOF. We start by proving existence. Fix z0 ∈ C. Put r = z0 - x and let
B(r, x) = {z : z - x ≤ r} denote the closed ball of radius r centered at x. Clearly,
min z - x 2 =
min
z - x 2.
z∈C
z∈C∩B(r,x)
Put f(z) = z - x 2. As we saw in Theorem ??, a continuous function on a nonempty
compact set (in this case C ∩ B(r, x)) attains its infimum. Therefore there exists an
x∗ ∈ C such that
x∗ - x ≤ z - x
for all z ∈ C.
Now, consider the question of uniqueness. Suppose that x∗ is not unique. That is,
suppose that there exists an x∗∗ in C that is distinct from x∗ and for which
x∗ - x = x∗∗ - x .
21. PROJECTION
87
x*
C
_
x
x
x**
T
x - x∗∗
(x∗ - x∗∗)
2
x
- x∗
+
2
1
((x - x∗) + (x - x∗∗))T ((x∗ - x) + (x - x∗∗))
2
Figure 17: Clearly x - x is orthogonal to x∗ - x∗∗ if x∗ and x∗∗ are equidistant from
x.
Put x = (x∗ + x∗∗)/2. By convexity of C, x belongs to C. Furthermore, x - x is
orthogonal to x∗ - x∗∗ (see Figure 17):
¯
¯
¯
¯ [ Pobierz całość w formacie PDF ]

Linki