Convex Optimization. Mikhail Moklyachuk

to m +1. Therefore, there exists a submatrix of the matrix A of size (m + 1) × (m + 1) whose determinant is not zero. Let this be a matrix composed of the first m + 1

      columns of the matrix A. We construct the function F : ℝ^{m + 1} → ℝ^{m + 1} with the help of functions fk(x), k = 0, … , m. Let

      Here x₁, … , x_{m + 1} are variables, and are fixed quantities. If is a solution of the constrained optimization problem, then . The functions Fk(x₁,… , x_{m + 1}), k = 1, … , m + 1 satisfy conditions of the inverse function theorem. Take y = (ε, 0, … , 0). For sufficiently small values of ε, there exists a vector such that

      that is

      where x(ε) = (x₁(ε),… , x_{m + 1}(ε), ) and . This contradicts the fact that is a solution to the constrained optimization problem [1.2], since both for positive and negative values of ε there are vectors close to on which the function f₀(x(ε)) takes values of both smaller and larger . □

      Thus, to determine m + n + 1 unknown λ₀, λ₁, … , λ_m, , we have n + m equations

      Note that the Lagrange multipliers are determined up to proportionality. If it is known that λ₀ ≠ 0, then we can choose λ₀ = 1. Then the number of equations and the number of unknowns are the same.

      Linear independence of the vectors of derivatives is the regularity condition that guarantees that λ₀ ≠ 0. However, verification of this condition is more complicated than direct verification of the fact that λ₀ cannot be equal to zero.

      Since the time of Lagrange, almost a century ago, the method of Lagrange multipliers has been used with λ₀ = 1, despite the fact that in the general case it is wrong.

As in the case of the unconstrained optimization problem, the stationary points of the constrained optimization problem need not be its solution. There also exist the necessary and sufficient conditions for optimality in terms of the second derivatives. Denote by

      the matrix of the second-order partial derivatives of the Lagrange function L (x, λ, λ₀).

      THEOREM 1.17.– Let the functions fi(x), i = 0,1, … , m be two times differentiable at a point and continuously differentiable in some neighborhood U of the point , and let the gradients be linearly independent. If is the point of local minimum of the problem [1.2], then

      for all λ, λ₀, satisfying the condition

      and all h ∈ ℝⁿ such that

      THEOREM 1.18.– Let the functions fi(x), i = 0, 1, … , m, be two times differentiable at a point ∈ ℝⁿ, satisfying the conditions

      Assume that for some λ, λ₀, the condition holds

      and, in addition,

      for all non-zero h ∈ ℝⁿ satisfying the condition

      Then is the point of local minimum of the problem [1.2].

      We can formulate the following rule of indeterminate Lagrange multipliers for solving constrained optimization problems with equality constraints:

      1 1) Write the Lagrange function

      2 2) Write the necessary conditions for the extremum of the function L, that is:

      3 3) Find the stationary points, that is, the solutions of these equations, provided that not all Lagrange multipliers λ0, λ1, … , λm are zero.

      4 4) Find a solution to the problem among the stationary points or prove that the problem has no solutions.

      1.4.2. Problems with equality and inequality constraints

      Let fi : ℝⁿ → ℝ be differentiable functions of n real variables. The constrained optimization problem with equality and inequality constraints is the following problem:

[1.3]

We will formulate the necessary conditions for solution of the problem [1.3].

      THEOREM