Mikhail Moklyachuk - Convex Optimization

is equal 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 + 1with the help of functions fk ( x ), k = 0, … , m . Let

Here x 1, … , x m + 1are variables, and are fixed quantities. If is a solution of the constrained optimization problem, then . The functions Fk ( x 1,… , 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 1( ε ),… , 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 0( x ( ε )) takes values of both smaller and larger . □

Thus, to determine m + n + 1 unknown λ 0, λ 1, … , λ m, , we have n + m equations

Note that the Lagrange multipliers are determined up to proportionality. If it is known that λ 0≠ 0, then we can choose λ 0= 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≠ 0. However, verification of this condition is more complicated than direct verification of the fact that λ 0cannot be equal to zero.

Since the time of Lagrange, almost a century ago, the method of Lagrange multipliers has been used with λ 0= 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 , λ, λ 0).

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 λ, λ 0, satisfying the condition

and all h ∈ ℝ nsuch that

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

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

and, in addition,

for all non-zero h ∈ ℝ nsatisfying the condition

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