Local minimum with equality constraints. Symbolic and numerical calculation
Given the perimeter of a rectangle find the dimensions that maximize the area using the necessary first-order conditions. Check that the sufficient second-order conditions are met.
The problem can be posed as minimizing $f(x,y) = -x\,y$ with the restriction that $2x+2y=p.$
Let's see the example with $p=1$. The representation of the function $f$ is a hyperbolic paraboloid. We can obtain its gradient $\nabla f$ at every point and it will be normal to the isoline of $f$ that passes through the point.
The equality constraint $2x+2y=1$ has represented as a black line. We can assume that this line is an isoline of the plane $g(x,y)=2x+2y-1$ and then, the normal vector to the line at each point is given by $\nabla g$.
We are looking for the minimum value of the function $f$ but we only take into account the points of the line. This minimum will be given by the point where a contour of $f$ is tangent to the line $2x+2y-1=0$ or, expressed in another way, the point where the normals to the two curves are parallel. That is, we look for the points where $\lambda$ is non-zero.
$$ \nabla f = -\lambda \nabla g \quad \Longrightarrow \quad \nabla f +\lambda \nabla g=\mathbf{0} \quad \Longrightarrow \quad \nabla (f +\lambda g)=\mathbf{0} $$The function
$$L(x,y,\lambda) = f(x,y) +\lambda g(x,y)$$is called lagrangian function and the minimum with equality restriction necessary condition is that $\nabla L=\mathbf{0}$
and we compute the gradient of $L$ and make it equal to zero
$$ \begin{align} L^{\prime}_{x}&=&-y+2\lambda&=&0 \\ L^{\prime}_{y}&=&-x+2\lambda&=&0 \\ L^{\prime}_{\lambda}&=&2x+2y-p&=&0 \end{align} \qquad x = \frac{p}{4} \quad y = \frac{p}{4} \quad \lambda = \frac{p}{8} $$And the point $x = \dfrac{p}{4} \quad y = \dfrac{p}{4}$ ($x =0.25 \quad y = 0.25$ for $p=1$) meets the necessary conditions of extreme.
Let's now look at the sufficient conditions. To check whether this point is a maximum or a minimum we will use the determinant of the Hessian matrix of the Lagrangian $L(x,y,\lambda)$ calculated at the critical point.
- If negative, the point is a minimum.
- If positive, the point is a maximum.
The Hessian matrix of the Lagrangian function is
$$ H_{F}= \left( \begin{array}{ccc} L^{\prime\prime}_{xx} & L^{\prime\prime}_{xy} & L^{\prime\prime}_{x\lambda}\\ L^{\prime\prime}_{yx} & L^{\prime\prime}_{yy} & L^{\prime\prime}_{y\lambda}\\ L^{\prime\prime}_{\lambda x} & L^{\prime\prime}_{\lambda y} & L^{\prime\prime}_{\lambda\lambda}\\ \end{array} \right) $$that is
$$ H = \left( \begin{array}{rrc} 0 & -1 & 2\\ -1 & 0 & 2\\ 2 & 2 & 0\\ \end{array} \right). $$As $\det(H)=-8 \lt 0,$ there is a minimum at the point $x = \dfrac{p}{4} \quad y = \dfrac{p}{4}$. Since $\det(H)=-8\lt 0$ at the point $x=\dfrac{p}{4} \quad y=\dfrac{p}{4}$ there is a minimum of the function $f(x,y)=-x\,y$, which corresponds to a maximum of $-f(x,y)=x\,y$, which is the area of the rectangle. Therefore the rectangle of maximum area, fixed the perimeter, is a square since the sides are equal.
Numerically: penalty function¶
We must fix the $p$ to solve the problem numerically. Let us choose $p=1.$
The idea of the penalty method is to replace the objective function $f$ by another function
$$F(x,y)=f(x,y)+c\,P(x,y)$$and solve the problem without constraints. For this, we take $c$ as a positive constant and we must choose $P$, the penalty function, in such a way that:
- $P$ is continuous in the domain of $f$.
- $P(x,y)\geq 0$ for every point in the domain of $f$, and
- $P(x,y)=0$ if and only if the point $(x,y)$ satisfies the constraints.
A possible function to approximate the constrained minimum would be
$$F(x,y)=-x\,y+100\,(2x+2y-1)^2$$Now, the absolute minimum of this function is close to the minimum with restrictions of $ f $ (the closer the greater the $c$ is), as seen in the following graph, and we can approximate it with a numerical method, such as Newton or the gradient descent method. It is an approximate solution, as numerical solutions generally are.
