.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/optimization/newton_quasi_newton/plot_01_bfgs_quasi_newton.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_optimization_newton_quasi_newton_plot_01_bfgs_quasi_newton.py>`
        to download the full example code.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_optimization_newton_quasi_newton_plot_01_bfgs_quasi_newton.py:


BFGS: Newton-like convergence without second derivatives
==============================================================

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'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.

.. GENERATED FROM PYTHON SOURCE LINES 13-19

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.optimization import BFGS, GradientDescentLineSearch, NewtonMethod, rosenbrock, rosenbrock_grad, rosenbrock_hess
    from mathematicskit.optimization.visualizers.plots import plot_contour_path, plot_convergence_comparison








.. GENERATED FROM PYTHON SOURCE LINES 20-22

BFGS against Newton's method and gradient descent
-------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 22-32

.. code-block:: Python


    x0 = [-1.2, 1.0]
    results = {
        "gradient descent": GradientDescentLineSearch(tol=1e-6, max_iter=5000).minimize(rosenbrock, rosenbrock_grad, x0),
        "Newton (exact Hessian)": NewtonMethod(tol=1e-8).minimize(rosenbrock, rosenbrock_grad, x0, hess=rosenbrock_hess),
        "BFGS (gradients only)": BFGS(tol=1e-8).minimize(rosenbrock, rosenbrock_grad, x0),
    }
    for name, result in results.items():
        print(f"{name}: {result.iterations} iterations, converged = {result.converged}, x = {result.x.round(6)}")





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    gradient descent: 5000 iterations, converged = False, x = [0.999049 0.998091]
    Newton (exact Hessian): 85 iterations, converged = True, x = [1. 1.]
    BFGS (gradients only): 34 iterations, converged = True, x = [1. 1.]




.. GENERATED FROM PYTHON SOURCE LINES 33-37

Superlinear convergence of BFGS
-------------------------------
The error ratio :math:`\|x_{k+1}-x^*\| / \|x_k-x^*\|` stays bounded away
from zero for a linearly convergent method; for BFGS it tends to zero.

.. GENERATED FROM PYTHON SOURCE LINES 37-43

.. code-block:: Python


    bfgs = results["BFGS (gradients only)"]
    err = np.linalg.norm(bfgs.path - np.array([1.0, 1.0]), axis=1)
    ratios = err[1:] / err[:-1]
    print("last BFGS error ratios:", np.round(ratios[-6:-1], 3))





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    last BFGS error ratios: [0.6   0.072 0.015 0.011 0.027]




.. GENERATED FROM PYTHON SOURCE LINES 44-46

Convergence rates and the BFGS path
-----------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 46-54

.. code-block:: Python


    fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(11, 4.5))
    plot_convergence_comparison(results, rosenbrock, f_star=0.0, ax=ax1)
    ax1.set_xlim(0, 100)
    ax1.set_title("BFGS keeps pace with Newton's method")
    plot_contour_path(rosenbrock, bfgs, ax=ax2, x_range=(-2.0, 2.0), y_range=(-1.0, 3.0), label="BFGS")
    ax2.set_title("BFGS iterates on the Rosenbrock valley")
    fig.tight_layout()



.. image-sg:: /api/gallery/optimization/newton_quasi_newton/images/sphx_glr_plot_01_bfgs_quasi_newton_001.png
   :alt: BFGS keeps pace with Newton's method, BFGS iterates on the Rosenbrock valley
   :srcset: /api/gallery/optimization/newton_quasi_newton/images/sphx_glr_plot_01_bfgs_quasi_newton_001.png
   :class: sphx-glr-single-img






.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.421 seconds)


.. _sphx_glr_download_api_gallery_optimization_newton_quasi_newton_plot_01_bfgs_quasi_newton.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_01_bfgs_quasi_newton.ipynb <plot_01_bfgs_quasi_newton.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_01_bfgs_quasi_newton.py <plot_01_bfgs_quasi_newton.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_01_bfgs_quasi_newton.zip <plot_01_bfgs_quasi_newton.zip>`


.. only:: html

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

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