The essence of optimization by the method of undetermined Lagrange multipliers. Conditional optimization. Lagrange multiplier method
First, let's consider the case of a function of two variables. The conditional extremum of a function $z=f(x,y)$ at the point $M_0(x_0;y_0)$ is the extremum of this function, achieved under the condition that the variables $x$ and $y$ in the vicinity of this point satisfy the connection equation $\ varphi (x,y)=0$.
The name “conditional” extremum is due to the fact that the variables are subject to additional condition$\varphi(x,y)=0$. If one variable can be expressed from the connection equation through another, then the problem of determining the conditional extremum is reduced to the problem of determining the usual extremum of a function of one variable. For example, if the connection equation implies $y=\psi(x)$, then substituting $y=\psi(x)$ into $z=f(x,y)$, we obtain a function of one variable $z=f\left (x,\psi(x)\right)$. IN general case However, this method is of little use, so the introduction of a new algorithm is required.
Lagrange multiplier method for functions of two variables.
The Lagrange multiplier method consists of constructing a Lagrange function to find a conditional extremum: $F(x,y)=f(x,y)+\lambda\varphi(x,y)$ (the $\lambda$ parameter is called the Lagrange multiplier ). The necessary conditions extrema are given by a system of equations from which stationary points are determined:
$$ \left \( \begin(aligned) & \frac(\partial F)(\partial x)=0;\\ & \frac(\partial F)(\partial y)=0;\\ & \varphi (x,y)=0. \end(aligned) \right.
A sufficient condition from which one can determine the nature of the extremum is the sign $d^2 F=F_(xx)^("")dx^2+2F_(xy)^("")dxdy+F_(yy)^("" )dy^2$. If at a stationary point $d^2F > 0$, then the function $z=f(x,y)$ has a conditional minimum at this point, but if $d^2F< 0$, то условный максимум.
There is another way to determine the nature of the extremum. From the coupling equation we obtain: $\varphi_(x)^(")dx+\varphi_(y)^(")dy=0$, $dy=-\frac(\varphi_(x)^("))(\varphi_ (y)^("))dx$, therefore at any stationary point we have:
$$d^2 F=F_(xx)^("")dx^2+2F_(xy)^("")dxdy+F_(yy)^("")dy^2=F_(xx)^( "")dx^2+2F_(xy)^("")dx\left(-\frac(\varphi_(x)^("))(\varphi_(y)^("))dx\right)+ F_(yy)^("")\left(-\frac(\varphi_(x)^("))(\varphi_(y)^("))dx\right)^2=\\ =-\frac (dx^2)(\left(\varphi_(y)^(") \right)^2)\cdot\left(-(\varphi_(y)^("))^2 F_(xx)^(" ")+2\varphi_(x)^(")\varphi_(y)^(")F_(xy)^("")-(\varphi_(x)^("))^2 F_(yy)^ ("") \right)$$
The second factor (located in brackets) can be represented in this form:
The elements of the determinant $\left| are highlighted in red. \begin(array) (cc) F_(xx)^("") & F_(xy)^("") \\ F_(xy)^("") & F_(yy)^("") \end (array)\right|$, which is the Hessian of the Lagrange function. If $H > 0$, then $d^2F< 0$, что указывает на условный максимум. Аналогично, при $H < 0$ имеем $d^2F >0$, i.e. we have a conditional minimum of the function $z=f(x,y)$.
A note regarding the notation of the determinant $H$. show\hide
$$ H=-\left|\begin(array) (ccc) 0 & \varphi_(x)^(") & \varphi_(y)^(")\\ \varphi_(x)^(") & F_ (xx)^("") & F_(xy)^("") \\ \varphi_(y)^(") & F_(xy)^("") & F_(yy)^("") \ end(array) \right| $$
In this situation, the rule formulated above will change as follows: if $H > 0$, then the function has a conditional minimum, and if $H< 0$ получим условный максимум функции $z=f(x,y)$. При решении задач следует учитывать такие нюансы.
Algorithm for studying a function of two variables for a conditional extremum
- Compose the Lagrange function $F(x,y)=f(x,y)+\lambda\varphi(x,y)$
- Solve the system $ \left \( \begin(aligned) & \frac(\partial F)(\partial x)=0;\\ & \frac(\partial F)(\partial y)=0;\\ & \ varphi (x,y)=0. \end(aligned) \right.$
- Determine the nature of the extremum in each of the ones found in previous paragraph stationary points. To do this, use any of the following methods:
- Compose the determinant of $H$ and find out its sign
- Taking into account the coupling equation, calculate the sign of $d^2F$
Lagrange multiplier method for functions of n variables
Let's say we have a function of $n$ variables $z=f(x_1,x_2,\ldots,x_n)$ and $m$ coupling equations ($n > m$):
$$\varphi_1(x_1,x_2,\ldots,x_n)=0; \; \varphi_2(x_1,x_2,\ldots,x_n)=0,\ldots,\varphi_m(x_1,x_2,\ldots,x_n)=0.$$
Denoting the Lagrange multipliers as $\lambda_1,\lambda_2,\ldots,\lambda_m$, we compose the Lagrange function:
$$F(x_1,x_2,\ldots,x_n,\lambda_1,\lambda_2,\ldots,\lambda_m)=f+\lambda_1\varphi_1+\lambda_2\varphi_2+\ldots+\lambda_m\varphi_m$$
The necessary conditions for the presence of a conditional extremum are given by a system of equations from which the coordinates of stationary points and the values of the Lagrange multipliers are found:
$$\left\(\begin(aligned) & \frac(\partial F)(\partial x_i)=0; (i=\overline(1,n))\\ & \varphi_j=0; (j=\ overline(1,m)) \end(aligned) \right.$$
You can find out whether a function has a conditional minimum or a conditional maximum at the found point, as before, using the sign $d^2F$. If at the found point $d^2F > 0$, then the function has a conditional minimum, but if $d^2F< 0$, - то условный максимум. Можно пойти иным путем, рассмотрев следующую матрицу:
Determinant of the matrix $\left| \begin(array) (ccccc) \frac(\partial^2F)(\partial x_(1)^(2)) & \frac(\partial^2F)(\partial x_(1)\partial x_(2) ) & \frac(\partial^2F)(\partial x_(1)\partial x_(3)) &\ldots & \frac(\partial^2F)(\partial x_(1)\partial x_(n)) \\ \frac(\partial^2F)(\partial x_(2)\partial x_1) & \frac(\partial^2F)(\partial x_(2)^(2)) & \frac(\partial^2F )(\partial x_(2)\partial x_(3)) &\ldots & \frac(\partial^2F)(\partial x_(2)\partial x_(n))\\ \frac(\partial^2F )(\partial x_(3) \partial x_(1)) & \frac(\partial^2F)(\partial x_(3)\partial x_(2)) & \frac(\partial^2F)(\partial x_(3)^(2)) &\ldots & \frac(\partial^2F)(\partial x_(3)\partial x_(n))\\ \ldots & \ldots & \ldots &\ldots & \ ldots\\ \frac(\partial^2F)(\partial x_(n)\partial x_(1)) & \frac(\partial^2F)(\partial x_(n)\partial x_(2)) & \ frac(\partial^2F)(\partial x_(n)\partial x_(3)) &\ldots & \frac(\partial^2F)(\partial x_(n)^(2))\\ \end( array) \right|$, highlighted in red in the matrix $L$, is the Hessian of the Lagrange function. We use the following rule:
- If the signs of the angular minors $H_(2m+1),\; H_(2m+2),\ldots,H_(m+n)$ matrices $L$ coincide with the sign of $(-1)^m$, then the stationary point under study is the conditional minimum point of the function $z=f(x_1,x_2 ,x_3,\ldots,x_n)$.
- If the signs of the angular minors $H_(2m+1),\; H_(2m+2),\ldots,H_(m+n)$ alternate, and the sign of the minor $H_(2m+1)$ coincides with the sign of the number $(-1)^(m+1)$, then the stationary the point is the conditional maximum point of the function $z=f(x_1,x_2,x_3,\ldots,x_n)$.
Example No. 1
Find conditional extremum functions $z(x,y)=x+3y$ under the condition $x^2+y^2=10$.
The geometric interpretation of this problem is as follows: it is required to find the largest and smallest values of the applicate of the plane $z=x+3y$ for the points of its intersection with the cylinder $x^2+y^2=10$.
It is somewhat difficult to express one variable through another from the coupling equation and substitute it into the function $z(x,y)=x+3y$, so we will use the Lagrange method.
Denoting $\varphi(x,y)=x^2+y^2-10$, we compose the Lagrange function:
$$ F(x,y)=z(x,y)+\lambda \varphi(x,y)=x+3y+\lambda(x^2+y^2-10);\\ \frac(\partial F)(\partial x)=1+2\lambda x; \frac(\partial F)(\partial y)=3+2\lambda y. $$
Let us write a system of equations to determine the stationary points of the Lagrange function:
$$ \left \( \begin(aligned) & 1+2\lambda x=0;\\ & 3+2\lambda y=0;\\ & x^2+y^2-10=0. \end (aligned)\right.$$
If we assume $\lambda=0$, then the first equation becomes: $1=0$. The resulting contradiction indicates that $\lambda\neq 0$. Under the condition $\lambda\neq 0$, from the first and second equations we have: $x=-\frac(1)(2\lambda)$, $y=-\frac(3)(2\lambda)$. Substituting the obtained values into the third equation, we get:
$$ \left(-\frac(1)(2\lambda) \right)^2+\left(-\frac(3)(2\lambda) \right)^2-10=0;\\ \frac (1)(4\lambda^2)+\frac(9)(4\lambda^2)=10; \lambda^2=\frac(1)(4); \left[ \begin(aligned) & \lambda_1=-\frac(1)(2);\\ & \lambda_2=\frac(1)(2). \end(aligned) \right.\\ \begin(aligned) & \lambda_1=-\frac(1)(2); \; x_1=-\frac(1)(2\lambda_1)=1; \; y_1=-\frac(3)(2\lambda_1)=3;\\ & \lambda_2=\frac(1)(2); \; x_2=-\frac(1)(2\lambda_2)=-1; \; y_2=-\frac(3)(2\lambda_2)=-3.\end(aligned) $$
So, the system has two solutions: $x_1=1;\; y_1=3;\; \lambda_1=-\frac(1)(2)$ and $x_2=-1;\; y_2=-3;\; \lambda_2=\frac(1)(2)$. Let us find out the nature of the extremum at each stationary point: $M_1(1;3)$ and $M_2(-1;-3)$. To do this, we calculate the determinant of $H$ at each point.
$$ \varphi_(x)^(")=2x;\; \varphi_(y)^(")=2y;\; F_(xx)^("")=2\lambda;\; F_(xy)^("")=0;\; F_(yy)^("")=2\lambda.\\ H=\left| \begin(array) (ccc) 0 & \varphi_(x)^(") & \varphi_(y)^(")\\ \varphi_(x)^(") & F_(xx)^("") & F_(xy)^("") \\ \varphi_(y)^(") & F_(xy)^("") & F_(yy)^("") \end(array) \right|= \left| \begin(array) (ccc) 0 & 2x & 2y\\ 2x & 2\lambda & 0 \\ 2y & 0 & 2\lambda \end(array) \right|= 8\cdot\left| \begin(array) (ccc) 0 & x & y\\ x & \lambda & 0 \\ y & 0 & \lambda \end(array) \right| $$
At point $M_1(1;3)$ we get: $H=8\cdot\left| \begin(array) (ccc) 0 & x & y\\ x & \lambda & 0 \\ y & 0 & \lambda \end(array) \right|= 8\cdot\left| \begin(array) (ccc) 0 & 1 & 3\\ 1 & -1/2 & 0 \\ 3 & 0 & -1/2 \end(array) \right|=40 > 0$, so at the point The $M_1(1;3)$ function $z(x,y)=x+3y$ has a conditional maximum, $z_(\max)=z(1;3)=10$.
Similarly, at point $M_2(-1,-3)$ we find: $H=8\cdot\left| \begin(array) (ccc) 0 & x & y\\ x & \lambda & 0 \\ y & 0 & \lambda \end(array) \right|= 8\cdot\left| \begin(array) (ccc) 0 & -1 & -3\\ -1 & 1/2 & 0 \\ -3 & 0 & 1/2 \end(array) \right|=-40$. Since $H< 0$, то в точке $M_2(-1;-3)$ имеем условный минимум функции $z(x,y)=x+3y$, а именно: $z_{\min}=z(-1;-3)=-10$.
I note that instead of calculating the value of the determinant $H$ at each point, it is much more convenient to expand it in general view. In order not to clutter the text with details, I will hide this method under a note.
Writing the determinant $H$ in general form. show\hide
$$ H=8\cdot\left|\begin(array)(ccc)0&x&y\\x&\lambda&0\\y&0&\lambda\end(array)\right| =8\cdot\left(-\lambda(y^2)-\lambda(x^2)\right) =-8\lambda\cdot\left(y^2+x^2\right). $$
In principle, it is already obvious what sign $H$ has. Since none of the points $M_1$ or $M_2$ coincides with the origin, then $y^2+x^2>0$. Therefore, the sign of $H$ is opposite to the sign of $\lambda$. You can complete the calculations:
$$ \begin(aligned) &H(M_1)=-8\cdot\left(-\frac(1)(2)\right)\cdot\left(3^2+1^2\right)=40;\ \ &H(M_2)=-8\cdot\frac(1)(2)\cdot\left((-3)^2+(-1)^2\right)=-40. \end(aligned) $$
The question about the nature of the extremum at the stationary points $M_1(1;3)$ and $M_2(-1;-3)$ can be solved without using the determinant $H$. Let's find the sign of $d^2F$ at each stationary point:
$$ d^2 F=F_(xx)^("")dx^2+2F_(xy)^("")dxdy+F_(yy)^("")dy^2=2\lambda \left( dx^2+dy^2\right) $$
Let me note that the notation $dx^2$ means exactly $dx$ raised to the second power, i.e. $\left(dx \right)^2$. Hence we have: $dx^2+dy^2>0$, therefore, with $\lambda_1=-\frac(1)(2)$ we get $d^2F< 0$. Следовательно, функция имеет в точке $M_1(1;3)$ условный максимум. Аналогично, в точке $M_2(-1;-3)$ получим условный минимум функции $z(x,y)=x+3y$. Отметим, что для определения знака $d^2F$ не пришлось учитывать связь между $dx$ и $dy$, ибо знак $d^2F$ очевиден без дополнительных преобразований. В следующем примере для определения знака $d^2F$ уже будет необходимо учесть связь между $dx$ и $dy$.
Answer: at point $(-1;-3)$ the function has a conditional minimum, $z_(\min)=-10$. At point $(1;3)$ the function has a conditional maximum, $z_(\max)=10$
Example No. 2
Find the conditional extremum of the function $z(x,y)=3y^3+4x^2-xy$ under the condition $x+y=0$.
First method (Lagrange multiplier method)
Denoting $\varphi(x,y)=x+y$, we compose the Lagrange function: $F(x,y)=z(x,y)+\lambda \varphi(x,y)=3y^3+4x^2 -xy+\lambda(x+y)$.
$$ \frac(\partial F)(\partial x)=8x-y+\lambda; \; \frac(\partial F)(\partial y)=9y^2-x+\lambda.\\ \left \( \begin(aligned) & 8x-y+\lambda=0;\\ & 9y^2-x+\ lambda=0; \\ & x+y=0. \end(aligned) \right.
Having solved the system, we get: $x_1=0$, $y_1=0$, $\lambda_1=0$ and $x_2=\frac(10)(9)$, $y_2=-\frac(10)(9)$ , $\lambda_2=-10$. We have two stationary points: $M_1(0;0)$ and $M_2 \left(\frac(10)(9);-\frac(10)(9) \right)$. Let us find out the nature of the extremum at each stationary point using the determinant $H$.
$$H=\left| \begin(array) (ccc) 0 & \varphi_(x)^(") & \varphi_(y)^(")\\ \varphi_(x)^(") & F_(xx)^("") & F_(xy)^("") \\ \varphi_(y)^(") & F_(xy)^("") & F_(yy)^("") \end(array) \right|= \left| \begin(array) (ccc) 0 & 1 & 1\\ 1 & 8 & -1 \\ 1 & -1 & 18y \end(array) \right|=-10-18y $$
At point $M_1(0;0)$ $H=-10-18\cdot 0=-10< 0$, поэтому $M_1(0;0)$ есть точка условного минимума функции $z(x,y)=3y^3+4x^2-xy$, $z_{\min}=0$. В точке $M_2\left(\frac{10}{9};-\frac{10}{9}\right)$ $H=10 >0$, therefore at this point the function has a conditional maximum, $z_(\max)=\frac(500)(243)$.
We investigate the nature of the extremum at each point using a different method, based on the sign of $d^2F$:
$$ d^2 F=F_(xx)^("")dx^2+2F_(xy)^("")dxdy+F_(yy)^("")dy^2=8dx^2-2dxdy+ 18ydy^2 $$
From the connection equation $x+y=0$ we have: $d(x+y)=0$, $dx+dy=0$, $dy=-dx$.
$$ d^2 F=8dx^2-2dxdy+18ydy^2=8dx^2-2dx(-dx)+18y(-dx)^2=(10+18y)dx^2 $$
Since $ d^2F \Bigr|_(M_1)=10 dx^2 > 0$, then $M_1(0;0)$ is the conditional minimum point of the function $z(x,y)=3y^3+4x^ 2-xy$. Similarly, $d^2F \Bigr|_(M_2)=-10 dx^2< 0$, т.е. $M_2\left(\frac{10}{9}; -\frac{10}{9} \right)$ - точка условного максимума.
Second way
From the connection equation $x+y=0$ we get: $y=-x$. Substituting $y=-x$ into the function $z(x,y)=3y^3+4x^2-xy$, we obtain some function of the variable $x$. Let's denote this function as $u(x)$:
$$ u(x)=z(x,-x)=3\cdot(-x)^3+4x^2-x\cdot(-x)=-3x^3+5x^2. $$
Thus, we reduced the problem of finding the conditional extremum of a function of two variables to the problem of determining the extremum of a function of one variable.
$$ u_(x)^(")=-9x^2+10x;\\ -9x^2+10x=0; \; x\cdot(-9x+10)=0;\\ x_1=0; \ ; y_1=-x_1=0;\\ x_2=\frac(10)(9); \; y_2=-x_2=-\frac(10)(9).
We obtained points $M_1(0;0)$ and $M_2\left(\frac(10)(9); -\frac(10)(9)\right)$. Further research is known from the course of differential calculus of functions of one variable. By examining the sign of $u_(xx)^("")$ at each stationary point or checking the change in the sign of $u_(x)^(")$ at the found points, we obtain the same conclusions as when solving in the first way. For example, we will check sign $u_(xx)^("")$:
$$u_(xx)^("")=-18x+10;\\ u_(xx)^("")(M_1)=10;\;u_(xx)^("")(M_2)=- 10.$$
Since $u_(xx)^("")(M_1)>0$, then $M_1$ is the minimum point of the function $u(x)$, and $u_(\min)=u(0)=0$ . Since $u_(xx)^("")(M_2)<0$, то $M_2$ - точка максимума функции $u(x)$, причём $u_{\max}=u\left(\frac{10}{9}\right)=\frac{500}{243}$.
The values of the function $u(x)$ for a given connection condition coincide with the values of the function $z(x,y)$, i.e. the found extrema of the function $u(x)$ are the sought conditional extrema of the function $z(x,y)$.
Answer: at the point $(0;0)$ the function has a conditional minimum, $z_(\min)=0$. At the point $\left(\frac(10)(9); -\frac(10)(9) \right)$ the function has a conditional maximum, $z_(\max)=\frac(500)(243)$.
Let's consider another example in which we will clarify the nature of the extremum by determining the sign of $d^2F$.
Example No. 3
Find the largest and smallest values of the function $z=5xy-4$ if the variables $x$ and $y$ are positive and satisfy the coupling equation $\frac(x^2)(8)+\frac(y^2)(2) -1=0$.
Let's compose the Lagrange function: $F=5xy-4+\lambda \left(\frac(x^2)(8)+\frac(y^2)(2)-1 \right)$. Let's find the stationary points of the Lagrange function:
$$ F_(x)^(")=5y+\frac(\lambda x)(4); \; F_(y)^(")=5x+\lambda y.\\ \left \( \begin(aligned) & 5y+\frac(\lambda x)(4)=0;\\ & 5x+\lambda y=0;\\ & \frac(x^2)(8)+\frac(y^2)(2)- 1=0;\\ & x > 0; \; y > 0. \end(aligned) \right.
All further transformations are carried out taking into account $x > 0; \; y > 0$ (this is specified in the problem statement). From the second equation we express $\lambda=-\frac(5x)(y)$ and substitute the found value into the first equation: $5y-\frac(5x)(y)\cdot \frac(x)(4)=0$ , $4y^2-x^2=0$, $x=2y$. Substituting $x=2y$ into the third equation, we get: $\frac(4y^2)(8)+\frac(y^2)(2)-1=0$, $y^2=1$, $y =1$.
Since $y=1$, then $x=2$, $\lambda=-10$. We determine the nature of the extremum at the point $(2;1)$ based on the sign of $d^2F$.
$$ F_(xx)^("")=\frac(\lambda)(4); \; F_(xy)^("")=5; \; F_(yy)^("")=\lambda. $$
Since $\frac(x^2)(8)+\frac(y^2)(2)-1=0$, then:
$$ d\left(\frac(x^2)(8)+\frac(y^2)(2)-1\right)=0; \; d\left(\frac(x^2)(8) \right)+d\left(\frac(y^2)(2) \right)=0; \; \frac(x)(4)dx+ydy=0; \; dy=-\frac(xdx)(4y). $$
In principle, here you can immediately substitute the coordinates of the stationary point $x=2$, $y=1$ and the parameter $\lambda=-10$, obtaining:
$$ F_(xx)^("")=\frac(-5)(2); \; F_(xy)^("")=-10; \; dy=-\frac(dx)(2).\\ d^2 F=F_(xx)^("")dx^2+2F_(xy)^("")dxdy+F_(yy)^(" ")dy^2=-\frac(5)(2)dx^2+10dx\cdot \left(-\frac(dx)(2) \right)-10\cdot \left(-\frac(dx) (2) \right)^2=\\ =-\frac(5)(2)dx^2-5dx^2-\frac(5)(2)dx^2=-10dx^2. $$
However, in other problems on a conditional extremum there may be several stationary points. In such cases, it is better to represent $d^2F$ in general form, and then substitute the coordinates of each of the found stationary points into the resulting expression:
$$ d^2 F=F_(xx)^("")dx^2+2F_(xy)^("")dxdy+F_(yy)^("")dy^2=\frac(\lambda) (4)dx^2+10\cdot dx\cdot \frac(-xdx)(4y) +\lambda\cdot \left(-\frac(xdx)(4y) \right)^2=\\ =\frac (\lambda)(4)dx^2-\frac(5x)(2y)dx^2+\lambda \cdot \frac(x^2dx^2)(16y^2)=\left(\frac(\lambda )(4)-\frac(5x)(2y)+\frac(\lambda \cdot x^2)(16y^2) \right)\cdot dx^2 $$
Substituting $x=2$, $y=1$, $\lambda=-10$, we get:
$$ d^2 F=\left(\frac(-10)(4)-\frac(10)(2)-\frac(10 \cdot 4)(16) \right)\cdot dx^2=- 10dx^2. $$
Since $d^2F=-10\cdot dx^2< 0$, то точка $(2;1)$ есть точкой условного максимума функции $z=5xy-4$, причём $z_{\max}=10-4=6$.
Answer: at point $(2;1)$ the function has a conditional maximum, $z_(\max)=6$.
In the next part we will consider the application of the Lagrange method for functions more variables.
Multiplier methodLagrange(in English literature “LaGrange's method of undetermined multipliers”) ˗ is a numerical method for solving optimization problems that allows you to determine the “conditional” extremum objective function(minimum or maximum value)
in the presence of specified restrictions on its variables in the form of equalities (i.e., the range of permissible values is defined)
˗ these are the values of the function argument ( controlled parameters) on the real domain at which the value of the function tends to an extremum. The use of the name “conditional” extremum is due to the fact that an additional condition is imposed on the variables, which limits the range of permissible values when searching for the extremum of the function.
The Lagrange multiplier method allows the problem of searching for a conditional extremum of an objective function on a set of admissible values to be transformed into the problem of unconditional optimization of a function.
In case the functions 
And 
are continuous along with their partial derivatives, then there are such variables λ that are not simultaneously equal to zero, under which the following condition is satisfied:
Thus, in accordance with the Lagrange multiplier method, to find the extremum of the objective function on the set of admissible values, I compose the Lagrange function L(x, λ), which is further optimized:
where λ ˗ is a vector of additional variables called undetermined Lagrange multipliers.
Thus, the problem of finding the conditional extremum of the function f(x) has been reduced to the problem of finding the unconditional extremum of the function L(x, λ).
And 
The necessary condition for the extremum of the Lagrange function is given by a system of equations (the system consists of “n + m” equations):
Solving this system of equations allows us to determine the arguments of the function (X) at which the value of the function L(x, λ), as well as the value of the target function f(x) correspond to the extremum.
The magnitude of the Lagrange multipliers (λ) is of practical interest if the constraints are presented in the form with a free term in the equation (constant). In this case, we can consider further (increase/decrease) the value of the objective function by changing the value of the constant in the equation system. Thus, the Lagrange multiplier characterizes the rate of change in the maximum of the objective function when the limiting constant changes.
There are several ways to determine the nature of the extremum of the resulting function:
First method: Let be the coordinates of the extremum point, and be the corresponding value of the objective function. A point close to the point is taken and the value of the objective function is calculated:
If 
, then there is a maximum at the point.
If 
, then there is a minimum at the point.
Second method: A sufficient condition from which the nature of the extremum can be determined is the sign of the second differential of the Lagrange function. The second differential of the Lagrange function is defined as follows:
If in given point 
minimum, if 
, then the objective function f(x) has a conditional maximum.
Third method: Also, the nature of the extremum of the function can be determined by considering the Hessian of the Lagrange function. The Hessian matrix is a symmetrical square matrix second partial derivatives of a function at the point at which the matrix elements are symmetrical about the main diagonal.
To determine the type of extremum (maximum or minimum of a function), you can use Sylvester’s rule:
1. In order for the second differential of the Lagrange function to be of positive sign 
it is necessary that the angular minors of the function be positive. Under such conditions, the function at this point has a minimum.
2. In order for the second differential of the Lagrange function to be negative in sign 
, it is necessary that the angular minors of the function alternate, and the first element of the matrix must be negativesv. Under such conditions, the function at this point has a maximum.
By angular minor we mean the minor located in the first k rows and k columns of the original matrix.
The main practical significance of the Lagrange method is that it allows you to move from conditional optimization to unconditional optimization and, accordingly, expand the arsenal of available methods for solving the problem. However, the problem of solving the system of equations to which this method reduces is, in the general case, no simpler original problem searching for an extremum. Such methods are called indirect. Their use is explained by the need to obtain a solution to an extremal problem in analytical form (for example, for certain theoretical calculations). When solving specific practical problems Direct methods are usually used, based on iterative processes of calculating and comparing the values of the functions being optimized.
Calculation method
1 step: We determine the Lagrange function from the given objective function and system of restrictions:
Forward
In order to add your comment to the article, please register on the site.
|
Lagrange method─ is a method for solving a constrained optimization problem in which constraints, written as implicit functions, are combined with an objective function in the form of a new equation called Lagrangian.
Let's consider special case common task nonlinear programming:
Given a system of nonlinear equations (1):
(1) gi(x1,x2,…,xn)=bi (i=1..m),
Find the smallest (or largest) value of the function (2)
(2) f (x1,x2,…,xn),
if there are no conditions for the variables to be non-negative and f(x1,x2,…,xn) and gi(x1,x2,…,xn) are functions that are continuous along with their partial derivatives.
To find a solution to this problem, you can apply the following method: 1. Enter a set of variables λ1, λ2,…, λm, called Lagrange multipliers, compose the Lagrange function (3)
(3) F(х1,х2,…,хn, λ1,λ2,…,λm) = f(х1,х2,…,хn)+ λi.
2. Find the partial derivatives of the Lagrange function with respect to the variables xi and λi and equate them to zero.
3. Solving the system of equations, find the points at which the objective function of the problem may have an extremum.
4. Among the points that are suspicious not an extremum, find those at which the extremum is reached, and calculate the values of the function at these points .
4. Compare the obtained values of the function f and choose the best one.
According to the production plan, the company needs to produce 180 products. These products can be manufactured in two technological ways. When producing x1 products using method I, the costs are 4*x1+x1^2 rubles, and when producing x2 products using method II, they are 8*x2+x2^2 rubles. Determine how many products should be produced using each method, so that the total cost of production is minimal.
Solution: The mathematical formulation of the problem consists of determining the smallest value of a function of two variables:
f = 4*x1+x1^2 +8*x2 +x2^2, provided x1 +x2 = 180.
Let's compose the Lagrange function:
F(x1,x2,λ) = 4*x1+x1^2+8*x2+x2^2+λ*(180-x1-x2).
Let's calculate its partial derivatives with respect to x1, x2, λ and equate them to 0:
Let's move λ to the right sides of the first two equations and equate their left sides, we get 4 + 2*x1 = 8 + 2*x2, or x1 − x2 = 2.
Solving the last equation together with the equation x1 + x2 = 180, we find x1 = 91, x2 = 89, that is, we have obtained a solution that satisfies the conditions:
Let's find the value of the objective function f for these values of the variables:
F(x1, x2) = 17278
This point is suspicious for an extreme point. Using second partial derivatives, we can show that at point (91.89) the function f has a minimum.
1.9 Lagrange's method of undetermined multipliers
Naturally, solving conditional optimization problems is much more difficult than solving unconditional optimization problems. It is natural to strive to reduce the problem of conditional optimization (search for a relative extremum) to a simpler problem of unconditional optimization (search for an absolute extremum). This procedure is carried out in the Lagrange method. Let's consider the essence of this method.
It is necessary to find the conditional extremum of the nonlinear function
n variables, with m restrictions
(1.56)
Inequality constraints are transformed into equalities, and free terms are transferred to the left sides of the constraints, i.e. system (1.56) is reduced to the form
(1.57)
In accordance with the Lagrange method, instead of the relative extremum of the function (1.55) under restrictions (1.57), the absolute extremum of the Lagrange function is sought, which has next view:
Where - indefinite factors Lagrange, which, like variables, are the sought variables.
It can be seen that the Lagrange function includes the objective function plus each constraint multiplied by the Lagrange multiplier.
It has been proven that the relative extremum of the objective function (1.55) under constraints (1.57) coincides with the absolute extremum of the Lagrange function (1.58).
The search for the absolute extremum of function (1.58) is performed using well-known methods. In particular, the partial derivatives of the Lagrange function are determined and set equal to zero:
(1.59)
The last m equations represent constraints (1.57) of the optimization problem.
System (1.59) contains (m+n) equations and the same number of unknowns.
Solving system (1.59) will give the coordinates of the absolute minimum of the Lagrange function (1.58) or the relative minimum of the objective function (1.55) under restrictions (1.57).
The solution of system (1.59) is carried out using well-known methods of computational mathematics. If system (1.59) is linear, the Gaussian method is usually used. If system (1.59) is nonlinear – Newton’s method.
1.10 Selecting an optimization method
Before choosing an optimization method, we will conduct a brief analysis of the problems that the software being developed should solve:
the program must solve the problem of conditional minimization, i.e. find the relative extremum, since in mathematical model in addition to linear restrictions, nonlinear ones will also occur;
since the objective function is a function of several variables, it may have several extrema, in which case the program must search for a local minimum.
After analyzing the most commonly used optimization methods, to achieve this goal, the gradient method of quadratic programming was chosen, which is the most effective of the above gradient methods, modified with polynomial approximation methods.
It is assumed that the objective function and boundary conditions are approximated by quadratic dependencies or second-order polynomials. This method will be discussed in more detail later in the “Development” section. software optimization method".
This method allows you to create reliable program, meeting all of the above requirements.
2. Development of an optimization method for re active power
The total power of compensating devices required in the electric power system (EPS) is determined from the reactive power balance equation (6.1). This power must be placed in nodes electrical network With minimal costs.
where is the total reactive power generated in the EPS, including reactive power coming from neighboring EPS;
The total reactive power of EPS consumers, including reactive power supplied to neighboring EPS;
Total reactive power of power plants' own needs;
Total reactive power losses;
Total reactive power consumption in EPS.
Let's consider the simplest scheme existing network(Fig. 2.1). from a power source with voltage U, through the network resistance R, the load is supplied with power S=P+jQ. A compensating device with a capacity of Qk is installed on the load busbars.
Figure 2.1 – The simplest scheme reactive power compensation
Active power losses in the line if the consumer does not have a compensating device () are
. (2.2)
When installing a compensating device () at the consumer, these losses will decrease to the value
. (2.3)
Thus, reactive power compensation makes it possible to reduce active power losses in a power supply circuit and, consequently, improve the technical and economic indicators of this circuit.
Let us evaluate the impact of CG on network costs.
The expression for the total costs of transmitting power to the load when installing the heat exchanger will have the form:
(2.4)
where ZK – costs for CG;
соΔР – costs of covering active power losses in the network;
с – cost per unit of lost active power;
зк – unit costs for CG.
To determine the minimum of function 3, we equate its derivative of the variable QK to zero:
(2.5)
From (2.5), economically feasible reactive power is determined, the transfer of which from the source to the consumer corresponds to the minimum cost
(2.6)
The value of QE does not depend on the active power P, but depends only on the ratio of the cost indicators zk and co and the parameters of the network U and R through which the power is transmitted.
The issue of placing compensating devices in the electrical network of a real EPS is a complex optimization problem. The challenge is that electrical power systems are large systems made up of interconnected subsystems. It is impossible to consider each individual subsystem in isolation, since the properties large systems determined by the nature of the interrelations of individual subsystems.
When analyzing large systems it is used systems approach, according to which the analysis big system is carried out when dividing it into subsystems that are not directly related to each other, but influence each other through the system more high level.
In relation to the issue under consideration, the electrical network seems to be at different levels, as shown in Fig. 2.2. the upper level is an electrical network with a voltage of 110 kV and above. This complex electrical network, represented by a complete equivalent circuit, is shown in Fig. 2.2 conventionally as ES1. Reactive powers generated by generators of power plants QES, compensating devices QK, power lines QС, as well as reactive powers flowing through connections with neighboring ES2 and ES3 (Q12, Q21, Q13, Q31) provide available reactive power Qр1 in ES1.
Figure 2.2 – Layout of the control unit in the electrical network
The second level is a set of n open local distribution networks with a voltage of 35 kV and below, connected to n nodes of the electrical network top level through transformers T. These local distribution networks are not directly connected to each other, but influence each other through the upper level network. Synchronous generators, compensators and motors in each such distribution network are represented by one equivalent synchronous machine G. Low-voltage consumers P+jQ are powered from local electrical networks through distribution transformers T1.
Compensating devices can be installed on the high-voltage (jQkv) and low-voltage (jQks) buses of transformers T, as well as on the 0.4 kV buses of distribution transformers T1 and in the 0.4 kV network itself (jQkn). The power value of these HRSGs is subject to determination.
In general, the problem of optimizing the placement of the CP is formulated as follows: determine the reactive powers available in the 6...35 kV nodes synchronous machines G, the power of the heat exchanger in networks of all voltages Qkv, Qks, Qkn, as well as the values of reactive powers Qеi (i=1, 2, …n) transmitted to the consumer networks, at which the minimum total costs are ensured.
Calculations of reactive power compensation for networks of all types are carried out both when designing the development of electrical networks and under their operating conditions. During the design, the power of the heat exchanger is determined and the problem of their distribution in the electrical network is solved. Under operating conditions, the optimal modes of the existing HRSGs are determined during the day. The optimality criteria in this case are the minimum power and energy losses and the compliance of voltage deviations acceptable values.
When designing a power supply circuit, as a rule, the monetary costs of this circuit are minimized. Reducing power losses by installing a heat exchanger reduces the cost of the circuit for the following reasons:
every kW of power lost must be generated at power plants and, therefore, spent on it cash;
generation of lost reactive power at power plants is much more expensive than consumption (3 times!).
However, compensating devices also require financial costs.
In this regard, the problem arises of determining the optimal power of compensating devices that meets the minimum total costs. This problem belongs to the problem of unconstrained optimization and can be solved, for example, by gradient methods.
Let's consider such a problem for the main power supply circuit (Fig. 2.3). It is necessary to determine the power of compensating devices QK1 and QK2 in nodes 1 and 2 based on the condition of minimum total costs for installing these devices and covering active power losses in the circuit.
Figure 2.3 – Power supply diagram
Initial data:
circuit voltage U;
line resistances R1 and R2;
reactive loads of nodes 1 and 2 Q1 and Q2;
specific costs for installing compensating devices zo;
specific costs for covering active power losses c.
The objective function, which represents the total costs of installing compensating devices and covering active power losses in the circuit, has the following form
where a1=R1∙co∙10-3/U2=0.0006;
a2=R2∙co∙10-3/U2=0.0004.
The introduction of a numerical coefficient of 10-3 is necessary to bring all components of the objective function to one dimension (cu).
To solve the problem, we choose the method of coordinate descent. Let us determine the partial derivatives of the objective function Z with respect to the variables Q1 and Q2:
(2.8)
Let's take the initial approximation:
For these values, we calculate the values of the objective function and its partial derivatives.
Let us assume that in the direction of the variable Qk2 the objective function Z decreases more strongly than in the direction of the variable Qk1, i.e.
(2.10)
In the direction of the variable Qk2 we will begin our descent.
Let's take the step size =400 kvar. The first approximation (first step) will be Qk11=0, Qk21=400 kvar. We calculate the value of the objective function Z1.
Second step: Qk12=0, Qk22=400 kvar. We calculate the value of the objective function Z2.
The descent along the Qk2 coordinate should continue until Zn Let's take a new step in the direction of another variable Qk1. A new value of the objective function Z is found. The descent along this variable continues in the same way as in the direction Qk2 - until Zm The point with the obtained coordinates Qk1m-1, Qk2n-1 is located in the vicinity of the minimum of the objective function Z. With the adopted step length = 400kvar, a more accurate solution cannot be obtained. To obtain a more accurate solution, it is necessary to reduce the step and continue descent. It is absolutely certain that the smaller the step, the more accurate the result will be. We cannot achieve such accuracy through manual calculation. To solve this problem, it would be advisable to use software designed to solve nonlinear programming problems with nonlinear constraints. One such programming language is C++. This was considered an unconstrained optimization problem, i.e. finding the absolute minimum. When solving the problem posed, in order to find the optimal operating mode of the network of OJSC Ilyich Iron and Steel Works, it is necessary to find a relative minimum, since the system of restrictions will have a nonlinear form (see below “Software Development”). Thus, we are faced with the problem of conditional optimization for reactive power, for which we use the previously selected gradient method of quadratic programming.
Information about the work “Analysis of operating modes of electrical networks of OJSC Ilyich Iron and Steel Works and development of an adaptive control system for power consumption modes” Students, graduate students, young scientists who use the knowledge base in their studies and work will be very grateful to you. Chelyabinsk Law College COURSE WORK in the discipline "Mathematical methods" Lagrange multiplier method Student gr. PO-3-05, Department of Law and Information Technologies Supervisor N.R. Khabibullina Chelyabinsk Introduction 1. Model building 2. Lagrange problem. Unconditional and conditional extremes 3. Lagrange problem with one constraint 4. The meaning of Lagrange multipliers 4.1. Lagrange's theorem 4. 2. Lagrange multiplier method 4.3. Lagrange's Undetermined Multiplier Method 4.4. Two-dimensional case Conclusion List of used literature Introduction The Lagrange method is based on several key ideas. One of them is how to find the minimum of a function if some restrictions are imposed on the function. This technique is now called the “Lagrange multiplier rule” This topic is relevant in modern times because the Lagrange multiplier method is used in solving nonlinear programming problems that arise in many fields (for example, in economics). An important place in the mathematical apparatus of economics is occupied by optimal problems - problems for which the best solution in a certain sense is sought. In economic practice, it is required to use available resources in the most profitable way. In economic theory, one of the starting points is the postulate that each economic subject, having a certain freedom to choose his behavior, looks for the best option from his point of view. And optimization problems serve as a means of describing the behavior of economic entities, a tool for studying the patterns of this behavior. 1. Model building To formulate the problem, it is necessary to analyze the system, study its features and possible methods of controlling the system. The diagram constructed as a result of such analysis is either a pictorial or an analogue model. Thus, the first stage of model construction is performed during the process of problem formulation. After such an analysis of the system, the list of various options for solutions that need to be evaluated is clarified. Measures of the overall effectiveness of these options are then determined. Therefore, the next step is to construct a model in which the efficiency of the system can be expressed as a function of the variables that define the system. Some of these variables can be changed in a real system, but other variables cannot be changed. We call those variables that can be changed “controllable”. Various options for solving a problem must be expressed using controlled variables. The construction of a mathematical (symbolic) model of a system can be started by listing all the elements of the system that affect the efficiency of the system. If “total expected cost” is used as a measure of overall efficiency, then one can begin by examining the pictorial or analogue model obtained at the problem formulation stage. You can select operations and materials to which certain costs are assigned. In this case, we get, for example, the following initial list: Production costs: a) purchase price of raw materials; b) costs of transporting raw materials; c) cost of receiving raw materials; d) cost of storing raw materials; e) cost of production planning; f) the cost of adjustment work in the workshop; g) the cost of the processing process; h) the cost of storing inventories during the production process; i) the cost of completing production and transferring finished products to the warehouse; j) the cost of analyzing the results of work by the planning group; k) cost of storing finished products. Sales costs. Overheads. Many optimization problems are formulated as follows. The decision that the subject must make is described by a set of numbers x 1, x 2,..., x n (or point X = (x 1, x 2,..., x n) of n-dimensional space). The merits of a particular solution are determined by the values of the function f(X) = f(x 1, x 2,…,x n) -- objective function. The best solution is a point X at which the function f(X) takes highest value. The problem of finding such a point is described as follows: From which options should the best one be chosen? In other words, among which points in space should we look for the optimum. The answer to this question is related to such an element of the optimization problem as set of feasible solutions. In some problems, any combination of numbers x 1, x 2,..., x n is valid, that is, the set of feasible solutions is the entire space under consideration. In other problems, various constraints must be taken into account, meaning that not all points in space are available for selection. In meaningful formulations of problems, this may be due, for example, to the limited amount of available resources. Constraints can be presented in the form of equalities of the form or inequality If the conditions have a slightly different form, say, g 1 (X) = g 2 (X) or g (X) A, then they can be brought to a standard form by transferring them to functions and constants in one of the parts of the equality or inequality. An extremum found in the entire space, without any limiting conditions, is called unconditional. If the objective function is continuously differentiable, then the necessary condition for the unconditional extremum of the function is that all its partial derivatives be equal to zero: If restrictions are specified, then the extremum is sought only among points that satisfy all the restrictions of the problem, since only such points are admissible. In this case, the extremum is called conditional. Consider the problem of finding a conditional extremum: under conditions (2) g 1 (X) = 0; g 2 (X) = 0, ..., g n (X) = 0, all of whose constraints are equalities. If the objective function and all limiting functions are continuously differentiable, then we will call such a problem Lagrange problem. Let's look at an example. There is a road along the mountainside, you need to find the highest point on it. In Fig. 1 shows a map of the area with lines marked on it equal heights; the thick line is the road. Point M, at which the road touches one level line, is the highest point of the road. If X = (x 1, x 2) is the density point, x 1 and x 2 are its coordinates, then the problem can be given the following form. Let f(X) be the height of point X above sea level, and the equation g(X) = 0 describes the road. Then the highest point of the road is the solution to problem (3). If the road passed through the top of a mountain, then its highest point would be the highest point in the area, and the restriction could be ignored. If the road does not pass through the peak, then by deviating slightly from the road, one could rise higher than by moving strictly along the road. Deviation from the road corresponds to hitting points where g(X) 0; for small deviations, the height achievable can be approximately considered proportional to the deviation. The idea of solving the Lagrange problem can be presented as follows: you can try to “correct” the terrain so that deviation from the road does not provide an advantage in achieving heights. To do this, you need to replace the height f(X) with a function. L(X) = f(X) - g(X), where the multiplier is selected in such a way that the section of the slope in the vicinity of point M becomes horizontal (too small will not eliminate the benefits of deviations from the road, and too large will give an advantage to deviations in the opposite direction). Now, since the relief L(X) makes the area in the vicinity of the optimum point horizontal, this point satisfies the equalities and since the point lies on the road, then the constraint g(X) = 0. The example of the mountain and the road is just an illustration of the idea; similarly, the two-dimensional case is used solely for clarity. One could reason in a similar way in the general n-dimensional case. The following statement is true: If f(x 1 ,…,x n) and g(x 1 ,…,x n) are continuously differentiable functions of all their arguments, then the solution to the problem f(x 1,…,x n) max given that g(x 1,…,x n) = 0 satisfies the equalities L(x 1,...,x n;) = f(x 1,...,x n) - g(x 1,...,x n). The function L(X;) is called Lagrange functions(or Lagrangian) of problem (3), and the coefficient is Lagrange multiplier. Note that equality (5) is the constraint g(X) = 0 presented in another form. The above reasoning, of course, is not proof of the statement formulated here; they only help to understand the essence of the method: the component g(X) in the Lagrange function must balance the possible increase in the maximum value of the function g(X) from zero. This circumstance will be very useful in the future when discussing the meaning of the Lagrange multiplier. Let's look at an extremely simple example. Using a rope of length A, you need to fence off a rectangular area of the largest area on the seashore (the coast is considered straight). Fig.3 To Dido's problem Let's denote the sides of the rectangle x 1 and x 2 (see Fig. 3). Let us first solve the problem without using the Lagrange method. Obviously, x 2 = A - 2 x 1 and the area of the rectangle is S = x 1 x 2 = x 1 (A - 2x 1). Considering it as a function of one argument x1, it is not difficult to find its value at which the area is maximum: x 1 = A/4. Hence x 2 = A/2. The maximum area is S* = A 2 /8. Now consider the same problem in the form of the Lagrange problem: given that 2 x 1 + x 2 - A = 0 The Lagrangian of this problem is equal to L(x 1,x 2 ;) = x 1 x 2 - (2x 1 + x 2 - A), and the extremum conditions have the form 2 x 1 + x 2 = A Substituting the values x 1 and x 2 from the first and second equalities into the third, we find that 4 = A, whence A/4; x 1 = A/4; x 2 =A/2, as in the first solution. This example shows a common way to solve the Lagrange problem. Relations (4) and (5) form a system of equations for x 1,..., x n and,. The system consists of n + 1 equations - n equations of the form (4) and one equation of the form (5). The number of equations is equal to the number of unknowns. From equations of the form (4), you can try to express each of the unknowns x 1,..., x 2 through, that is, solve it as a system of n equations, considering it as a parameter. Substituting the resulting expressions into equation (5) - we know that it coincides with the constraint - we obtain the relative equation. By solving it, they find it, after which the initial unknowns x 1,..., x n are determined. 4. The meaning of Lagrange multipliers When solving the Lagrange problem, we were interested in the values of x 1,..., x n; in addition, we could be interested in the extreme value of the objective function f(X). But during the solution process, the value of another quantity was simultaneously determined - the Lagrange multiplier. It turns out that the Lagrange multiplier is a very significant characteristic of the problem being solved. To make its meaning clearer, let us slightly change the wording of the restriction without changing anything in essence. A typical economic situation is characterized by the fact that one has to look for the most profitable solution with a limited amount of a certain resource. If r is a given amount of a resource, and the function h(X) characterizes the amount required to reach point X, then it is natural to give the constraint the form Given the nature of the problem, it is often clear that to achieve the optimum the resource must be fully utilized, so the constraint can be written as This condition can be represented in the form g(X) = h(X) - r = 0. But of significant interest is the maximum achievable level of the function f(x) depending on the available amount of resource r. Let's denote F(r) = max f(X) h(X) = r. On the right side is the accepted designation for a conditional extremum: a condition is written after the vertical line. Let us recall that when discussing the structure of the Lagrangian, we interpreted g(X) as a component that balances the possible increase in the maximum f(X) when g(X) deviates from zero. But the deviation of g(X) from zero is the deviation of h(X) from r. If the available amount of a resource increases by r, then we should expect the maximum of the function f(X) to increase by r. In reality, this ratio is approximate. We would get the exact result in the limit at r 0: Thus, the Lagrange multiplier characterizes the rate of change in the maximum of the objective function when the limiting constant r in the constraint of the form (6) changes. In the version of Dido’s problem considered in the previous paragraph, the limited resource was the length of the rope A. The maximum area turned out to be equal to S(A) = A 2 /8. Hence dS(A)/dA = A/4, which exactly corresponds to the value found in the solution. Let us give one more reasoning. For all possible points X, we find the values of f(X) and h(X) and plot these values as points in Cartesian coordinates (Fig. 4). If for each value of h(X) there is a maximum of the function f(X), then all points will be located below a certain curve, shown in the figure with a thick line. We are interested in points corresponding to the condition h(X) = r. The maximum of f(X) is marked by the point M*; Let's denote the slope of the curve at this point. If we take not f(X) as the ordinate, but L(X;) = f(X) - , then the new upper boundary would have a horizontal tangent at the point M*. This means that in the original n-dimensional space the corresponding point M is a stationary point of the function L (X;) with a given parameter value. Thus, is the Lagrange multiplier. But the thick black curve is a graph of the function F(r), and is its slope, which implies equality (7). 4.1 Lagrange's theorem Suppose a function?(x) is given on the plane and a curve g(x) = 0 is given. If the function?, limited to a given curve, reaches its minimum or maximum at a point, then the vectors?() and g"() are collinear ( provided that both functions have derivatives at a point). In Lagrange's general theorem, the function? depends not on two, but on n variables, and there are several functions g(x) that specify the constraints (x)=0, i=l,..., m. We will leave this theorem without proof; this would lead us too far towards mathematical analysis. Let's see how well it works at finding maxima and minima. Theorem (Snell's Law on the refraction of light). Two media are separated by a straight line, in the first the speed of light propagation is equal, and in the second - . If a ray of light leaves the first medium at an angle to the normal and enters the second at an angle, then Proof. A straight line on a plane is given by the equation where is an arbitrary point on a line, a n is a vector perpendicular to a line. Let's choose an arbitrary point on the incoming beam of light and a point on the refracted one (Fig. 30). Light always travels along the path that takes the least amount of time. This means that we need to find a point x on the boundary of the media for which the quantity?(x) = takes on the smallest value. We get the task: ?(x)=-min under the condition g(x) = n (x--) = 0. According to Lagrange's principle, at the minimum point the vectors "(x) and g"(x) are collinear. The derivative?(x) is equal to the sum of a vector that has length 1/ and is codirectional with the vector x--, and a vector of length 1/, codirectional with the vector x--. And the derivative g"(x) is equal to the vector n. The collinearity condition means that the sum + is perpendicular to the line, that is, the projections of the vectors and onto the line are equal. Thus, what was required. Well, now we are ready to present the promised solutions to the problems of the minimum sum of distances to a point on a straight line and to a point on a plane. 66. Problem on the minimum sum of distances from k points on a plane to a point on a line. A line and k points are given on a plane. Find (or characterize) the position of a point on a line for which the sum of the distances to these points is minimal. Solution. Let l be the given line and let be the given points. Let's solve the problem to the minimum: ?(x) = |x--|+...+|x--|^min provided g(x) = n (x--) = 0, where is an arbitrary point on the line l, and n is a vector perpendicular to this line. Let us denote by a vector of unit length, codirectional with the vector x--. Then?"(x)=+...+, a g"(x)=n. According to Lagrange's theorem, at the minimum point the vector?(x) is collinear to n, that is, perpendicular to the straight line l. Thus: The solution to the problem is a point on the line l for which the sum of the projections onto the line k of unit vectors directed from it to the given points is equal to zero. If out of the given k points there is at least one that does not lie on line l, then the problem has a unique solution. It is quite simple to prove this if you use the technique from problem 62. If k? 3, then such a point, generally speaking, cannot be constructed using a compass and a ruler (calculating its coordinates leads to an equation of high degree). Therefore, in the general case, we have nothing better than the description of the minimum point that we gave. The problem of the minimum sum of distances from k points in space to a point on a given plane. A plane and k points are given in space. Find (or characterize) the position of a point on the plane for which the sum of distances to these points is minimal. The solution to this problem is no different from the previous one and leads to a similar answer: The minimum is achieved at point x of the plane, for which the sum of the projections onto the plane of k unit vectors directed from x to these points is equal to zero. 4.2
Lagrange multiplier method Method for finding the conditional extremum of a function f(x), where, relatively m restrictions i(x) = 0, i varies from one to m. Let the NP problem be given under equality constraints of the form Minimize (4.2.1) under restrictions Let us assume that all functions are differentiable. Let us introduce a set of variables (the number of which is equal to the number of constraints), which are called Lagrange multipliers, and compose a Lagrange function of this form: This statement is true: in order for a vector to be a solution to problem (4.2.1) under constraints (5.2.2), it is necessary that there exist a vector such that a pair of vectors would satisfy the system of equations Let us show the necessity of conditions (4.2.4), (4.2.5) using a simple example: minimize (4.2.6) under restrictions Constraints (5.2.7) define the feasible region, which is a curve in space and is the result of the intersection of and. Let us assume that the problem under consideration has a minimum point at: , the functions have continuous first-order derivatives on some open set and gradients linearly independent. If two variables in equations (4.2.7) can be expressed through a third one in the form, then substituting them into the objective function (5.2.6), we transform the original problem into the following problem without restrictions, which contains only one variable: minimize. (4.2.8) Since the gradients are continuous and linearly independent, we can apply the well-known theorem of mathematical analysis about the implicit function and find the stationary point, and then. The above approach can, in principle, be extended to the case of a function of variables in the presence of equality constraints: If the functions satisfy the conditions of the implicit function theorem, then the variable equations (4.2.9) can be expressed in terms of the remaining variables, substitute them into and thus transform the constrained minimization problem into an unconditional minimization problem with variables. However, this approach is difficult to implement in practice, since it is very difficult to resolve equations (4.2.9) with respect to some variables. In the general case this is completely impossible. Therefore, let's consider another approach, which is based on the Lagrange multiplier method. Let be the minimum point defined by expression (4.2.8). In accordance with the well-known theorem of mathematical analysis about the implicit function, we can write We obtain similar relations for the restrictions Let us write equations (4.2.10), (4.2.11) together in the form Since the vector is not zero, it follows from (4.2.12) that. It follows from this that the row vectors Scalar A cannot equal 0, since, according to the assumption, and are linearly independent. Therefore, after dividing (5.2.13) by, we get Thus, for a minimization problem with constraints (4.2.6), there are those for which equation (4.2.14) is valid and which at the same time do not vanish. So, the validity of conditions (4.2.4) for the case n=3 is shown. Thus, to find the minimum (4.2.6) under conditions (4.2.7), it is necessary to find the stationary point of the Lagrange function: In order to find the required values, it is necessary to jointly solve the system of equations (4.2.14), (4.2.5). From a geometric point of view, condition (4.2.14) means that it lies in the plane spanned by the vectors Now let's consider the general case for arbitrary ones. Let the NP problem be given in the form (4.2.1), (4.2.2), all functions have continuous partial derivatives on the set. Let be a subset of the set on which all functions, that is, Then the following theorem about Lagrange multipliers is valid. Theorem. Let's sayThuoh there is such a point
, in which the relative extremum of the NP problem (5.2.1) is achieved under conditions (4.2.2). If rankmatrices
at the point
equals
, then there are
numbers
, not all of which are equal to zero at the same time, for which This theorem justifies the Lagrange multiplier method, which consists of the following steps. Compose the Lagrange function Find partial derivatives Solve a system of equations and find points that satisfy system (4.2.16). 4.3 Lagrange's method of undetermined multipliers It is used to solve problems with an analytical expression for the optimality criterion and in the presence of restrictions on independent variables such as equalities. To obtain an analytical solution, it is required that the constraints have an analytical form. The use of indefinite Lagrange multipliers allows us to reduce the optimization problem with constraints to a problem solved by methods of studying functions of classical analysis. In this case, the order of the system of equations solved to find the extremum of the optimization criterion increases by the number of constraints. The method is effective when the number of variables is three or less. The method is also used when the number of variables is more than three, if the process is described by finite equations. Let it be necessary to find the extremum of a function that depends on n variables, which in turn are connected by relationships. The extremum achieved by a function, taking into account the fulfillment of conditions, is called relative, or conditional. If the number of variables is equal to the number of relations (), then the unknown unknowns are found by solving the system of equations described by the relations. Solving the optimization problem comes down to checking the values of the variables found in this way against the functions. Thus, the extremal problem can be solved by simply enumerating variables that satisfy the conditions. If m< n
, then from the communication equations we can find the dependence m variables from n - m remaining variables, i.e. The function can be obtained by substituting the resulting variables into the function. Then it will depend only on variables that are not bound by additional conditions. Consequently, by removing the restrictions it is possible to reduce the dimension of the original optimization problem. Often the problem cannot be solved analytically in this way. Therefore, to solve problems of finding the extremum of a function of many variables, the Lagrange method of indefinite multipliers is usually used. When introducing new variables called indefinite Lagrange multipliers, it becomes possible to introduce a new function those. function m+n variables, in which the restrictions imposed by the system of functions are included as an integral part. An extreme value of a function coincides with an extreme value of a function if the constraint condition is met. A necessary condition for the extremum of a function of many variables is that the differential of this function at the extremal point is equal to zero, i.e. In order for this expression to be satisfied for any values of the independent differentials, it is necessary that the coefficients of these differentials be equal to zero, which gives a system of equations In this case, new independent ones are determined from the condition The combination of systems (4.3.1) and (4.3.2) can be obtained Thus, the problem in the form (4.3.3) reduces to the task: find Separately, it should be noted that in the general case, the Lagrange multiplier method allows one to find only the necessary conditions for the existence of a conditional extremum for continuous functions that have continuous derivatives. However, from the physical meaning of the problem being solved, it is usually known whether we are talking about the maximum or minimum of the function; in addition, as a rule, in design problems the function on the segment under consideration is unimodal. Therefore, in design problems there is no need to check the values of variables found when solving the considered systems of equations for extremum using the analysis of higher order derivatives. 4.4
Two-dimensional case Suppose we need to find the extremum of some function of two variables f(x,y) under the condition specified by the equation w( x,y) = 0. We will assume that all functions are continuously differentiable, and this equation defines a smooth curve S on surface ( x,y). Then the problem reduces to finding the extremum of the function f on the curve S. We will also assume that S does not pass through points where the gradient f turns to 0. Level lines f(x,y) and curve S Let's draw on the plane ( x,y) function level lines f(that is, curves f(x,y) = const). From geometric considerations it is clear that the extremum of the function f on the curve S there can only be points at which tangents to S and the corresponding level line coincide. Indeed, if the curve S crosses the level line f at point ( x 0 ,y 0) transversally (that is, at some non-zero angle), then moving along the curve S from point ( x 0 ,y 0) we can get to the level lines corresponding to a larger value f, and less. Therefore, such a point cannot be an extremum point. Thus, a necessary condition for an extremum in our case will be the coincidence of the tangents. To write it in analytical form, note that it is equivalent to the parallelism of the gradients of the functions f and w at this point, since the gradient vector is perpendicular to the tangent to the level line. This condition is expressed in the following form: where l is a non-zero number that is a Lagrange multiplier. Let's now consider Lagrange function, depending on x,y and l: L(x,y,l) = f(x,y) ? lsh( x,y) A necessary condition for its extremum is that the gradient be equal to zero. In accordance with the rules of differentiation, it is written in the form We have obtained a system, the first two equations of which are equivalent to the necessary condition for a local extremum (1), and the third is equivalent to the equation w( x,y) = 0. From it we can find ( x 0 ,y 0 ,l 0). Moreover, since otherwise the gradient of the function f vanishes at a point, which contradicts our assumptions. It should be noted that the points found in this way ( x 0 ,y 0) may not be the desired points of the conditional extremum - the considered condition is necessary, but not sufficient. Finding a conditional extremum using an auxiliary function L and forms the basis of the Lagrange multiplier method, applied here for the simplest case of two variables. It turns out that the above reasoning can be generalized to the case of an arbitrary number of variables and equations specifying the conditions Conclusion A method for solving a problem in which the coefficients a[i] are determined by directly solving the system - the method of undetermined coefficients. Newton's interpolation formula and its variants. Construction of a Lagrange interpolation polynomial for a given function. laboratory work, added 11/16/2015 Application of the Lagrange function in convex and linear programming. The simplest problem of Boltz and the classical calculus of variations. Using the Euler-Lagrange equation to solve the isoperimetric problem. Boundary conditions for finding constants. course work, added 01/16/2013 Finding the extremum of a function of several variables not over the entire domain of definition, but over a set that satisfies a certain condition. A practical example of finding the maximum and minimum points of a function. Main features of the Lagrange multiplier method. presentation, added 09/17/2013 Methods of conditional and unconditional nonlinear optimization. Study of a function for an unconditional extremum. Numerical methods for minimizing a function. Minimization with mixed constraints. Saddle points of the Lagrange function. Using MS Excel and Matlab packages. laboratory work, added 07/06/2009 Advantages of Lagrange equations and their applications. Classification of connections within a mechanical system. Possible movements of the mechanical system and the number of degrees of freedom. Application of Lagrange equations of the second kind to the study of a mechanical system. course work, added 08/21/2009 Application of Lagrange's theorem in solving problems. Its use in solving inequalities and equations, when finding the number of roots of some equation. Solving problems using the monotonicity condition. Relationships between increasing or decreasing functions. abstract, added 03/14/2013 Proof of the existence and uniqueness of the Lagrange interpolation polynomial. The concept of Lagrangian coefficients. Methods for specifying the slopes of an interpolating cubic spline, its use for approximating functions over large intervals. presentation, added 10/29/2013 Finding extrema of functions using the Lagrange multiplier method. Extended objective function expression. Scheme of the algorithm for numerical solution of the problem by the method of penalty functions in combination with the method of unconditional minimization. Construction of constraint lines. course work, added 05/04/2011 Formation of the Lagrange function, Kuhn and Tucker conditions. Numerical optimization methods and flowcharts. Application of methods of penalty functions, external point, coordinate descent, conjugate gradients to reduce conditional optimization problems to unconditional ones. course work, added 11/27/2012 Plotting a graph of a continuous function. Definition of the Lagrange multiplier. Critical points are values of the argument from the domain of definition of the function at which the derivative of the function vanishes. The largest and smallest values of a function on a segment.Send your good work in the knowledge base is simple. Use the form below
Department of Mathematical and Natural Sciences
2. Lagrange problem
.
Unconditional and conditional extremes
f(X) max.
If the function f(X) characterizes the negative aspects of the decision (damage, losses, etc.), then the point X is searched for at which the value of f(X) is minimal:
f(X) min.
The minimum and maximum are united by the concept of extremum. To be specific, we will only talk about maximization problems. Finding the minimum does not require special consideration, since by replacing the objective function f(X) with -f(X) you can always “turn disadvantages into advantages” and reduce minimization to maximization.
3. Lagrange problem with one constraint
Consider a problem with the following structure:
f(X) max
subject to (3)
g(X) = 0.
the matrices A must be linearly dependent. Therefore, there are three such scalars not all equal to 0, such thatThe use of mathematical models has now become a very pressing issue in connection with the constantly developing economy.
The construction of a mathematical (symbolic) model of a system can be started by listing all the elements of the system that affect the efficiency of the system. If “total expected cost” is used as a measure of overall efficiency, then one can begin by examining the pictorial or analogue model obtained at the problem formulation stage.
The Lagrange multiplier method allows you to find the maximum or minimum of a function under equality constraints. The main idea of the method is to move from the problem of finding a conditional extremum to the problem of finding the unconditional extremum of some constructed Lagrange function.
Thus, the method of Lagrange multipliers plays an important role in the development, prediction, construction of the optimal option, the human sphere of activity
.
List of used literature
1. V.I. Varfolomeev “Modeling elements of economic systems.” Moscow 2000
2. Buslenko N.P. “Modeling of complex systems” Moscow, 1999.
3. W. Churchman, R. Akof, L. Artof. “Introduction to Operations Research.” Science: Moscow, 1968.
4. A. Budylin “Elementary problems”. Moscow, 2002
5. Vanko V.I., Ermoshina O.V., Kuvyrkin G.N. Variational “Calculus and optimal control”. Moscow, 1999
6. Ashmanov S.A., Timokhov A.V. “Optimization theory in problems and exercises.” Moscow, 1991
7. “Laboratory workshop on optimization methods.” A.G.Kovalenko, I.A.Vlasova, A.F.Fedechev. - Samara, 1998
Similar documents
