Convex Optimization. Mikhail Moklyachuk
Чтение книги онлайн.
Читать онлайн книгу Convex Optimization - Mikhail Moklyachuk страница 11
Название: Convex Optimization
Автор: Mikhail Moklyachuk
Издательство: John Wiley & Sons Limited
Жанр: Математика
isbn: 9781119804086
isbn:
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 x1, … , xm + 1 are variables, and are fixed quantities. If
is a solution of the constrained optimization problem, then
. The functions Fk(x1,… , xm + 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(ε) = (x1(ε),… , xm + 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 f0(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 λ0 cannot 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 ∈ ℝn such 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 ∈ ℝn 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 : ℝn → ℝ be differentiable functions of n real variables. The constrained optimization problem with equality and inequality constraints is the following problem: