:orphan:

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:

- :doc:`/tutorials/newtons_method_across_domains`

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.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. thumbnail-parent-div-close

.. raw:: html

    </div>

Nonlinear conjugate gradient
------------------------------

Fletcher-Reeves and Polak-Ribiere nonlinear CG.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Compares Polak-Ribiere nonlinear CG against plain gradient descent on the same ill-conditioned quadratic bowl -- CG&#x27;s conjugate search directions avoid the zig-zagging that slows gradient descent down.">

.. only:: html

  .. image:: /api/gallery/optimization/conjugate_gradient/images/thumb/sphx_glr_plot_01_cg_vs_gradient_descent_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/conjugate_gradient/plot_01_cg_vs_gradient_descent`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Nonlinear conjugate gradient vs. gradient descent</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Constrained optimization
---------------------------

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


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Minimizes x^2+y^2 subject to x+y=1. At the constrained optimum (0.5, 0.5) the objective&#x27;s gradient is parallel to the constraint&#x27;s gradient, \nabla f = -\lambda \nabla h with \lambda=-1, which is Lagrange&#x27;s condition. Rewriting the constraint as the inequality x+y \geq 1 gives a Karush-Kuhn-Tucker problem whose multiplier must also be non-negative.">

.. only:: html

  .. image:: /api/gallery/optimization/constrained/images/thumb/sphx_glr_plot_01_lagrange_multipliers_kkt_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/constrained/plot_01_lagrange_multipliers_kkt`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Lagrange multipliers and the KKT conditions</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Minimizes a convex quadratic over the triangle \{x \geq 0,\ x_1 + x_2 + x_3 = 1\} without ever projecting onto it. Each step solves a linear program, whose solution is a vertex, and moves toward that vertex. The Frank-Wolfe gap certifies how far the objective is from optimal.">

.. only:: html

  .. image:: /api/gallery/optimization/constrained/images/thumb/sphx_glr_plot_02_frank_wolfe_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/constrained/plot_02_frank_wolfe`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Frank-Wolfe: optimization over the probability simplex</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Fiacco and McCormick&#x27;s sequential unconstrained minimization replaces \min x^2+y^2 subject to x+y=1 with the unconstrained problems \min x^2+y^2+\mu(x+y-1)^2 for growing \mu. Each penalized minimizer violates the constraint slightly, and the violation shrinks like 1/\mu as the minimizers approach the constrained optimum (0.5, 0.5).">

.. only:: html

  .. image:: /api/gallery/optimization/constrained/images/thumb/sphx_glr_plot_03_penalty_method_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/constrained/plot_03_penalty_method`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">The quadratic penalty method: a sequence of unconstrained problems</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Direct search
-------------

Derivative-free minimization with the Nelder-Mead simplex method.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="The Nelder-Mead simplex method uses function values only. On the Rosenbrock function it needs more function evaluations than BFGS, which uses gradients, but it also works on objectives that have no gradient at all.">

.. only:: html

  .. image:: /api/gallery/optimization/direct_search/images/thumb/sphx_glr_plot_01_nelder_mead_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/direct_search/plot_01_nelder_mead`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Nelder-Mead: minimizing without derivatives</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Dynamic programming
-------------------

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


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Fills a table of optimal values for every prefix of the items and every capacity, then traces back the chosen items. The table is the dynamic-programming &quot;value function&quot;.">

.. only:: html

  .. image:: /api/gallery/optimization/dynamic_programming/images/thumb/sphx_glr_plot_01_knapsack_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/dynamic_programming/plot_01_knapsack`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Bellman's principle of optimality: the 0/1 knapsack</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Game theory
-----------

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


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Solves two zero-sum games as linear programs: rock-paper-scissors, whose optimal strategy is uniform with value zero, and a lopsided variant in which the row player&#x27;s rock beats scissors for double stakes, which tilts the game in the row player&#x27;s favour. In every game, the row player&#x27;s guaranteed payoff equals the column player&#x27;s guaranteed loss.">

.. only:: html

  .. image:: /api/gallery/optimization/game_theory/images/thumb/sphx_glr_plot_01_zero_sum_games_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/game_theory/plot_01_zero_sum_games`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Von Neumann's minimax theorem: optimal mixed strategies</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Gradient descent
------------------

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


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Gradient descent zig-zags across a narrow, elongated quadratic bowl. Backtracking line search adapts its step length automatically and converges in far fewer iterations than any single fixed step size.">

.. only:: html

  .. image:: /api/gallery/optimization/gradient_descent/images/thumb/sphx_glr_plot_01_fixed_vs_line_search_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/gradient_descent/plot_01_fixed_vs_line_search`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Fixed step vs. backtracking line search on an ill-conditioned bowl</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Nonlinear least squares
-----------------------

Curve fitting with the Levenberg-Marquardt method.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Fits a four-parameter damped cosine to noisy data. The residuals depend nonlinearly on the decay rate and frequency, so the fit needs an iterative method; Levenberg-Marquardt blends gradient descent (far from the solution) with Gauss-Newton (close to it).">

.. only:: html

  .. image:: /api/gallery/optimization/least_squares/images/thumb/sphx_glr_plot_01_levenberg_marquardt_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/least_squares/plot_01_levenberg_marquardt`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Levenberg-Marquardt: fitting a damped oscillation</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Linear programming
---------------------

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


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Maximize the profit 3x + 5y from two products subject to x + 2y \leq 40 labor-hours and 2x + y \leq 30 units of material. The simplex method starts at the vertex (0, 0) of the feasible polygon and pivots along its edges to an adjacent vertex with a higher profit, until no neighbour improves. The tableau pivots are written out below, and the answer is checked against linear_program.">

.. only:: html

  .. image:: /api/gallery/optimization/linear_programming/images/thumb/sphx_glr_plot_01_simplex_method_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/linear_programming/plot_01_simplex_method`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Dantzig's simplex method: walking the vertices of a production LP</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="The LP relaxation of an integer program can have a fractional optimum that rounding does not repair. Branch and bound (Land and Doig, 1960) finds the true integer optimum; here it is at a different vertex from the relaxation&#x27;s.">

.. only:: html

  .. image:: /api/gallery/optimization/linear_programming/images/thumb/sphx_glr_plot_02_branch_and_bound_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/linear_programming/plot_02_branch_and_bound`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Branch and bound: integer versus relaxed optimum</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Momentum methods
----------------

Nesterov's accelerated gradient and the Adam optimizer.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="On an ill-conditioned convex quadratic, plain gradient descent reduces the objective gap like O(1/k) until the strongly convex regime kicks in; Nesterov&#x27;s accelerated gradient, with the same step size, achieves the optimal first-order rate O(1/k^2).">

.. only:: html

  .. image:: /api/gallery/optimization/momentum/images/thumb/sphx_glr_plot_01_nesterov_acceleration_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/momentum/plot_01_nesterov_acceleration`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Nesterov acceleration: O(1/k^2) versus O(1/k)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="A quadratic whose two coordinates differ in curvature by a factor of 1000. Fixed-step gradient descent must use a step small enough for the stiff coordinate, so it crawls along the flat one. Adam rescales each coordinate by its root-mean-square gradient and moves both at a similar speed.">

.. only:: html

  .. image:: /api/gallery/optimization/momentum/images/thumb/sphx_glr_plot_02_adam_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/momentum/plot_02_adam`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Adam on a badly scaled problem</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Newton's method and BFGS
---------------------------

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


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="On the Rosenbrock function from (-1.2, 1.0), BFGS builds an inverse-Hessian approximation from gradients alone. It needs only a few dozen iterations, as few as Newton&#x27;s method with the exact Hessian at every step, while gradient descent needs thousands. Near the minimum its convergence is superlinear: the ratio of successive errors tends to zero.">

.. only:: html

  .. image:: /api/gallery/optimization/newton_quasi_newton/images/thumb/sphx_glr_plot_01_bfgs_quasi_newton_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/newton_quasi_newton/plot_01_bfgs_quasi_newton`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">BFGS: Newton-like convergence without second derivatives</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

One-dimensional search
----------------------

Golden-section search for the minimum of a unimodal function.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Locates the minimum of a unimodal function on an interval. Each iteration costs one new function evaluation and shrinks the bracket by the factor 1/\varphi \approx 0.618.">

.. only:: html

  .. image:: /api/gallery/optimization/scalar_search/images/thumb/sphx_glr_plot_01_golden_section_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/scalar_search/plot_01_golden_section`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Golden-section search: shrinking the bracket</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Stochastic approximation
------------------------

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


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Minimizes a quadratic using only noisy gradient observations. With Robbins and Monro&#x27;s step sizes a_k = a_0/(k+1), the noise averages out and the error shrinks like 1/\sqrt{k}. A constant step size instead stalls at a noise floor.">

.. only:: html

  .. image:: /api/gallery/optimization/stochastic/images/thumb/sphx_glr_plot_01_robbins_monro_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/stochastic/plot_01_robbins_monro`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Robbins-Monro: stochastic gradient descent with decaying steps</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Benchmark functions
-------------------

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


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="f(x, y) = 100(y-x^2)^2 + (1-x)^2 has its minimum f=0 at (1, 1), at the end of a banana-shaped valley along the parabola y = x^2. The walls are steep, but the floor is almost flat, so a method without curvature information finds the valley quickly and then crawls along it.">

.. only:: html

  .. image:: /api/gallery/optimization/test_functions/images/thumb/sphx_glr_plot_01_rosenbrock_banana_thumb.png
    :alt:

  :doc:`/api/gallery/optimization/test_functions/plot_01_rosenbrock_banana`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Rosenbrock's banana function: a narrow curved valley</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:
   :includehidden:


   /api/gallery/optimization/conjugate_gradient/index.rst
   /api/gallery/optimization/constrained/index.rst
   /api/gallery/optimization/direct_search/index.rst
   /api/gallery/optimization/dynamic_programming/index.rst
   /api/gallery/optimization/game_theory/index.rst
   /api/gallery/optimization/gradient_descent/index.rst
   /api/gallery/optimization/least_squares/index.rst
   /api/gallery/optimization/linear_programming/index.rst
   /api/gallery/optimization/momentum/index.rst
   /api/gallery/optimization/newton_quasi_newton/index.rst
   /api/gallery/optimization/scalar_search/index.rst
   /api/gallery/optimization/stochastic/index.rst
   /api/gallery/optimization/test_functions/index.rst



.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_