Strictly Convex Function Minimum

Problem Overview

This question is usually asked in two layers:

• Solve the 1D version on an integer interval
• Extend the same idea to a 2D bounded rectangle You are given black-box access to a strictly convex function f(x). Your goal is to find the minimum value of this function within a given range.

1D Version

Problem Statement

Given a strictly convex function f(x) and an integer interval [a, b], find the minimum value of f(x) within this interval.

Examples

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

   • The minimum value is 1 at x = 1.

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

   • The minimum value is 0 at x = 2.

Constraints

• 1 <= a < b <= 10^9
• f(x) is a strictly convex function.

Hints

1. Use binary search to find the minimum value efficiently.
2. Since f(x) is strictly convex, the minimum value must occur at one of the endpoints or at a single point within the interval.

2D Version

Problem Statement

Given a strictly convex function f(x, y) and a 2D bounded rectangle [a, b] x [c, d], find the minimum value of f(x, y) within this rectangle.

Examples

1. f(x, y) = (x - 1)^2 + (y - 2)^2, a = 0, b = 2, c = 1, d = 3

   • The minimum value is 0 at (x, y) = (1, 2).

2. f(x, y) = (x^2 + y^2), a = -1, b = 1, c = -2, d = 2

   • The minimum value is 0 at (x, y) = (0, 0).

Constraints

• 1 <= a < b <= 10^9
• 1 <= c < d <= 10^9
• f(x, y) is a strictly convex function.

Hints

1. Use a similar binary search approach as in the 1D version, but extend it to two dimensions.
2. Since f(x, y) is strictly convex, the minimum value must occur at one of the corners of the rectangle or at a single point within the rectangle.

Solution

1D Version

To solve the 1D version, you can use binary search. Here's a Python function to find the minimum value:

python def find_min_1d(f, a, b, tol=1e-10): while b - a > tol: mid = (a + b) / 2 if f(mid) < f(a): a = mid else: b = mid return (a + b) / 2

2D Version

To solve the 2D version, you can extend the binary search approach to two dimensions. Here's a Python function to find the minimum value:

python def find_min_2d(f, a, b, c, d, tol=1e-10): while b - a > tol and d - c > tol: mid_x = (a + b) / 2 mid_y = (c + d) / 2 if f(mid_x, mid_y) < f(a, mid_y): if f(mid_x, mid_y) < f(mid_x, c): a = mid_x else: c = mid_y else: if f(mid_x, mid_y) < f(b, mid_y): b = mid_x else: d = mid_y return (a + b) / 2, (c + d) / 2

These functions should help you find the minimum value of a strictly convex function within a given range or rectangle.