Examples#

This gallery walks through every public feature of mathematicskit.optimization: gradient descent, nonlinear conjugate gradient, Newton’s method and BFGS, momentum methods (Nesterov, Adam), Nelder-Mead, golden-section search, stochastic approximation, nonlinear least squares, constrained optimization (Lagrange/KKT, the penalty method, Frank-Wolfe), linear and integer programming, zero-sum games, and dynamic programming.

See also the narrative tutorial:

Each script in this gallery is self-contained and can be run directly with python examples/optimization/<section>/<script>.py.

Sections#

  • gradient_descent – fixed-step and backtracking-line-search gradient descent.

  • conjugate_gradient – nonlinear conjugate gradient (Fletcher-Reeves, Polak-Ribiere).

  • newton_quasi_newton – Newton’s method and BFGS on the Rosenbrock function, and a convergence-rate comparison across all five unconstrained methods.

  • momentum – Nesterov’s accelerated gradient and Adam.

  • direct_search – derivative-free Nelder-Mead simplex search.

  • scalar_search – golden-section search in one dimension.

  • stochastic – Robbins-Monro stochastic approximation.

  • least_squares – Levenberg-Marquardt nonlinear least squares.

  • constrained – Lagrange multipliers, KKT verification, the penalty method, and the Frank-Wolfe method.

  • linear_programming – linear programming via scipy.optimize.linprog and integer programming by branch and bound via scipy.optimize.milp.

  • game_theory – zero-sum matrix games and the minimax theorem.

  • dynamic_programming – Bellman’s recursion for the knapsack problem.

Nonlinear conjugate gradient#

Fletcher-Reeves and Polak-Ribiere nonlinear CG.

Nonlinear conjugate gradient vs. gradient descent

Nonlinear conjugate gradient vs. gradient descent

Constrained optimization#

Lagrange multipliers and the KKT conditions, the Frank-Wolfe method, and the quadratic penalty method.

Lagrange multipliers and the KKT conditions

Lagrange multipliers and the KKT conditions

Frank-Wolfe: optimization over the probability simplex

Frank-Wolfe: optimization over the probability simplex

The quadratic penalty method: a sequence of unconstrained problems

The quadratic penalty method: a sequence of unconstrained problems

Dynamic programming#

Bellman’s principle of optimality applied to the 0/1 knapsack problem.

Bellman’s principle of optimality: the 0/1 knapsack

Bellman's principle of optimality: the 0/1 knapsack

Game theory#

Zero-sum matrix games and von Neumann’s minimax theorem, solved as linear programs.

Von Neumann’s minimax theorem: optimal mixed strategies

Von Neumann's minimax theorem: optimal mixed strategies

Gradient descent#

Fixed-step and backtracking-line-search gradient descent.

Fixed step vs. backtracking line search on an ill-conditioned bowl

Fixed step vs. backtracking line search on an ill-conditioned bowl

Nonlinear least squares#

Curve fitting with the Levenberg-Marquardt method.

Levenberg-Marquardt: fitting a damped oscillation

Levenberg-Marquardt: fitting a damped oscillation

Linear programming#

Dantzig’s simplex method and branch and bound for integer programs.

Dantzig’s simplex method: walking the vertices of a production LP

Dantzig's simplex method: walking the vertices of a production LP

Branch and bound: integer versus relaxed optimum

Branch and bound: integer versus relaxed optimum

Momentum methods#

Nesterov’s accelerated gradient and the Adam optimizer.

Nesterov acceleration: O(1/k^2) versus O(1/k)

Nesterov acceleration: O(1/k^2) versus O(1/k)

Adam on a badly scaled problem

Adam on a badly scaled problem

Newton’s method and BFGS#

Quasi-Newton BFGS compared with Newton’s method and gradient descent on the Rosenbrock function.

BFGS: Newton-like convergence without second derivatives

BFGS: Newton-like convergence without second derivatives

Stochastic approximation#

The Robbins-Monro iteration: stochastic gradient descent on noisy gradients.

Robbins-Monro: stochastic gradient descent with decaying steps

Robbins-Monro: stochastic gradient descent with decaying steps

Benchmark functions#

Rosenbrock’s banana function, the standard stress test for optimizers.

Rosenbrock’s banana function: a narrow curved valley

Rosenbrock's banana function: a narrow curved valley

Gallery generated by Sphinx-Gallery