Week 6: Extrema and Optimization

Week 6: Extrema and Optimization#

Exercises – Long Day#

1: Stationary Points and Extremum Values#

A function \(f: \mathbb{R}^2 \to \mathbb{R}\) is given by

\[\begin{equation*} f(x,y)=xy(2-x-y)+1. \end{equation*}\]

Question a. By Hand#

Find all stationary points of \(f\). Calculate the function value at all stationary points.

Question b. SymPy#

Plot the level curves of the function and describe their shape. You do not need to provide a precise mathematical description of the level curves.

Question c#

Find a parametric representation \(\pmb{r}(t)\), \(t \in \mathbb{R}\), for a straight line through one of the stationary points. Plot the graph of the composite function \(f \circ \pmb{r}\).

Hint

The straight line can, for example, follow one of the coordinate axes. Let \((x_0, y_0)\) be the stationary point. Then we can use \(\pmb{r}(t) = (x_0, t y_0)\).

Hint

The points on the graph are of the form \((t, f(\pmb{r}(t)))\). With the parameterization from the previous hint, it would be relevant to plot \(f(\pmb{r}(t))\) for \(t \in [0,2]\) or another interval that includes \(t = 1\), which corresponds to the point.

Question d#

Repeat Question c but choose a different straight line through one of the stationary points.

Hint

For example, you can choose \(\pmb{r}(t) = (t x_0, t y_0)\). Which line does this parameterization correspond to?

Hint

The straight line from the previous hint is a line that passes through both the origin \((0,0)\) and the point \((x_0, y_0)\).

Question e#

On Short Day, we will study methods to determine whether stationary points are maximum points, minimum points, or neither. Based on what you know about the function, for example from your plots, you should make a qualified guess as to whether the found stationary points are maximum points, minimum points, or neither.

2: A Return to Theme Exercise 1#

In Theme 1: The Gradient Method, we considered three functions of the form \(f_i: \mathbb{R}^2 \to \mathbb{R}\). All the functions had exactly one minimum but no maximum as they grew towards infinity. You may use this information without proof.

Here, we use the functions (with their default values) given in Python by:

# Variables and parameters that are involved in the functions
x1, x2 = symbols('x1 x2', real=True)
a, lambda1 = symbols('a lambda1',  positive=True)

def f1(x1, x2, a = S(1/2)):
    return a * x1**2 + 1 * x2**2

def f2(x1, x2, lambda1 = 0.5):
    Q = 1/sqrt(2) * Matrix([[1,1],[1,-1]])
    A = Q.T * Matrix([[lambda1,0],[0,1]]) * Q
    b = Matrix([-2,4])
    x = Matrix([x1,x2])
    q = x.T * A * x + x.T * b
    return q[0] 

def f3(x1, x2):
    return (1 - x1)**2 + 100*(x2 - x1**2)**2

In the theme exercise, we used the gradient method to search for the minimum point and minimum value. This is a good method, for example, when the function has many (possibly infinitely many) points where it is not differentiable. However, for well-behaved functions (such as functions that are infinitely differentiable, so-called smooth functions), like the three considered functions, it is much easier to simply find the points where the gradient is equal to the zero vector.

Find all stationary points and the corresponding minimum value for each of the three functions. Even though the functions are given in Python, you are welcome to solve this task by hand – that will not take longer.

State the image set of each function.

3: Extremum or not. By Hand#

Let \(f: \mathbb{R}^2 \to \mathbb{R}\) be given by

\[\begin{equation*} f(x,y)=x^2 y + y. \end{equation*}\]

Determine all local extrema of \(f\).

Hint

Since the function is defined on the entire \(\mathbb{R}^2\) without any boundary points, and since the function is differentiable everywhere, any possible extrema can only be found at the stationary points of the function.

Answer

The function has no stationary points. Hence, it has no extrema.

4: A Function that is not Differentiable Everywhere#

Let \(f: \mathbb{R}^2 \to \mathbb{R}\) be given by

\[\begin{equation*} f(x,y)=-|x| ((y-1)^2+1). \end{equation*}\]

Question a#

Find all points where the function could have an extremum value.

Hint

It might be a good idea to inspect the graph of the function using dtuplot.plot3d(-abs(x)*((y-1)**2+1),(x,-2,4),(y,-2,4)).

Hint

The points where the function could have an extremum value are:

  1. boundary points of \(\operatorname{dom}(f)\) (which simultaneously belong to \(\operatorname{dom}(f)\))

  2. exceptional points where the function is not differentiable

  3. stationary points

Hint

The function is not differentiable along the line \(x = 0\) for the same reason that \(x \mapsto |x|\) is not differentiable at \(x = 0\).

Answer

The function is differentiable on \((\mathbb{R} \setminus \{0\}) \times \mathbb{R}\) and has no stationary points. Therefore, the function can only take an extremum value at exceptional points where the function is not differentiable. These points are found on the line \(\{(0, y) | y \in \mathbb{R} \}\), which are all extremum points for the function.

Question b#

Find the global maximum and minimum value of the function.

Hint

Both of the terms \(|x|\) and \(((y-1)^2+1)\) are non-negative.

Answer

From the hint, we have that \(f(x, y) \le 0\) for all \((x, y)\). We also see that \(f(x, 1) = -|x|\), which takes all values in \(]-\infty, 0]\). Therefore, there is no minimum value. Along the line \(\{(0, y) | y \in \mathbb{R} \}\), the function takes the value \(0\). This is the maximum value. The range is \(\operatorname{im}(f) = ]-\infty, 0]\).

5: Global Maximum and Global Minimum#

Let \(f: A \to \mathbb{R}\) be given by:

\[\begin{equation*} f(x,y)=xy(2-x-y)+1, \end{equation*}\]

where \(A \subset \mathbb{R}^2\) denotes the region in the \((x,y)\) plane where \(x\in\left[ 0,1\right]\) and \(y\in\left[ 0,1\right]\). Note that the functional expression for \(f\) is the same as in 1: Stationary Points and Extremum Values.

Question a#

Find by hand all stationary points of \(f\) in the interior of \(A\).

Answer

In the interior of \(A\), there is one stationary point, namely \(\left( \frac{2}{3}, \frac{2}{3} \right)\).

Question b#

Determine the global maximum value and the global minimum value for \(f\) as well as the points where these values are attained.

Hint

Can we even be sure that \(f\) has a global maximum and global minimum?

Hint

Yes, because the function is continuous and \(A\) is bounded and closed. Find this statement in the book.

Hint

The global extrema are found:

  1. on the boundary of \(A\) (but within \(A\)),

  2. at exceptional points where the function is not differentiable, or

  3. at the stationary points of the function.

Hint

The boundary investigation is easiest if we consider the restriction of \(f\) to the relevant parts of the line segments \((x, 0)\), \((0, y)\), \((x, 1)\), and \((1, y)\). (By “relevant,” we mean here that we only need to consider \(x\) and \(y\) between \(0\) and \(1\), as we otherwise no longer would be on the boundary of \(A\).)

Hint

Once you have found the stationary points and local extrema along the restrictions, you should calculate the function values at all these points as well as at the endpoints of the line segments: \((0,0)\), \((1,0)\), \((0,1)\), and \((1,1)\). The largest of these function values is the global maximum of \(f\) and the smallest is the global minimum.

Answer

Global maximum value = \(\frac{35}{27}\), which is attained at \(\left( \frac{2}{3}, \frac{2}{3} \right)\).
Global minimum value = 1, which is attained on the entire line segment \((x, 0)\) for \(0 \leq x \leq 1\), on the entire line segment \((0, y)\) for \(0 \leq y \leq 1\), and at the point \((x, y) = (1, 1)\).

Question c#

This exercise is about a differentiable function of two variables defined on \([0, 1]^2\). How would you approach the problem if it was about a differentiable function of five variables defined on \([0, 1]^5\)? Discuss a possible approach. You can include a good AI chatbot, such as https://chatgpt.com/ or https://copilot.microsoft.com/, in the discussion.

Hint

First, find stationary points in \(]0,1[^5\), the interior of \([0,1]^5\). Since the function is differentiable, there are no exceptional points.

Hint

The boundary consists of points \((x_1, x_2, \dots, x_5)\) where one of the coordinates is 0 or 1. Therefore, the boundary consists of \(2 \cdot 5 = 10\) different 4-dimensional “surfaces”; we call them hypersurfaces.

Hint

For each of the 10 different boundary hypersurfaces, we now consider the restriction of \(f\) to the boundary hypersurface, for example, \((x_1, x_2, x_3, x_4, 0)\) where \(x_i \in [0, 1]\). Here, \(f\) becomes a function of 4 variables, for which we again need to find extrema.

Hint

But this new function has \(2 \cdot 3 = 6\) boundary hypersurfaces of dimension 3, and we have 10 of these functions. The procedure quickly becomes unmanageable by hand (and actually also for computers).

Note

A “cube” in \(\mathbb{R}^n\), called a hypercube, has \(2n\) boundary hypersurfaces and \(2^n\) corner points. Note that this is not a universal rule for “rectangular domains” in higher dimensions. For example, a “diamond/octahedron” in \(\mathbb{R}^n\), called a cross-polytope, given by \(|x_1| + |x_2| + \cdots + |x_n| \leq 1\), has \(2^n\) boundary hypersurfaces and \(2n\) corner points.

Question d#

Determine the image set of \(f\).

Answer

Since \(A\) is connected, we conclude that the image set is \(\operatorname{im}(f) = [f_\text{min},f_\text{max}] = [1,35/27]\).

Question e#

Plot the graph of \(f\) along with points that show where on the graph the largest and smallest values are attained. Do a visual check that your results look reasonable.

6: Global Maximum and Global Minimum again#

Consider the function \(f:\mathbb{R}^2\rightarrow\mathbb{R}\) given by

\[\begin{equation*} f(x,y)=x^2-3y^2-3xy \end{equation*}\]

as well as the set \(A=\lbrace(x,y) \in \mathbb{R}^2 \,| \, x^2+y^2\leq 1\rbrace\).

Justify that \(f\) has both a global maximum and a global minimum on \(A\), and determine these values as well as the points where they are attained.

Hint

The function is continuous, and \(A\) is bounded and closed.

Hint

The candidates for the largest and smallest values are the stationary points of the function, as well as the local extrema on the boundary of \(A\).

Hint

The only stationary point for \(f\) in the domain is \((0,0)\). Next, we need to examine the restriction of \(f\) to the boundary of \(A\).

Hint

The boundary of \(A\) can be parameterized as \((x,y) = (\cos(t), \sin(t))\) where \(t \in [0, 2\pi]\).

Hint

The restriction of \(f\) to the boundary of \(A\) is then \(g(t) = f(\cos(t), \sin(t))\) where \(t \in [0, 2\pi]\). Plot the graph of \(g'(t)\) and find out where it is zero.

Hint

The candidates for the global maximum and minimum are \((0,0)\), the points corresponding to the solution to \(g'(t) = 0\), and the value of \(g\) at the endpoints of the boundary curve (in fact, there is only one endpoint, why?). Calculate the function values of \(f\) at these points. The largest function value is the global maximum of \(f\) on \(A\), and the smallest value is the global minimum of \(f\) on \(A\).

Answer

Global minimum = \(-\frac{7}{2}\) attained at \(\left( \frac{\sqrt{10}}{10}, \frac{3\sqrt{10}}{10} \right)\) and \(\left( -\frac{\sqrt{10}}{10}, -\frac{3\sqrt{10}}{10} \right)\).

Global maximum = \(\frac{3}{2}\) attained at \(\left( \frac{3\sqrt{10}}{10}, \frac{-\sqrt{10}}{10} \right)\) and \(\left( \frac{-3\sqrt{10}}{10}, \frac{\sqrt{10}}{10} \right)\).

7: Stationary Points for Quadratic Forms#

Let \(q : \mathbb{R}^n \to \mathbb{R}\) be a quadratic form. In other words, \(q\) has the functional expression

\[\begin{equation*} q(\pmb{x}) = \pmb{x}^T A \pmb{x} + \pmb{x}^T \pmb{b} + c, \end{equation*}\]

where \(A\) is an \(n \times n\) matrix (which is not the zero matrix), \(\pmb{b} \in \mathbb{R}^n\) is a column vector and \(c \in \mathbb{R}\).

It holds that \(q\) is a differentiable function with \(\nabla q(\pmb{x}) = (A + A^T) \pmb{x} + \pmb{b}\) according to this example. This does not need to be shown (until the last exercise).

Question a#

Write a system of equations whose solution describes the stationary points. Argue that \(q\) can have either zero, one, or infinitely many stationary points.

Answer

The stationary points are given by: \(\nabla q(\pmb{x}) = (A + A^T) \pmb{x} + \pmb{b} = \pmb{0}\), which corresponds to \((A + A^T) \pmb{x} = -\pmb{b}\).

Hint

The linear system of equations has either zero, one, or infinitely many stationary solutions. Recall from linear algebra in Mathematics 1a when each of these three situations occurs.

Question b#

Assume that \((A + A^T)\) is invertible. Argue that \(q\) has exactly one stationary point. Find the stationary point (i.e., derive a formula or expression for the stationary point).

Answer

\(\pmb{x} = - (A + A^T)^{-1} \pmb{b}\).

Question c#

Assume \(A\) is symmetric. Argue that \(q\) has exactly one stationary point if and only if \(\lambda = 0\) is not an eigenvalue of \(A\).

Hint

If \(A\) is symmetric, then \(2A = (A + A^T)\). Therefore, the system of equations is \(2A \pmb{x} = -\pmb{b}\), which has exactly one solution if and only if \(A\) is invertible, which occurs if and only if \(\lambda = 0\) is not an eigenvalue. Note that \(A = \frac{1}{2} \pmb{H}_q\), according to what the Hessian matrix says about stationary points.

Question d (Optional)#

Derive the formula we started out by assuming: \(\nabla q(\pmb{x}) = (A + A^T) \pmb{x} + \pmb{b}\)

Hint

Start by showing the statement for \(n = 1\). Then see Example 3.6 in the additional notes.

8: A Challenge in Linear Algebra#

Let \(A\) be an \(n \times n\) matrix. Does it hold that the symmetric matrix \((A + A^T)\) is invertible, if \(A\) is invertible? Proof it or provide a counterexample!

Hint

We provide no hints for this exercise, but you are welcome to discuss it on Ed.

Exercises – Short Day#

1: Usage of Hessian Matrix. By Hand.#

Consider the function \(f:\mathbb{R}^2\rightarrow\mathbb{R}\) given by

\[\begin{equation*} f(x,y)=x^2+4y^2-2x-4y. \end{equation*}\]

Question a#

Argue that the function \(f\) has exactly one extremum. Determine this extremum point and the corresponding extremum value.

Hint

Any potential extremum points can only be found at the function’s stationary points.

Hint

Determine the Hessian matrix and its eigenvalues. What significance do the eigenvalues have? Check Theorem 5.2.4, Second partial derivative test.

Answer

The function has one stationary point, namely \((x, y) = (1, \frac{1}{2})\). The Hessian matrix is constant and has positive eigenvalues everywhere (and therefore also at this point), so there is a local minimum at this point. The minimum value is \(f(1, \frac{1}{2}) = -2\).

Question b#

What is the difference between an extremum and a strict extremum, also sometimes called a proper extremum? Is the extremum we found a strict extremum?

Answer

The answer to the last part of the question is yes. See Theorem 5.2.4, Second partial derivative test.

2: Local Extrema and Approximating Second-Degree Polynomial#

Given function \(f:\mathbb{R}^2\rightarrow\mathbb{R}\) with the expression

\[\begin{equation*} f(x,y)=x^3+2y^3+3xy^2-3x^2. \end{equation*}\]

Question a#

Show that the points \(A = (2, 0)\), \(B = (1, -1)\), and \(C = (0, 0)\) are stationary points for \(f\), and determine for each of them whether there is a local maximum or a local minimum (or neither) there. If so, indicate the local maximum/minimum value attained at the point, and determine if it is strict.

Hint

For \(A\) and \(B\), the question can be answered using the eigenvalues of the Hessian matrix at the points. \(C\) requires further investigation; for example, a sign analysis of \(f\) along the line \(x = 0\).

Hint

More specifically: What happens with \(f(0, y) = 2y^3\) when passing \(y = 0\)? What does this indicate about the possibility of an extremum?

Answer

There is a strict minimum at point \(A\) with the minimum value \(f(2, 0) = -4\). There is no extremum at \(B\) and \(C\).

Question b#

Show that the approximating quadratic polynomial for \(f\) with the expansion point \(A\) can be written as an equation in the unknowns \(x\), \(y\), and \(z\) in the following form:

\[\begin{equation*} z-c_3=\frac 12\lambda_1(x-c_1)^2+\frac 12\lambda_2(y-c_2)^2. \end{equation*}\]

What surface does this equation describe, and what do the constants represent?

Hint

Now, bring the equation to the form

\[\begin{equation*} z-c_3=\frac{(x-c_1)^2}{a^2}+\frac{(y-c_2)^2}{b^2}. \end{equation*}\]

The surface is called a quadric surface (this is conic section on higher-dimensional “cones”, producing a surface rather than a curve). Find the standard equation (also called a normal form) here: https://en.wikipedia.org/wiki/Quadric#Euclidean_space.

Hint

Consider the equations and figures in the table titled Non-degenerate real quadric surfaces.

Answer

\(\lambda_1\) and \(\lambda_2\) are eigenvalues of the Hessian matrix \(\pmb{H}_f\). The equation describes an upward-facing elliptical paraboloid with the vertex at \(T = (c_1, c_2, c_3) = (2, 0, -4)\). Note: The first two coordinates of \(T\) constistute \(A\), while the last one is the minimum value of \(f\) at point \(A\).

Question c#

Plot the graph of \(f\) along with the graph of the approximating second-degree polynomials for \(f\) with the expansion points \(A\), \(B\), and \(C\). Discuss whether the eigenvalues of the Hessian matrices at the three points can determine the type of quadric surface described by the second-degree polynomials.

3: A Return to Theme Exercise 1 once more#

We consider the quadratic form \(f_2: \mathbb{R}^2 \to \mathbb{R}\) from Theme 1: The Gradient Method. It is given by \(q: \mathbb{R}^2 \to \mathbb{R}\)

\[\begin{equation*} q(\pmb{x}) = \pmb{x}^T A \pmb{x} + \pmb{b}^T \pmb{x}, \end{equation*}\]

where \(A\) is a \(2 \times 2\) matrix that depends on \(\lambda_1 \in \mathbb{R}\),

\[\begin{equation*} A = Q^T \Lambda Q, \quad Q = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}, \quad \Lambda = \begin{bmatrix} \lambda_1 & 0 \\ 0 & 1 \end{bmatrix}, \end{equation*}\]

and where \(\pmb{b} = - 2 A [1,2]^T\). We will change the following from the Theme exercise: 1) \(\lambda_1\) may be zero or negative, and 2) we use a new definition of \(\pmb{b}\).

Question a. By Hand#

Find the eigenvalues of \(A\).

Hint

The matrix \(Q\) is real orthogonal.

Answer

Due to the spectral theorem we easily read the eigenvalues from the diagonal of \(\Lambda\) to be \(\lambda_1\) and 1.

Question b. By Hand#

Find all stationary points of \(q\) when \(\lambda_1 \neq 0\).

Hint

The matrix \(A\) is symmetric. Also, it is invertible when \(\lambda_1 \neq 0\). Remember the formula for the gradient of a quadratic form. You do not need to do any calculations.

Answer

The gradient at \(\pmb{x}\) is \(2 A \pmb{x} + \pmb{b}\). So, the stationary point is \(-(1/2) A^{-1} \pmb{b}\), which with the definition \(\pmb{b} = - 2 A [1,2]^T\) becomes

\[\begin{equation*} -(1/2) A^{-1} \pmb{b} = -(1/2) A^{-1} (- 2 A) [1,2]^T = [1,2]^T. \end{equation*}\]

Question c#

How is \(A\) and the Hessian matrix \(\pmb{H}_f\) related? Find the result in the book if you cannot remember. Describe the stationary point for each of the three cases \(\lambda_1 > 0\), \(\lambda_1 = 0\) and \(\lambda_1 < 0\).

Question d#

How is \(q\) and the approximating second-degree polynomial (with an arbitrary expansion point) related? Plot \(q\) for each of the three cases \(\lambda_1 > 0\), \(\lambda_1 = 0\) and \(\lambda_1 < 0\). Which normal forms are we dealing with (see https://en.wikipedia.org/wiki/Quadric#Euclidean_space)?

4: Global Extrema for Function of Three Variables#

We consider the function \(f:\mathbb{R}^3\rightarrow \mathbb{R}\) given by

\[\begin{equation*} f(x,y,z)=\sin(x^2+y^2+z^2-1)-x^2+y^2-z^2 \end{equation*}\]

as well as the solid unit sphere

\[\begin{equation*} \mathcal{K}=\left\{(x,y,z)\in \mathbb{R}^3 \mid x^2+y^2+z^2\leq 1\right\}. \end{equation*}\]

Question a#

Show that \(f\) in the interior of \(\mathcal{K}\) only has one stationary point, that being \(O=(0,0,0)\), and investigate whether \(f\) has an extremum at \(O\).

Answer

The Hessian matrix shows that there is not extremum at \((0,0,0)\).

Question b#

Determine the global maximum value and the global minimum value of \(f\) on \(\mathcal{K}\) as well as the points where these values are attained.

Answer

Global maximum \(= 1\) and is attained at \((0,1,0)\) and \((0,-1,0)\). Global minimum \(= -1\) and is attained on the circle \(\lbrace(x,y,z) \mid y=0 \text{ and } x^2+z^2=1\rbrace\).

Question c#

Determine the image set of \(f\) on \(\mathcal{K}\).

5: Where are the Global Extrema?#

Given function \(f:\mathbb{R}^2\rightarrow\mathbb{R}\) with the expression

\[\begin{equation*} f(x,y)=\exp(x^2+y^2)-4xy. \end{equation*}\]

Keep in mind that \(\exp(x^2+y^2) = \operatorname{e}^{x^2+y^2}\).

Question a#

Find all stationary points of \(f\).

Hint

Set up the two equations for the stationary points. SymPy has trouble solving the equations, so we will need to help it along.

Hint

We first notice that \(x = y = 0\) is a solution. We need to check if there are any others. Let’s assume, for example, that \(x \neq 0\). From the two equations, we can conclude that \(y^2 = x^2\), i.e., \(y = \pm x\). How? (Try isolating an expression in one equation and substituting it into the other. Remember that you can divide by \(x\) since it’s never zero.)

Hint

Since \(\exp(x^2 + y^2) \ge 0\), then we can actually conclude based on \(y^2 = x^2\), i.e., \(y = \pm x\) that \(y = x\).

Hint

Substitute \(y = x\) into the two equations and find the solution. This can be done using SymPy or by hand.

Answer

The three stationary points are

\[\begin{equation*} (0,0) , \; \Big(\sqrt{\frac{1}{2} \ln{2}},\sqrt{\frac{1}{2} \ln{2}}\Big) , \; \Big(-\sqrt{\frac{1}{2} \ln{2}},-\sqrt{\frac{1}{2} \ln{2}}\Big) \end{equation*}\]

Question b#

Find all local extrema.

Answer

There are strict minima at the points \((\sqrt{\frac{1}{2} \ln{2}},\sqrt{\frac{1}{2} \ln{2}}) \) and \( (-\sqrt{\frac{1}{2} \ln{2}},-\sqrt{\frac{1}{2} \ln{2}})\) with the minimum value \(2-2 \ln 2\).

Question c#

Determine whether the function \(f\) has a global maximum or minimum. If so, state the values of them.

Answer

There is no global maximum. Global minimum is attained at the points \((\sqrt{\frac{1}{2} \ln{2}},\sqrt{\frac{1}{2} \ln{2}})\) and \((-\sqrt{\frac{1}{2} \ln{2}},-\sqrt{\frac{1}{2} \ln{2}})\) with the value \(2-2 \ln 2\).

Question d#

State the range of the function.

Answer

\(\operatorname{im}(f)=[2-2 \ln 2,\infty[\).

Contents