Numerical Function Minimization via Gradient Descent

Worked Solution

How to Think About It: Gradient descent repeatedly steps in the direction that decreases $f$. Here $f$ is a polynomial given by its coefficient list, coeffs, so $f(x) = \sum_i \text{coeffs}[i]\, x^i$. We do NOT get an analytic derivative, so we approximate $f'(x)$ from function evaluations. This problem pins a fully deterministic protocol so the answer is reproducible: central difference with finite-difference step $h = 10^{-5}$, convergence tolerance $\text{tol} = 10^{-10}$ on $|x_{new} - x|$, update rule $x \leftarrow x - \text{lr} \cdot f'(x)$, starting at $x_0$, stopping when $|x_{new} - x| < \text{tol}$ or max_iter is reached. The function returns the final $x$ (the approximate argmin).

Algorithm:

1. Build $f(x) = \sum_i \text{coeffs}[i]\, x^i$ from the coefficient list.
2. At each step approximate $f'(x) \approx \dfrac{f(x+h) - f(x-h)}{2h}$ (central difference, $O(h^2)$ accurate).
3. Update $x \leftarrow x - \text{lr} \cdot f'(x)$.
4. Stop when $|x_{new} - x| < \text{tol}$ or max_iter iterations elapse; return the final $x$.

Code:

```python def gd_minimize(coeffs, x0, lr, max_iter): # Minimize f(x) = sum(coeffs[i] * x**i) by gradient descent, approximating # f'(x) with a CENTRAL difference. Pinned deterministic protocol: # h = 1e-5, tol = 1e-10, update x <- x - lr * f'(x), # stop when |x_new - x| < tol OR max_iter reached. Start at x0. h = 1e-5 tol = 1e-10

def f(x): total = 0.0 for i, c in enumerate(coeffs): total += c * x**i return total

x = x0 for _ in range(max_iter): grad = (f(x + h) - f(x - h)) / (2 * h) x_new = x - lr * grad if abs(x_new - x) < tol: x = x_new break x = x_new return x ```

Why central difference: The forward difference $\frac{f(x+h)-f(x)}{h}$ is $O(h)$ accurate and costs one extra evaluation, while the central difference $\frac{f(x+h)-f(x-h)}{2h}$ is $O(h^2)$ accurate at two evaluations — the first-order error term cancels by symmetry. The optimal $h$ balances truncation error against floating-point roundoff, giving $h^\star \approx \epsilon^{1/3} \approx 10^{-5}$, which is exactly the pinned value.

Enhancements that improve convergence:

1. Adaptive step size (backtracking line search): instead of a fixed lr, shrink the step until the Armijo sufficient-decrease condition $f(x - \alpha g) \le f(x) - c\,\alpha g^2$ holds.
2. Newton's method: use the numerical second derivative $f''(x) \approx \frac{f(x+h) - 2f(x) + f(x-h)}{h^2}$ and step $x \leftarrow x - f'(x)/f''(x)$ for quadratic convergence near the minimum (at the risk of diverging when $f''$ is small or negative).
3. Momentum: accumulate a running average of past gradients to damp oscillations in narrow valleys.

Note: the function signature is gd_minimize(coeffs, x0, lr, max_iter) and it must return the final $x$ (a float), not print it.