.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/optimization/constrained/plot_02_frank_wolfe.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_constrained_plot_02_frank_wolfe.py>`
        to download the full example code.

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

.. _sphx_glr_api_gallery_optimization_constrained_plot_02_frank_wolfe.py:


Frank-Wolfe: optimization over the probability simplex
============================================================

Minimizes a convex quadratic over the triangle
:math:`\{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.

.. GENERATED FROM PYTHON SOURCE LINES 13-18

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.optimization import frank_wolfe








.. GENERATED FROM PYTHON SOURCE LINES 19-21

Project a point onto the simplex
--------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 21-28

.. code-block:: Python


    y = np.array([1.0, 0.2, -0.5])
    f = lambda x: float(np.sum((x - y) ** 2))
    grad = lambda x: 2.0 * (x - y)
    result = frank_wolfe(f, grad, [0.0, 0.0, 1.0], a_eq=np.ones((1, 3)), b_eq=np.array([1.0]), max_iter=500)
    print(f"Frank-Wolfe solution: {result.x.round(4)} (exact projection: [0.9, 0.1, 0.0])")





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

 .. code-block:: none

    Frank-Wolfe solution: [0.9 0.1 0. ] (exact projection: [0.9, 0.1, 0.0])




.. GENERATED FROM PYTHON SOURCE LINES 29-31

Iterates in barycentric coordinates, and the duality gap
--------------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 31-50

.. code-block:: Python


    corners = np.array([[0.0, 0.0], [1.0, 0.0], [0.5, np.sqrt(3) / 2]])
    xy = result.path @ corners
    fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10, 4))
    ax1.fill(*corners.T, color="0.92")
    ax1.plot(*xy.T, ".-", ms=3, lw=0.8)
    ax1.plot(*(np.array([0.9, 0.1, 0.0]) @ corners), "*", ms=12, color="tab:red", label="optimum")
    ax1.set_aspect("equal")
    ax1.axis("off")
    ax1.legend()
    ax1.set_title("Iterates on the simplex")
    k = np.arange(len(result.extra["gaps"]))
    ax2.loglog(k + 1, result.extra["gaps"], label="Frank-Wolfe gap")
    f_star = f(np.array([0.9, 0.1, 0.0]))
    ax2.loglog(k + 1, [f(x) - f_star for x in result.path[: len(k)]], label=r"$f(x_k) - f^*$")
    ax2.set_xlabel("iteration k + 1")
    ax2.legend()
    ax2.set_title("O(1/k) convergence (Frank & Wolfe, 1956)")
    fig.tight_layout()



.. image-sg:: /api/gallery/optimization/constrained/images/sphx_glr_plot_02_frank_wolfe_001.png
   :alt: Iterates on the simplex, O(1/k) convergence (Frank & Wolfe, 1956)
   :srcset: /api/gallery/optimization/constrained/images/sphx_glr_plot_02_frank_wolfe_001.png
   :class: sphx-glr-single-img






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

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


.. _sphx_glr_download_api_gallery_optimization_constrained_plot_02_frank_wolfe.py:

.. only:: html

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

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

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

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

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

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

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


.. only:: html

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

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