Unconstrained Optimization

Tags: Python, Gradient algorithm, SciPy, CG, BFGS

Let’s practice our coding skills and check if we have a good handle on the basics of local optimization! We’ll do this by writing our own steepest descent solver.

Section A- Find the minimum of the following function:

​ 𝑓(𝑥,𝑦)=12𝑥2+5𝑦2+23(𝑥−2)4+8(𝑦+1)4

1) Define the function and its analytical gradient in Jupyter notebook. ( 2 marks)

2) Implement a steepest gradient algorithm. Use x0 = 10, y0 = 20 as starting points. You can consider that the algorithm has converged to a solution if f(x,y) is within 0.0001 of its optimal value. (8 marks)

3) Plot the values of f(x,y)—or log(f(x,y))—x and y at each step during optimization (2 marks).

4) Instead of using your own method, use the CG and BFGS algorithms available in the SciPy.optimize.minimize module. (tip: you can input the analytical gradient that you implemented above using “jac=”; this will make the calculation much more efficient than having the computer perform numerical derivatives.) Use x0 = 10, y0 = 20 as starting points. (6 marks)

5) Which method provided the best results, in your opinion? Explain your reasoning (2 marks)

Section B- Minimize the following function instead:

​ 𝑓(𝑥,𝑦)=12𝑥2+5𝑦2+13𝑥3

1) Define the function and its analytical gradient in Jupyter notebook. ( 2 marks)

2) Implement a steepest gradient algorithm. Use x0 = 2, y0 = 20 as starting points. You can consider that the algorithm has converged to a solution if f(x,y) is within 0.0001 of its optimal value. (4 marks).

3) BONUS (2 marks): Plot the value of f(x,y), x, and y. For example:

4) Use the CG and BFGS algorithms available in the SciPy.optimize.minimize module. Use x0 = 2, y0 = 20 as starting points. (4 marks).

5) How many minima does this function have? (2 marks)

6) Can the computer find them all? (2 marks)

7) Are they local or global? (2 marks)

Section C- Explain in about half-a-page (400 words) how the CG and BFGS algorithms function. Feel free to use equations and graphs.