Master Python Optimization: Bisection, Fibonacci, Golden Section & Newton Methods

Bisection Method

The article introduces a simple bisection algorithm implemented in Python. The function asdf(x) computes a cubic expression, and a loop repeatedly narrows the interval until the desired precision is reached, finally printing the left and right limits and the minimal x value.

<code>def asdf(x):
    rres = 8*x**3 - 2*x**2 - 7*x + 3
    return rres

i = 2
left = 0
right = 1
while i > 0:
    i = i - 1
    ans = 0.1
    mid1 = (left + right + ans) / 2
    mid2 = (left + right - ans) / 2
    a = asdf(mid1)
    c = asdf(mid2)
    if a > c:
        right = mid1
    else:
        left = mid2
b = (left + right) / 2
print("左极限=%s,右极限=%s,极小值x=%s" % (left, right, b))</code>

Output example:

<code>左极限=0.45,右极限=0.775,极小值x=0.6125</code>

In Python a return statement must appear on a new line after the function body; otherwise the function produces no output.

Three‑Point Division Method (格点法)

A similar approach is applied using NumPy to evaluate a quadratic function.

<code>import numpy as np

def qwer(x):
    third = np.exp(x) - 5*x
    return third

left = 1
right = 2
mid1 = float(left + right) / 2
mid2 = (left + mid1) / 2
mid3 = (mid1 + right) / 2

a = qwer(mid1)
 b = qwer(mid2)
 c = qwer(mid3)
# Iterative comparison updates left/right and mid points
# ... (loop omitted for brevity)
print("最小值=%s" % mid1)
print("函数值=%s" % a)</code>

Result:

<code>最小值=1.609375
函数值=-3.047189552275773</code>

Fibonacci Method

The classic Fibonacci search is implemented to locate a minimum of a quadratic function.

<code>def fibonacci(n):
    i = 0
    a = 0
    b = 1
    for i in range(n):
        i = i + 1
        c = a + b
        a = b
        b = c
    return c

def bn(x):
    ert = x**2 - 6*x + 2
    return ert

z = 2
p = 0
left = 0.00000
right = 10.00000
L1 = right - left
while z < 100:
    m = fibonacci(z)
    l = L1 / m
    k = 1.000 / m
    if k < 0.03:
        print("n=%s,Fn=%s" % (z, m))
        L2 = l * fibonacci(z-1)
        t = left + L2
        r = right - L2
        while p < 3:
            p = p + 1
            # further updates omitted
        break
    else:
        z = z + 1
print("极小值x=", (left+right)/2)
print("极小值y=", bn((left+right)/2))</code>

Golden‑Section Method

Using the golden ratio to shrink the search interval.

<code>def gold(x):
    gg = x**2 - 6*x + 9
    return gg

left = 1
right = 7
ans = 0.4
a = left + 0.618 * (right - left)
b = left + 0.382 * (right - left)
while i < 7:
    print("i=%s" % i)
    print("left=%s,right=%s" % (left, right))
    print("x左=%s,x右=%s" % (a, b))
    print("y左=%s,y右=%s" % (gold(b), gold(a)))
    c = right - left
    if c > 0.4:
        i = i + 1
        if gold(a) > gold(b):
            right = a
            a = b
            b = left + 0.382 * (right - left)
            gga = gold(b)
            ggb = gold(a)
        else:
            left = b
            b = a
            a = left + 0.618 * (right - left)
            ggb = gold(a)
            gga = gold(b)
    else:
        break</code>

Quadratic Interpolation Method (二次插值法)

Interpolates a cubic polynomial using three points.

<code>def yy(x):
    y = x**4 - 4*x**3 - 6*x**2 - 16*x + 4
    return y

def xing(xm1, xm2, xm3, fm1, fm2, fm3):
    yxxx = 0.5000 * ((xm2**2 - xm3**2) * fm1 + (xm3**2 - xm1**2) * fm2 + (xm1**2 - xm2**2) * fm3) / ((xm2 - xm3) * fm1 + (xm3 - xm1) * fm2 + (xm1 - xm2) * fm3)
    return yxxx

x1 = -1.0
f1 = yy(x1)
x3 = 6
f3 = yy(x3)
x2 = 0.5 * (x1 + x3)
f2 = yy(x2)
xp = xing(x1, x2, x3, f1, f2, f3)
fp = yy(xp)
while abs(xp - x2) > 0.05:
    if xp > x2:
        if fp > f2:
            x3, f3 = xp, fp
            xp = xing(x1, x2, x3, f1, f2, f3)
            fp = yy(xp)
        else:
            x1, f1 = x2, f2
            x2, f2 = xp, fp
            xp = xing(x1, x2, x3, f1, f2, f3)
            fp = yy(xp)
    else:
        if fp > f2:
            x1, f1 = xp, fp
            xp = xing(x1, x2, x3, f1, f2, f3)
            fp = yy(xp)
        else:
            x3, f3 = x2, f2
            x2, f2 = xp, fp
            xp = xing(x1, x2, x3, f1, f2, f3)
            fp = yy(xp)
    print("ans=%s" % abs(xp - x2))
    print("left=%s,right=%s" % (x1, x3))
    print("x*=%s,fp*=%s" % (xp, fp))
    print("******************")
</code>

Newton's Method (牛顿法)

Applies Newton's iteration to solve for a root of a cubic polynomial.

<code>def fd(x):
    y = 4*x**3 - 12*x**2 - 12*x - 16
    return y

def fdd(x):
    ys = 12*x**2 - 24*x - 12
    return ys

i = 1
x0 = 3.0
ans = 0.001
while i < 7:
    fd0 = fd(x0)
    fdd0 = fdd(x0)
    if abs(fd0) > ans:
        x1 = x0 - (fd0 / fdd0)
        x0 = x1
        print("次数：%s,所得的值x:%s" % (i, x1))
        i = i + 1
    else:
        print("$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$")
        print("Bingo!顺利通关！祝您开学愉快！")
        print("Boss  X=%s" % x0)
        break
</code>

The author notes common pitfalls such as incorrect loop conditions, missing break statements, and the importance of proper debugging.