3_Non-negative_Least_Squares.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<table>\n",
    "<tr>\n",
    "<td width=15%><img src=\"./img/UGA.png\"></img></td>\n",
    "<td><center><h1>Introduction à la Recherche Opérationelle</h1><br/>M2 Statistique Science des Données (SSD)</center></td>\n",
    "<td width=15%>\n",
    "<a href=\"https://www-ljk.imag.fr/membres/Anatoli.Iouditski/\" style=\"font-size: 16px; font-weight: bold\">Anatoli Juditsky</a><br/>\n",
    "<a href=\"http://www.iutzeler.org\" style=\"font-size: 16px; font-weight: bold\">Franck Iutzeler</a> </td>\n",
    "</tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br/><br/>\n",
    "<center><a style=\"font-size: 30pt; font-weight: bold\">TP 3 - Moindres Carrés Positifs </a></center>\n",
    "<br/><br/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1- Problème de régression positive\n",
    "\n",
    "On considère le modèle de régression normale\n",
    "$$ y=X\\theta+\\sigma\\xi,\\;\\;\\xi\\sim \\mathcal{N}(0, I_m),$$\n",
    "où  $X\\in \\mathbb{R}^{m\\times n}$ et $y\\in \\mathbb{R}^m$ sont les observables, et $\\theta\\in \\mathbb{R}_+^n$ est le paramètre inconnu.\n",
    "\n",
    "Dans les moindres carrés positifs, on modélise $\\theta$ comme un vecteur à valeurs positives et donc on ne cherche que les solutions positives du problème des moindres carrés. On veut donc résoudre le problème d'optimisation:\n",
    "$$\\tag{P1} \\min_{\\theta\\in  \\mathbb{R}^n} \\|X\\theta-y\\|_2^2,~~~\\;\\mbox{sous contrainte}\\;\\theta\\geq0.$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exemple de données pour tester votre code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exemple jouet\n",
    "import numpy as np\n",
    "\n",
    "n = 10\n",
    "m = 20\n",
    "sigma = 0.1\n",
    "\n",
    "X = np.random.randn(m,n)\n",
    "\n",
    "theta_true = np.random.rand(n)\n",
    "\n",
    "xi = np.random.randn(m)\n",
    "y = np.dot(X,theta_true) + sigma*xi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2- Résolution du problème\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> **Question:** Écrivez une fonction qui résoud le problème (P1) de régression positive à partir de `X` et `y`. Testez la sur l'exemple ci-dessus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3- Ajout de contraintes\n",
    "\n",
    "Afin d'améliorer la stabilité du modèle, on décide d'ajouter la contrainte que la somme des valeurs de theta ne doit pas dépasser une constante $S$. le problème devient alors\n",
    "$$\\tag{P2} \\min_{\\theta\\in  \\mathbb{R}^n} \\|X\\theta-y\\|_2^2,~~~\\;\\mbox{sous contrainte}\\;\\theta\\geq0 \\text{ et } \\sum_{i=1}^n \\theta_i \\leq S.$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> **Question:** Écrivez une fonction qui résoud le problème (P2) à partir de `X`, `y`, et `S`. Testez la sur l'exemple ci-dessus avec $S=1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> **Question:** Faites varier $S$. Est-ce que la valeur du problème change? Est-ce que la solution change? Est-ce que le problème reste faisable?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4- Observation des variables duales\n",
    "\n",
    "> **Question:** Écrivez une fonction qui résoud le problème (P2) à partir de `X`, `y`, et `S` et qui retourne la solution ainsi que les variables duales du problème"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> **Question:** Pour différentes valeurs de $S$, observez quelles sont les contraintes actives et non-actives. Mettez en relation vos observations avec la valeur de la solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.8.10"
  },
  "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": 1
}