Introduction to maths optimisation¶

If your browser cannot display the notebook, try this link : https://gist.github.com/bdallard/e9f3eaa70a6026796813c3456bb61164

Exercise 1: Function Plotting and Analytical Determination of Critical Points¶

Determine analytically the coordinates and nature of the critical points of the following functions:

• $$f_1(x,y) = x^3 + y^3 -3x -12y$$
• $$f_2(x,y) = x^3 -12xy + 8y^3$$
• $$f_3(x,y) = {(x-1)}^2 + 10 {(x^2-y)}^2$$

Vocabulary: An "analytical" determination means that the calculation is done "by hand", without using numerical tools or formal computation.

In [ ]:

# Import numpy and pyplot libraries
import numpy as np
import math 
import matplotlib.pyplot as plt

# Import numpy and pyplot libraries import numpy as np import math import matplotlib.pyplot as plt

In [ ]:

def f1(x,y) :
    pass
def f2(x,y) :
    pass
def f3(x,y) :
    pass

def f1(x,y) : pass def f2(x,y) : pass def f3(x,y) : pass

Exercise 2: Plotting Function Graphs¶

2.1 The instruction blocks below allow you to plot the graph of the function $f_1(x,y)$ for $x \in [-4,4]$ and different fixed values of y.

Execute the different instruction blocks, then analyze what each line does.

Subsequently, you will rely on this example to plot function graphs.

In [ ]:

# Definition of the plotting domain
xmin, xmax, nx = -4, 4, 41
ymin, ymax, ny = -4, 4, 41
# Discretization of the plotting domain
x1d = np.linspace(xmin,xmax,nx)
y1d = np.linspace(ymin,ymax,ny)
x2d, y2d = np.meshgrid(x1d, y1d)

# Plot contour lines (isovalues) of f1
nIso = 21
plt.contour(x2d,y2d,f2(x2d,y2d),nIso)
plt.title('Contour Lines')
plt.xlabel('x values')
plt.ylabel('y values')
plt.grid()
plt.axis('square')

# Definition of the plotting domain xmin, xmax, nx = -4, 4, 41 ymin, ymax, ny = -4, 4, 41 # Discretization of the plotting domain x1d = np.linspace(xmin,xmax,nx) y1d = np.linspace(ymin,ymax,ny) x2d, y2d = np.meshgrid(x1d, y1d) # Plot contour lines (isovalues) of f1 nIso = 21 plt.contour(x2d,y2d,f2(x2d,y2d),nIso) plt.title('Contour Lines') plt.xlabel('x values') plt.ylabel('y values') plt.grid() plt.axis('square')

Out[ ]:

(-4.0, 4.0, -4.0, 4.0)

In [ ]:

# Definition of the plotting domain
xmin, xmax, nx = -4, 4, 41
ymin, ymax, ny = -4, 4, 41
# Discretization of the plotting domain
x1d = np.linspace(xmin,xmax,nx)
y1d = np.linspace(ymin,ymax,ny)
x2d, y2d = np.meshgrid(x1d, y1d)

# Plot contour lines (isovalues) of f1
nIso = 21
plt.contour(x2d,y2d,f3(x2d,y2d),nIso)
plt.title('Contour Lines')
plt.xlabel('x values')
plt.ylabel('y values')
plt.grid()
plt.axis('square')

# Definition of the plotting domain xmin, xmax, nx = -4, 4, 41 ymin, ymax, ny = -4, 4, 41 # Discretization of the plotting domain x1d = np.linspace(xmin,xmax,nx) y1d = np.linspace(ymin,ymax,ny) x2d, y2d = np.meshgrid(x1d, y1d) # Plot contour lines (isovalues) of f1 nIso = 21 plt.contour(x2d,y2d,f3(x2d,y2d),nIso) plt.title('Contour Lines') plt.xlabel('x values') plt.ylabel('y values') plt.grid() plt.axis('square')

Out[ ]:

(-4.0, 4.0, -4.0, 4.0)

In [ ]:

# Create array of x samples
xmin, xmax, nx = -4, 4, 41
tab_x = np.linspace(xmin,xmax,nx)
# Calculate values of f(x,y) for x values in tab_x and different y values
tab_zm2 = f1(tab_x,-2)
tab_z0 = f1(tab_x,0)
tab_zp2 = f1(tab_x,2)
# Plot the graph
plt.plot(tab_x, tab_zm2,'k-',label='y = -2')
plt.plot(tab_x, tab_z0,'r-',label='y = 0')
plt.plot(tab_x, tab_zp2,'b-',label='y = +2')
plt.xlabel('x values')
plt.ylabel('f1(x,y=constant) values')
plt.legend()
plt.grid()

# Create array of x samples xmin, xmax, nx = -4, 4, 41 tab_x = np.linspace(xmin,xmax,nx) # Calculate values of f(x,y) for x values in tab_x and different y values tab_zm2 = f1(tab_x,-2) tab_z0 = f1(tab_x,0) tab_zp2 = f1(tab_x,2) # Plot the graph plt.plot(tab_x, tab_zm2,'k-',label='y = -2') plt.plot(tab_x, tab_z0,'r-',label='y = 0') plt.plot(tab_x, tab_zp2,'b-',label='y = +2') plt.xlabel('x values') plt.ylabel('f1(x,y=constant) values') plt.legend() plt.grid()

2.2 Plot the graph of the function $f_1(x,y)$ for $y \in [-4,4]$ and different fixed values of x.

In [ ]:

# Create array of y samples
ymin, ymax, ny = -4, 4, 41
tab_y = np.linspace(ymin,ymax,ny)
# Calculate values of f(x,y) for y values in tab_y and different x values
tab_zm2 = f1(-2,tab_y)
tab_z0 = f1(0,tab_y)
tab_zp2 = f1(2,tab_y)
# Plot the graph
plt.plot(tab_y, tab_zm2,'k-',label='x = -2')
plt.plot(tab_y, tab_z0,'r-',label='x = 0')
plt.plot(tab_y, tab_zp2,'b-',label='x = +2')
plt.xlabel('y values')
plt.ylabel('f1(x=constant,y) values')
plt.legend()
plt.grid()

# Create array of y samples ymin, ymax, ny = -4, 4, 41 tab_y = np.linspace(ymin,ymax,ny) # Calculate values of f(x,y) for y values in tab_y and different x values tab_zm2 = f1(-2,tab_y) tab_z0 = f1(0,tab_y) tab_zp2 = f1(2,tab_y) # Plot the graph plt.plot(tab_y, tab_zm2,'k-',label='x = -2') plt.plot(tab_y, tab_z0,'r-',label='x = 0') plt.plot(tab_y, tab_zp2,'b-',label='x = +2') plt.xlabel('y values') plt.ylabel('f1(x=constant,y) values') plt.legend() plt.grid()

2.3 Plot the graph of the function $f_1(x,\alpha .x)$ for $x \in [-3,3]$ and $\alpha \in \{ 1/\sqrt3, 1, \sqrt3 \}$. What do these graphs represent?

In [ ]:

# Create array of x samples
xmin, xmax, nx = -4, 4, 41
tab_x = np.linspace(xmin,xmax,nx)
# Calculate values of f(x,y) for x values in tab_x and different y values
tab_zm2 = f1(tab_x,tab_x*(1/math.sqrt(3)))
tab_z0 = f1(tab_x,tab_x)
tab_zp2 = f1(tab_x,tab_x*math.sqrt(3))
# Plot the graph
plt.plot(tab_x, tab_zm2,'k-',label='alpha =1/√3')
plt.plot(tab_x, tab_z0,'r-',label='alpha =1')
plt.plot(tab_x, tab_zp2,'b-',label='alpha = √3')
plt.xlabel('x values')
plt.ylabel('f1(x,y) values')
plt.legend()
plt.grid()

# Create array of x samples xmin, xmax, nx = -4, 4, 41 tab_x = np.linspace(xmin,xmax,nx) # Calculate values of f(x,y) for x values in tab_x and different y values tab_zm2 = f1(tab_x,tab_x*(1/math.sqrt(3))) tab_z0 = f1(tab_x,tab_x) tab_zp2 = f1(tab_x,tab_x*math.sqrt(3)) # Plot the graph plt.plot(tab_x, tab_zm2,'k-',label='alpha =1/√3') plt.plot(tab_x, tab_z0,'r-',label='alpha =1') plt.plot(tab_x, tab_zp2,'b-',label='alpha = √3') plt.xlabel('x values') plt.ylabel('f1(x,y) values') plt.legend() plt.grid()

Exercise 3: Plotting Contour Lines (Isovalues) of a Function of Two Variables¶

3.1 The instruction block below allows you to plot the contour lines (isovalues) of the function $f_1(x,y)$ for $x \in [-4,4]$ and $y \in [-4,4]$.

Execute the instruction block, then analyze what each line does.

Vary the different plotting parameters (intervals of x and y, number of discretization points, number of contour lines) and analyze their influence. In particular, what happens if the domain discretization is insufficient?

Subsequently, you will rely on this example to plot function contour lines.

In [ ]:

# Definition of the plotting domain
xmin, xmax, nx = -4, 4, 41
ymin, ymax, ny = -4, 4, 41
# Discretization of the plotting domain
x1d = np.linspace(xmin,xmax,nx)
y1d = np.linspace(ymin,ymax,ny)
x2d, y2d = np.meshgrid(x1d, y1d)

# Plot contour lines (isovalues) of f1
nIso = 21
plt.contour(x2d,y2d,f1(x2d,y2d),nIso)
plt.title('Contour Lines')
plt.xlabel('x values')
plt.ylabel('y values')
plt.grid()
plt.axis('square')

# Definition of the plotting domain xmin, xmax, nx = -4, 4, 41 ymin, ymax, ny = -4, 4, 41 # Discretization of the plotting domain x1d = np.linspace(xmin,xmax,nx) y1d = np.linspace(ymin,ymax,ny) x2d, y2d = np.meshgrid(x1d, y1d) # Plot contour lines (isovalues) of f1 nIso = 21 plt.contour(x2d,y2d,f1(x2d,y2d),nIso) plt.title('Contour Lines') plt.xlabel('x values') plt.ylabel('y values') plt.grid() plt.axis('square')

Out[ ]:

(-4.0, 4.0, -4.0, 4.0)

3.2 On the contour line representation of $f_1$, locate the critical points calculated in exercise 1. It will likely be necessary to adjust the contour plot parameters.

3.3 The instruction block below provides the template for the function df1, which calculates and returns the gradient of $f_1$. Complete this instruction block so that df1 does what is expected. Then use this function to verify that the gradient of $f_1$ is indeed zero at the critical points.

In [ ]:

def df1 (x,y) :
# Partial derivative with respect to x
# Partial derivative with respect to y 
    return [df_dx,df_dy]

def df1 (x,y) : # Partial derivative with respect to x # Partial derivative with respect to y return [df_dx,df_dy]

In [ ]:

# To be completed to calculate the gradient of f1 at the critical points you previously calculated
df1(,)

# To be completed to calculate the gradient of f1 at the critical points you previously calculated df1(,)

Out[ ]:

[0, 0]

3.4 The instruction block below provides the template for the function d2f1, which calculates and returns the Hessian matrix of $f_1$. Complete this instruction block so that d2f1 does what is expected. Then use this function to verify the nature of the critical points of $f_1$.

In [ ]:

# Instruction block to be completed
def d2f1 (x,y) :
    # Second-order partial derivatives
    return [[d2f_dxdx,d2f_dxdy],[d2f_dydx,d2f_dydy]]

# Instruction block to be completed def d2f1 (x,y) : # Second-order partial derivatives return [[d2f_dxdx,d2f_dxdy],[d2f_dydx,d2f_dydy]]

In [ ]:

# Template for calculating eigenvalues of a matrix, to be adapted:
matrice = [[1,2],[3,4]]
valProp = np.linalg.eigvals(matrice)
print('Eigenvalues of the matrix {} :'.format(matrice))
print('  vp1 = {}'.format(valProp[0]))
print('  vp2 = {}'.format(valProp[1]))

# Template for calculating eigenvalues of a matrix, to be adapted: matrice = [[1,2],[3,4]] valProp = np.linalg.eigvals(matrice) print('Eigenvalues of the matrix {} :'.format(matrice)) print(' vp1 = {}'.format(valProp[0])) print(' vp2 = {}'.format(valProp[1]))

Valeurs propres de la matrice [[1, 2], [3, 4]] :
  vp1 = -0.3722813232690143
  vp2 = 5.372281323269014

In [ ]:

# To be completed to determine the nature of the critical points of f1

# Calculate the Hessian matrix
matrice1 = d2f1 (-1,-2)
# Calculate the eigenvalues of the Hessian matrix, then test their sign
valProp = np.linalg.eigvals(matrice1)
print('Eigenvalues of the matrix {} :'.format(matrice1))
print('  vp1 = {}'.format(valProp[0]))
print('  vp2 = {}'.format(valProp[1]))

# To be completed to determine the nature of the critical points of f1 # Calculate the Hessian matrix matrice1 = d2f1 (-1,-2) # Calculate the eigenvalues of the Hessian matrix, then test their sign valProp = np.linalg.eigvals(matrice1) print('Eigenvalues of the matrix {} :'.format(matrice1)) print(' vp1 = {}'.format(valProp[0])) print(' vp2 = {}'.format(valProp[1]))

Valeurs propres de la matrice [[-6, 0], [0, -12]] :
  vp1 = -6.0
  vp2 = -12.0

3.5 Redo questions 3.2, 3.3, and 3.4 for the function $f_2$ from exercise 1.