Convex Optimization. Mikhail Moklyachuk
Чтение книги онлайн.

Читать онлайн книгу Convex Optimization - Mikhail Moklyachuk страница 12

Название: Convex Optimization

Автор: Mikhail Moklyachuk

Издательство: John Wiley & Sons Limited

Жанр: Математика

Серия:

isbn: 9781119804086

isbn:

СКАЧАТЬ href="#fb3_img_img_a310a3a2-f175-5cd4-a2f7-091cdfef3207.jpg" alt="image"/>

      THEOREM 1.19.– (Theorem on indeterminate Lagrange multipliers) Let image be a point of local solution of the problem [1.3], and let the functions fi(x), i = 0, … , m + s, be continuously differentiable in some neighborhood U of the point image. Then there will exist the Lagrange multipliers λ0, λ1, … , λm+s, not all equal to zero, such that for the Lagrange function

image

      the following conditions hold true:

       – stationarity condition with respect to x

       – complementary slackness condition

       – non-negativity condition

      Consequently, the rule of indeterminate Lagrange multipliers for solving constrained optimization problems with equality and inequality constraints is as follows:

      1 1) Write the Lagrange function

      2 2) Write the necessary conditions:– stationarity condition– complementary slackness condition– non-negativity condition

      3 3) Find the critical points, that is, all admissible points that satisfy the necessary conditions with the Lagrange multiplier λ0 = 0 and λ0 ≠ 0.

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

      REMARK 1.1.– Using the rule of indeterminate Lagrange multipliers for solving constrained optimization problems with equality constraints, one can choose the number λ0 as both positive and negative. For constrained optimization problems with equality and inequality constraints, the sign of λ0 is significant.

      EXAMPLE 1.2.– Solve the constrained optimization problem

image

      The only obvious solution to this problem is the point image. We solve the problem by the Lagrange method.

      1 1) Write the Lagrange function .

      2 2) Write the stationary equations

      3 3) If λ0 = 1, we get the equationsThe first equation is incompatible with the condition . Therefore, the system of equationshas no solutions.

      4 4) If λ0 = 0, then x1 = 0, x2 = 0 is a solution of the system of equations.

      Answer. (0, 0) ∈ absmin.

      Example 1.2 shows that by applying the rule of indeterminate Lagrange multipliers, it is not always possible to take λ0 = 1.

      EXAMPLE 1.3.– Solve the constrained optimization problem

image

      where a > 0 and b > 0 are given numbers.

      Solution.

      1 1) Write out the (regular) Lagrange function (as indicated in theorem 1.15 the regularity condition is satisfied here):

      2 2) Since

      the system of equations for determination of stationary points has the form:

image

      This system of equations has three solutions:

image

      1 3) Next we have

      For the three solutions found, this matrix takes the form accordingly

image

      The condition image, i = 1, … , m, here is of the form image. For the first two solutions, this means that h2 = 0 and h1 = 0, respectively. It is clear from this that matrices A1 and A2 satisfy the conditions of theorem 1.17 (although they are not positive definite). Therefore, the points (0, 1), (1, 0) are strict local solutions of the problem. For the matrix, A3 conditions of theorem 1.17 are not satisfied. That is why the point

image

      cannot be a solution of the minimization problem. This point is a local solution of the maximization problem of the same function under the same restrictions.

      Answer. image ∈ locmin, image ∈ locmin,

image

      EXAMPLE 1.4.– Solve the constrained optimization problem

image

      Solution.

      1 1) Write out the Lagrange function

      2 2) Write the necessary conditions:– stationarity condition– complementary slackness condition– non-negativity condition λ0 ≥ 0, λ1 ≥ 0.

      3 3) If λ0 = 0, then, in accordance with the condition of stationarity we have λ1 = 0, and λ2 = 0. So all Lagrange multipliers are zero. This contradicts the conditions of the Lagrange theorem 1.19. Take λ0 = 1/2. Let λ1 ≠ 0. Then, under the complementary slackness condition we have 2x1 – x2 + x3 – 5 = 0. We express x1, x2, x3 through λ1, λ2 and substitute into the equationWe get λ1 = –9/14 < 0. This contradicts the non-negativity condition. Let λ1 = 0, then x1 = x2 = x3 = 1 is a critical point.

      4 4) The function as ∥x∥ → ∞. By the corollary of the Weierstrass theorem, a solution of the problem exists. Since the critical point is unique, the solution of the problem can be only this point.

      Answer. СКАЧАТЬ