Lecture 1 : Basic Notions and Facts from Optimization Theory.

Points of Extremum and Other Definitions

f : R^{n} ↦ R

Definition 1. A point x^{∗} ∈ R^{n} is said to be a local minimum (maximum) point in R^{n} for f if

∃ε > 0 : f(x) ≥ f(x^{∗}) (f(x) ≤ f(x^{∗})) ∀x ∈ R^{n}, ∥x − x^{∗}∥ ≤ ε.

Definition 2. A point x^{∗} ∈ R^{n} is said to be a global minimum (maximum) point in R^{n} for f if

f(x) ≥ f(x^{∗}) (f(x) ≤ f(x^{∗})) ∀x ∈ R^{n}.

The points of minimum and maximum together are called the points of extremum.

If we substitute in Definitions 1-2 R^{n} by A ⊂ R^{n} then we get notions of minimum and maximum points in the set A.

Definition 3. A function f is said to be convex if

∀x, y ∈ R^{n} ∀α ∈ [0, 1] f(αx + (1 − α)y) ≤ αf(x) + (1 − α)f(y).

It is said to be strictly convex if

∀x, y ∈ R^{n}, x ≠ y ∀α ∈ (0, 1) f(αx+(1−α)y) < αf(x)+(1−α)f(y).

If f is a convex (strictly convex) function then −f is a concave (strictly concave) function.

Definition 4. A function f is said to be continuous at the point x^{∗} if

∀ε > 0 ∃δ(ε) > 0 : ∀x ∈ R^{n}, ∥x − x^{∗}∥ ≤ δ ⟹ |f(x) − f(x^{∗})| ≤ ε.

A function f is called to be continuous on the set A ⊂ R^{n} if it is continuous at each point of A.

Existence of Extremum

Theorem 1. Let f be continuous on A ⊂ R^{n} and the set A be closed and bounded. Then there exist a global minimum and a global maximum points in A for f.

Theorem 2. Let f be continuous on R^{n} and the set {x : f(x) ≤ z} ({x : f(x) ≥ z}) for some z be non-empty and bounded. Then there exists a global minimum (maximum) point in R^{n} for f.

Boundedness of the above set is essential. For example, the functions f : R ↦ R, f(x) = x, f(x) = \frac{1}{1+x^{2}} have no minimum points.

Theorem 3. Let f be continuous on R^{n} and such that

f(x) → +∞ (f(x) → −∞) if ∥x∥ → +∞.

Then there exists a global minimum (maximum) point in R^{n} for f.

Definition 5. A set A ⊂ R^{n} is said to be convex if

∀x, y ∈ A ∀α ∈ [0, 1] αx + (1 − α)y ∈ A.

If A is a convex set then it contains any linear combination of its points, that is

∀x_{1}, …, x_{k} ∈ A ∀α_{i} ≥ 0, k ; ∑ ; i=1 α_{i} = 1 : k ; ∑ ; i=1 α_{i}x_{i} ∈ A.

Existence of Extremum (continuation)

Theorem 4. If A ⊂ R^{n} is a convex set and f is a convex (concave) function on A then any local minimum (maximum) point in A for f is also a global minimum (maximum) point.

Theorem 5. A global minimum (maximum) point for the strictly convex (concave) function on the convex set A ⊂ R^{n} is unique.

Definition 6. A point x^{∗} is said to be an extreme point of the set A if

∀x, y ∈ A, x, y ≠ x^{∗} ∀α ∈ (0, 1) x^{∗} ≠ αx + (1 − α)y.

Theorem 6. Let

A = { k ; ∑ ; i=1 α_{i}x_{i} : α_{i} ≥ 0, k ; ∑ ; i=1 α_{i} = 1, x_{i} ∈ E} ,

where E is a non-empty finite set of the extreme points of A ⊂ R^{n}. Then the points of extremum in A for any linear function are in the set E.

Points of Extremum for Differentiable Functions

Necessary condition for an extremum. If x^{∗} is a point of a local extremum in R^{n} for f and f is differentiable then

grad f(x^{∗}) = (\frac{∂f}{∂x_{1}}, …, \frac{∂f}{∂x_{n}} )|_{x^{∗}} = (0, …, 0).  (1)

The points for which (1) holds are called stationary.

Sufficient condition for an extremum. Let f be a convex (concave) and differentiable function. If grad f(x^{∗}) = 0 then x^{∗} is a global minimum (maximum) point in R^{n} for f. Necessary condition for an extremum. If x^{∗} is a point of a local minimum (maximum) in R^{n} for f and f is twice differentiable then

Hess f(x^{∗}) = ∥ \frac{∂^{2}f}{∂x_{i}∂x_{j}} |_{x^{∗}} ∥_{i,j=1}^{n} ≥ 0 (≤ 0).

Sufficient condition for an extremum. Let f be twice differentiable, grad f(x^{∗}) = 0 and Hess f(x^{∗}) > 0(< 0). Then x^{∗} is a local minimum (maximum) point in R^{n} for f.

Example. Let f : R^{2} ↦ R, f(x_{1}, x_{2}) = 3x_{1}^{3} + x_{2}^{2} − 9x_{1} + 4x_{2}. To find the points of an extremum, we calculate the gradient

grad f(x) = (9x_{1}^{2} − 9, 2x_{2} + 4) = (0, 0) ⟹ x^{∗} = (1, −2), x^{∗} = (−1, −2).

Now we calculate the Hessian in both points :

Hess f(1, −2) = ( \begin{matrix}18 & 0 \\ 0 & 2 \end{matrix} ) , Hess f(−1, −2) = ( \begin{matrix}−18 & 0 \\ 0 & 2 \end{matrix} ) .

Therefore, the point x^{∗} = (1, −2) is that of a local minimum, while the point x^{∗} = (−1, −2) is neither that of a local minimum nor that of a local maximum.

Lagrangian Function and Lagrange Multiplies

Consider the problem of minimization (maximization) of a continuously differentiable function f over a set A ⊂ R^{n}, where A is given as

A = {x ∈ R^{n} : g_{i}(x) = 0, i = 1, 2, …, m},  (2)

and the functions g_{i} are also continuously differentiable.

The function

L(x, λ) = f(x) + λ′g(x), g(x) = (g_{1}(x), …, g_{m}(x))′, is known as the Lagrangian function, while the components λ_{1}, …, λ_{m} of λ are known as the Lagrange multipliers.

Necessary condition for an extremum. If x^{∗} is a point of a local minimum (maximum) in A for f and, in addition, the vectors grad g_{i}(x^{∗}), i = 1, …, m are linearly independent then there exist λ^{∗} so that

grad L(x^{∗}, λ^{∗})= (\frac{∂L}{∂x_{1}}, …, \frac{∂L}{∂x_{n}}, \frac{∂L}{∂λ_{1}}, …, \frac{∂L}{∂λ_{m}} )|_{(x^{∗},λ^{∗})}= (0, …, 0). (3)

The condition of linear independency is essential. The simple example confirms that fact. Let f : R ↦ R, f(x) = x, g(x) = x^{2}. Then A = {0}. Clearly, the point x^{∗} = 0 is that of an extremum but (3) does not hold since f′(x^{∗}) = 1, g′(x^{∗}) = 0.

Example. Let f : R^{3} ↦ R, f(x_{1}, x_{2}, x_{3}) = (x_{1} + 2)^{2} + 2(x_{2} − 1)^{2} + x_{3}^{2}, g_{1}(x_{1}, x_{2}, x_{3}) = x_{1} + x_{2} − 1, g_{2}(x_{1}, x_{2}, x_{3}) = x_{2} + x_{3} − 6. Due to the necessary condition for an extremum,

\{ \begin{matrix}\frac{∂L}{∂x_{1}} & = & 0 \\ \frac{∂L}{∂x_{2}} & = & 0 \\ \frac{∂L}{∂x_{3}} & = & 0 \\ g_{1}(x) & = & 0 \\ g_{2}(x) & = & 0 \end{matrix} ⟺ \{ \begin{matrix}2(x_{1} + 2) + λ_{1} & = & 0 \\ 4(x_{2} − 1) + λ_{1} + λ_{2} & = & 0 \\ 2x_{3} + λ_{2} & = & 0 \\ x_{1} + x_{2} & = & 1 \\ x_{2} + x_{3} & = & 6 \end{matrix} ⟺ \{ \begin{matrix}x_{1}^{∗} & = & −\frac{7}{4} \\ x_{2}^{∗} & = & \frac{11}{4} \\ x_{3}^{∗} & = & \frac{13}{4} \\ λ_{1}^{∗} & = & −\frac{1}{2} \\ λ_{2}^{∗} & = & −\frac{13}{2} \end{matrix} .

Lagrangian Function and Lagrange Multiplies (continuation)

Necessary condition for an extremum. If in addition to the previous conditions the functions f, g_{i}, i = 1, …, m are twice continuously differentiable then there exists λ^{∗} so that

z′Hess L_{xx}(x^{∗}, λ^{∗})z ≥ 0(≤ 0), where Hess L_{xx}(x^{∗}, λ^{∗}) = ∥ \frac{∂^{2}L}{∂x_{i}∂x_{j}} |_{(x^{∗},λ^{∗})}∥_{i,j=1}^{n} ,

whenever z satisfies grad g_{i}(x^{∗})z = 0, i = 1, …, m.

Sufficient condition for an extremum. Let x^{∗} ∈ A, functions f and g_{i}, i = 1, …, m, be twice continuously differentiable, grad g_{i}(x^{∗}), i = 1, …, m be linearly independent, necessary condition (3) be fulfilled and

z′Hess L_{xx}(x^{∗}, λ^{∗})z > 0 (< 0)

whenever z ≠ 0 satisfies grad g_{i}(x^{∗})z = 0, i = 1, …, m. Then x^{∗} is a local minimum (maximum) point in A for f.

Example. Consider the problem of minimization of the function f : R^{n} ↦ R, f(x) = x_{1}^{2} + ⋯ + x_{n}^{2} over the set A ⊂ R^{n} of the form (2) with g(x) = x_{1} + ⋯ + x_{n} − 1. The Lagrangian function is of the form

L(x, λ) = n ; ∑ ; i=1 x_{i}^{2} + λ ( n ; ∑ ; i=1 x_{i} − 1) .

Due to the necessary condition for an extremum,

\{ \begin{matrix}\frac{∂L}{∂x_{i}} & = & 0, i = 1, …, n \\ \frac{∂L}{∂λ} & = & 0 \end{matrix} ⟺ \{ \begin{matrix}2x_{i} + λ & = & 0, i = 1, …, n \\ ∑_{i=1}^{n} x_{i} & = & 1 \end{matrix} .

Hence, x^{∗} = (\frac{1}{n}, …, \frac{1}{n}), λ^{∗} = −\frac{2}{n}. Now we use the sufficient condition to verify whether x^{∗} is really the point of minimum :

grad f(x) = (2x_{1}, …, 2x_{n}), Hess L_{xx}(x^{∗}, λ^{∗}) = 2I_{n} > 0.

Lagrangian Function and Lagrange Multiplies (continuation)

Consider the problem of minimization (maximization) of a continuously differentiable function f over a set A ⊂ R^{n}, where A is given as

A = {x ∈ R^{n} : g_{i}(x) ≤ 0, i = 1, …, r, g_{i}(x) = 0, i = r+1, …, m}, (4)

and the functions g_{i} are also continuously differentiable. For any point x ∈ A define

I^{∗}(x) = {i : g_{i}(x) = 0, i = 1, …, r},
I(x) = {i : g_{i}(x) = 0, i = 1, …, m}.

Necessary condition for an extremum. If x^{∗} is a local minimum (maximum) point in A for f and, in addition, the vectors grad g_{i}(x^{∗}), i ∈ I(x^{∗}) are linearly independent then there exists λ^{∗} so that

grad L_{x}(x^{∗}, λ^{∗})= (\frac{∂L}{∂x_{1}}, …, \frac{∂L}{∂x_{n}} )|_{(x^{∗},λ^{∗})}= (0, …, 0),  (5)
λ_{i}^{∗} ≥ 0 (≤ 0), λ_{i}^{∗}g_{i}(x^{∗}) = 0, i = 1, …, r.  (6)

Example. Let f : R^{2} ↦ R, f(x_{1}, x_{2}) = x_{1}^{2}+3x_{2}^{2}−4x_{1}−6x_{2}, m = r = 1, g(x_{1}, x_{2}) = x_{1} + 2x_{2} − 4. Due to the necessary condition for an extremum,

\{ \begin{matrix}\frac{∂L}{∂x_{1}} & = & 0 \\ \frac{∂L}{∂x_{2}} & = & 0 \\ g(x_{1}, x_{2}) & = & 0 \end{matrix} ⟺ \{ \begin{matrix}2x_{1} − 4 + λ & = & 0 \\ 6x_{2} − 6 + 2λ & = & 0 \\ x_{1} + 2x_{2} & = & 4 \end{matrix} ⟺ \{ \begin{matrix}x_{1}^{∗} & = & 2 \\ x_{2}^{∗} & = & 1 \\ λ^{∗} & = & 0 \end{matrix} .

Therefore, the point x^{∗} = (2, 1) can be the point of extremum.

Lagrange Function and Lagrange Multiplies (continuation)

Sufficient condition for an extremum. Let x^{∗} ∈ A, the number of elements in I(x^{∗}) equals to n, the vectors grad g_{i}(x^{∗}), i ∈ I(x^{∗}) be linearly independent, (5) and (6) be fulfilled with λ_{i}^{∗} > 0(< 0), i ∈ I^{∗}(x^{∗}). Then x^{∗} is a point of a local minimum (maximum) in A for f.

For example, if we minimize the function f : R ↦ R over a set A of the form (4) with m = r = 1, g(x) = −x, then f′(0) > 0 ⟹ x^{∗} = 0.

Necessary condition for an extremum. If in addition to the previous conditions the functions f, g_{i}, i = 1, …, m are twice continuously differentiable then there exists λ^{∗} so that

z′Hess L_{xx}(x^{∗}, λ^{∗})z ≥ 0 (≤ 0),

whenever z satisfies

grad g_{i}(x^{∗})z = 0, i ∈ I^{∗}(x^{∗}), λ_{i}^{∗} > 0(< 0),  (7)
grad g_{i}(x^{∗})z ≥ 0, i ∈ I^{∗}(x^{∗}), λ_{i}^{∗} = 0,  (8)
grad g_{i}(x^{∗})z = 0, i = r + 1, …, m.  (9)

Sufficient condition for an extremum. Let x^{∗} ∈ A, the functions f and g_{i}, i = 1, …, m be twice continuously differentiable, conditions (5) and (6) be fulfilled. If in addition for any z ≠ 0 satisfying (7)-(9) the inequality

z′Hess L_{xx}(x^{∗}, λ^{∗})z > 0 (< 0)

holds then x^{∗} is a local minimum (maximum) point in A for f.

In the previous example, the point x^{∗} = (2, 1) is that of a minimum since the conditions (7)-(9) hold because

Hess L_{xx}(x^{∗}, λ^{∗}) = ( \begin{matrix}2 & 0 \\ 0 & 6 \end{matrix} ) > 0.

Lagrange Function and Lagrange Multiplies (continuation)

Example. Consider the problem of minimization of the function f : R^{2} ↦ R, f(x_{1}, x_{2}) = x_{1}^{2} + x_{2}^{2} over the set A ⊂ R^{n} of the form (4) with m = r = 1, g(x) = 2x_{1} + x_{2} + 4.

The Lagrangian function is of the form

L(x, λ) = x_{1}^{2} + x_{2}^{2} + λ(2x_{1} + x_{2} + 4).

Due to the necessary conditions for an extremum,

\{ \begin{matrix}\frac{∂L}{∂x_{1}} & = & 0 \\ \frac{∂L}{∂x_{2}} & = & 0 \\ 2x_{1} + x_{2} + 4 & = & 0 \end{matrix} ⟺ \{ \begin{matrix}2x_{1} + 2λ & = & 0 \\ 2x_{2} + λ & = & 0 \\ 2x_{1} + x_{2} & = & −4 \end{matrix} ⟺ \{ \begin{matrix}x_{1}^{∗} & = & −\frac{8}{5} \\ x_{2}^{∗} & = & −\frac{4}{5} \\ λ^{∗} & = & \frac{8}{5} \end{matrix} .

Hence, x^{∗} = (−\frac{8}{5}, −\frac{4}{5}).

Now we use the sufficient condition to verify whether x^{∗} is really the point of minimum :

Hess L_{xx}(x^{∗}, λ^{∗}) = 2I_{2} > 0.

Lemma on Minimal Area

Let f : R^{n} ↦ R be continuous integrable nonnegative function such that

∫_{R^{n}} f(u)du = c > 0

and

λ({u ∈ R^{n} : f(u) = z}) = 0 ∀z > 0,

where λ(·) is the Lebesque measure in R^{n}. Denote

A_{α} = {B ∈ B^{n} : ∫_{B} f(u)du = α}

for given 0 < α < c and

B_{z} = {u ∈ R^{n} : f(u) ≥ z}

for given z > 0.

Then the set B_{z_{α}}, where z_{α} is defined by the equation

∫_{B_{zα}} f(u)du = α,

possesses the property

B_{z_{α}} ∈ arg min_{B∈A_{α}} λ(B).

Moreover, if

A ∈ arg min_{B∈A_{α}} λ(B),

then λ(A△B_{z_{α}}) = 0.

Questions and Exercises after Lecture 1

1. Show that the function f(x) = \frac{1}{2}x′Bx − b′x with degenerated matrix B ≥ 0 is convex but not strictly convex.

Show that the function f(x) = ∥x∥^{α} is convex when α ≥ 1 and strictly convex when α > 1.

2. In some cases the points of a global extremum exist even if the conditions of Theorem 2 do not hold. Indeed, let f(x) = x′Bx−b′x, B ≥ 0 and f(x) is bounded from below (for example, f(x) = ∥Cx−d∥^{2}). Prove that f achieves the minimum in R^{n} although the conditions of Theorem 2, in general, do not hold.

3. Determine the points of an extremum for the functions below :

(a) f : R^{2} ↦ R, f(x_{1}, x_{2}) = x_{1}^{2} + x_{2}^{2}, f(x_{1}, x_{2}) = x_{1}^{2} − x_{2}^{2}, f(x_{1}, x_{2}) = x_{1}^{2} + 2x_{1}x_{2} + x_{2}^{2}, f(x_{1}, x_{2}) = x_{1}^{3} + x_{2}^{3} − 6x_{1}x_{2};

(b) f : R^{3} ↦ R, f(x_{1}, x_{2}, x_{3}) = x_{1}^{2} + 6x_{2}^{2} + 2x_{3}^{2} + 18x_{1} + x_{2} − x_{3} + 50, f(x_{1}, x_{2}, x_{3}) = x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + 2x_{1}x_{2} − x_{2}x_{3} − 2x_{1}, with the help of the necessary and sufficient conditions for an extremum.

4. Let f : R^{n} ↦ R, f(x) = ∥Bx − b∥^{2}, where B is m × n-matrix, b ∈ R^{m}. Write, please, the necessary conditions for an extremum. Are they also sufficient ? Is the minimum point unique ?

5. Apply the method of the Lagrangian function to searching for the points of an extremum for the function f : R^{2} ↦ R over the set A of the form (2) :

(a) f(x_{1}, x_{2}) = x_{2}, g_{1}(x_{1}, x_{2}) = (x_{1} − 1)^{2} + x_{2}^{2} − 1, g_{2}(x_{1}, x_{2}) = (x_{1} + 1)^{2} + x_{2}^{2} − 1;

(b) f(x_{1}, x_{2}) = 2x_{1}x_{2}, g(x_{1}, x_{2}) = x_{1}^{2} + x_{2}^{2} − 1.

6. Show that minimizing the function f over the set A of the form (2) with g(x) = Bx − b, the necessary conditions for a point of minimum are of the form

grad f(x^{∗}) + B′λ^{∗} = 0, z′Hess f(x^{∗})z ≥ 0 ∀z : Bz = 0.

7. If we minimize the function f : R^{2} ↦ R, f(x_{1}, x_{2}) = x_{1}^{2} − x_{2}^{2} over the set A of the form (2) with g(x_{1}, x_{2}) = x_{2}, then the point of minimum is x^{∗} = (0, 0) and λ^{∗} = 0. Verify that L_{xx}(x^{∗}, λ^{∗}) ≥ 0 does not hold.

8. Solve the problem of minimization of the function f over the set A of the form (2) with the help of the Lagrangian function :

(a) f(x) = ∑_{i=1}^{n} x_{i}, g(x) = ∑_{i=1}^{n} x_{i}^{2} − 1;

(b) f(x) = x′Ax, g(x) = ∑_{i=1}^{n} x_{i}^{2} − 1;

(c) f(x) = ∑_{i=1}^{n} x_{i}^{2}, g(x) = x′Ax − 1.

9. Verify whether the necessary condition for an extremum holds at given point x^{∗} ∈ A, where A is of the form (4), f : R^{2} ↦ R :

(a) f(x_{1}, x_{2}) = x_{1}^{2}+x_{2}^{2}, r = 3, m = 4, g_{1}(x_{1}, x_{2}) = x_{1}^{2}+x_{2}^{2}−5, g_{2}(x_{1}, x_{2}) = −x_{1}, g_{3}(x_{1}, x_{2}) = −x_{2}, g_{4}(x_{1}, x_{2}) = x_{1} + 2x_{2} − 4, x^{∗} = (\frac{4}{5}, \frac{8}{5});

(b) f(x_{1}, x_{2}) = (x_{1} −3)^{2} +(x_{2} −2)^{2}, g_{i} are the same as in (a), x^{∗} = (2, 1).

10. Solve the problem of minimization of the function f over the set A of the form (4) with the help of the Lagrangian function :

(a) f(x_{1}, x_{2}, x_{3}) = x_{1} − 3x_{2} + x_{3}^{2}, r = 1, m = 2, g_{1}(x_{1}, x_{2}, x_{3}) = x_{1} + x_{2} + x_{3}, g_{2}(x_{1}, x_{2}, x_{3}) = −x_{1} + 2x_{2} + 1.5x_{3}^{2};

(b) f(x_{1}, x_{2}) = −2x_{1} − 3x_{2}, m = r = 4, g_{1}(x_{1}, x_{2}) = x_{1} + x_{2} − 8, g_{2}(x_{1}, x_{2}) = −x_{1} + 2x_{2} − 4, g_{3}(x_{1}, x_{2}) = −x_{1}, g_{4}(x_{1}, x_{2}) = −x_{2}.