Minimize a Convex Function

Minimize a Convex Function - Uber Coding Interview | ShowOffer

You are given a convex function f(x) that is defined on the real numbers. The function is guaranteed to have a unique minimum. You are also given a range [a, b] that contains the minimum of the function. Your task is to find the minimum of the function within the given range.

Examples:

1. f(x) = (x - 1)^2, a = 0, b = 2

   • Minimum is at x = 1.

2. f(x) = x^2 + 10x + 25, a = -10, b = 0

   • Minimum is at x = -5.

Constraints:

• The function f(x) is convex and has a unique minimum.
• The range [a, b] contains the minimum of the function.
• The function f(x) can be evaluated at any real number x.

Hints:

1. Since the function is convex and has a unique minimum, you can use a binary search approach to find the minimum within the given range.
2. Evaluate the function at the midpoint of the current range and compare it with the function values at the endpoints. If the function value at the midpoint is less than the function values at the endpoints, update the range to include the midpoint. Otherwise, update the range to exclude the midpoint.
3. Repeat the process until the range is sufficiently small, indicating that the minimum has been found.

Solution:

To find the minimum of a convex function f(x) within a given range [a, b], you can use a binary search approach. Here's a step-by-step algorithm:

1. Initialize the range [a, b] that contains the minimum of the function.
2. Calculate the midpoint m = (a + b) / 2.
3. Evaluate the function at the midpoint: f(m).
4. If f(m) < f(a) and f(m) < f(b), update the range to [a, m].
5. Otherwise, update the range to [m, b].
6. Repeat steps 2-5 until the range is sufficiently small, indicating that the minimum has been found.

This approach works because the function is convex, and the minimum is guaranteed to be unique. By evaluating the function at the midpoint and updating the range accordingly, you can efficiently narrow down the range until the minimum is found.

Here's a Python implementation of the algorithm:

python def minimize_convex_function(f, a, b, tol=1e-6): while (b - a) > tol: m = (a + b) / 2 if f(m) < f(a) and f(m) < f(b): a = m else: b = m return (a + b) / 2

You can use this function to find the minimum of a convex function within a given range by passing the function f, the range [a, b], and an optional tolerance tol to control the accuracy of the result.