Convex Optimization. Mikhail Moklyachuk

Convex Optimization

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

The vector cannot be represented as a linear combination of vectors and . The relation

at the point can only be performed with

Gradients and in this case are linearly dependent.

Answer. ∈ absmin, S_min = 0.

EXAMPLE 1.6.– Solve the convex constrained optimization problem

Solution. Slater’s condition is fulfilled. Therefore, we write the regular Lagrange function:

The system for finding stationary points in this case (s = 0, n = 2, k = m = 3) can be written in the form

At point , the first and third restrictions are active, and the second is passive. Therefore, λ₂ = 0. As a result, we obtain a system for determining λ₁ and λ₃:

System solution , λ₃ = 1/2. The point is a solution of the problem. Make sure that there are no other stationary points and, therefore, no solution to the problem (see Figure 1.2).

Answer. ∈ absmin, .

EXAMPLE 1.7.– Let the numbers a > 0, b > 0, and let a < b. Find points of the local minimum and the local maximum of the function

on the set of solutions of the system

Solution. We denote this set by X. Let us write the Lagrange function

Schematic illustration of a solution with no stationary points.

Figure 1.2. Example 1.6

The system for determining stationary points has the form

[1.4]

[1.5]

[1.6]

[1.7]

[1.8]

Let x_i = 0. Then it follows from the system that x₂ ≥ 1, . Hence either x₂ = 1 or x₂ ≥ –1. In other case, λ₁ = 0. If x₂ < –1, then λ₂ = 0. But then λ₁ = 0, which contradicts the conditions of the problem. Now we easily get the first two groups of system solutions.

1 1) x1 = 0, x2 = 1, bλ0 + 3λ1 − 2λ2 = 0, λ1 ≥ 0, λ2 ≥ 0, (λ1, λ2) ≠ 0;

2 2) x1 = 0, x2 = −1, bλ0 − 2λ2 = 0, λ1 = 0, λ2 > 0.

Similarly, assuming that x₂ = 0, we obtain two other groups of solutions:

1 3) x1 = 1, x2 = 0, aλ0 + 3λ1 − 2λ2 = 0, λ1 ≥ 0, λ2 ≥ 0, (λ1, λ2) ≠ 0;

2 4) x1 = −1, x2 = 0, aλ0 − 2λ2 = 0, λ1 = 0, λ2 > 0.

Assume that x₁ ≠ 0, x₂ ≠ 0. Then equations of the system can be presented in the form

If here λ₁ = 0, then λ₀ = 0, since a ≠ b. But then λ₂ = 0, which contradicts the system of conditions. It remains to be assumed that λ₁ > 0. Then . Given that λ₁ ≠ 0, λ₂ ≠ 0, we deduce from this that , and therefore λ₂ = 0. Now we can easily get another group of solutions of the system:

Note that in (1) and (3) the multiplier λ₀ can accept both positive and negative values, in (2) and (4) it can accept only positive values and in (5) it can accept only negative values. Therefore, (0, 1) and (1, 0) are stationary points both in the minimization problem and in the maximization problem, (0, –1) and (–1, 0) are stationary points only in the minimization problem, and the point of (5) is the stationary point only in the problem of maximization.

Now we will study the stationary points for optimality. The function f is strongly convex on ℝ². Therefore, it reaches the global minimum on any closed set X. We calculate the value of f at the stationary points of the minimization problem:

Since a < b, hence (1.0) and (–1.0) are points of the global minimum of the function

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