{ "cells": [ { "cell_type": "markdown", "source": [ "# Optimisation" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Dans plusieurs problèmes, on doit maximiser (ou minimiser) une fonction. On peut aussi devoir résoudre une équation pour une inconnue. Prenons un problème tout simple d'optimisation\n", "\n", "$$ \\max_x x (a - b x) $$\n", "\n", "Bien sur la CPO de ce problème est \n", "\n", "$$ a-2bx = 0 $$\n", "\n", "et donc la solution est $x^* = \\frac{a}{2b}$. C'est la solution analytique. On peut la programmer directement:\n" ], "metadata": {} }, { "cell_type": "code", "execution_count": 1, "source": [ "def xstar(a,b):\n", "\treturn a/2*b\n", "\n", "xstar(10,1)\n", "\n" ], "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "5.0" ] }, "metadata": {}, "execution_count": 1 } ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Parfois, la solution n'est pas disponible analytiquement. Alors on a le problème \n", "\n", "$$ \\max_x g(x) $$\n", "\n", "Et donc la CPO\n", "\n", "$$ g'_x(x^*) = 0 $$\n", "\n", "Comment résoudre ce problème?" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "## Résoudre par la condition de premier ordre\n", "\n", "D'abord, on peut résoudre la condition de premier ordre si celle-ci est disponible analytiquement. On utilise alors le module `scipy` et en particulier son sous-module optimize. Une algorithme simple qui permet de résoudre cette équation est la bisection (`bisect`):" ], "metadata": {} }, { "cell_type": "code", "execution_count": 2, "source": [ "from scipy.optimize import bisect" ], "outputs": [], "metadata": {} }, { "cell_type": "markdown", "source": [ "Utilisons l'exemple ici-haut, on a " ], "metadata": {} }, { "cell_type": "code", "execution_count": 3, "source": [ "def g(x,a,b):\n", "\treturn a - 2*b*x" ], "outputs": [], "metadata": {} }, { "cell_type": "markdown", "source": [ "On utilise `partial` de functools pour concentrer les arguments" ], "metadata": {} }, { "cell_type": "code", "execution_count": 4, "source": [ "from functools import partial\n", "\n", "f = partial(g,a=10,b=1)" ], "outputs": [], "metadata": {} }, { "cell_type": "markdown", "source": [ "Ne reste qu'à trouver le zéro de cette fonction avec bisect: " ], "metadata": {} }, { "cell_type": "code", "execution_count": 5, "source": [ "bisect(f,0,10)" ], "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "5.0" ] }, "metadata": {}, "execution_count": 5 } ], "metadata": {} }, { "cell_type": "markdown", "source": [ "On peut encapsuler tout ceci dans une fonction" ], "metadata": {} }, { "cell_type": "code", "execution_count": 7, "source": [ "def xstar(a,b):\n", "\tf = partial(g,a=a,b=b)\n", "\treturn bisect(f,0,a)\n", "\n", "xstar(10,1)" ], "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "5.0" ] }, "metadata": {}, "execution_count": 7 } ], "metadata": {} }, { "cell_type": "markdown", "source": [ "## Optimiser directement\n", "\n", "Le module `scipy` a des fonctions pour minimiser. Si on veut maximiser, on a qu'a minimiser le négatif d'une fonction, \n", "\n", "$$ \\argmax_x f(x) = \\argmin_x -f(x) $$\n", "\n", "Alors, on utilise la fonction `minimize_scalar`:" ], "metadata": {} }, { "cell_type": "code", "execution_count": 14, "source": [ "from scipy.optimize import minimize_scalar" ], "outputs": [], "metadata": {} }, { "cell_type": "code", "execution_count": 15, "source": [ "def g(x,a,b):\n", "\treturn x*(a - b*x)" ], "outputs": [], "metadata": {} }, { "cell_type": "code", "execution_count": 16, "source": [ "f = partial(g,a=10,b=1)" ], "outputs": [], "metadata": {} }, { "cell_type": "markdown", "source": [ "Pour changer le signe de la fonction, on en fait une nouvelle à l'aide de la commande pour créer des fonctions simples `lambda`:" ], "metadata": {} }, { "cell_type": "code", "execution_count": 17, "source": [ "fm = lambda x: -f(x)" ], "outputs": [], "metadata": {} }, { "cell_type": "markdown", "source": [ "La fonction `minimize_scalar` retourne un objet qui contient la solution et d'autres informations. La variable x contient la solution. " ], "metadata": {} }, { "cell_type": "code", "execution_count": 20, "source": [ "opt = minimize_scalar(fm,bracket=[0,10])\n", "opt" ], "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ " fun: -25.0\n", " nfev: 9\n", " nit: 5\n", " success: True\n", " x: 5.0" ] }, "metadata": {}, "execution_count": 20 } ], "metadata": {} }, { "cell_type": "code", "execution_count": 21, "source": [ "opt.x" ], "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "5.0" ] }, "metadata": {}, "execution_count": 21 } ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Encapsulons:" ], "metadata": {} }, { "cell_type": "code", "execution_count": 22, "source": [ "def xstar(a,b):\n", "\tf = partial(g,a=10,b=1)\n", "\tfm = lambda x: -f(x)\n", "\topt = minimize_scalar(fm,bracket=[0,a])\n", "\treturn opt.x\n", "\t" ], "outputs": [], "metadata": {} }, { "cell_type": "code", "execution_count": 23, "source": [ "xstar(10.0,1.0)" ], "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "5.0" ] }, "metadata": {}, "execution_count": 23 } ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Les fonctions d'optimisation de `scipy` sont puissantes et nombreuses. La fonction `minimize` permet de trouver des optimums avec plusieurs variables. Il existe aussi des packages plus puissant, tel que `nlopt`, qui peuvent aider avec les problèmes plus complexes." ], "metadata": {} } ], "metadata": { "orig_nbformat": 4, "language_info": { "name": "python", "version": "3.8.5", "mimetype": "text/x-python", "codemirror_mode": { "name": "ipython", "version": 3 }, "pygments_lexer": "ipython3", "nbconvert_exporter": "python", "file_extension": ".py" }, "kernelspec": { "name": "python3", "display_name": "Python 3.8.5 64-bit ('base': conda)" }, "interpreter": { "hash": "ba2340ab882356406e091df0706039b4b3cc5191eef6c073d3fb97005dbe0324" } }, "nbformat": 4, "nbformat_minor": 2 }