黃金分割法是求解單峰函數極小值的經典優化算法,收斂速度快、無需導數、實現簡單。本文提供完整的 Python 實現,包含括定極小值區間和區間內精確搜索兩階段,並解釋核心數學原理。
φ = (√5 - 1)/2 ≈ 0.618,1-φ ≈ 0.382。tol。from math import log, ceil
GOLDEN_RATIO = 1.618033989
INV_GOLDEN = 0.618033989
COMPLEMENT = 1.0 - INV_GOLDEN # 0.381966011
def bracket(f, x1, h):
"""從 x1 以步長 h 向下搜索,返回包含極小值的區間 (a, b)"""
c = GOLDEN_RATIO
f1 = f(x1)
x2 = x1 + h
f2 = f(x2)
# 確定下降方向
if f2 > f1:
h = -h
x2 = x1 + h
f2 = f(x2)
# 檢查 x1 兩側是否已括定
if f2 > f1:
return x2, x1 - h
# 擴展搜索
for _ in range(100):
h *= c
x3 = x2 + h
f3 = f(x3)
if f3 > f2:
return x1, x3
x1, x2, f1, f2 = x2, x3, f2, f3
raise RuntimeError("Bracket did not find a minimum")
def search(f, a, b, tol=1.0e-9):
"""在區間 (a,b) 內黃金分割搜索極小值"""
n_iter = int(ceil(-2.078087 * log(tol / abs(b - a)))) # 理論迭代次數
R = INV_GOLDEN
C = COMPLEMENT
# 初始兩個試點
x1 = R * a + C * b
x2 = C * a + R * b
f1 = f(x1)
f2 = f(x2)
# 主循環
for _ in range(n_iter):
if f1 > f2:
a = x1
x1, f1 = x2, f2
x2 = C * a + R * b
f2 = f(x2)
else:
b = x2
x2, f2 = x1, f1
x1 = R * a + C * b
f1 = f(x1)
return (x1, f1) if f1 < f2 else (x2, f2)
# 使用示例
if __name__ == '__main__':
def f(x):
return (x - 2) ** 2 + 1 # 最小值在 x=2, f=1
a, b = bracket(f, 0, 0.1)
print("Bracket:", a, b)
x_min, f_min = search(f, a, b)
print("Minimum at x =", x_min, "f(x) =", f_min)
Bracket: 1.8541019662496847 2.1458980337503154
Minimum at x = 2.0000000000000004 f(x) = 1.0
bracket 中步長按黃金比指數增長,快速跳出局部平坦區。n_iter = ceil(-2.078 * log(tol/|b-a|)) 來自區間縮減幾何級數公式,避免過度迭代。黃金分割法是優化算法工具箱中的「瑞士軍刀」,理解其幾何直覺與代碼實現,能為更複雜的優化問題打下堅實基礎。