Convex Optimization. Mikhail Moklyachuk

Convex Optimization

alt="image"/> there exists δ > 0, such that the inequality

holds true for all x ∈ (, ).

If the function takes values in , then definitions 1.1 and 1.2 make sense when . In the case where , the function f is considered to be lower semicontinuous (upper semicontinuous) by agreement.

Here are examples of semicontinuous functions:

1 1) the function y = [x] (integer part of x) is upper semicontinuous at the points of discontinuity;

2 2) the function y = {x} (fractional part of x) is lower semicontinuous at the points of discontinuity;

3 3) the Dirichlet function, which is equal to 0 at rational points and equal to 1 at irrational points, is lower semicontinuous at each rational point and upper semicontinuous at each irrational point;

4 4) if the function has a local minimum (maximum) at the point then it is lower (upper) semicontinuous at the point;

5 5) the function A for x ≠ 0, f(0) = +∞, is lower semicontinuous at the point 0. If we define the function at the point 0 arbitrarily, then it will remain lower semicontinuous.

THEOREM 1.1.– Let f and g be lower semicontinuous functions. Then:

– the function f + g is lower semicontinuous;

– the function αf is lower semicontinuous for α ≥ 0 and it is upper semicontinuous for α ≤ 0;

– the function f · g is lower semicontinuous for f ≥ 0, g ≥ 0;

– the function 1/f is upper semicontinuous if f > 0;

– the function max{f, g}, min{f, g} is lower semicontinuous;

– the functions sup{fi} (inf{fi}) are lower (upper) semicontinuous, if the functions fi are lower (upper) semicontinuous.

THEOREM 1.2.– (Weierstrass theorem) A lower (upper) semicontinuous on the interval [a, b] function f: ℝ → ℝ is bounded from below (from above) on [a, b] and attains the smallest (largest) value.

THEOREM 1.3.– (Fermat’s theorem) If is a point of local extremum of the differentiable at the point function f(x), then .

Fermat’s theorem gives the first-order necessary condition for existence of a local extremum of the function f(x) at point . The following theorems give the second-order necessary and sufficient conditions for the extremum.

THEOREM 1.4.– (Necessary conditions of the second order) If is a point of local minimum (maximum) of the function f(x), which has the second-order derivative at the point then the following conditions hold true:

THEOREM 1.5.– (Sufficient conditions of the second order) If the function f(x) has at a point the second-order derivative and

then is the point of local minimum (maximum) of the function f(x).

The necessary and sufficient conditions of the higher order of existence of an extremum of the function f(x) are given in the following theorems.

THEOREM 1.6.– (Necessary conditions of higher order) If is a point of local minimum (maximum) of the function f(x), which has at this point the nth order derivative, then

for some m ≥ 1, 2m ≤ n.

PROOF.– According to Taylor’s theorem, for a function which is n times differentiable at the point we have

If n = 1, then the assertion of the theorem is true as a result of Fermat’s theorem. Let n > 1, then

Let l be an odd number. Then the function , u ∈ R can be expanded in a series by Taylor’s theorem

The function g(u) has a derivative at point u = 0. Since ∈ locmin f, then 0 ∈ locming g. According to Fermat’s theorem, . Hence . This contradicts the condition . Therefore, the number l is even, l = 2m. According to Taylor’s theorem

Since , then if ∈ locmin f and if ∈ locmax

Скачать книгу