"""ch13_gradient_descent.py Companion code for Chapter 13: Optimization and Data Fitting. Gradient descent with Armijo backtracking. Edit the example settings in main(); numerical routines are reusable on import. Run: python3 ch13_gradient_descent.py [--no-plot] Requires NumPy; optional plots require Matplotlib. Fixed seeds reproduce runs with the same software; languages need not share sequences. """ import sys import numpy as np def main(): make_plot = "--no-plot" not in sys.argv fun = lambda p: p[0]**2+4*p[1]**2+2*p[0]*p[1] grad = lambda p: np.array([2*p[0]+2*p[1],8*p[1]+2*p[0]]) p0 = np.array([1.8,-1.6]) step_initial,tol_grad,max_iter = 1.0,1e-6,1000 p,fx,info = gradient_descent(fun,grad,p0,step_initial,tol_grad,max_iter) report(p,fx,info) if make_plot: plot_contour(fun,[-0.5,2.0],[-2.0,0.5],p,"Gradient descent",p0) def vector(x, name="data"): if np.iscomplexobj(x): raise ValueError(name + " must be real") a = np.asarray(x, dtype=float) if a.ndim != 1 or a.size == 0 or not np.all(np.isfinite(a)): raise ValueError(name + " must be a nonempty finite vector") return a def checked(fun, x): value = np.asarray(fun(x)) if value.ndim != 0 or np.iscomplexobj(value) or not np.isfinite(value): raise ValueError("Objective must return a finite real scalar") return float(value) def bounds(lower, upper): lo, hi = vector(lower, "lower"), vector(upper, "upper") if lo.shape != hi.shape or not np.all(np.isfinite(hi - lo)) or np.any(hi <= lo): raise ValueError("Require matching finite bounds with upper > lower") return lo, hi def integer(value, minimum, name): if not np.isscalar(value) or not np.isfinite(value) or int(value) != value or value < minimum: raise ValueError(name + " must be an integer >= " + str(minimum)) return int(value) def positive(value, name): if not np.isscalar(value) or not np.isfinite(value) or value <= 0: raise ValueError(name + " must be positive and finite") return float(value) def gradient_descent(fun, grad, p0, step_initial=1.0, tol_grad=1e-6, max_iter=1000): """Unconstrained gradient descent with Armijo backtracking. Small gradient means stationary, not necessarily a minimum. Scale variables and gradient tolerance according to the physical units. """ p = vector(p0, "p0").copy() positive(step_initial, "step_initial"); positive(tol_grad, "tol_grad") max_iter = integer(max_iter, 0, "max_iter") fp = checked(fun, p); calls = 1; gcalls = 0; steps = 0 status = "Maximum iteration count reached." while True: g = vector(grad(p), "gradient"); gcalls += 1 if g.shape != p.shape: raise ValueError("Gradient and point must have matching shapes") norm = float(np.linalg.norm(g)) if not np.isfinite(norm): raise ValueError("Gradient norm overflow; rescale the problem") if norm <= tol_grad: status = "Gradient tolerance reached."; break if steps >= max_iter: break step = step_initial; accepted = False for _ in range(60): trial = p - step*g if np.array_equal(trial, p): break if np.all(np.isfinite(trial)): ft = checked(fun, trial); calls += 1 if ft <= fp - 1e-4*step*norm*norm: p, fp = trial, ft; accepted = True; break step *= 0.5 if not accepted: status = "Backtracking failed or the step stagnated."; break steps += 1 return p, fp, dict(iterations=steps, evaluations=calls, gradient_calls=gcalls, gradient_norm=norm, status=status) def report(p, value, info): for j,x in enumerate(np.atleast_1d(p),1): print(f"p({j}) = {x:.12g}") print(f"Objective value: {value:.12g}") for key,value in info.items(): print(f"{key}: {value}") def plot_contour(fun, lower, upper, p, title, start=None): import matplotlib.pyplot as plt X,Y=np.meshgrid(np.linspace(*lower,150),np.linspace(*upper,150)) Z=np.array([fun(np.array([x,y])) for x,y in zip(X.ravel(),Y.ravel())]).reshape(X.shape) plt.contour(X,Y,Z,25,colors="0.6") if start is not None: plt.plot(*start,"ko",fillstyle="none",label="Start") plt.plot(*p,"k+",ms=10,label="Best point");plt.xlabel("p1");plt.ylabel("p2") plt.title(title,fontweight="normal");plt.xlim(lower);plt.ylim(upper);plt.gca().set_aspect("equal") plt.legend(loc="best");plt.grid(True);plt.tight_layout();plt.show() if __name__ == "__main__": main()