Convex Optimization. Mikhail Moklyachuk
href="#fb3_img_img_fe390cec-922e-5114-aa22-c8cfa8e814a9.jpg" alt="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
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
The only obvious solution to this problem is the point
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
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:
This system of equations has three solutions:
1 3) Next we have
For the three solutions found, this matrix takes the form accordingly
The condition
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.
EXAMPLE 1.4.– Solve the constrained optimization problem
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.
EXAMPLE 1.5.– An example of the irregular problem. Consider the constrained optimization problem
Figure 1.1. Example 1.5
Solution. Figure 1.1 depicts the admissible set of the problem and the level line of the objective function. The solution of the problem is the point