Optimisation

Optimisation experiments, mostly on the Rosenbrock function

f(x) = c·(x₁² − x₂)² + (x₁ − 1)²      (c = 100, minimum at x = (1, 1))

The project contains the original MATLAB scripts and a Python port of each method.

MATLAB driver scripts: steepest_armijo_main.m, steepest_backtracking_main.m, steepeest_gradient_main.m, newton_armijo_main.m, mfo_main.m. Supporting files: rosenbrock*.m, func_plot.m. q3.mlx holds a coursework question and the .asv files are MATLAB autosaves.

Install the dependencies (numpy, scipy) with pip install -r requirements.txt. Every module is self-contained and returns a small result dataclass.

rosenbrock_optimiser.py: RosenbrockOptimiser

The Rosenbrock function, gradient and Hessian, plus steepest descent and Newton's method with Armijo backtracking. Stops when ‖∇f(x)‖ ≤ epsilon.

from rosenbrock_optimiser import RosenbrockOptimiser

opt = RosenbrockOptimiser(c=100, tau=0.5, beta=1e-4, epsilon=1e-6)
r = opt.newton([2, -2])             # ~[1, 1] in 15 iterations
r = opt.steepest_descent([2, -2])   # ~12,400 iterations

Each solver returns an OptimisationResult with x, iterations, converged, and per-iteration path, step_sizes and values. If the Newton direction is not a descent direction, that step falls back to steepest descent.

gradient_descent.py: GradientDescent

Extends RosenbrockOptimiser with the two simpler step rules.

from gradient_descent import GradientDescent

gd = GradientDescent(max_iter=200_000)
gd.constant_step([2, -2], alpha=3e-4)   # converges, ~104,000 iterations
gd.constant_step([2, -2], alpha=1e-2)   # diverges: converged=False
gd.backtracking([2, -2])                # plain decrease, no Armijo constant

A constant step must be small for this problem (roughly below 2 divided by the largest Hessian eigenvalue). Otherwise the iteration diverges and the result has converged=False.

moth_flame_optimiser.py: MothFlameOptimiser

A population-based minimiser for any objective, ported from Mirjalili's MFO. It defaults to the Rosenbrock benchmark on [−10, 10]².

from moth_flame_optimiser import MothFlameOptimiser

mfo = MothFlameOptimiser(lb=-10, ub=10, dim=2, n_agents=30, max_iter=500, seed=0)
r = mfo.optimise()
r.best_position, r.best_score, r.convergence_curve

Pass your own fobj, lb, ub and dim for other problems. lb and ub can be scalars or per-variable arrays. Set seed for reproducible runs.

linear_programming.py: LinearProgram

Wraps scipy.optimize.linprog. The defaults reproduce demo_LP.m: maximise 3x₁ + 5x₂ subject to x₁ ≤ 4, 2x₂ ≤ 12, 3x₁ + 2x₂ ≤ 18 and x ≥ 0.

from linear_programming import LinearProgram

r = LinearProgram().solve()
r.x, r.objective        # [2, 6], 36.0

Use maximise=False to minimise. objective is reported in the original sense, so you don't need to negate it.

quasi_newton_baseline.py: QuasiNewtonBaseline

BFGS from SciPy, standing in for MATLAB's fminunc. It's a reference to compare the hand-written methods against.

from quasi_newton_baseline import QuasiNewtonBaseline, question4_function

QuasiNewtonBaseline().minimise([2, -2])                           # Rosenbrock, analytic gradient
QuasiNewtonBaseline(question4_function, tol=1e-4).minimise([2, 2])  # the variant in Question4.m

Without an analytic jac, SciPy uses finite differences, which limits tol to about 1e-4. The default Rosenbrock problem supplies its gradient, so it reaches 1e-6.

Open the folder in MATLAB and run a driver script, for example newton_armijo_main.