Uge 6: Extremum and Optimization

Uge 6: Extremum and Optimization#

Key Terms#

  • Image/range of a continuous function

  • Extremum (minimum or maximum)

  • Global extremum

  • Local extremum

  • Stationary points and other conditions

  • Extremum determination

  • Second-order test and Hessian

  • Positive (semi-)definite matrices

Preparation and Syllabus#

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\). Compute the function value at all stationary points.

Question b. With SymPy#

Plot the level curves of the function and describe their form. You do not have to provide a precise mathematical description of these level curves.

Question c#

Determine a parametric representation \(\pmb{r}(t)\), \(t \in \mathbb{R}\), of 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 instance 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

Points on the graph of the composite function are of the form \((t,f(\pmb{r}(t)))\). With the parametrization from the previous hint it will be relevant to plot \(f(\pmb{r}(t))\) for \(t \in [0,2]\) or for another interval that contains \(t=1\), which corresponds to the point.

Question d#

Repeat question c with another straight line through a stationary point.

Hint

You can for example choose \(\pmb{r}(t) = (t x_0, t y_0)\). Which straight line does this parametrization represent?

Hint

It represents a straight line that passes through both the origin \((0,0)\) as well as the point \((x_0,y_0)\).

Question e#

We will on Short Day learn methods for determination of whether stationary points are maximum points, minimum points, or neither. Based on what you know about the function, e.g. from looking at the plot, we are today only asking you to give an educated guess on 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 of the functions had precisely one minimum but no maximum since they grew towards infinity. You may use this information without proof.

We will here use the functions (with their standard 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 look for the minimum point and the minimum value. This is a good method for some functions, for instance when the function has many (maybe infinitely many) points at which it is not differentiable. But for “nice” functions (such as functions that are infinitely many times differentiable - also known as smooth), like the three functions in the question, it is much easier to simply find the points at which the gradient is equal to the zero vector.

Find all stationary points and their corresponding minimum values for each of the three functions. State the image 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 all of \(\mathbb{R}^2\) and thus has no boundary points, and since the function is differentiable everywhere, any extremum points can only be found at the stationary points of the function.

Answer

The function has no stationary points. Hence, there are 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 can attain an extremum value.

Hint

Plot the function using dtuplot.plot3d(-abs(x)*((y-1)**2+1),(x,-2,4),(y,-2,4)).

Hint

The points where the function can take an extremum value are:

  1. bounday points of \(\mathrm{dom}(f)\) (which still must belong to \(\mathrm{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\) of 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. The function can thus only attain an extremum value at exceptional points where the function is not differentiable. This is along the line \(\{(0,y)| y \in \mathbb{R}\}\), which contains points that all are extremum points of the function.

Question b#

Find the global maximum and minimum values of the function.

Hint

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

Answer

From the hint we see that \(f(x,y)\le 0\) for all \((x,y)\). At the same time we see that \(f(x,1) = -|x|\) which attains all values in \(]-\infty,0]\). Hence, there is no minimum value. Along the line \(\{(0,y)| y \in \mathbb{R}\}\), the function attains the value \(0\). Hence, this is the maximum value. The range is \(\mathrm{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 of \(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\) one stationary point exists, that being \((\frac{2}{3},\frac{2}{3})\).

Question b#

Determine the global maximum and minimum values of \(f\) as well as the points at which these values are attained.

Hint

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

Hint

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

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

A boundary investigation is most easily carried out by considering the restriction of \(f\) to the relevant parts of the line segments \((x,0)\), \((0,y)\), \((x,1)\), and \((1,y)\).

Hint

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

Answer

Global maximum value = \(\frac{35}{27}\) which is attained at \((\frac{2}{3},\frac{2}{3})\). 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\), as well as at the point \((x,y)=(1,1)\).

Question c#

This exercise concerns a differentiable function of two variables defined on \([0,1]^2\). How would you solve this exercise if it was concerning a differentiable function of five variables defined on \([0,1]^5\)? Discuss a possible approach. You may include a chatbot such as https://copilot.microsoft.com/ in your discussion.

Hint

One first finds the stationary points in \(]0,1[^5\), the interior of \([0,1]^5\). Since the function is differentiable, there will be no exceptional points.

Hint

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

Hint

For each of the 10 different boundary hypersurfaces we now must consider the restriction of \(f\) to the boundary hypersurface, such as \((x_1,x_2,x_3,x_4,0)\) where \(x_i \in [0,1]\). Here \(f\) becomes a function of 4 variables, which we then must find extremum points of.

Hint

But this new function again has \(2 \cdot 4 = 8\) boundary hypersurfaces of dimension \(3\). And we now have \(10\) of these functions. The approach clearly quickly becomes immense and too much to do by hand (and in fact also for computes).

Note

A “hyper-cube” in \(\mathbb{R}^n\) has \(2 \, n\) edge faces (of dimension \(n-1\)) and \(2^n\) corner points. Note that this is not a universal property of “square domains” in higher dimensions. E.g., a “diamond/octahedron” in \(\mathbb{R}^n\) which is given by \(|x_1|+ |x_2| + \cdots + |x_n| \le 1\), conversely has \(2^ n\) edge faces and \(2 \, n\) corner points.

Question d#

Determine the range of \(f\).

Answer

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

Question e#

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

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 compute these values as well as the points at which they are attained.

Hint

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

Hint

The candidates for the largest and smallest values will now be found among the stationary points of the function and the local extrema on the boundary of \(A\).

Hint

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

Hint

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

Hint

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

Hint

The candidates for global maximum and minimum are constituted by \((0,0)\), the points that correspond to the solution to \(g'(t)=0\), and the value of \(g\) at the boundary curve’s end points (actually, there is only one end point - why?). Compute the function values of \(f\) at these points. The largest function value is the global maximum of the function on \(A\), and the smallest value is the global minimum of the function on \(A\).

Answer

Global minimum = \(-\frac{7}{2}\) is 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}\) is 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 of 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{b}^T \pmb{x} + c, \end{equation*}\]

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

It applies that \(q\) is a differentiable function with \(\nabla q(\pmb{x}) = (A + A^T) \pmb{x} + \pmb{b}\), according to this example. You do not have to show this (not until the final question, that is).

Question a#

Write out 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 correspond to \((A + A^T) \pmb{x} = - \pmb{b}\).

Hint

A system of linear equations has either zero, one, or infinitely many (stationary) solutions. Remember back to the topic of linear algebra in Mathematics 1a, where it was taught when and how these three situations appear.

Question b#

Assume that \(A + A^T\) is invertible. Argue that \(q\) has exactly one stationary point. Find the stationary point (you must find the formula or expression for the stationary point).

Answer

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

Question c#

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

Hint

If \(A\) is symmetric, then \(2A = (A + A^T)\). So, the equation system is \(2 A \pmb{x} = -\pmb{b}\), which has exactly one solution if and only if \(A\) is invertible, which in turn happens if and only if \(0\) is not an eigenvalue. Note that \(A = 1/2 \pmb{H}_q\), according to what the Hessian matrix tells about the stationary points.

Question d#

Derive the formula that we assumed to begin with: \(\nabla q(\pmb{x}) = (A + A^T) \pmb{x} + \pmb{b}\).

Hint

Begin by showing the proposition for \(n=1\).

8: A Challenge in Linear Algebra#

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

Hint

There are no hints for this exercise but you are welcome to discuss it on Ed.

Exercises – Short Day#

1: Application 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#

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

Hint

Extremum points, if any exist, can only be found at the stationary points of the function since the function is unbounded.

Hint

Determine the Hessian matrix and its eigenvalues. What influence does the eigenvalues have? Check for example Theorem 5.2.4, Second partial derivative test.

Answer

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

Question b#

What is the difference between an extremum and a strict extremum (also known as a proper extremum)? Is the found extremum a strict extremum?

Answer

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

2: Local extrema and Approximating Second-Degree Polynomial#

A function \(f:\mathbb{R}^2\rightarrow\mathbb{R}\) is given by 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 of \(f\) and determine for each of them whether it is a local maximum point or a local minimum point. If so, then state the corresponding local maximum/minimum value, and determine whether it is strict.

Hint

For \(A\) and \(B\) the job can be done using the eigenvalues of the Hessian Matrix at the points. \(C\) requires further investigation; one can for instance do a sign-check of \(f\) along the line \(x=0\).

Hint

In more words: What happens with \(f(0,y)=2y^3\) when passing through \(y=0\)? And what does that tell about the possibility for 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 second-degree polynomial for \(f\) with expansion point \(A\) can be written as an equation in the unknowns \(x,y\), and \(z\) in the form:

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

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

Hint

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*}\]

This surface is a so-called conic section. Find the equation, which is called a normal form of this particular conic section, here https://en.wikipedia.org/wiki/Quadric#Euclidean_space.

Hint

Have a look at the equations and figures in the table Non-degenerate real quadric surfaces on the linked webpage.

Answer

\(\lambda_1\) and \(\lambda_2\) are eigenvalues of the Hessian matrix \(\pmb{H}_f\). The equation describes an upwards-turned elliptic paraboloid with its vertex (stationary point) at \(T=(c_1,c_2,c_3)=(2,0,-4)\). Note: The two first coordinates of \(T\) are the same as \(A\), while the last coordinate is the minimum value of \(f\) at point \(A\).

Question c#

Draw 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 one, based on the eigenvalues of the Hessian matrix at the three points, can determine which type of conic section these second-degree polynomials describe.

3: A Return to Theme Exercise 1, yet again#

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

\[\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}\). The following information is given:

\[\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 \(\pmb{b} = - 2 A [1,2]^T\). The changes that we do here compared to the Theme Exercise are: 1) \(\lambda_1\) must be zero or negative, and 2) we use a new definition of \(\pmb{b}\).

Question a. By Hand#

Compute the eigenvalues of \(A\).

Hint

The matrix \(Q\) is (real) orthogonal.

Answer

From the spectral theorem we can simply 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 \neq 0\).

Hint

Matrix \(A\) is symmetric. And it is invertible when \(\lambda \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 are \(A\) and the Hessian matrix \(\pmb{H}_f\) related? Find the resultat in the book if you cannot remember. Describe the stationary points 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 here (refer to https://en.wikipedia.org/wiki/Quadric#Euclidean_space).

4: Global Extrema of 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|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 extremum at \(O\).

Answer

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

Question b#

Compute 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\) is attained at \((0,1,0)\) and \((0,-1,0)\). Global minimum = \(-1\) is attained on the circle \(\lbrace(x,y,z)|y=0\text{ and }x^2+z^2=1\rbrace\).

Question c#

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

5: Where is the Global Maximum? Minimum?#

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

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

Remember that \(\exp(x^2+y^2) = \mathrm{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 difficulties solving the equations, so we will have to give it a hand.

Hint

First, we notice that \(y=x=0\) is a solution. We must find out if there are more. Let us assume for instance that \(x \neq 0\). From the two equations we can conclude that \(y^2 = x^2\), meaning \(y = \pm x\). How? (Try isolating expressions in one equation and inserting them into the other. Remember that you may divide by \(x\), since it is not zero.)

Hint

Since \(\exp(x^2+y^2) \ge 0\), we can from \(y^2 = x^2\), meaning \(y = \pm x\), conclude that \(y=x\).

Hint

Insert \(y=x\) into the two equations and find the solution. This can be done in 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 is strict minimum at the points \(\left(\sqrt{\frac{1}{2} \ln{2}},\sqrt{\frac{1}{2} \ln{2}}\right) \) and \(\left(-\sqrt{\frac{1}{2} \ln{2}},-\sqrt{\frac{1}{2} \ln{2}}\right)\) with the minimum value \(2-2 \ln 2\).

Question c#

Determine whether the function \(f\) has a global maximum or minimum, and compute the values of these if they exist.

Answer

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

Question d#

State the range of the function.

Answer

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

Contents