Assignment 1: Finding the minimum in a 2D space

Deadline: Nov, 11 2024 14:00 CET

Finding the minimum point of functions is an important topic in many disciplines, including machine learning and natural language processing. In this exercise, we will work on a simpler (in some ways more difficult) form of the problem. Given a matrix (2D grid) of values that come from a strictly convex function, we want to find the minimum value in the matrix. We further assume that the true minimum is within our grid.

A visualization of an example concave function is provided below. You can re-genrate the visualization, or visualize other potential input matrices using visualization script.

The above simplifications means you are working with a constrained problem, where a greedy algorithm (possibly with some memoization) can work faster than a general purpose min() implementation.

Exercise

Implement the function find_minimum() in the template. Your code should run for any matrix whose values are sampled from a strictly convex function given a grid of (x, y) values.

Furthermore, your function should be faster than the generic min() implementation from numpy.

As usual, your implementation should pass the provided tests.

Wrapping up

Do not forget to

• indicate your name(s) in the file header
• commit all your changes
• push it to your GitHub repository