Convex Optimization. Mikhail Moklyachuk

      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

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