optimization-basics.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Optimization Basics\n",
    "\n",
    "In this seminar you will learn about the basics of optimizations and their applications. This notebook explores:\n",
    "- what an optimization problem is\n",
    "- structuring a objective function\n",
    "- convexity, optimality and extremum\n",
    "- basic gradient descent algorithm\n",
    "\n",
    "In this example we will fit a simple polynomial:\n",
    "$$f_c(x) = c_1x^2 + c_2x + c_3$$\n",
    "where $c$ is the vector of coefficients that are to be found.\n",
    "\n",
    "Our task is to find the most likely values of $c$ given a set $P$ of sampling from the image of $f$ corrupted by guassian noise. To structure this as an optimization problem, we incorporate the _mean square error_ as a measurement of \"how far off\" $f_c$ is given an arbitrary $c$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "# dependencies\n",
    "\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Library/Frameworks/Python.framework/Versions/3.7/lib/python3.7/site-packages/ipykernel_launcher.py:6: VisibleDeprecationWarning: Creating an ndarray from ragged nested sequences (which is a list-or-tuple of lists-or-tuples-or ndarrays with different lengths or shapes) is deprecated. If you meant to do this, you must specify 'dtype=object' when creating the ndarray\n",
      "  \n"
     ]
    }
   ],
   "source": [
    "# initializing parameters\n",
    "\n",
    "np.random.seed(420)\n",
    "\n",
    "c = np.random.rand(3) * 10\n",
    "f = lambda x, c=c: c.dot(np.array([x ** 2, x, 1]))\n",
    "\n",
    "data_x = np.linspace(-15, 15, 75)\n",
    "data_y = f(data_x) + np.random.randn(*data_x.shape) * 50"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD4CAYAAAAXUaZHAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAYo0lEQVR4nO3df5BdZX3H8fc3m0UXW1mEHQY2pEk1wtBmNLiDdNI6AlZ+dZoYfwyd/mAcZlJnoLXiUEP/aLUznaylLdWOpZOKNY4/EBEhCiNagnXqDNSNQSH8GFcQyBog2iztmK3ZJN/+cc+Gm5tz7zn33vPzOZ/XTGbvPefe3efs5n7Pc77P93mOuTsiIhKWZWU3QEREsqfgLiISIAV3EZEAKbiLiARIwV1EJEDLy24AwOmnn+6rVq0quxkiIrWya9eun7r7RNy+SgT3VatWMTMzU3YzRERqxcye6bZPaRkRkQApuIuIBEjBXUQkQAruIiIBUnAXEQlQJaplRESa5q7dc9x035P8ZH6Bs8bHuOHSc9i4bjKz76/gLiJSsLt2z3HjnY+wsHgEgLn5BW688xGAzAK80jIiIgW76b4njwX2JQuLR7jpvicz+xkK7iIiBfvJ/EJf2weRKrib2QfMbI+ZPWpmXzCzV5rZajN7yMxmzeyLZnZS9NpXRM9no/2rMmutiEgAzhof62v7IBKDu5lNAn8KTLn7rwMjwFXAR4Gb3f11wAHgmugt1wAHou03R68TEZHIDZeew9joyHHbxkZHuOHSczL7GWnTMsuBMTNbDpwM7AMuBu6I9m8HNkaPN0TPifZfYmaWSWtFRAKwcd0kWzetZXJ8DAMmx8fYumltsdUy7j5nZn8HPAssAN8AdgHz7n44etleYKlVk8Bz0XsPm9lLwGnAT9u/r5ltBjYDrFy5cvgjERGpkY3rJjMN5p3SpGVOpdUbXw2cBbwKuGzYH+zu29x9yt2nJiZiV6wUEZEBpUnLvA142t33u/sicCewHhiP0jQAK4C56PEccDZAtP8U4GeZtlpERHpKE9yfBS40s5Oj3PklwGPAA8C7otdcDdwdPd4RPSfav9PdPbsmi4hIksTg7u4P0RoY/R7wSPSebcCHgOvNbJZWTv3W6C23AqdF268HtuTQbhER6cGq0Kmemppy3YlJRKQ/ZrbL3afi9mmGqohIgLRwmIhIAfJeBbKTgruISM6KWAWyk9IyIiI5K2IVyE4K7iIiOStiFchOCu4iIjkrYhXITgruIiI5K2IVyE4aUBURydnSoKmqZUREApP3KpCdlJYREQmQgruISIAU3EVEAqScu4hIxopeaiCOgruISIbKWGogjtIyIiIZKmOpgTgK7iIiGSpjqYE4Cu4iIhkqY6mBOAruIiIZKmOpgTgaUBURyVAZSw3EUXAXEclY0UsNxAkmuFehrlREpCqCCO5VqSsVEamKIAZUq1JXKiJSFUEE96rUlYqIVEUQaZmzxseYiwnkRdeVikgzVXHML4iee1XqSkWkeZbG/ObmF3BeHvO7a/dcqe0KIrhvXDfJ1k1rmRwfw4DJ8TG2blpb+plTRMJX1TG/INIyUI26UhFpnqqO+QUT3EVEitKeY19mxhH3E15T9pifgruISB8659XEBfYqjPkpuIuI9CEuxw4wYsZR98pUyyi4i4j0oVsu/ag7T09fWXBruguiWkZEpChVWa89iXruIiIJ2gdQTxkbZXTEWDzycq69Cjn2TgruIiI9dA6gzi8sMrrMOPXkUeYPLlYmx95JwV1EpIe4AdTFo87JJy1n91++vaRWJVPOXUSkh6pOUkqSKrib2biZ3WFmT5jZ42b2G2b2GjP7ppn9MPp6avRaM7OPm9msmf3AzM7P9xBERPJTlwHUTml77h8Dvu7u5wJvAB4HtgD3u/sa4P7oOcDlwJro32bglkxbLCJSoLouTJgY3M3sFOAtwK0A7n7I3eeBDcD26GXbgY3R4w3AZ7zlQWDczM7MuN0iIoWo68KEaQZUVwP7gX8zszcAu4D3A2e4+77oNc8DZ0SPJ4Hn2t6/N9q2r20bZraZVs+elStXDtp+EZHc1XFhwjRpmeXA+cAt7r4O+Dkvp2AAcHcHTlxgoQd33+buU+4+NTEx0c9bU7tr9xzrp3eyess9rJ/eWfr6yiIiRUkT3PcCe939oej5HbSC/QtL6Zbo64vR/jng7Lb3r4i2FaqqC+iLiBQhMbi7+/PAc2a2NHpwCfAYsAO4Otp2NXB39HgH8EdR1cyFwEtt6ZvMJPXKq7qAvohIEdJOYvoT4HNmdhLwFPBeWieG283sGuAZ4D3Ra+8FrgBmgYPRazPVOWNsqVcOHMuL1bU2VUQkC6mCu7s/DEzF7Lok5rUOXDtcs3rr1StfCu66abaINFktZ6im6ZXXtTZVRCQLtQzuaWaM1bU2VUQkC7VcOOyGS885LucO8b3yOtamiohkoZbBfSlgL62vXNUlN0VEylLL4A7qlYuI9FLLnLuIiPSm4C4iEqDapmVERPLSfs/Uuo7pKbiLiLRJMwO+DpSWERFpE8q6VAruIiJtQlmXSsFdRKRNXe+Z2qlRwV037xCRJKGsS9WYAdVQBklEJF+hzIBvTHBPs0ywiAiEMQO+McE9lEESERleCHXsSRqTcw9lkEREhtOU+ys3JrinGSTRgKtI+EKpY0/SmLRM0iBJ3IDrDV/6Ph/56h7mDy4Ge+km0jRNSdE2JrhD70GSuLP54lHnwMFFQNU1IqFoyv2VG5OWSZLmrB3ipZtI04RSx56kUT33Tu0j5svMOOKe+J7QLt1EmiYuRXvRuRPcdN+TfOCLDweTgm1scO/MsacJ7BDepZtIE7WnaEOd4NjYtExcjh1gxAwDxsdGGR2x4/aFeOkm0gS9KuFCrZ5pbM+9W3rlqDtPT18JNGOig0joknrmoVbPNDa4pxkxD2EKskjTJS09Emr1TGPTMk0ZMRdpuqSeeaixoLE991BWfhOR3pJ65qHGAvOUVSJ5mpqa8pmZmbKbISIB6sy5Q6tnvnXT2voHcLNd7j4Vt6+xPXcRCVdnMcQ73zTJA0/sD6pnnkTBXUSCElcd8+Vdc0H01PvR2AFVEQlTqHXr/VJwF5GghFq33i8FdxEJim7M06LgLiJBCbVuvV8aUM2Rli8QKV6odev9UnDPSagrzYnUgZYO6SMtY2YjZrbbzL4WPV9tZg+Z2ayZfdHMToq2vyJ6PhvtX5VT2ytNI/YiUqZ+cu7vBx5ve/5R4GZ3fx1wALgm2n4NcCDafnP0usbRiL2IlClVcDezFcCVwCej5wZcDNwRvWQ7sDF6vCF6TrT/kuj1jaIRexEpU9qe+z8Cfw4cjZ6fBsy7++Ho+V5gKcE1CTwHEO1/KXr9ccxss5nNmNnM/v37B2t9hWnEXkTKlDigama/A7zo7rvM7K1Z/WB33wZsg9bCYVl93yL1qobRiL2IlClNtcx64HfN7ArglcCrgY8B42a2POqdrwCW7ls1B5wN7DWz5cApwM8yb3kJ2oP5KWOj/PzQYRaPtM5LcdUwGrEXkbIkpmXc/UZ3X+Huq4CrgJ3u/vvAA8C7opddDdwdPd4RPSfav9OrsK7wkJZKG+fmF3BgfmHxWGBfomoYEamKYWaofgi43sxmaeXUb4223wqcFm2/HtgyXBOrodsNtTupGkZEqqCvSUzu/i3gW9Hjp4ALYl7zf8C7M2hbpaQN2qqGEZEq0NoyKaUJ2qqGEZGqUHBPKa60cXSZcerJoxgwOT7WuJsBiEh1aW2ZlFTaKCJ1ouDeB5U2ikhdKC0jIhIg9dwzpPXbRaQqFNwzovXbRaRKlJbJiNZvF5EqUc89I1q/XaQcSofGU889I1q/XaR4nWs+LaVD79o9l/je0Cm4Z0Trt4sUT+nQ7pSWyYgmOYkMZpi0itKh3Sm4Z0iTnET6M2yV2VnjY8zFBHKlQ5WWEZESDZtWUTq0O/XcC9Z5CXrRuRM88MR+pXKkkYZNqygd2p2Ce4HiLkE/++Czx/Zr4pM0TRZpFaVD4yktU6A0d3PSSL80idIq+VHPvUBpLzU10i9NobRKfhTcC9TtErTTMjNWb7lH/9GlEfpNq2hGajpKyxQo7hI0zhF3zbYTiaEZqekpuBdo47pJtm5ay+T42LFb8/3BhSuPPR8xO+E9C4tH+ODt32f1lntYP71T/4ml0TQjNT2lZQrW6xJ09ZZ7YrcfcQdUTSPN0Cvtohmp6Sm4V0ianPxSL0XBXUIUVy58w5e+z0e+uof5g4ssMzvW2WmnGaknUlqmQtLm5NVLkVDFpV0WjzoHDi7iEBvYVToZTz33CuksC1MvRZombcdlxIyj7qqW6UHBvWLac/Kdl6igXoqELW258FF3np6+soAW1ZfSMhUWV12zddNa9VKkVu7aPcf66Z2pKr7SpiZ19ZpMPfeK07oZUmf9LunbmZo8ZWyUnx86zOKRl9OTunpNR8FdRHLTqy69W6els0OjGamDUXAXkdxkUZeuq9fBKOcuIrnRjePLo+AuIrnRkr7lUVpGRHKjJX3Lo+AuIrlSzrwcSsuIiARIPXcRKZRKG4uR2HM3s7PN7AEze8zM9pjZ+6PtrzGzb5rZD6Ovp0bbzcw+bmazZvYDMzs/74MQkXrQzTaKkyYtcxj4oLufB1wIXGtm5wFbgPvdfQ1wf/Qc4HJgTfRvM3BL5q0WkVrSzTaKkxjc3X2fu38vevy/wOPAJLAB2B69bDuwMXq8AfiMtzwIjJvZmVk3XETqRzfbKE5fA6pmtgpYBzwEnOHu+6JdzwNnRI8ngefa3rY32tb5vTab2YyZzezfv7/fdotIDWlSU3FSB3cz+yXgy8Cfufv/tO9zdwdOXHi8B3ff5u5T7j41MTHRz1tFpKY0qak4qaplzGyUVmD/nLvfGW1+wczOdPd9UdrlxWj7HHB229tXRNtEpOE0qak4icHdzAy4FXjc3f+hbdcO4GpgOvp6d9v268zsNuDNwEtt6RsZksrIpO40qakYaXru64E/BB4xs4ejbX9BK6jfbmbXAM8A74n23QtcAcwCB4H3ZtngJut3bWwRaa7E4O7u/wlYl92XxLzegWuHbJfEGGRtbBFpJs1QrRGVkUkdKHVYDQruNdLt5sHtZWT6YEmZlDqsDi0cViNJZWRppnb3c7NikX5pBmp1qOdeI0llZEk5efWqpFPnld5F507wwBP7B77yU+qwOhTca6ZXGVnSB0sDstIu7mT/2QefPbY/7uSflPZLkzqUYigtE5Ckqd3qVUm7uJN9p/aUSpq0n2agVoeCe0CSPlha10PapT2pJ135fXjHnmPjODfd9yTvfNMkk+NjGDA5PsbWTWt1ZVgCpWUCkpSTv+HSc467DAf1qpqsWwol7nXQ/WQwv7DI/MIi0OrNf3nXnAJ6BSi4B6ZXTl7reki7uJN9p84rvzQnA43jVIOCe8NoXQ9ZEney71Utk+ZksETjOOVTcK85TVqSYfRzso87GRw8dJgDBxdPeK3Gccqn4F5jWdWt6wQhaXWeDDr/D4LGcapC1TI1lsVsQN2wWIaxcd0kWzetVXVMBannXmNp6taTeuVlTGzSlUJYNI5TTQruNZY0GzBN2qboiU1aAkGkGAruNZZUt56mV17EdPH2nvoyM4748bfbVenc4HQVJN0ouNdYUt16ml55FhObegWYzp56Z2CPa5Okk+YqSMG/uRTca65XvjNNr3zYiU1JASbN+iWdbZJ0ilgFVCeH+lJwD1jaXvkwA2JJASZNj1ylc4PJexVQjY/Um0ohA1ZEmVpSgOnWIx8x66tNusnIifJeBVQ33qg39dwDl3eZWlLqp9vVQz8nGfUg48X9bkeXGQcPHWb1lntiB68hfQpMS0TXm3ruMpSkZYazuHqoSg+yalcPnb/b8bFRMDhwcBEnfvC6nxSYloiuN/XcZShpBmSHvXqoQg9ykKuHIgYj23+366d3Hlt6t92IGUfd+26DloiuNwV3OUG/Qans1E8R+h2cLONk0O1kd9Sdp6evTP19lmiJ6HpTcJfjVLF8Lk0PMu9ecr9XD0WcDDrlcRLU0gL1pZy7HGfY/HYeC5El5e2LWPys3/xzlieDtNLcv7Rq4waSH/Xc5Th5ls8N0wPs1YMsYvGzfvPP3XrRy8xYveWegWYTJ0lKo6jqqFkU3OU4w17alzH4WcTP7Df/3O2uRUsVLJ2BNauUStknQakOBXc5TlLtdFJQGyRIDZsvzyPX3K1Ng961KGnBtCIqU6pQdSTFUc5djpNUO52Uz06T922XRb6835+ZJKsc/sZ1k3xny8U8PX0lRxMWTCtiNrHq1pvFvMt/uiJNTU35zMxM2c2QGOund8b2invVTvfTE+/2/SfHx/jOlotTtzPLaplB29SrDVkd5zC63RJPd06qLzPb5e5TcfuUlpGeul2yd8sdL31NGyy6ff+5+QXWT+8spdZ+kPRF0mBlFSYEqW69WRTcpadu+ex2wwzKdfv+Bse2F13VMUgOP2mwsiqBVXXrzaHgLj11q/roNOigXNz3N6AzWVhkVUfaXnZ7GqZbcrP996LAKkVScJee0lR9wOCDcnE92m5XCllWdfTKj6fpZcflr+NosFLKouAuidp7nN0G5YbJHXf2aLsNPmYVKNNM5knqZae5w5QW2ZIyqRRS+lJEyV7WpY2dspjq3+sqIq/fi0g/cum5m9llwMeAEeCT7j6dx8+RcuSdO8578DGLyTzd0kdFljaK9JJ5cDezEeATwG8De4HvmtkOd38s658l4crzBJLFjNYqlDaK9JJHWuYCYNbdn3L3Q8BtwIYcfo7IQLJI+2SRntIKjZKnPNIyk8Bzbc/3Am/ufJGZbQY2A6xcuTKHZojEyyrtM8zVRVXv7CThKK1axt23AdugtfxAWe2QZuoMzEu96KICZxk385BmySMtMwec3fZ8RbRNpJKKuNlHpzJu5iHNkkdw/y6wxsxWm9lJwFXAjhx+jkgmygiced/ZSSTz4O7uh4HrgPuAx4Hb3X1P1j9HpJd+BivLCJz9DupquV7pVy6TmNz9Xnd/vbu/1t3/Jo+fIdJNv2mWMgJnv9U2eU/skvBo+QEJTr+DlWXVrA9zZydVy0gSBXcJTq814uNuFViXwKlVJaUfCu5SS71qvnutLNmepoHBbjBSFNW1yzC0cJjUTlJOPS4/3anqZYRllGdKWBTcpXaSShc7Byu7qXIZoeraZVhKy0jtpCldbE+z5L0+fB5U1y7DUs9daqff0sU6lhGqrl2GpeAutdNvsC7iBiNZq+MJSapFaRmpnUFKF6tYDdNLXcozpbrMY252XLSpqSmfmZkpuxkiIrViZrvcfSpun9IyIiIBUnAXEQmQgruISIAU3EVEAqTgLiISoEpUy5jZfuCZAd9+OvDTDJtTJh1L9YRyHKBjqaphjuVX3H0ibkclgvswzGymWylQ3ehYqieU4wAdS1XldSxKy4iIBEjBXUQkQCEE921lNyBDOpbqCeU4QMdSVbkcS+1z7iIicqIQeu4iItJBwV1EJEC1De5m9m4z22NmR81sqm37KjNbMLOHo3//UmY70+h2LNG+G81s1syeNLNLy2pjv8zsw2Y21/Z3uKLsNvXLzC6Lfu+zZral7PYMw8x+bGaPRH+LWi3BamafMrMXzezRtm2vMbNvmtkPo6+nltnGNLocR26fk9oGd+BRYBPw7Zh9P3L3N0b/3ldwuwYReyxmdh5wFfBrwGXAP5tZ7zs/V8vNbX+He8tuTD+i3/MngMuB84Dfi/4edXZR9LeoW334p2n9/2+3Bbjf3dcA90fPq+7TnHgckNPnpLbB3d0fd/cg7hbc41g2ALe5+y/c/WlgFrig2NY11gXArLs/5e6HgNto/T2kYO7+beC/OzZvALZHj7cDG4ts0yC6HEduahvcE6w2s91m9h9m9ltlN2YIk8Bzbc/3Rtvq4joz+0F0OVr5y+YOdf/dd3LgG2a2y8w2l92YDJzh7vuix88DZ5TZmCHl8jmpdHA3s383s0dj/vXqQe0DVrr7OuB64PNm9upiWtzdgMdSaQnHdAvwWuCNtP4mf19mW4XfdPfzaaWZrjWzt5TdoKx4q567rjXduX1OKn0PVXd/2wDv+QXwi+jxLjP7EfB6oNRBpEGOBZgDzm57viLaVglpj8nM/hX4Ws7NyVqlf/f9cve56OuLZvYVWmmnuPGqunjBzM50931mdibwYtkNGoS7v7D0OOvPSaV77oMws4mlQUcz+1VgDfBUua0a2A7gKjN7hZmtpnUs/1Vym1KJPnBL3kFr0LhOvgusMbPVZnYSrYHtHSW3aSBm9ioz++Wlx8Dbqd/fo9MO4Oro8dXA3SW2ZWB5fk4q3XPvxczeAfwTMAHcY2YPu/ulwFuAvzazReAo8D53L2wQYxDdjsXd95jZ7cBjwGHgWnc/UmZb+/C3ZvZGWpfLPwb+uNTW9MndD5vZdcB9wAjwKXffU3KzBnUG8BUzg9Zn/vPu/vVym5SemX0BeCtwupntBf4KmAZuN7NraC0X/p7yWphOl+N4a16fEy0/ICISoODSMiIiouAuIhIkBXcRkQApuIuIBEjBXUQkQAruIiIBUnAXEQnQ/wMuWBADz+IVzwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# sample plot\n",
    "\n",
    "plt.scatter(data_x, data_y)\n",
    "_ = plt.plot()"
   ]
  },
  {
   "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.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}