<commit_before>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Notas para contenedor de docker:**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comando de docker para ejecución de la nota de forma local:\n",
    "\n",
    "nota: cambiar `<ruta a mi directorio>` por la ruta de directorio que se desea mapear a `/datos` dentro del contenedor de docker.\n",
    "\n",
    "```\n",
    "docker run --rm -v <ruta a mi directorio>:/datos --name jupyterlab_numerical -p 8888:8888 -d palmoreck/jupyterlab_numerical:1.1.0\n",
    "```\n",
    "\n",
    "password para jupyterlab: `<PASSWORD>",
    "\n",
    "Detener el contenedor de docker:\n",
    "\n",
    "```\n",
    "docker stop jupyterlab_numerical\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Documentación de la imagen de docker `palmoreck/jupyterlab_numerical:1.1.0` en [liga](https://github.com/palmoreck/dockerfiles/tree/master/jupyterlab/numerical)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nota generada a partir de [liga1](https://drive.google.com/file/d/1zCIHNAxe5Shc36Qo0XjehHgwrafKSJ_t/view), [liga2](https://drive.google.com/file/d/12L7rOCgW7NEKl_xJbIGZz05XXVrOaPBz/view)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Dando click en: [![Binder](https://mybinder.org/badge_logo.svg)](https://mybinder.org/v2/gh/palmoreck/dockerfiles-for-binder/jupyterlab_numerical?urlpath=lab/tree/analisis-numerico-computo-cientifico/temas/IV.optimizacion_convexa_y_machine_learning/4.4.Metodo_de_Newton_para_puntos_iniciales_factibles_Python.ipynb) se ejecuta la nota de forma interactiva**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[33m  WARNING: The scripts futurize and pasteurize are installed in '/home/miuser/.local/bin' which is not on PATH.\n",
      "  Consider adding this directory to PATH or, if you prefer to suppress this warning, use --no-warn-script-location.\u001b[0m\n",
      "\u001b[33mWARNING: You are using pip version 19.3.1; however, version 20.1.1 is available.\n",
      "You should consider upgrading via the 'pip install --upgrade pip' command.\u001b[0m\n"
     ]
    }
   ],
   "source": [
    "!pip3 install --user -q cvxpy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En esta nota se consideran resolver problemas de optimización con restricciones lineales de igualdad de la forma:\n",
    "\n",
    "$$\\min f_o(x)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\text{sujeto a:} Ax=b$$\n",
    "\n",
    "con variable de optimización $x \\in \\mathbb{R}^{n}$ y $A \\in \\mathbb{R}^{p \\times n}, b \\in \\mathbb{R}^p$ conocidos. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Se asume lo siguiente:\n",
    "\n",
    "* $f:\\mathbb{R}^n \\rightarrow \\mathbb{R}$ convexa y $\\mathcal{C}^2(\\text{dom}f_o)$.\n",
    "\n",
    "* $rank(A) = p < n$: tenemos menos restricciones que variables y los renglones de $A$ son linealmente independientes. \n",
    "\n",
    "* Existe un punto óptimo $x^*$ por lo que el problema tiene solución y el valor óptimo se denota por $p^* = f_o(x^*) = \\inf f_o(x)$.\n",
    "\n",
    "* Los puntos iniciales $x^{(0)}$ de los métodos iterativos están en $\\text{dom}f_o$ y los conjuntos $f_o(x^{(0)})$-subnivel son conjuntos cerrados.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Método de Newton aplicado a las [condiciones de Karush-Kuhn-Tucker](https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions) (KKT) de optimalidad"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> **Algoritmo**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Se comparan los resultados del **paquete [cvxpy](https://github.com/cvxgrp/cvxpy)** con los obtenidos en la implementación hecha por el prof en [algoritmos/Python](algoritmos/Python), en específico [algoritmos/Python/algorithms_for_ceco.py](https://github.com/ITAM-DS/analisis-numerico-computo-cientifico/blob/master/temas/IV.optimizacion_convexa_y_machine_learning/algoritmos/Python/algorithms_for_ceco.py) para problemas tipo CECO (*Constrained Equality Convex Optimization*)"
   ]
  },
  {<commit_msg>adding Newtons method description<commit_after>{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Notas para contenedor de docker:**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comando de docker para ejecución de la nota de forma local:\n",
    "\n",
    "nota: cambiar `<ruta a mi directorio>` por la ruta de directorio que se desea mapear a `/datos` dentro del contenedor de docker.\n",
    "\n",
    "```\n",
    "docker run --rm -v <ruta a mi directorio>:/datos --name jupyterlab_numerical -p 8888:8888 -d palmoreck/jupyterlab_numerical:1.1.0\n",
    "```\n",
    "\n",
    "password para jupyterlab: `<PASSWORD>",
    "\n",
    "Detener el contenedor de docker:\n",
    "\n",
    "```\n",
    "docker stop jupyterlab_numerical\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Documentación de la imagen de docker `palmoreck/jupyterlab_numerical:1.1.0` en [liga](https://github.com/palmoreck/dockerfiles/tree/master/jupyterlab/numerical)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nota generada a partir de [liga1](https://drive.google.com/file/d/1zCIHNAxe5Shc36Qo0XjehHgwrafKSJ_t/view), [liga2](https://drive.google.com/file/d/12L7rOCgW7NEKl_xJbIGZz05XXVrOaPBz/view)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Dando click en: [![Binder](https://mybinder.org/badge_logo.svg)](https://mybinder.org/v2/gh/palmoreck/dockerfiles-for-binder/jupyterlab_numerical?urlpath=lab/tree/analisis-numerico-computo-cientifico/temas/IV.optimizacion_convexa_y_machine_learning/4.4.Metodo_de_Newton_para_puntos_iniciales_factibles_Python.ipynb) se ejecuta la nota de forma interactiva**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\u001b[33m  WARNING: The scripts futurize and pasteurize are installed in '/home/miuser/.local/bin' which is not on PATH.\n",
      "  Consider adding this directory to PATH or, if you prefer to suppress this warning, use --no-warn-script-location.\u001b[0m\n",
      "\u001b[33mWARNING: You are using pip version 19.3.1; however, version 20.1.1 is available.\n",
      "You should consider upgrading via the 'pip install --upgrade pip' command.\u001b[0m\n"
     ]
    }
   ],
   "source": [
    "!pip3 install --user -q cvxpy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En esta nota se consideran resolver problemas de optimización con restricciones lineales de igualdad de la forma:\n",
    "\n",
    "$$\\min f_o(x)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\text{sujeto a:} Ax=b$$\n",
    "\n",
    "con variable de optimización $x \\in \\mathbb{R}^{n}$ y $A \\in \\mathbb{R}^{p \\times n}, b \\in \\mathbb{R}^p$ conocidos. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Se asume lo siguiente:\n",
    "\n",
    "* $f:\\mathbb{R}^n \\rightarrow \\mathbb{R}$ convexa y $\\mathcal{C}^2(\\text{dom}f_o)$.\n",
    "\n",
    "* $rank(A) = p < n$: tenemos menos restricciones que variables y los renglones de $A$ son linealmente independientes. \n",
    "\n",
    "* Existe un punto óptimo $x^*$ por lo que el problema tiene solución y el valor óptimo se denota por $p^* = f_o(x^*) = \\inf f_o(x)$.\n",
    "\n",
    "* Los puntos iniciales $x^{(0)}$ de los métodos iterativos están en $\\text{dom}f_o$ y los conjuntos $f_o(x^{(0)})$-subnivel son conjuntos cerrados.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Método de Newton aplicado a las [condiciones de Karush-Kuhn-Tucker](https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions) (KKT) de optimalidad"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">**Algoritmo de Newton con punto inicial factible para problemas de optimización con restricciones de igualdad lineales**\n",
    ">> **Dados** un **punto inicial** $x$ en $\\text{dom}f_o$ con $Ax=b$ y una tolerancia $\\epsilon >0$.\n",
    "\n",
    ">> **Repetir** el siguiente bloque para $k=0,1,2,...$\n",
    "\n",
    ">>> 1. Calcular la dirección de descenso de Newton $\\Delta x_{\\text{nt}}$ y el decremento de Newton al cuadrado: $\\lambda^2 (x)$.\n",
    ">>> 2. Criterio de paro: finalizar el método si $\\frac{\\lambda^2(x)}{2} \\leq \\epsilon$.\n",
    ">>> 3. Búsqueda de línea. Elegir un tamaño de paso $t > 0$ (usar el cálculo de $\\lambda^2 (x)$ del paso anterior).\n",
    ">>> 3. Hacer la actualización: $x = x + t\\Delta x_{\\text{nt}}$.\n",
    "\n",
    ">> **hasta** convergencia (satisfacer criterio de paro).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Se comparan los resultados del **paquete [cvxpy](https://github.com/cvxgrp/cvxpy)** con los obtenidos en la implementación hecha por el prof en [algoritmos/Python](algoritmos/Python), en específico [algoritmos/Python/algorithms_for_ceco.py](https://github.com/ITAM-DS/analisis-numerico-computo-cientifico/blob/master/temas/IV.optimizacion_convexa_y_machine_learning/algoritmos/Python/algorithms_for_ceco.py) para problemas tipo CECO (*Constrained Equality Convex Optimization*)"
   ]
  },
  {
{'fraction_non_alphanumeric': 0.1850202829721975, 'fraction_numerical': 0.01553378846344118, 'mean_word_length': 3.2081598667776854, 'pattern_counts': {'":': 90, '<': 11, '<?xml version=': 0, '>': 31, 'https://': 16, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4236348', 'n_tokens_mistral': 4055, 'n_tokens_neox': 3888, 'n_words': 861}