Contents

• 1  Analytically
  • 1.1  We look for local extrema.
  • 1.2  We look for extrema at the borders
  • 1.3  We add the intersection points of the borders
  • 1.4  We consider the value of the function in all the points
• 2  Numerically: penalty function

Maximum and minimum with inequality constraints. Symbolic and numerical calculus

Find the maximum and the minimum of the function

$$f(x,y)=x^2-16x+y^2-10y+24$$

with the constraints $x+y\leq5\quad x+2y\leq8 \quad x\geq0 \quad \mathrm{and} \quad y\geq0$.

---

Analytically

The Extreme Value Theorem says that if $$f: A \in \mathbb{R}^n \rightarrow \mathbb{R}$$ is continuous on a closed and bounded subset of $\mathbb{R}^n$, $f$ reaches an absolute maximum and minimum within such subset.

The conditions $x\geq0$ and $y\geq0$ mean that the study area is in the first quadrant and, thus, axis $X,$ whose equation is $y=0$ and axis $Y$ whose equation is $x=0$ are borders of the area.

The additional borders of the area are

$$ \begin{align} x+y=5\\ x+2y=8 \end{align} $$

If we write the lines in the intercept form

$$\dfrac{x}{a}+\dfrac{y}{b}=1$$

$a$ is the intersection point of the line with the $X$ axis and $b$ with the $Y$ axis.

If we divide the first expression by 5 and the second one by 8

$$ \begin{align} \dfrac{x}{5}+\dfrac{y}{5}=1\\ \dfrac{x}{8}+\dfrac{y}{4}=1 \end{align} $$

and the representation of the lines is

Each line divides the plane into three zones. For example, $x+y=5$ divides the plane into the zones

• $x+y \gt 5$ is a half-plane.
• $x+y = 5$ is the line.
• $x+y \lt 5$ is the other half-plane.

To check which of the two zones is the one that contains, for example, the point $(0,0)$ it is enough to try with this point and the inequality $x+y\le 5$

$$0 + 0 \le 5$$

Therefore $x+y\le 5$ is the area that includes the line and the half-plane below the blue line.

Similarly, we test with $(0,0)$ and $x+2y \le 8$ and $$0+2(0)\le 8$$ and it is the half-plane below the red line.

And the area that meets both conditions is the intersection, which is green int the third graph.

Interactive plot

Therefore, considering the constraints, we are looking for a maximum and a minimum in the area below the red and blue lines, that is, the green region. We perform the following steps:

1. We look for local extrema.
2. We look for extrema at the borders.
3. We add the intersection points of the borders.
4. We consider the value of the function in all the previous points, and the point for which the function has the smallest value, is the minimum and for the greatest value, we have a maximum.

We look for local extrema

The extreme necessary condition for a point $\left(x_{m},y_{m}\right)$ is that $\nabla f\left(x_{m},y_{m}\right)=\left(f^{\prime}_{x},f^{\prime}_{y}\right)=\left(0,0\right)$. That is, for

$$ f(x,y)=x^2-16x+y^2-10y+24 $$

we have

$$ \begin{cases} f^{\prime}_{x}=0\\ f^{\prime}_{y}=0 \end{cases} \qquad \begin{cases} 2x-16=0\\ 2y-10=0 \end{cases} \qquad \begin{cases} x=8\\ y=5 \end{cases} $$

And we have obtained a point (red in the plot)

$$\fbox{(8,5)}$$

We look for extrema at the borders

Function $f(x,y)=x^2-16x+y^2-10y+24$ and constraint $x=0$.

The Lagrangian function is $L(x,y,\lambda)=f(x,y)+\lambda g(x,y)$

$$ L(x,y,\lambda)= x^2-16x+y^2-10y+24 +\lambda (x) $$

We calculate the partial derivatives and make them equal to zero

$$ \begin{array}{l} L'_x = 2x -16+\lambda=0\\ L'_y = 2y -10 =0 \\ L'_{\lambda} = x = 0 \end{array} $$

From the second equation $y = 5$, and from the third $x = 0.$ If we substitute these values in the first equation $\lambda = 16$

A possible extreme is the point (in white in the plot) $$\fbox{(0,5)}$$

Function $f(x,y)=x^2-16x+y^2-10y+24$ and constraint $y=0$.

The Lagrangian function is

$$ L(x,y,\lambda)= x^2-16x+y^2-10y+24 +\lambda (y) $$

We calculate the partial derivatives and make them equal to zero

$$ \begin{array}{l} L'_x = 2x -16=0\\ L'_y = 2y -10+\lambda =0 \\ L'_{\lambda} = y = 0 \end{array} $$

From the first equation $x = 8$, and from the third $y = 0.$ If we substitute these values in the second equation $\lambda = 5$

A possible extreme is the point (in white in the plot) $$\fbox{(8,0)}$$

Function $f(x,y)=x^2-16x+y^2-10y+24$ and constraint $x+y=5$.

The Lagrangian function is

$$ L(x,y,\lambda)= x^2-16x+y^2-10y+24 +\lambda (x+y-5) $$

We calculate the partial derivatives and make them equal to zero

$$ \begin{array}{l} L'_x = 2x -16+\lambda=0\\ L'_y = 2y -10+\lambda =0 \\ L'_{\lambda} = x+y-5 = 0 \end{array} $$

From the first equation $x =\dfrac{16-\lambda}{2}$, from the second one $y = \dfrac{10-\lambda}{2}.$ If we use these values in the third equation

$$\frac{16-\lambda}{2}+\frac{10-\lambda}{2}-5=0 \quad \rightarrow \quad 16-\lambda+10-\lambda=10 \quad \rightarrow \quad \lambda =8$$

And substituting this $\lambda$ value in $x$ and $y$ we have $\lambda$ $x =\dfrac{16-\lambda}{2}=\dfrac{16-8}{2}=4$ and also $y = \dfrac{10-\lambda}{2}=\dfrac{10-8}{2}=1$ and a possible extreme is $$\fbox{(4,1)}$$

Function $f(x,y)=x^2-16x+y^2-10y+24$ and constrain $x+2y=8$.

The Lagrangian function is

$$ L(x,y,\lambda)= x^2-16x+y^2-10y+24 +\lambda (x+2y-8) $$

We calculate the partial derivatives and make them equal to zero

$$ \begin{array}{l} L'_x = 2x -16+\lambda=0\\ L'_y = 2y -10+2\lambda =0 \\ L'_{\lambda} = x+2y-8 = 0 \end{array} $$

From the first equation $x =\dfrac{16-\lambda}{2}$, from the second equation $y = \dfrac{10-2\lambda}{2}.$ Using these values in the third equation

$$\frac{16-\lambda}{2}+2\frac{10-2\lambda}{2}-8=0 \quad \rightarrow \quad 16-\lambda+20-4\lambda=16 \quad \rightarrow \quad \lambda =4$$

and substituting this $\lambda$ in $x$ and $y$ as $x =\dfrac{16-\lambda}{2}=\dfrac{16-4}{2}=6$ and also $y = \dfrac{10-2\lambda}{2}= \dfrac{10-2(4)}{2}=1$ and a possible extreme $$\fbox{(5,-1)}$$

We add the intersection points of the borders

We obtain the intersection of the two borders $x+y=5\quad \mathrm{and} \quad x+2y=8$ subtracting the second equation from the first. We obtain $y=3$. Substituting this value in the first equation we have $x=2$ and the point is $$\fbox{(2,3)}$$

The intersections of the lines with the axis are $$\fbox{(0,4)} \quad \fbox{(5,0)}$$

Finally, the intersection of the two axis is $$\fbox{(0,0)}$$

We consider the value of the function in all the points

Therefore, we have 9 candidate points that we place in the first column. The first thing is to check if they meet the constraints:

• $(8,5)$ Does it meet the condition $x+y\le 5$? As $8+5 \gt 5$, it does not.

• $(0,5)$ Does it meet the condition $x+2y\le 8$? As $0+2(5) \gt 8$, it does not.

• $(8,0)$ Does it meet the condition $x+y\le 5$? As $8+0 \gt 5$, it does not.

• $(4,1)$ Does it meet the condition $x+y\le 5$? Yes, $4+1= 5$. Does it meet the condition $x+2y\le 8$? Yes, $4+2(1)\lt 8$ Also, both values are positives.

• $(6,1)$ Does it meet the condition $x+y\le 5$? As $6+1 \gt 5$, it does not.

• $(2,3)$ Does it meet the condition $x+y\le 5$? Yes, $2+3= 5$ Does it meet the condition $x+2y\le 8$? Yes, $2+2(4)=8$ Also, both values are positives.

• $(0,4)$ Does it meet the condition $x+y\le 5$? Yes, $0+4\lt 5$ Does it meet the condition$x+2y\le 8$? Si, $0+2(4)=8$ Also, both values are positives.

• $(5,0)$ Does it meet the condition $x+y\le 5$? Yes, $5+0= 5$ Does it meet the condition $x+2y\le 8$? Yes, $5+2(0)\lt 8$ Also, both values are positives.

• $(0,0)$ Does it meet the condition $x+y\le 5$? Si, $0+0 \lt 5$ ¿Cumple $x+2y\le 8$? Si, $0+2(0)\lt 8$ Also, both values are zero.

Five points have passed the first filter. Now, we evaluate the function at these five points

$$ \begin{array}{|c|c|r|c|c|} \hline \mathrm{Point} & \mathrm{Within}\; \mathrm{domain?} & f(x,y) & \mathrm{Minimum}& \mathrm{Maximum}\\ \hline (8,5) & \mathrm{No} & & & \\ (0,5) & \mathrm{No} & & &\\ (8,0) & \mathrm{No} & & &\\ (4,1) & \mathrm{Yes} & -33 & \mathrm{Yes} & \\ (6,1) & \mathrm{No} & & &\\ (2,3) & \mathrm{Yes} & -25 & & \\ (0,4) & \mathrm{Yes} & 0 & &\\ (5,0) & \mathrm{Yes} & -31 & &\\ (0,0) & \mathrm{Yes} & 24 & &\mathrm{Yes}\\ \hline \end{array} $$

The smallest value is $-33$ and the minimum is (4,1). And the greatest value is $24$ and the maximum is (0,0).

Numerically: penalty function

We will search a minimum. To obtain a maximum change the sign an proceed similarly.

The idea of the penalty method is to replace the objective function $f$ by another function

$$F(x,y)=f(x,y)+c_1\,g_1(x,y)+c_2\,g_2(x,y)+c_3\,g_3(x,y)+c_4\,g_4(x,y)$$

and solve the problem without constraints. For this, we take $c_i$ as a positive constant and we must choose $g_i$, the penalty functions, in such a way that:

• $g_i$ is continuous in the domain of $f$.

• $g_i(x,y)\geq 0$ for every point in the domain of $f$, and

• $g_i(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) = f(x,y) + 50 g_1(x,y) + 50 g_2(x,y) + 50 g_3(x,y) + 50 g_4(x,y)$$

where

$$ g_1(x,y)=\begin{cases} 0 & \mathrm{if} & x+y\le 5\\ (x+y-5)^2 & \mathrm{if} & x+y\gt 5 \end{cases} \qquad g_2(x,y)=\begin{cases} 0 & \mathrm{if} & x+2y\le 8\\ (x+2y-8)^2 & \mathrm{if} & x+2y\gt 8 \end{cases} $$

and

$$ g_3(x,y)=\begin{cases} 0 & \mathrm{if} & x\ge 0\\ x^2 & \mathrm{if} & x\lt 0 \end{cases} \qquad g_4(x,y)=\begin{cases} 0 & \mathrm{if} & y\ge 0\\ y^2 & \mathrm{if} & y\lt 0 \end{cases} $$