{ "cells": [ { "cell_type": "markdown", "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-36382da48191ad9d", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "\n", "# Practical work: Multi-dimensional minimization\n", "**Marc Buffat** Dpt mécanique, UCB Lyon 1\n", "![Minimisation 2D](Images/minimisation2D.jpg)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-5e01b39169bbb683", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "%matplotlib inline\n", "#algèbre linéaire\n", "import numpy as np\n", "import sympy as sp\n", "import time\n", "#représentation des résultats\n", "import matplotlib.pyplot as plt\n", "from IPython.display import display,Markdown\n", "def printmd(text):\n", " display(Markdown(text))\n", "plt.rc('font', family='serif', size='18')" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "hide_input": false, "nbgrader": { "grade": false, "grade_id": "cell-18967de19009975a", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "from validation.validation import info_etudiant, bib_validation\n", "def printmd(string):\n", " display(Markdown(string))\n", "# test si numero étudiant spécifier\n", "try: NUMERO_ETUDIANT\n", "except NameError: NUMERO_ETUDIANT = None \n", "if type(NUMERO_ETUDIANT) is not int :\n", " printmd(\"**ERREUR:** numéro d'étudiant non spécifié!!!\")\n", " NOM,PRENOM,NUMERO_ETUDIANT=info_etudiant()\n", " #raise AssertionError(\"NUMERO_ETUDIANT non défini\")\n", "# parametres spécifiques\n", "_uid_ = NUMERO_ETUDIANT\n", "np.random.seed(_uid_)\n", "printmd(\"**Login étudiant {} {} uid={}**\".format(NOM,PRENOM,_uid_))\n", "# fonctionnelle a minimiser\n", "bib_validation('cours','IntroIA')\n", "from Fonctionnelle import Fonctionnelle\n", "J = Fonctionnelle(_uid_)\n", "printmd(\"**Fonctionnelle J à minimiser**\")\n", "J.info()" ] }, { "cell_type": "markdown", "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-404992da11713a45", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "## Objectives\n", "\n", "Find the vector X minimizing the function J(X).\n", "\n", "The function J() is written in Python as an object (i.e. a class instance)\n", "\n", " - J : object name\n", " - J.dim() : dimension of X, i.e. number of variables\n", " - J(X) : calculate the value of J for a given vector X of dimension J.dim()\n", " - J.grad(X) : calculate the gradient of J at X\n", " - J.err(X) : calculate the norm of the error ||X-Xe|| where Xe minimize J(X)\n", " - J.min() : calculate the minimum of J\n" ] }, { "cell_type": "markdown", "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-7ea7973a606a32b5", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "## 1D Minimization\n", "\n", "Study of the minimization of $J(\\mathbf{X})$ in a given direction $\\mathbf{D}$ \n", "\n", "Given a vector $D$, we will minimize $J(\\alpha \\mathbf{D})$ (as a 1D function of $\\alpha$)\n", "\n", "In the following cells:\n", "\n", " - calculate $J(\\alpha \\mathbf{D})$ for different values of $\\alpha$ between -2 and 2\n", " - plot the function $J(\\alpha)$\n", " - use the function `minimize_scalar` in scipy to calculate $\\alpha$ that minimize $J(\\alpha)$ \n", " - put the result in the variable `alpha_min`" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": true, "grade_id": "cell-61f53cf8dcead0b8", "locked": false, "points": 0, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "# calcul variation dans une direction D\n", "D = np.zeros(J.dim())\n", "D[NUMERO_ETUDIANT % J.dim()] = 1\n", "Alpha = None\n", "JAlpha = None\n", "\n", "### BEGIN SOLUTION\n", "Alpha = np.linspace(-2,2,21)\n", "JAlpha = np.array([J(alpha*D) for alpha in Alpha])\n", "plt.figure(figsize=(10,8))\n", "plt.plot(Alpha,JAlpha)\n", "plt.xlabel(\"$\\\\alpha$\")\n", "plt.title(\"J($\\\\alpha$) dans la direction D\");\n", "### END SOLUTION" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-e360c0864b4a9b87", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "from scipy.optimize import minimize_scalar\n", "\n", "alpha_min = None\n", "### BEGIN SOLUTION\n", "F = lambda alpha:J(alpha*D)\n", "res = minimize_scalar(F,method='Brent')\n", "print(\"Jmin=\",res.fun)\n", "alpha_min = res.x\n", "print(\"solution alpha=\",alpha_min)\n", "X = alpha_min*D\n", "print(\"err=\",J.err(X))\n", "res\n", "### END SOLUTION" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": true, "grade_id": "cell-3bd042dd2023bc6d", "locked": true, "points": 2, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "print(f\"alpha={alpha_min} minimise J suivant D\\n\",D)\n", "assert(J.err1D(alpha_min,D)<1.e-5)\n" ] }, { "cell_type": "markdown", "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-ef6ef15f94d75be4", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "## multi-dimensional minimization\n", "\n", "use of the `scipy` library\n", "\n", " - function **minimize** (local minimization)\n", " \n", " - method using exact gradient : Conjugate Gradients, Newton GC, \n", " - méthod using approximate gradient : BFGS, \n", " - line search Powell, Simplex Nelder-Mead\n", " \n", " - global optimization\n", " - simulated annealing\n", " \n", "In the following cell, define 2 new functions :\n", "\n", " - **F(X)** to calculate J(X)\n", " - **Fgrad(X)** to calculate the gradient\n", " \n", "we use python functions because the minimization function does not allow class method.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-974f72e000114574", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "F = None\n", "Fgrad = None\n", "### BEGIN SOLUTION\n", "F = lambda X:J(X)\n", "Fgrad = lambda X:J.grad(X)\n", "### END SOLUTION\n", "X0 = np.zeros(J.dim())" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": true, "grade_id": "cell-579ae495b34e1726", "locked": true, "points": 2, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "print(\"solution initiale X0:\\n\",X0)\n", "assert np.allclose(F(X0),J(X0))\n", "assert np.allclose(Fgrad(X0),J.grad(X0))\n" ] }, { "cell_type": "markdown", "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-fbadd64f5eb390af", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "### Using the default minimize method\n", "\n", "for each method, we have too:\n", "\n", " - calculate the solution Xe, \n", " - calculate the value of J(Xe) \n", " - calculate the error (that should be less than 1.e-5)\n", " \n", " We have to prescribe the optional parameters in order to obtain the prescribed precision\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-c6c3dadb0c84cd3b", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "from scipy.optimize import minimize\n", "\n", "Xe = None\n", "### BEGIN SOLUTION\n", "\n", "\n", "\n", "\n", "res = minimize(F, X0,options={'disp':True})\n", "Xe = res.x\n", "print(\"Jmin=\",res.fun,res.message)\n", "print('solution J(Xe)={J(Xe)} pour Xe:\\n',Xe)\n", "print(\"Erreur = \",J.err(Xe))\n", "### END SOLUTION" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": true, "grade_id": "cell-9c28563eb190fcc4", "locked": true, "points": 2, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "print(f\"J={J(Xe)} avec erreur={J.err(Xe)} pour X:\\n\",Xe)\n", "assert( J.err(Xe) < 1.e-5)\n" ] }, { "cell_type": "markdown", "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-f3e07488399be59a", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "### Conjugate gradient Method\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-cbae438fdcdea680", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "Xe = None\n", "### BEGIN SOLUTION\n", "res = minimize(F, X0, jac=Fgrad, method='CG',options={'disp':True})\n", "print(\"Jmin=\",res.fun,res.message)\n", "Xe = res.x\n", "print('solution J(Xe)={J(Xe)} pour Xe:\\n',Xe)\n", "print(\"Erreur = \",J.err(Xe))\n", "### END SOLUTION" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": true, "grade_id": "cell-57dec395ba0af6a8", "locked": true, "points": 2, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "print(f\"J={J(Xe)} avec erreur={J.err(Xe)} pour X:\\n\",Xe)\n", "assert( J.err(Xe) < 1.e-5)\n" ] }, { "cell_type": "markdown", "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-85f0494d4cff9012", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "### Conjugate gradient Method with Newton \n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-5203ef66c4a06a40", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "Xe = None\n", "### BEGIN SOLUTION\n", "res = minimize(F, X0, jac=Fgrad, method='Newton-CG',options={'disp':True})\n", "print(\"Jmin=\",res.fun,res.message)\n", "Xe = res.x\n", "print('solution J(Xe)={J(Xe)} pour Xe:\\n',Xe)\n", "print(\"Erreur = \",J.err(Xe))\n", "### END SOLUTION" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": true, "grade_id": "cell-fb4aff67e8977a5b", "locked": true, "points": 2, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "print(f\"J={J(Xe)} avec erreur={J.err(Xe)} pour X:\\n\",Xe)\n", "assert( J.err(Xe) < 1.e-5)\n" ] }, { "cell_type": "markdown", "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-c1cfc822eb8ea9db", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "### Method BFGS (optimized version of the gradient method)\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-ec2012aadf4dbe0b", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "Xe = None\n", "### BEGIN SOLUTION\n", "res = minimize(F, X0, method='BFGS',options={'disp':True})\n", "print(\"Jmin=\",res.fun,res.message)\n", "Xe = res.x\n", "print('solution J(Xe)={J(Xe)} pour Xe:\\n',Xe)\n", "print(\"Erreur = \",J.err(Xe))\n", "### END SOLUTION" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": true, "grade_id": "cell-6112fa17edd7ecf0", "locked": true, "points": 2, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "print(f\"J={J(Xe)} avec erreur={J.err(Xe)} pour X:\\n\",Xe)\n", "assert( J.err(Xe) < 1.e-5)\n" ] }, { "cell_type": "markdown", "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-ed4801da3c3cb84c", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "### Powell Algorithm (line search 2D)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-28d2ad99da5ae273", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "Xe = None\n", "### BEGIN SOLUTION\n", "res = minimize(F, X0, method='Powell',options={'disp':True,'xtol':1.e-8,'ftol':1.0e-8})\n", "print(\"Jmin=\",res.fun,res.message)\n", "Xe = res.x\n", "print('solution J(Xe)={J(Xe)} pour Xe:\\n',Xe)\n", "print(\"Erreur = \",J.err(Xe))\n", "### END SOLUTION" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": true, "grade_id": "cell-24d162de7fe55867", "locked": true, "points": 2, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "print(f\"J={J(Xe)} avec erreur={J.err(Xe)} pour X:\\n\",Xe)\n", "assert( J.err(Xe) < 1.e-3)\n" ] }, { "cell_type": "markdown", "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-34f59c472beb012d", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "### Simulated annealing" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-ca1a2d5a4c09000b", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "from scipy.optimize import dual_annealing\n", "\n", "Xe = None\n", "### BEGIN SOLUTION\n", "bounds = [[-1,1]]*J.dim()\n", "res=dual_annealing(F,bounds=bounds)\n", "print(res)\n", "print(\"Jmin=\",res.fun,res.message)\n", "Xe = res.x\n", "print('solution J(Xe)={J(Xe)} pour Xe:\\n',Xe)\n", "print(\"Erreur = \",J.err(Xe))\n", "### END SOLUTION" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": true, "grade_id": "cell-193e811a2b82e6f0", "locked": true, "points": 3, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "print(f\"J={J(Xe)} avec erreur={J.err(Xe)} pour X:\\n\",Xe)\n", "assert( J.err(Xe) < 1.e-4)\n" ] }, { "cell_type": "markdown", "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-dea0352d17b4edf0", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "### Simplex Method (Nelder-Mead)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-6b6840cb5ec3cdba", "locked": false, "schema_version": 3, "solution": true, "task": false } }, "outputs": [], "source": [ "Xe = None\n", "### BEGIN SOLUTION\n", "bounds = [[-1,1]]*J.dim()\n", "res = minimize(F, X0, method='Nelder-Mead',bounds=bounds,\n", " options={'disp':True, 'maxiter':500000, \n", " 'fatol':1.0e-5,'xatol':1.0e-5})\n", "print(\"Jmin=\",res.fun,res.message)\n", "Xe = res.x\n", "print('solution J(Xe)={J(Xe)} pour Xe:\\n',Xe)\n", "print(\"Erreur = \",J.err(Xe))\n", "# non cvge\n", "### END SOLUTION" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbgrader": { "grade": true, "grade_id": "cell-5a39e9f7a5927ddc", "locked": true, "points": 3, "schema_version": 3, "solution": false, "task": false } }, "outputs": [], "source": [ "print(f\"J={J(Xe)} avec erreur={J.err(Xe)} pour X:\\n\",Xe)\n", "#assert( J.err(Xe) < 0.8)\n" ] }, { "cell_type": "markdown", "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-a9e2c132f600e2a5", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "## Analysis\n", "\n", "comparison of the different methods\n", "\n", " - computational cost\n", " - precision" ] }, { "cell_type": "markdown", "metadata": { "nbgrader": { "grade": true, "grade_id": "cell-f3050dccc48c8ba5", "locked": false, "points": 10, "schema_version": 3, "solution": true, "task": false } }, "source": [ "Write your analysis using Markdown syntax\n", "\n", "%%% BEGIN SOLUTION\n", "\n", "%%% END SOLUTION" ] }, { "cell_type": "markdown", "metadata": { "nbgrader": { "grade": false, "grade_id": "cell-dc9ffd095189e04c", "locked": true, "schema_version": 3, "solution": false, "task": false } }, "source": [ "## The End" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "celltoolbar": "Create Assignment", "hide_input": false, "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.10.12" }, "toc": { "base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": true, "title_cell": "Table of Contents", "title_sidebar": "Contents", "toc_cell": false, "toc_position": {}, "toc_section_display": true, "toc_window_display": false }, "varInspector": { "cols": { "lenName": 16, "lenType": 16, "lenVar": 40 }, "kernels_config": { "python": { "delete_cmd_postfix": "", "delete_cmd_prefix": "del ", "library": "var_list.py", "varRefreshCmd": "print(var_dic_list())" }, "r": { "delete_cmd_postfix": ") ", "delete_cmd_prefix": "rm(", "library": "var_list.r", "varRefreshCmd": "cat(var_dic_list()) " } }, "types_to_exclude": [ "module", "function", "builtin_function_or_method", "instance", "_Feature" ], "window_display": false } }, "nbformat": 4, "nbformat_minor": 4 }