{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hard nonlinear complementarity problem with Billup's function\n",
    "\n",
    "**Randall Romero Aguilar, PhD**\n",
    "\n",
    "This demo is based on the original Matlab demo accompanying the  <a href=\"https://mitpress.mit.edu/books/applied-computational-economics-and-finance\">Computational Economics and Finance</a> 2001 textbook by Mario Miranda and Paul Fackler.\n",
    "\n",
    "Original (Matlab) CompEcon file: **demslv09.m**\n",
    "\n",
    "Running this file requires the Python version of CompEcon. This can be installed with pip by running\n",
    "\n",
    "    !pip install compecon --upgrade\n",
    "\n",
    "<i>Last updated: 2022-Sept-05</i>\n",
    "<hr>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## About\n",
    "\n",
    "Solve hard nonlinear complementarity problem on R using semismooth and minmax methods.  Problem involves Billup's function.  Minmax formulation fails semismooth formulation suceeds.\n",
    "\n",
    "The function to be solved is $$f(x) = 1.01 - (1- x)^2$$\n",
    "where $x \\geq 0$. Notice that $f(x)$ has roots $1\\pm\\sqrt{1.01}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Preliminary tasks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "from numpy.linalg import norm\n",
    "from compecon import MCP, tic, toc, nodeunif"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Billup's function roots are"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "roots = 1 + np.sqrt(1.01), 1 - np.sqrt(1.01)\n",
    "print(roots)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Set up the problem\n",
    "The class **MCP** is used to represent mixed-complementarity problems. To create one instance, we define the objective function and the boundaries $a$ and $b$ such that for $a \\leq x \\leq b$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def billups(x):\n",
    "    fval = 1.01 - (1 - x) ** 2\n",
    "    return fval, 2*(1 - x )\n",
    "\n",
    "a = 0\n",
    "b = np.inf\n",
    "\n",
    "Billups = MCP(billups, a, b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solve by applying Newton method\n",
    "* Using minmax formulation\n",
    "Initial guess is $x=0$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t1 = tic()\n",
    "x1 = Billups.newton(0.0, transform='minmax')\n",
    "t1 = 100*toc(t1)\n",
    "n1 = norm(Billups.minmax(x1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Using semismooth formulation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t2 = tic()\n",
    "x2 = Billups.newton(0.0, transform='ssmooth')\n",
    "t2 = 100*toc(t2)\n",
    "n2 = norm(Billups.minmax(x2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Print results\n",
    "Hundreds of seconds required to solve hard nonlinear complementarity problem using Newton minmax and semismooth formulations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "results = pd.DataFrame.from_records(\n",
    "    [('Newton minmax',t1, n1, x1), \n",
    "     ('Newton semismooth', t2, n2, x2)],\n",
    "    columns = ['Algorithm', 'Time', 'Norm', 'x']\n",
    "    ).set_index('Algorithm')\n",
    "\n",
    "results.style.format(precision=3, subset=['Time', 'x'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Plot results\n",
    "Here we use the methods *ssmooth* and *minmax* from class **MCP** to compute the semi-smooth and minimax transformations. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "original = {'label':'Original', 'alpha':0.5, 'color':'gray'}\n",
    "xls = [[-0.5, 2.5], [-0.035, 0.035]]\n",
    "yls = [[-1, 1.5], [-0.01, 0.06]]\n",
    "ttls = 'Difficult NCP', 'Difficult NCP Magnified'\n",
    "\n",
    "fig, axs = plt.subplots(1, 2, figsize=[12,6])\n",
    "for xl, yl, ttl, ax in zip(xls, yls, ttls, axs):\n",
    "    a, b = xl\n",
    "    x = np.linspace(a, b, 500)\n",
    "    ax.set(title=ttl,\n",
    "           xlabel='x',\n",
    "           ylabel='',\n",
    "           xlim=xl,\n",
    "           ylim=yl,\n",
    "           aspect=1)\n",
    "    ax.hlines(0, a, b, 'gray', '--')\n",
    "    ax.plot(x, billups(x)[0], **original)\n",
    "    ax.plot(x, Billups.ssmooth(x), label='Semismooth')\n",
    "    ax.plot(x, Billups.minmax(x), label='Minmax')\n",
    "    ax.legend(loc='best')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.7 ('base')",
   "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.9.7"
  },
  "vscode": {
   "interpreter": {
    "hash": "ad2bdc8ecc057115af97d19610ffacc2b4e99fae6737bb82f5d7fb13d2f2c186"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}