{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "075806aa",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "c9235b01",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A l'itété 0, on trouve x=[-0.2  -0.42]\n",
      "A l'itété 1, on trouve x=[ 0.148  -0.2112]\n",
      "A l'itété 2, on trouve x=[ 0.27328  -0.136032]\n",
      "A l'itété 3, on trouve x=[ 0.3183808  -0.10897152]\n",
      "A l'itété 4, on trouve x=[ 0.33461709 -0.09922975]\n",
      "A l'itété 5, on trouve x=[ 0.34046215 -0.09572271]\n",
      "A l'itété 6, on trouve x=[ 0.34256637 -0.09446018]\n",
      "A l'itété 7, on trouve x=[ 0.34332389 -0.09400566]\n",
      "A l'itété 8, on trouve x=[ 0.3435966  -0.09384204]\n",
      "A l'itété 9, on trouve x=[ 0.34369478 -0.09378313]\n"
     ]
    }
   ],
   "source": [
    "# Un premier exemple de descente par coordonnées\n",
    "\n",
    "# Itéré intial\n",
    "x = np.array([-1/2, -1])\n",
    "\n",
    "maxiter = 10\n",
    "for k in range(maxiter):\n",
    "    #On mets (de façon optimale) x1\n",
    "    x[0] = (6*x[1]+4)/10\n",
    "    #On mets (de façon optimale) x2\n",
    "    x[1] = (6*x[0]-3)/10\n",
    "    print(f\"A l'itété {k}, on trouve x={x}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "999a5a80",
   "metadata": {},
   "outputs": [],
   "source": [
    "def CDquadratic(Q,c,p,x,maxiter=10**2):\n",
    "    # Ce code applique la méthode de descente par coordonnées\n",
    "    # au problème min_x 0.5 x'*Q*x-c'*x+p\n",
    "    # Le x fournit en paramètre est l'itéré initial\n",
    "    # Q nous est donnée sous forme symétrique\n",
    "    n = len(x)\n",
    "    # Une itération coûte O(n^2)\n",
    "    for k in range(maxiter):\n",
    "        # Dans cette boucle, on mets les variables à jour\n",
    "        for i in range(n):\n",
    "            somme = 0\n",
    "            for j in range(n):\n",
    "                if not j==i:\n",
    "                    somme += Q[i,j]*x[j]\n",
    "            x[i] = (c[i]-somme)/Q[i,i]\n",
    "        print(f\"A l'itété {k}, on trouve x={x}\")\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d7a850ff",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A l'itété 0, on trouve x=[-0.2  -0.42]\n",
      "A l'itété 1, on trouve x=[ 0.148  -0.2112]\n",
      "A l'itété 2, on trouve x=[ 0.27328  -0.136032]\n",
      "A l'itété 3, on trouve x=[ 0.3183808  -0.10897152]\n",
      "A l'itété 4, on trouve x=[ 0.33461709 -0.09922975]\n",
      "A l'itété 5, on trouve x=[ 0.34046215 -0.09572271]\n",
      "A l'itété 6, on trouve x=[ 0.34256637 -0.09446018]\n",
      "A l'itété 7, on trouve x=[ 0.34332389 -0.09400566]\n",
      "A l'itété 8, on trouve x=[ 0.3435966  -0.09384204]\n",
      "A l'itété 9, on trouve x=[ 0.34369478 -0.09378313]\n"
     ]
    }
   ],
   "source": [
    "Q = np.array([[10, -6],[-6, 10]])\n",
    "c = np.array([4, -3])\n",
    "p = 0\n",
    "x = np.array([-1/2, -1])\n",
    "xopt = CDquadratic(Q,c,p,x,10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "960500d8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def leastsquares(A,b,x,maxiter=10**2):\n",
    "    Q = 2*A.T@A\n",
    "    c = 2*A.T@b\n",
    "    p = b.T@b\n",
    "    x = CDquadratic(Q,c,p,x,maxiter)\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "560043ef",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A l'itété 0, on trouve x=[ 0.  -0.5]\n",
      "A l'itété 1, on trouve x=[ 0.25  -0.625]\n",
      "A l'itété 2, on trouve x=[ 0.3125  -0.65625]\n",
      "A l'itété 3, on trouve x=[ 0.328125  -0.6640625]\n",
      "A l'itété 4, on trouve x=[ 0.33203125 -0.66601562]\n",
      "A l'itété 5, on trouve x=[ 0.33300781 -0.66650391]\n",
      "A l'itété 6, on trouve x=[ 0.33325195 -0.66662598]\n",
      "A l'itété 7, on trouve x=[ 0.33331299 -0.66665649]\n",
      "A l'itété 8, on trouve x=[ 0.33332825 -0.66666412]\n",
      "A l'itété 9, on trouve x=[ 0.33333206 -0.66666603]\n"
     ]
    }
   ],
   "source": [
    "A = np.array([[1,0], [0,1], [1,1]])\n",
    "b = np.array([3,2,-3])\n",
    "x = np.array([1.0, 0.0]) # Attention au entiers\n",
    "xopt = leastsquares(A,b,x,10)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "optinonlin",
   "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.13.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
