Pattern-Recognition-and-Machine-Learning/Appendix/Appendix-E-Lagrange-Multipliers.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 附录 E：Lagrange 乘子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 等式约束下的拉格朗日乘子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "拉格朗日乘子（`Lagrange multipliers`），又叫不定乘子（`undetermined multipliers`），用于找到多变量函数在有约束条件下的驻点。\n",
    "\n",
    "考虑最大化函数 $f(x_1, x_2)$，约束条件为\n",
    "\n",
    "$$\n",
    "g(x_1, x_2) = 0\n",
    "$$\n",
    "\n",
    "一个可能的方法是通过这个约束求出 $x_2 = h(x_1)$ 再带入函数消去 $x_2$，但很多时候函数 $h$ 是很难找到的。\n",
    "\n",
    "一个更普遍和简单的方法是引入一个拉格朗日乘子 $\\lambda$。\n",
    "\n",
    "现在考虑一个 $D$ 维变量 $\\mathbf x$ 的优化问题：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\max_{\\mathbf x}~& f(\\mathbf x) \\\\\n",
    "s.t.~& g(\\mathbf x) = 0\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "$g(\\mathbf x) = 0$ 定义了空间中一个 $D-1$ 维的超平面。\n",
    "\n",
    "我们注意到，梯度 $\\triangledown g(\\mathbf x)$ 平行于这个超平面 $g(\\mathbf x) = 0$。\n",
    "\n",
    "考虑超平面上的两点 $\\mathbf x, \\mathbf{x+\\epsilon}$，做泰勒展开有：\n",
    "\n",
    "$$\n",
    "g(\\mathbf{x+\\epsilon}) \\approx g(\\mathbf{x}) + \\mathbf\\epsilon^{\\text{T}} \\triangledown g(\\mathbf x) \n",
    "$$\n",
    "\n",
    "因为它们都在超平面上，所以有 $\\mathbf\\epsilon^{\\text{T}} \\triangledown g(\\mathbf x) \\approx 0$，令 $\\|\\mathbf \\epsilon\\|\\to 0$，我们有 $\\mathbf\\epsilon^{\\text{T}} \\triangledown g(\\mathbf x) = 0$，而 $\\epsilon$ 平行于超平面，所以 $\\triangledown g(\\mathbf x)$ 平行于超平面。\n",
    "\n",
    "在这个超平面上，最大化 $f(\\mathbf x)$ 的点 $\\mathbf x^\\star$ 也需要满足 $\\triangledown f(\\mathbf x^\\star)$ 垂直于超平面 $g(\\mathbf x) = 0$，否则，我们总可以在这个超平面上移动一点距离使得 $f(\\mathbf x)$ 增大。\n",
    "\n",
    "因此 $\\triangledown f(\\mathbf x^\\star)$ 与 $\\triangledown g(\\mathbf x^\\star)$ 应当平行，这意味着存在 $\\lambda \\neq 0$，使得：\n",
    "\n",
    "$$\n",
    "\\triangledown f + \\lambda \\triangledown g = 0\n",
    "$$\n",
    "\n",
    "此时我们可以引入一个拉格朗日函数：\n",
    "\n",
    "$$\n",
    "L(\\mathbf x, \\lambda) \\equiv f(\\mathbf x) + \\lambda g(\\mathbf x)\n",
    "$$\n",
    "\n",
    "其驻点满足 $\\triangledown_x L = 0$ 即 $\n",
    "\\triangledown f + \\lambda \\triangledown g = 0\n",
    "$，以及偏导 $\\frac{\\partial L}{\\partial \\lambda}$ 使得 $g(\\mathbf x) = 0$。\n",
    "\n",
    "因此，问题转化为求这个拉格朗日函数的驻点 $(x^\\star, \\lambda)$。\n",
    "\n",
    "由于拉格朗日函数是无约束的，我们很容易通过求偏导得到驻点的值。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAEACAYAAABI5zaHAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XncpXP9x/HX25Yl29iyFCnZsxRDjNTYIhqRFhSVQllq\nsjVJ0aKSLeFHJZKyZF/HEIqxJjSJsWRXlC0qzHx+f3yuu7nnzL3Pue/vOdd5Px+P87jv+9zXOdfn\nMPf7fM/3+i6KCMzMrF7mKF2AmZk1n8PdzKyGHO5mZjXkcDczqyGHu5lZDTnczcxqyOFuZlZDDncz\nsxpyuJuZ1ZDD3cyshhzuZmY15HA3M6shh7uZWQ053M3MasjhbmZWQw53M7MacribmdWQw93MrIYc\n7mZmNeRwNzOrIYe7mQ0bSStI+uQgHzNB0jzDVVOncLib2bCQNAr4FvDLQT70XODU5lfUWRzuZjbb\nJH1U0hmSLpD07uruI4GjImLaYJ4rIu4H7pL06aYX2kEUEaVrMLM2JultwBTgrcDdwO7AA8DxEbHF\nEJ9zQWAysE5EvNasWjuJW+5mNrt2AO6JiKciYomIuBTYBzh9qE8YES8BtwHbN6nGjjNX6QLMrCxJ\niwCLDeDQ1yLi0R7u3xC4qeG+rYAfzmZpNwHjgHNm83k6klvuZrYc8BdgKnB/D7ep1W2v7g+StIOk\nXwBbA2tWfe6jJS0PLBIRDzUcf6ikeyVNl/RkdewtkqZJulXSxxrqug3YYBheb0dwn7uZIekEYNGI\n2LmH320HnAy8PSJeafjdgsALwNoRcXd13xjglIhYtYfnWgS4j2xYrgocBMwREeN7OHZZ4BFgPve7\nD55b7mYGcBiwlaSNu99ZjTc/GjikMdgrawKvky3/LksCz/d0koh4HvgK2Q10PvBBYEIvNf0TELDI\nwF+GdXG4mxkR8Q/gcODHktTtVwcCz0VEbxdHVwcejIhXu903BzC9j3P9ArgO2Ag4JiL+08uh08hw\nd/fCEDjczazLCeQgi70BJC1Hdpvs28dj1gD+1HDfM8Cofs51Kxnc+0vqbWDHYsDrEfFsP89lPXC4\nmxkA1WSj8cDhkhYHjgIujojJfTxsDeCehvueoI/RN5LWJkfBHAesTH466Mko4G8Dq94a+YKqmc1E\n0iXAosBawKoR8Xgfxz4L7BERFzTc/ziwfkQ82XD/3MAtZL/7TeTkp6WANSPi4YZjdwF2jIhxs/+q\nOo9b7mbWaDywHvCDfoJ9WfJN4A89/HoiMKbh+GPJMF8D2AJYFpgTmA+YVI3Y6W4McNkQX0PHc8vd\nzGYhaX/g5D4udiJpG+C4iHh7D7/bFNg3Ij48xPPPQy5lsF41W9UGyS13sxqTNIekH0s6YDCPi4hj\newt2SYdL2gBYB7i8l8dfB8wraaXB1lz5JPBLB/vQOdzNakrSUsAV5OiXlZv0nIsDB5MXOzcFTuzj\n8L2AIxqGVg7kHEsB25CrStoQOdzNakjSB4A7qx8fAP7ajOethiWeDLwHuCAi/tLHsY+QI26+MMjT\nHAR83rNSZ4/73FtRTuleutttFLAwsFC328LAgsAbgLmr2zzdvp+LnEgyrbq93vD9f4CXq9sr3b5/\nGXiRnB3YdXuu2/cv4380La3qr74e+Cbwc7L1/peI+F7JumxkeVXIEqQ3ACsC7+h2W4kcPbA0Obnj\nqW63Z8nAfRF4vNv3LwH/BV5ruL1KBvgc5GiErttc3b7OCyzQcJu/+rp4Vc8ocjTEqG63uZCeBrpu\nTzV8fYxcD+SffhMoo5otuqGkQ4FryKUA3AruMG65DzdpPvLC0/rVbT3gzcCjzLry3uNkSL7UssGY\nr2cp4E3kG1Hj1zcDy5OfHh4lg77r9jBdKwxGvDjitXcQSYuRC3RtQP67eyoiflu2KhtJDvdmy0ka\nG5ELIr2PXPnuXnLixq3kMqb3U/f+RGkhMuS731YkPxG8nfzU0bWUbNcb3BTgQSJeL1FynUj6PrBQ\nROxZuhYrw+HeDBlk48hA3xx4kJx8MRH4AxH/Llhd68nRE8swoztqJXI0x+pk6/8+Muj/1O32SMt+\nmmkxkpYh/5utGRFPlK7HynC4zw5pXWBP4CPkBayLgSuIeKpoXe1MWoD8tLNGdVudXFZ2AXImZPfb\nVCJ6XX2wU0k6CfhXRAxqbLvVi8N9sLLV+RFybYwlgVOAnxHxdNG66k5akrx28S5g3eq2OPBHsrtr\nMjCZhrVMOk21WfUtwCpeTbGzOdwHQ1ofOIZcC+PrZCt9WtmiOpg0igz5Dch9PDcA/kVX0Oftztpf\n3+im2vZuakQcXroWK8vhPhC5NdjxwGbA14DTHeotKD9VrcSMoN+IvJA7mdwc4nrg9rqGvaQ1gUnk\ndniett/hHO79kd4BXEL+0RyM/2jaSw4JHENOld+UHLFzM3AtecH7j3Xpt5d0IXBDRBxduhYrz+He\nF2lz4JfABCJOLV2ONUF25YwBxgJbkvtzXk0G/cR2vXYiaTRwHrBSXys5WudwuPdG2hC4CNiRiBtK\nl2PDRFqBXFt8S+D95GSrS8mRT7e3S6te0jXA2RFxSularDU43HsiLQHcAXyRiItLl2MjJPfyHA1s\nC2xHLr1wCRn017TqfAVJY8nFvFbzYlvWxeHeKC/KXUW22r5auhwrKNci7wr6dcmum3OAy4h4uWRp\nXarldG8GjomIX5eux1qHw72R9H7gR8BangZv/5MXZj8E7ESOxrmKDPrLiXilXFkaB3wDWDfapAvJ\nRobDvZH0G2ASESeVLsVaVG5YMY6czDaa7KM/g+y6GbEhspLmJLeiOzAivNeozcTh3l1u+HsPsLyH\nPNqA5PWZj5Lbwi1Ljq46g4g/Df+ptSu5/MXG4T9ka+CdmGa2MfBbB7sNWMQzRJxAxPrkJLfXgSuQ\n/oC0N9LCw3HaakOObwKHONitJw73ma0APFS6CGtTEfdWF+FXILeKex/wV6SfIK3PIPcS7cdngfvD\nw3StF96JaWarA3eVLsLaXPa7Xw1cTW72vDvwK+BFpBOBM2dnWKWk+cllMLbt45j9yJ211gEOAz5M\n7vC1aESMH+q5rX245T6zXWnSLvFmAET8jYgjyTVvDiID+RGkb1fXeIZiH+DGiLijp19K2he4MiK+\nSw7fvA44jdxvd5chntPajMN9ZieRF1TNmitiOhETidiOXNBsQeAepLOQ3j3Qp1EuYvcVclXS3swZ\nEfdV3y8H3Bm5FPLJ5NILPT3v/JJuHGgd1voc7jN7jPxjMBs+EVOJ2JdcxOx24Hykq5HeN4B++a8A\nl0TEvb0/fRzT7cdNyJY7EfFERNzfy8P2B0ZXwyutBhzuM3uM3ODZbPhFPE+u4Ph24CyyZX0T0nZI\ns/xtKvvv9yJHyfSrGlGzAbnUcV/HrQf8GXiV3ObQasDhPrMpwLubPKrBrG8RrxJxGrAa8ENyxukf\nkLZt+Ld4CHBmRDzS21NJmkvS+6ofN6y+3lb9bnFJOzceD4yLiAuBv5Fj9a0GHO4z+yO5y9IqpQux\nDhQxjYjzyK0EDwO+DUxG2myUtCAwHTi2n2f5HHC5pPnIi7f/iBnLaHyR3Li9uy8C/1d9/zS5cbnV\ngIdCdhcRSBeTa4j02qdpNqxyUtJFSJcAOz0PJy4GSz8H8wLvlzSmj52WbgDOJ1v55wMvS/oh8Apw\nbkQ833WgciOa9YBXqgXI5sEt99rw8gONpC2AbxKxYb/Hmo2AhaSNX4brpsOcc8L0reDDl0ZcNDvP\nqezTPxw4tGuGq6TjgJfDq6HWgrtlZnUdsCLSaqULMQN4CcZNh/uBV5eEv58FP6vGyS84lOeT9F7g\nSuAt3YJ9E2AtYKykTZtVu5XjlntPpK8BbyNi99KlWGeTtC656uQ6wFuBKQELk/3xY4HxwDn4D9ka\nONx7kvtsPkCu6f5Y6XKsc0m6Arg0In7cwy83IifePUXuGjZ1hMuzFuZumZ5E/JOcrv2l0qVY56q6\nSlYBet6cPeJGcmTNVeSomm+QY9vN3HLvlbQcuRHCakQ8Xboc6yzV6JUbgFMj4owBPGA5shX/FmA3\nIu4c3gqt1bnl3puIx4GfAt8tXYp1pA8Ao8jNP/qX/163A44CrkL6plvxnc0t975IC5Hj3XckYnLp\ncqwzVMMU7wAOj4gLhvAEy5ATk5YDPsaMRcSsg7jl3peIF4EDgRPwgko2cnYkd3S6cEiPzhUgtyPX\nqvk90u5eUqPzuOXenxl9n78g4pTS5Vi9VWu9TAG+GBFXN+EJVwd+DfwJ+HzVYLEO4JZ7f/Ld74vA\nEdXHXbPh9CngCWBSU54tYgqwPvACcCuS103qEG65D5T0DXL51A94wogNB0nzkjNRd4qIm4fhBJ8G\njgQ+R64CaTXmlvvAfZscvbBX6UKstvYkd01qfrADRPwM+CBwfDUm3v3wNeaW+2BIKwO/Bzai9x1t\nzAZNuU7MVGDziBjerR5z04+LyE8JnyXi1WE9nxXhlvtg5JCyw4AzkeYuXY7Vyn7ApGEPdshNu+H9\n5D6uV5L7slrNuOU+WPlR9grgdiK+Vroca3+SFgPuAzaIiAdG8MRzkjs/bQZsTsRTI3ZuG3ZuuQ9W\nvht+CtgNaZvS5VgtHAicN6LBDl07P+1PDpW8Hsn7B9eIW+5DlSvynQ9sQMTDpcux9qQcXnsP8M6I\neKJgIePJIb9jiXioWB3WNA732SHtD+xKXmD9T+lyrP1IOpHc/eiA0rUg7Q0cBIwh4tHS5djscbjP\njux/Pxt4jojPly7H2ouktwG3ACtHxD9K1wOA9GXg88Am1YVXa1Puc58d+c74GeC9SLsVrsbazzeA\n41sm2AEijib74K/yKJr25pZ7M+T6Hb8FtiXiltLlWOuTtCZwNbBSRLxUup6Z5CfS48mNQrYm4rXC\nFdkQuOXeDLl+x6eB8z3iwAboCOB7LRfs0PWJdH/gVXI2q2eytiGHe7NEXAocA1yMtEDpcqx1SdqA\n3B7vpNK19CpiGvBxYGNgn8LV2BC4W6aZsoXzU3J3+o8QMb1wRdZCJE0CtgQmAr+KiJ8ULql/0grk\nRd/tibipbDE2GA73ZpPeQC7Xeh0Rh5Yux1pDtSfqdGAL4MfA6sDr0Q5/gNK2wAnAurTSxV/rk7tl\nmi3iv8AOwC5InyhdjrWMOclw/zZwHHkxtT1WGI24BDgX+Ln739uHW+7DRVoDuJbcf/WG0uVYWZLm\nIzfMeAJYADga+EFk33bry4XybgF+RMRppcux/jnch5M0FjgL2JSIe0uXY+UoN1t/AXgKGBcRtxYu\nafCktcgux7UpuVSCDYi7ZYZTxDXAAcDlSG8qXY4V9S/gV+Rs1PYLdoCIu8i+95NLl2L9c8t9JEiH\nAuOA9xLxr9LlmA2ZNA+50NmXiLi8dDnWO4f7SMiLUKcCSwMfIuL1whWZDZ20NXnN4J3exal1uVtm\nJOQ76F7kiIkTPeLA2lq22B8G9i5divXOLfeRlPtkXg9cSMThpcsxG7JcG2ci8DYiXildjs3KLfeR\nlOuIbA18EmnP0uVYa5C0gqRPDvIxE5T932XkXq83AZ8rVoP1yS33EnId798B+xDxm9LlWDmSRpEr\nMH5qMGPeJb0DmBARnxq24vovYm3gcmBFb1bTetxyLyHiQWAb4CSkTQtXY2UdCRw12MlMEXE/cJek\nTw9PWQMq4o/kyJkdi9VgvXK4lxJxJ/BR4JyqBWQdRtIqwAqRITkUpwJfVs4eLeVEfGG1JTncS4r4\nLfmHcRnSiqXLsRG3D3D6UB9crQV/G7B90yoavMuA5ZDWKViD9WCu0gV0vIjzkBYntzUbQ8TTpUuy\nWSm3nFtsAIe+FgPfXHor4IdDrwrIi5rjgHNm83mGJuJ1pJ8DuwB3FqnBeuSWeyuIOBk4A+9b2cqW\nA/4CTAXu7+E2tbrNtNKjpC0lnV6NbtlP0u8krSVpeWCRiHio4fhDJd0rabqkJyWNlnSLpGmSbpX0\nsYa6bgM2GJZXPHDnAB9Bcp60EI+WaRU5seloYH1gCyJeLlyRNZB0ArBoROzcw++2I9dcWSmq/3eS\ndgB+AKwTES9I+gK53O8SwBrAKRGxag/PtQhwH9n4WhU4CJgjIsb3cOyywCPAfFFyr1NpCrCHN/Ro\nHX6nbRX5LjuebP2dR8kxzNabw4CtJG3c/c5qvPnRwCHdgn0R4BTgqxHxQnXo08DUiHgOWBJ4vqeT\nRMTzwFfIbqDzgQ8CE3qp6Z+AgNKf+C4g67QW4XBvJbkt32eB/wC/QJqzcEXWTeQuRIcDP9bMS0gc\nCDwXEd0vju4GzA9c3O2+TYAbq+/nIDfv6O1cvwCuAzYCjonex5FPI8O99EfwScDYwjVYNw73VpOL\nin0cWJwcB+91aFrLCeRAhL0BJC1Hdpvs23DcGOCOmHlq/ibkBVCAZ4BR/ZzrVjK495fU2+CHxcjt\n+p4d8CsYHpOB1ZAWLVyHVRzurShbaeOAtYHvFq7GuqkmG40HDleOcjoKuDgiJjccOi95ARb4XzfN\nmsxouT9BH6NvlHMfxpF99CuTnw56Mgr42+BfSZPl9pI3k580rAU43FtVjmH+ALAt0sGly7EZIuJK\nsgV+ITnT+KAeDrsWWLDbz98nu27uq55jKvCqpGUaH1hNSvoZ+engEOCvwFclvbWH86wD3DHkF9Nc\ndwDrli7CksO9lWUf7+bAHkieBdhaxgPrkfugPt7D738E/FvSYZIOARYmW7bdTSS7b/5H0rHAFHI0\nzRbAsuRS0fMBk6oRO92NIScStYI/kG821gI8FLIdZIvtBmACEWeULseSpP2Bk/u42Nn92OuAKyPi\nyG73bQrsGxEfHuL55wHuBtarZquWlYuZXUVET58wbIS55d4OIh4mW3HfQxpSEFjzRcSxPQW7pDdJ\nGt3t5wXJVv71DY+/DphX0kpDLOGTwC9bItjTw8AylF3rxioO93YRcS+5FvzJSFuWLsf6dHx16zIB\nmNjDRVfIGa1HaJCjoiQtRfb3H9nfsSMmJ1E9Tc7mtcIc7u0kV5LcHjgTaUx/h1sxlwD3SzpA0tHA\ny8BHejowIh4hR9x8YZDnOAj4fNFZqT37K+BumRbgPvd2JG0GnAVsTcTtpcsx+x/pbOACIn5dupRO\n55Z7O4qYBOwBXIq0RulyzLp5nvJLIRhe8rd9RVyEtAC5kuSm5Lhps9JeIId9WmEO93YWcRbS/MAk\npE3I/luzkl4EFipdhDnc21/ET6oW/DXVZh9PlS7JOtp0cj0cK8zhXgcRx1UBP6nqonmmdElmVpYv\nqNZFxHfItU68m5OV5FZ7i3C418vXyGUKrkB6Y+lirCPNS+5HYIU53OskJy18CfgTcAnSfIUrss6z\nEHlR1QpzuNdNBvye5Hrh5yO9oXBF1lkWJodDWmEO9zrKDSV2I6e9n+2FnGwELYLDvSU43Osqt+v7\nBDkiyvux2khZFniydBHmcK+3iFeBHcnt3H6K5P/fNtzeDDxWugjzwmGdIcfAX0Hu8LM3/p9uwyGv\n77wEzFd1DVpBbsl1goiXgQ+SW6D9kEGuHW42QG8BnnCwtwaHe6eIeJHccPt9wLcKV2P1tCpwb+ki\nLHn5gU4S8RzSFsB1SP8mwiFvzbQa8OfSRVhyy73T5LozY4FdkQ4oXY7VisO9hTjcO1HE08D7gT2R\n9i1djtXGWuTsaGsB7pbpVBFPIL0fuB7pv0T8X+mSrI3liKyVgLtKl2LJ4d7JIh5BGkv2wb9KxGml\nS7K29S7gHiL+W7oQSw73ThfxYLXh9rVVC/6s0iVZWxoN3FK6CJvB4W4QcV81imZS1YI/r3RJ1nY2\nAs4uXYTN4BmqNoO0NnAVsAcRF5cux9pErlv0LLAKEX8rXY4lj5axGSL+CGwD/ARp69LlWNtYh5yZ\n6mBvIQ53m1nE7cB2wM+rrhqz/owFri1dhM3M4W6zirgZ2B44sxouadaXvF5jLcV97tY76b3AecAO\nRNxQuhxrQbkZ+6PAm4h4pXQ5NoNb7ta7iOuBjwG/QdqodDnWkrYCrnewtx6Hu/Ut4hpgF+ACpNGl\ny7GWsx3gkVUtyN0yNjA5euY0YJvqoqt1utyc4ylgdSKeKl2OzcwtdxuYiMuBPYDLkNYtXY61hK2A\nux3srckzVG3gIi6uJqxcjvQBIu4sXZIV9XHg16WLsJ65W8YGT/owcCKwVTXxyTqN9EbgCeBtRDxb\nuhyblVvuNngR5yPNAVyJtCURXua183wIuNHB3roc7jY0EedVG213BfzdpUuyEbU7cGrpIqx3Dncb\nuohzq4C/CmkLIu4pXZKNAGlFctelC0uXYr1zuNvsiTinCviJSJsT4W3W6u/TwJnemKO1Odxt9kWc\nXfXBdwX8lNIl2TCR5iK7ZLYsXYr1zeFuzRHxKyTIDT/cB19fHwQe8Se01udwt+bJgJ9OtuA9TLKe\n9gOOL12E9c/hbs2VXTTTyFE0WxPxh9IlWZNI7wTeAfymdCnWP4e7NV8Ok5wGXIHktWjqY1/gRCJe\nK12I9c8zVG34SNuRY6G3JeLW0uXYbJCWAO4H3kHEM6XLsf655W7DJ9eimQ5civQhIiaXLsmGbD/g\n1w729uGWuw0/6QPA6cD2RNxYuhwbJGlh4EFgfSIeKl2ODYyX/LXhF3EFMzb88J6s7Wdv4AoHe3tx\ny91GTu7Jei6wW7U+vLU6aX7gIWCsJ6e1F7fcbeTknqzbAach7VC6HBuQPYGbHOztxy13G3nSOsDl\nwAFEnFm6HOuFtBAwlWy1e0Zqm/FoGRt5EXcijSVnss5PxCmlS7IefQmY6GBvT265WznS24FJwLFE\nHFu6HOtGWhz4Cx4h07bccrdyIh5A2gS4BmkB4Du4tdEqDgbOcbC3L7fcrTxpaWBidTuAiOmFK+ps\n0krAZGANIp4uXY4NjcPdWoM0CrgEeAD4rNcvKUi6iBwh873SpdjQOdytdeSY6nOBAHYi4pXCFXUe\naQvgRGB177TU3jzO3VpHhvk44DlyJM2ihSvqLNLcwDHAeAd7+3O4W2vJ7phPAbcC1yMtU7iiTrIP\n8CRwcelCbPa5W8ZaU266fTCwB7AlEVMLV1Rv0luB24AN/d+6HjwU0lpTtjq+i/QM2YL/EBG3lS6r\nlvKN9GTgKAd7fbhbxlpbxE/I9U0uQ/pQ6XJqamdgKeCHpQux5nG3jLUH6d3ARcD3iTiudDm1IS0J\n3A180Nsh1ovD3dqHtDxwGXAt8CUiphWuqL1ld8zFwBQiDi5djjWXu2WsfUQ8AmwMrAZciPTGwhW1\nuz2BpYGvly7Ems/hbu0l4nlga6DrQuvShStqT9JqwOHAzkS8Wrocaz6Hu7WfDKPPAOcDN1frw9tA\nSW8AzgK+SsR9pcux4eE+d2tv0k7Aj4H9ifhl6XLagnQSsCSwo1fhrC+Pc7f2FnEO0r3k5tvvAg4k\n4vXSZbUs6XPApsBoB3u9ueVu9ZCrSp4FzAN8lIhnClfUeqT3ABcCGxNxf+lybHi5z93qIeKfwDbA\nzcBtSOsWrqi15Bo95wK7O9g7g8Pd6iNiGhFfBb4CXIX0ydIltQRpQXIC2IlEXFa6HBsZ7paxepJW\nJ0fTTAb2IeKlwhWVIc1LTvx6ANjT/eydwy13q6eIKcC6wGvAnUijC1c08qS5yOsQ/wD2buVgl7SC\nBvlJS9IESfMMV03tzuFu9RXxMhF7AAcBFyNNQJqzdFkjYsZKj28Edm3lpRqUF8O/BQx2KOu5wKnN\nr6ge3C1jnUFaDjgDmJMMu0cLVzR88g3sBGAdYDMi/lW4oj5JOgU4MSL+OITHfhl4PiJ+1vzKZjrP\nPsA7gL8BawBfjxa/MO2Wu3WGiMeBzYHLgduRPlG1buslZ5/+mgyiLdog2FcBVhhKsFdOBb6s3CJw\nWEj6DLBzROwTEd8Cfg5MVP63blkOd+scOZrme+TaNAcDVyK9vXBVzZOjYi4DBGxNxIuFKxqIfYDT\nh/rgyAvltwHbN62iWU2gW40RcSU5n2LnYTznbHO4W+fJdcvfBVxNrk1zKC3eCutXLqD2W3JUzEfb\naIPrrcgRTbPjJnJj9aaTtBKwAjCl4VdTyE+CLcvhbp0p4jUijiJH1LwLuAvpfYWrGhppM+AOcvbp\nXq128VTSlpJOr0a37Cfpd5LWUq7Pv0hEPNTt2EMl3StpuqQnJY2WdIukaZJulfSxHk5xG7DBMJX/\nNiCAxk9BL5Gh37K8tox1trywOq7awu/nSDcAE9rigmteOP06uYn4rkRcU7iiWUjaAfgBsE5EvCDp\nC8CGwKPkhcm/dz8+Io6Q9CPgPmBu4EHgBuD3ETG+l9M8A7xF0twR8VqTX8Ki1deXG+7/V7fftSSH\nuxlAxEVI1wCHkOPizwa+U12IbT0zRv8EsC4RTxeuaBaSFgFOAb4QES9Udz8NTI2I55Rb/D3f+LiI\neF7SV8h+7vOBJciRP735J3mdYREy6LvXcA45HJTqmFlOV90fwPcj4rqG33ctQtf4aWhuWjw/W7o4\nsxGVI0smIB1LLmFwF9KvgO8S8UTZ4irSfMB4YH/gWLK2luqG6WY3YH5yK78umwA3Vt/PAUzv6YER\n8QtJuwPvBfaKiP/0cZ5pzAjoxufZafBlz6TrzaKxC3sBenhjaiXuczdrFPEMEQcBqwL/Bu5GOh5p\nxWI1SSK7OP4MrA2sR8S3WjjYAcYAd0TEK93u24S8AAoZnKP6ePytZGjvr5xt25vFgNcj4tnZKbYX\nD1Y1LNVw/yjy4nXLcsvdrDcRfwcOQDqKbMnfjPRncpzzeSMyhjyn148D9gUWBj5DxLXDft7mmBf4\nS9cPVTfNmsxouT9BBvMsJK1Nvu7jyNd+IPCdXs4zipxc1NPzdO+W6U2v3TIR8Zhyv4BVuuqu3mjW\nAE7r53mL8gxVs4HKoN0G2J1slV5IBv3vm96Clt4CfI7cTvA+4CTgN+20EYmk8cD6EfHR6udTgO0j\nYoluxzxeHfNkt/vmBm4h31BvIocdLgWsGREP93CeXYAdI2K4hkN+uap7TPXzzsARwBoNn0pailvu\nZgOVe7deQO76tBSwC3A8sDzSZOB3wO+B24j496CeOycgvYfsttgEWI1ca2UsEX9u2msYWT8CTpF0\nGPAq+cllP0WdAAACLUlEQVTj5oZjJpJvlGcDKK93bE0OM9wCeIRcMmI+YJKkKyLiiw3PMYacvDVc\njgEWrt6cHgfeCWzRysEObrmbzT5pCWAjMmQ2BlYnW5uPk0P9nqm+/p28zrVYdVu8+roy+bH/DnLY\n3w3AjbR4eAyWpOuAKyPiyG73bQrsGxEfHuJzzgPcDawXnbqscy8c7mbNJi1AXvRcmtyIeonq61Lk\n6JBnyWV4u77+lWztt8us0n5JehOwfETcUv28IDkMcrOImNxw7OXAfhExdQjn+SywdEQc0YSya8Xh\nbmZNV13IXD4iRlc/HwmsHBGzrAFTzVT9HvDxGEQgKbvGTgZ2GobJS23P4W5mTSdpV7LP/G7yE8xz\nwHejlwvCkt4NbBARJwziHEcDR0aOarIGDnczsxryJCYzsxpyuJuZ1ZDD3cyshhzuZmY15HA3M6sh\nh7uZWQ053M3MasjhbmZWQw53M7MacribmdWQw93MrIYc7mZmNeRwNzOrIYe7mVkNOdzNzGrI4W5m\nVkMOdzOzGnK4m5nVkMPdzKyGHO5mZjXkcDczqyGHu5lZDTnczcxqyOFuZlZDDnczsxpyuJuZ1ZDD\n3cyshhzuZmY15HA3M6shh7uZWQ053M3MasjhbmZWQw53M7MacribmdWQw93MrIYc7mZmNeRwNzOr\nIYe7mVkNOdzNzGrI4W5mVkMOdzOzGnK4m5nVkMPdzKyGHO5mZjXkcDczqyGHu5lZDTnczcxq6P8B\nNwNDiCvDRBUAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f6ba4e59110>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import scipy as sp\n",
    "\n",
    "%matplotlib inline\n",
    "\n",
    "fig, ax = plt.subplots()\n",
    "\n",
    "an = np.linspace(0, 2*np.pi, 100)\n",
    "\n",
    "xx, yy = -20 / (3 - np.cos(an)), -7 / (2 + np.sin(an)) + np.cos(an)\n",
    "\n",
    "ax.plot(xx, yy, 'r')\n",
    "\n",
    "ax.set_xlim(-11, -3)\n",
    "ax.set_ylim(-8, -1)\n",
    "\n",
    "x, y = xx[30], yy[30]\n",
    "\n",
    "ax.annotate(\"\",\n",
    "            xy=(x, y), \n",
    "            xytext=(x+0.4, y+1),\n",
    "            arrowprops=dict(arrowstyle=\"<-\",\n",
    "                            connectionstyle=\"arc3\")\n",
    "           )\n",
    "\n",
    "ax.annotate(\"\",\n",
    "            xy=(x, y), \n",
    "            xytext=(x-0.4, y-1),\n",
    "            arrowprops=dict(arrowstyle=\"<-\",\n",
    "                            connectionstyle=\"arc3\")\n",
    "           )\n",
    "\n",
    "ax.text(-5, -7, \"$g(\\mathbf{x}) = 0$\", fontsize=\"xx-large\")\n",
    "\n",
    "ax.text(x+0.5, y+1, r\"$\\triangledown f(\\mathbf{x})$\", fontsize=\"xx-large\")\n",
    "ax.text(x-0.8, y-1.5, r\"$\\triangledown g(\\mathbf{x})$\", fontsize=\"xx-large\")\n",
    "ax.text(x+0.2, y, '$x_A$', fontsize=\"xx-large\")\n",
    "\n",
    "ax.set_axis_off()\n",
    "\n",
    "ax.plot([x], [y], 'k.', linewidth=30)\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 例子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "考虑这样的问题：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\max_{x_1, x_2}~& f(x_1, x_2)=1-x_1^2-x_2^2 \\\\\n",
    "s.t.~& g(x_1,x_2) = x_1 + x_2 - 1 = 0\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "对应的拉格朗日函数为\n",
    "\n",
    "$$\n",
    "L(\\mathbf x, \\lambda) = 1-x_1^2-x_2^2 + \\lambda(x_1 + x_2 - 1)\n",
    "$$\n",
    "\n",
    "驻点满足：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "-2x_1 + \\lambda & = 0\\\\\n",
    "-2x_2 + \\lambda & = 0\\\\\n",
    "x_1 + x_2 - 1 & = 0 \\\\\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "因此得到 $(x_1^\\star, x_2^\\star)=(\\frac 1 2, \\frac 1 2)$，$\\lambda = 1$。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADtCAYAAAAcNaZ2AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJztnXlYVeX2x79HyHkWQQTnBBwTjXIWLYnEMlEc8nLVSjPt\n1nXWX5ahGdcxx0q7eQ2ncgDLHOs6gAamXVDJAUxRUUGZRWZ4f3+sIFFAzmG/e+/DWZ/nOY9xhne9\nEHz32utdg0EIAYZhGEYdqmi9AYZhGEuCRZdhGEZFWHQZhmFUhEWXYRhGRVh0GYZhVIRFl2EYRkWs\nn/A655PJIj4e6N8fGDkSmD9f691ogsFgAKcsMpUUQ2kvPEl0GVnY2QFHj5LwAhYrvAxjabDoagkL\nL8NYHCy6WsPCyzAWBYuuHmDhZRiLgUVXL5ih8K5atQoZGRkIDw+Hn58fAgMDIYRAcnIyli9frvX2\nGEaXcMqYnigU3u++A/z8tN5NmaxevRqenp6YO3cuPDw84O7ujvHjxyM7OxtbtmwBAOzcuRMrVqzA\n2LFjsW7dOo13zDD6gD1dvWEmHm9+fj6cnZ0BALGxsXB1dUXTpk0xadIk+Pr64urVq0hPT8e0adOQ\nnZ0NFxcXdO3aFT169NB45wyjLezp6hEz8HinTp1a9N/BwcFwd3cHADg4OMDJyQnnz5/H/D8vGNWq\nVYObmxtOnjypxVYZRlew6OoVMxBeAMjJyUFYWBj69etX7HkvLy/s37+/6Otbt27BxcVF7e0xjO5g\n0dUzOhXevLw8HD16FAAQGhoKAHBzcwMAJCQkYOvWrbC2tkbHjh0BABEREQCAwYMHa7BbhtEXLLp6\nR4fCu2HDBgwaNAiZmZnYu3cvGjVqBGtrOh5Yu3YtvLy8it6blZWFJUuW4Pvvv9dquwyjKwxPqH3n\nwni9oKNeDZGRkfD390ebNm3g6emJQ4cOIT09HTVr1oSPjw86d+5c9F4/Pz+88847sLW1RUxMDFq2\nbFn0GvdeYCoxpfZeYNE1J3QkvOVh/fr1cHV1RYsWLZCZmYmwsDCMGjWq6HUWXaYSww1vKgVmkk4G\nACdPnsSUKVMghIAQAgaDAcHBwVpvi2E0hz1dc8TMPN7SYE+XqcSwp1upMCOPl2GY4rDomissvAxj\nlrDomjMsvAxjdrDomjssvAxjVrDoVgZYeBnGbGDRrSyw8DKMWcCiW5lg4WUY3cOiW9lg4WUYXcOi\nWxlh4WUY3cKiW1lh4WUYXcKiW5lh4WUY3cGiW9lh4WUYXcGiawmw8DKMbmDRtRRYeBlGF7DoWhIs\nvAyjOSy6lgYLL8NoCouuJcLCyzCawaJrqbDwMowmsOhaMiy8DKM6LLqWDgsvw6gKiy7DwsswKsKi\nyxAsvAyjCiy6zF+w8DKMdFh0meKw8DKMVFh0mcdh4WUYabDoMiXDwsswUmDRZUqHhZdhFIdFlykb\nFl6GURQWXebJsPAyjGKw6DLlg4WXYRSBRZcpPyy8DFNhWHQZ42DhZZgKwaLLGA8LL8OYDIsuYxos\nvLpGCAGDwWDxe9AjVbTeAGPGFArvd98Bfn5a78bsiYmJQUBAgCJrHTx4UJF1ZO9h0aJFyMnJUWE3\n+oFFl6kYLLyKkJSUhHnz5mHMmDEVXis2Nhb79+9XYFfy9+Dj44MJEyaosCP9wOEFpuJwqKHCzJkz\nBzNmzICVlZVJn09ISMDp06fRvHlzhIeH48yZM7h58yauX78Oa2trdO/eXeEdK7MHJycnPPPMM9i4\ncSPeeOMN6XvUBUKIsh4MU37i4oRo106Ijz8u19vp14+5ePGiGDhwYIXXCQ4OFh07dhQGg0EYDAZR\nvXp18cEHH4isrCwFdilvD2lpaaJDhw4iJydHtX2qQKm6yqLLKEtcnBDt25dLeFl0icmTJ4stW7Yo\nslZaWpqoUaOGqFKlili0aJEia6qxh3HjxonvvvtO8s5UpVRd5Zguoyx2dsCRIxzjNYKDBw+iR48e\niqy1fft2vPbaa9i3bx8CAwMVWVONPfTs2RN79uyRvDN9wDFdRnk4xlturl+/jpSUFLRu3fqx11at\nWoWMjAyEh4fDz88PgYGBEEIgOTkZy5cvL3G9goICbNu2DQBga2uLsLCwCsVz1dqDm5sb/P39Td6n\nWVGWG6yBS85UJp4Q4wWHF0RwcLBwcXF57PlVq1aJS5cuCSGE+Oqrr4Stra24deuWmDdvnrC1tVVl\nb2ruITY2VlhZWVWmuC6HFxgN4HSyJ3L37l3Ur1//sefz8/Ph7OwMgNKvXF1d0bRpU0yaNAkhISGq\n7E3NPTRs2BBCCKSkpCi6rh7h8AKjGGlpQGQkcOUKEBsL3LwJxMbaIafqUaz7tD++Xw4srDIfDx4A\nhYVKdesC1tb0r40NPRo3BuztgbZt/3o0bfrXZyoTBQUFqFLlcd9n6tSpRf8dHBwMDw8PAICDg8Nj\n742IiMDmzZtLvd03lfLuYefOnbh58ybOnj2L5557DlOmTDHalpWVlcVUsLHoMibx4AEQGgqEhAD/\n+x9w/jxw7x7Qvj3g5AQ0awZ07Ah4egL29nYQOUfx3hv9MXkYYOVHMd5q1Uicc3NJsO/dAxIS6BEb\nS+sHBADR0WSva1fguecANzf6t0UL8xfixo0bIykpqdTXc3JyEBYWhkWLFpX4+tKlSxEaGlqit6wU\nZe3h6tWrSE9Px7Rp05CdnQ0XFxd07drV6IPBxMREWFtbw8bGRqlt65eyYg8axEEYnZKXJ8TJk0LM\nni3E888LUbOmEL16CTFnjhC7dwsRFUXvKZNHYrwwIqablCTE4cNCfPKJEEOGCGFnJ0SrVkJMmiRE\nUJAQqakV+OY0JCoqSjRu3LjYc7m5ueLIkSNCCCGOHTsmatSoIXJzc4UQQty7d++x9LJNmzaJ8ePH\nK7qv8u5hz549olmzZkWf8/HxEUuXLjXaXmRkpHB0dFRg57qBY7qM8eTlAfv3AxMmAA4OwKRJFAr4\n17/IGz1xAvD3B7y9KQTwxGKqwhjvjh1Gx3gbNAAGDgQ++ADYswe4cwf4/nugTRvg889pf56ewDff\nAKmppn/PatO2bVtUrVoVt2/fLnpuw4YNGDRoEDIzM7F37140atQI1tZ0U7p27Vp4eXkpYnvPnj2w\ns7NDRETEY6+Vdw9eXl7Fyn1v3boFFxcXo/cSHh6Obt26mfidmBccXmAe4+JF4D//ATZvBlq2BHx8\ngDlzSOAqTGEeb2E6mYkYDECnTvSYMQNITwd+/BHYvh147z3ghReAN98kITaxslY1PDw8EBISgpEj\nRwIA+vbtC29vb/j7+8Pb2xu1atXC9OnTUbNmTfj4+CgWSigoKEBubi4CAwPRpUuXYq+Vdw/W1tbo\n2LEjABSJ9+DBg43eS0hIiGIXE91TlhusiVPOaEJenhA7dgjRs6cQTZpQGOHiRYkG4+IovFDOkmFj\nSEoS4quvhOjWjUIQS5YIkZCguBnFOHr0qBg6dKjJn69oeOFjBf4fZGZmitGjR4t79+4Z/dns7Gzh\n7Ows0tLSKrwPHcHhBaZkMjKAdevo8GvlSvIab96kEIIJd4nlx86O/pWQTtagAfDWW8Dp0+T5nj8P\nPP008O67dECnN9zd3ZGVlYXo6GjVbd++fRu2trYVXmfx4sVYuXIlbGxsEBMTY9RnAwICMGbMGNSp\nU6fC+zAHWHQtlOxsYNUqoHVr4OefKZRw8iQwdCjFbVVDYh6vwQA8/zxlQFy6BNSoAXTuDEyeTBcW\nPfHFF1/gww8/pIYoJmDq57Zu3Yrhw4eb9NlC1q9fj5dffhlCCMTExCAsLKzcn42Pj8e+ffswZ86c\nCu3BrCjLDVbfI2dkk5cnRECAEC1bCuHlJcTZs9rtBYXZC0Z2J6sI8fEUOmnYUIhZs/SV9XD69Gmx\nZs0aoz6zatUq0adPH9GyZUvx8ccfi1QjvqHY2Fjx+eefG7vNYpw4cUJYWVmJKlWqCIPBIKpUqSJO\nnDhR7s9PnTpVxMfHV2gPOqVUXTWIsq+Qpl0+GV1y+jRlIFStCixeDPTtq+1+DAbDXx5afDwdro0c\nqUqvhrg44P/+Dzh4EPjkE2DcOKCEGgWGMZVSM8hZdC2A1FRKtdq1C1i6FPjb3/RRVFBMdAHVhReg\nC9H771OBxsaNlA3BMApQ6l8YX9srOXv3UpVYdjZw4QLg66sPwS2RCuTxmoqbG8Wy334bGDCAvN7c\nXFVMMxYKe7qVlIwMYPp04MABOkjSOpRQEo95uoVo4PECwI0bwMSJwN27wJYtdLFiGBNhT9eSiIgA\nunWjfgZnz+pTcMtEo+5kzZvTReqdd4B+/Uh4teLatWvIZZe7UsKiW8nYvJnKZefNA7ZuBerV03pH\nJqKR8BoMVPZ85AiwcCGFHbKyVDOP69evw9fXFz179sSdO3fUM8yoBotuJSEvjwob/PxIqxSY5K09\nGvbj7dSJDtlSUoDevYGHWiNIITk5GbNmzULXrl3RunVrREVFoXnz5nKNMprAolsJSE0FvLwolPDr\nr9RSsdKgofDWrQt8+y0wbBjQowdVtilNdnY2VqxYAWdnZ6SmpiIyMhJ+fn4WU51libDomjnx8YC7\nOzWjOXAAaNhQ6x1JQEPhNRiAuXOpLPqFF4DDh5VZt3COmIuLC44fP47jx49j/fr1sLe3V8YAo1u4\ny5gZExMDeHgAr79Oh/y6TQVTAo2HXY4eDTg6AsOHA2vXUuc1Uzly5AhmzpwJa2trfPPNN+hrdied\nTEVg0TVTLl2iA7NZs4B//EPr3aiExsLbpw95up6eQH4+MGqUcZ8/f/48Zs+ejaioKPj7+2P48OEW\nMZ6GKQ6Lrhly9SoJ7sKFVL5qUWgsvM88Q8L70kskvOU5sIyNjcVHH32Effv2Yd68edizZw+qVq0q\nf7OMLmHRNTNiY4EXX6S+ARYnuIVoLLydOlFnthdfBKpXp4O2kkhNTcWSJUvw5Zdf4u2330ZUVBTq\nmW0OH6MULLpmxL179Ic+eTIl8JsDWVl0oYiNpf2np9MjP59e//JLyiW2sQFsbWlSRbl0SWPhbd8e\n2LePPF5bWwo9FJKTk4P169fjk08+gZeXF86ePQtHR0dV98foFxZdMyE7m3rdentTPq4eSU2lPga/\n/AKcO0ePO3dofLqjI4lTnTpA7dp/9ewND6fPJSRQ+e21a9T31smJquqee47StVq3LsGgxsLr6koF\nKMOHUzFF+/YCu3btwty5c+Hk5ISffvoJnTt3VnVPjP7h3gtmgBDA2LHUT2HHDv20IBSCcle//x74\n4Qearfbcc0CvXkCXLnQb3qZN6TPKSuq9IAS1Xbx0CThzhgoUTpwgIfbwAF55hbz9YiFRjXo1FLJ1\nKzBtWggcHWcCyMWSJUvwwgsvqL4PRldwa0dzxt+f2jIGBwO1amm9G6rOCgig4ZU5OcBrrwFDhpBH\nWq1a+dcpteHNIwgBREYChw4BQUHA5cvk8b/1Fok8AM2E9+LFi5gzZw6OHz8Le/tFOHt2NKpW1clV\nkdGS0tNSyupwrmKXdaYUDh8WomlTIWJjtd6JEKdOCeHjI0SDBkJMmCBEaKgQBQWmrweY9it27ZoQ\nn35KQyeffVaIb74RIidHqDqB4vbt22LixInCxsZGLFu2TKSnZwpPTyGmTZNumjEPStVVFl0dc+eO\nEPb2Qvz8s7b7OHlSCHd3IZo3F+Kzz4RQamirqaJbSF6eED/+KMSAASTAX30lRPaNigtvbm5uqa+l\npaWJjz76SDRs2FDMmDFDJCYmFr2WmEj7+O47k00zlQcWXXMjP1+IgQOFmDdPuz1cuiTEq68K0ayZ\nEBs3/ulNKkhFRfdhQkKEePFFIZychPhpi+nCe/fuXdG8eXOR8MjM9pycHPHFF1+IJk2aiDFjxohr\n166V+PnffhOicWMhbtww5btgKhEsuubGkiVC9O4tRBlOlzQyM4X46CMhGjUSYulS+loGSopuIfv2\nCeHsLMToAXEi+2njhLegoEC89tprYtasWcWeCwoKEs7OzmLAgAHit99+e+I6n3wixAsv0IWTsVhY\ndM2Jy5dJ8EpxpqRy5gyJlre3EDdvyrUlQ3SFECI7m2K+7RrGiST7dqJgfvmEd+PGjaJz584iKytL\nCCHEL7/8Inr16iU6deokDhw4IArKGcDOzRWie3chVq82+VtgzB8WXXMhP1+Ifv0odqq23X/9i26N\nt29Xx6Ys0S0kMlIIj2fixPXa7UTG7LKF9+rVq8LGxkacO3dOREVFiWHDhglHR0fxn//8R+Tl5Rlt\nOyqKLpx//GHq7hkzh0ewmwtffQV8/TUVGZSW36o0aWk0ITgpCdi2jcbWqEF5U8YqQk4OsGBKPMZ+\n0x+1xo9E0/WPp5Pl5+ejf//+GDBgABISEvDtt99ixowZeO+991CzZk2Tbfv7A6GhlMPMWBycMmYO\nJCQIYWMjxLlz6tn84w8h2rcXYtIkui1XE0j2dB/m+w1x4pJVO3Fx1OMe78KFC0XLli1Fw4YNxfvv\nvy/u3btX9FpeXl65wwqPkpUlRNu2Quzda/K2GfOFPV1z4J//pPHf69apY+/sWWDQIGqeM2WKOjYf\nRg1P92HCD8aj1iv9kTxwJJ7fTx5vZGQkOnXqhFq1aqFp06bIz89HRkYGMjMzkZGRgby8POzYsQPD\nhw83yeahQ9QrIzKSquoYi4Er0vROdDRVdF28CDRuLN9eaChVklW0IXdFUFt0AeDG6Xjk9OqPuH4j\n0fun+cjLy0NQUBBatGiBGjVqoGbNmqhRo0bRf1etWrXCPW+HDgV69gRmzlTom2DMARZdvTNsGODm\nBsyZI9/Wb78BL79MpbyenvLtlYYWogsAt8PjkdG9P+70GYk+P8svGY6MpFE/V65Qwx/GImDR1TMR\nETRY8soV+begv/9OArB+PfVL0BKtRBcA4s7G475bf6R5jkS3H+QL75gxQLt2wLx50k0x+oBFV8+M\nHAk8/zwwbZpcO3fvkp2FCylbQWu0FF0AuBoaj7w+/SFGjoTzVrnCGxVFIYboaKBBA6mmGH1Qquhy\nOySNiYqilrATJ8q1k5VFMVxfX30Irh5o3cMO93+gKcP33pU7ZdjJiQ4tN2yQaoYxA9jT1Zg33wRa\ntAA++kiuncmTqfvhzp366certadbyLbP4vHcnP5oNn0kqn0qz+P93/8opHP1KvDUU9LMMPqAPV09\nkpgI7N4tP11r927g4EFg40b9CK6eeH2qHb7wOYqEdd8BfvI83q5daQJGYKA0E4wZwH+CGhIQQJMQ\nGjWSZ+P2bZqn9u235Zw9ZqEs3GAHH5ujSPtKrvD+85/AZ59JW54xA1h0NUIIyiCQHct9913g7bcf\nmrDAlEjNmsBn2+zQM/so8rbJE95XX6Uhnb//LmV5xgxg0dWIkBC61e/dW56NoCDgwgXggw/k2ahM\nPP884OFrh5nd6HBNhvBaWQGvvw5s2aL40oyZwAdpGjFpEtCqFTB7tpz1s7MBFxdqnjNggBwb5SEx\nkQZLnj5NF4AbN6ixTlYWcOeOAZ06CdjbA23b0vTf3r2Bp58GKlgEZjJpaZRP+/2GeDw7U87MtfPn\nKS87JoZj7JUYztPVE/n5NJb8l19oWq4Mli2jQZZadLhKSwO2b6cpuWfPUnlz9+5Ahw6UqWFjQwMs\nHR0NOHtWIDaWhk2eOQMcO0a3+iNGAG+8Ie/nUxYBART6ObE7HoYBcoTX1RVYseKv6fFMpYO7jOmJ\no0eFcHWVt35qKnUru3hRno2SuHdPiJkzhWjYUIhhw4T44Yeyp06ghC5jBQU08mb6dPoehgyhr9Uk\nL486rx04IKQNu/T3F+LddxVdktEXpeoq39xowK5dgIlNq8rFF18AHh4UXlCD/HxgzRqyd/8+5aPu\n2kWZGdWrG7eWwUCpVcuWUShiwAC6FR8/nkIVamBlBSxYAHz4ISBs7ah6ReEYr5cX8OOPdKDKWBYs\nuhqwbx+dYssgM5NSktRonAOQMLq7U9FFSAgJfosWyqxdowbw3nsUeqhfH+jUiVolqsHQoRQmOXEC\ngJ3ywtuxI12sLl5UZDnGjGDRVZlr10gYO3SQs/6OHRQv7NRJzvoPExJCJ/6DB1Mstl07OXbq1qUL\nyfbtVMH36afyPcQqVYD33wdWrvzzCYWF12Agb3ffvgovxZgZLLoqc+QI3TLLOp3fsIEyI2Szdy+1\nowwIoAwMNU7h+/UDfv2VQhfvvgsUFMi19/e/k87euvXnEwoL70svAT//XOFlGDODRVdl/vtfaq0o\ngwsXKA3Jy0vO+oUcPAi89Rawfz8wcKBcW4/StCl51RERVN0l0+OtXRvw9qa5cUUoKLw9ewKnTsm/\neDD6gkVXZU6cAPr2lbP2jh3AqFGAtbWc9QHg3DnqVBYUBDz7rDw7ZVG3Lgn+sWMP3f5LwtcX2Lz5\nkScVEl5bW0qf47iuZcGiqyIJCUBqqrzc05075WZF3L9PIYWVK8lL05J69SjEsXgxxZZl0acPZU1E\nRz/ygkLC27Mn5WszlgOLroqEh9Mhl4z455UrQHIyHWzJYvp0iquOGSPPhjG0aEEj6//+dyA9XY6N\nKlWoD26JB14KCO/zz1OcmrEcWHRVpFB0ZfDzz8CLL8o70Dp5EjhwAFi+XM76pvLKK1Q6vHChPBtl\nZhlUUHg7dODwgqXBoqsiZ88CzzwjZ+0jR+Qd0AkBzJgB+Pvrsz3kkiXk8d64IWd9d3cgLAzIyyvl\nDRUQ3nbtSHS5SMJyYNFVkatXqZmLDGQe0P33vxSLfv11OetXFHt7apG5ZImc9evXp1DGuXNlvMlE\n4bW1JcG9d6/i+2TMAxZdFYmJAVq2VH7d+Hjq2iVjbQBYtYriuXruiPX++5TalZIiZ/0ePcjbLRMT\nhNdgoPLpy5crvkfGPNDxn1HlIjOTDrqaNlV+7cJYsYyCi7g48qJHjVJ+bSWxt6cwwK5dctbv1Kmc\njcdNEF5Hx4cKMJhKD4uuSly/DjRrJsdbvHQJaN9e+XUBYM8e4OWXgVq15KyvJKNH0zw4Gbi4GHHg\nZaTwNmlCFzfGMmDRVYnERKBxYzlrX7tGDdFlcPiw/Ao3pfDwoJzd7Gzl13Z2BqKijPiAEcJrb8+i\na0mw6KpESgrQoIGctWNi5IiuEJQqJuuATmnq1QOcnKi1pNLY21PsPD/fiA+VU3ibNAHu3Kn4Hhnz\ngEVXJZKT6RRcBnfv0t+30sTFkcg4Oiq/tixcXZ+QZWAiVauSqBvd07ccwlu3LlX7MZYBi65KpKTI\nE11Za1+9SrPLtJpXZgpOTlSdJ4PGjU1M7XqC8NaoQdknjGUgsTUK8zDZ2cZPUSgvskQ3Lo5ufc0J\ne3sgMlLO2hUSx0LhLRyK9tDMterVWXQtCfZ0KwH5+XI6i92/T7e+5kRqKo3BkUF4OGWhmEwpHu+D\nB/Q0YxmUOQ3YYDBwcSLDMIwJCCFKDMyV6emWNdGSH8Y9li0TmDZNztq2tgJ37ii/7rffCvj4yPuZ\nyPgd27ZNYORIOfvt1k3g118VWi8uDqJdO4iPP8bRowJ9+8r7OfNDk0epJyEc01UJK6syGqZUkDp1\nKBSgdPzVxsb8egLcvUv9DGSQlaVgXP6hGK/DFaB69flP/gxTKWDRVYn69eX1BZC1dosWVHhhTly9\nqtw04kdJTla4y9qfwmv3bH+MqwUALLyWAB+kqYRM0W3UiKZSKE2rVrSurH3L4Px5OZOWCwrIi1Y8\nm8PODj/NPYo+d5Qb787oGxZdlZApui1aUFWa0lhZAd26laO7lk7IzQXOnAGee075tRMSyMutWlX5\nta9n2WH9SOWmDDP6hsMLKtGggQnVTOWkZUs5ogtQY/RDhwBPTznrK8nJk1Qc0bCh8mtfuQK0bq38\nugCVANu0sQMWlpzHy2jDqlWrkJGRgfDwcPj5+SEwMBBCCCQnJ2N5BUaosKerEs2b02QDISEJr21b\nef1Yhw4FAgPNY0z47t3Aq6/KWfviRZryIIOiIhQFx7szFWP16tXw9PTE3Llz4eHhAXd3d4wfPx7Z\n2dnYsmVL0fsiIiIwffp0o9Zm0VWJBg2orWNysvJrd+lCifsy6NiR9v7f/8pZXykyM0mrZA3NvHBB\nnujeuUOVdABYeHVCfn4+nJ2dAQCxsbFwdXVF06ZNMWnSJIT8OX566dKlWLBgAZKN/KNm0VWRli3l\nZAO0aUNiLiN8YTAAkyfT2HU9s2ULxXJljbc/dUpOrBiglpHFxjix8GrO1KlTi/47ODgY7u7uAAAH\nBwc4OTkBAGbOnIkhQ4YYvTaLroq0akUpTUpTpQrg5gaEhiq/NkAjzs+e1e+o8Jwc4NNPgTlz5Kyf\nnU13EjJE9/59OqR7LM2NhVcX5OTkICwsDP369VNsTRZdFWnfXl4zlgED5IUAqlenv/upU/UZ2125\nktLEeveWs/7p09TEvHZt5de+dIkO/6ysSniRhVcT8vLycPTPZhihf3oybm5uAICEhARs3bq1Quuz\n6KpI167yYq8vvCA37jpuHAnul1/Ks2EK0dE0BVhm+GP/fnnZG088oGPhVZ0NGzZg0KBByMzMxN69\ne9GoUSNY/9lRau3atfCq4CgVThlTEVdXmlorg2efpVPwq1flpDZZWQH/+Q/Qpw9NkujYUXkbxpKV\nRWPh58+XN9oeAPbtA774Qs7av/1GB6FlUkZbSEZ5+vbtC29vb/j7+8Pb2xu1atXC9OnTUbNmTfj4\n+KB+BfuosuiqSKtWQHq6nP4A1taU3rV7NzBzprJrF+LiAqxYAQwZQgdLNjZy7JQHIYC336bDyXff\nlWcnOpouZs8/L2f9X34BPvusHG9k4VWNjh07Fgsh9OzZs8z3CyPzQDm8oCIGA9C9O/2hycDHB/j2\nWzlrF+LrS+PYPT2pd60WCAHMmkXx0E2b5E622LKFpgyXGHOtIA8eUCpat27l/ACHGnTF6tWr8fXX\nX+PYsWPw8/NDWlpauT5XZj9dANxPV2GWLAFu3gTWrFF+7fx8Ci0EBVH8WBZC0KFacDBw4IDp89kM\nBoPRXkJ+Ptk+cQL46SfqOyGLggIKW+zcaYQwGsHx48Ds2SaUWcfHk8c7ciR7vPqlVFeAPV2VGTAA\nOHJEztoNKaVfAAASoklEQVRWVsCECcCGDXLWL8RgoFvioUMpjerMGbn2CklKooqz33+nn6FMwQWA\ngwepZ4asC9iRIxQjNxr2eM0aFl2VcXUFbt+WN3L7zTeBHTvkdB17GIMB+PBDivEOGgQsWkT5srI4\ndIgOnJycyLuWNeTzYVauJK9aVvhi3z5g8GATP8zCa7aw6KqMlRXw4ouUhiQDe3tg+HA54YuSGDaM\n8lhPniRR/OEHZftLXLxINiZNAv79b/KwZXT6epSICMqpHjFCzvp37lCmyRPOaMqGhdcsYdHVgGHD\nKMtAFrNmAZ9/rt5BV4sW5LUtXgzMm0fi++9/U7WVKeTnAz//TD+nfv2o2u7CBcDDQ9l9l8VHH1GF\nW7VqctY/cAAYOBB46qkKLsTCa3bwQZoG3L8PODjQZNkGDeTYeOstSun617/krF8aQlAoYP16Ktbo\n148KN7p3p6qxOnX+em/hQVpODvDHHxQbPnaM7gLs7Sk+7esrpxKsLE6doruF6GgFx/M8gpcX5Rgr\n1qCHD9f0RqlBKRZdjXjtNcDbm/oayOD2baBTJ0q+b9lSjo0nkZJCh1FHj5KgXrxIImZjQ/+eP2+A\nvb1AUhLg6EgZAr17Ay+/LLfYoSwKCoBevUjw33hDjo34eCorvnULqFVL4YVZePUCi67e2LaNckwP\nH5ZnY8ECEt09e+TmspYXIeiALzmZWjF26WLArVsCjRsrcJutEBs3UvbHL79QIyEZrFpF/18CAiQs\nzsKrF1h09UZWFtCsGXXuatVKjo3sbMqWWLCAbpf1hil5ujKJjweeeYbi0zLycgt59lnA359iulJg\n4dUDnKerN6pXp3jlV1/Js1GtGh1ovfee+Y1SVxsh/gopyBTc8HDSxAED5NngwzV9w56uhly8SH98\nN27Ivb2eMwc4dw748Ud5t8ymoCdP99//BtaupTsPmSlpY8dSi8/Zs+XZKII9Xi3h8IJeGTCAvKu/\n/U2ejdxc6gzm7S2vGY4p6EV0//c/4KWXqCy3fXt5duLiqI3jH3/IGZ5ZIiy8WsHhBb0yZw6ldcls\nDv7UU9QIZ8UKyg9l/iIxkfKBP/9cruAC1B5y1CgVBRfgUIMOYdHVmIEDKb67d69cOy1aALt20e3t\n77/LtWUuZGQAr7xCQujjI9dWaiqJ7j//KddOibDw6goWXY0xGID/+z/qXSD7TrtXLyqjffllOQMy\nzYm8PGrZ2Lo1/exls3Il/dz/HDCrPiy8uoFjujqgoIBKZxcupAbhsvn8c2D5cmrN6OAg315paBXT\nzcujzJHkZOoVIbuXQ2Iiie2pU/KmFZcbjvGqBcd09UyVKsDSpdQzITdXvr3Jk+nRt6+c6cR6JjeX\nym9TUqjvsBrNc5YupUNMzQUXYI9XB7CnqyNeeolijDLHzzzM+vXkXe/bR0UBaqO2p5uaSrHb6tWp\n/aWsvgoP88cfNOonIoJKnXVDYbLwiBHs8cqBU8bMgXPn6GDt0iV5jXAeZedO8no3bKCm5Gqipuhe\nv069a/v0AVavpplyalBoU5W8XGPhUINMOLxgDnTuTJ6Ymrm0Pj7U1eu99+jvLj9fPdtqceAATbh4\n4w1g3Tr1BHfvXuDKFWqErks41KAJ7OnqjLQ0Gm++aZPkUtFHiIujWGdeHrB5M6WYyUa2p5udTReS\nLVuA7dtNHI1jIunp1OVtwwaJPRaUgj1eGbCnay7UrUvZBRMnUh6pWjRpQoMeBw+mpuEbNsgt2JDN\nmTPUQ+HyZao4U1NwAWDGDMDd3QwEF2CPV2XY09Upr79OfWdXr1bf9rlzwNtvU1bFF19Q2EMGMjzd\nxESa+rBrF+XGjhqlflvLAweAd94Bzp4F6tVT13aFYI9XSdjTNTfWraMc0h9+UN92584088zXlzy1\nsWPpIErPZGRQ7nG7dnSxuHCBih/UFtzERJrasWmTmQkuwB6vSrDo6pQGDajR+YQJwM2b6tuvUoWG\nQUZHU3y3a1cSk4sX1d9LWaSmAsuWUWVZaChpxpo18sezl0RBAU0CGT2aQgtmSaHw7tjBwisJFl0d\n07Mn1eqPHi13vHlZ1K1LTdAvXwaaNycxGTQICAzUbk9C0K37pEk0iui33ygevWsXzWHTigULaP6d\nv792e1AEOzvgyBH2eCXBMV2dU1AAvPoq0LQpFTNoPXYnM5OcoI0bKZ942DCa9+bubnx1lzExXSEo\nZBAURJkI6emUAjZxIg2x1Jp9+ygOfuYMHUpWCjjGWxG4OMKcSUujZjVvvqlRl6pSuHKFRsl//z2F\nHXr1otLi3r0pLvykKb5liW5+Pons6dMUXz58mPJrBw8mz797d/00ZL9wgbQpKIjuTioVLLymwqJr\n7sTEAD160IQDLy+td/M4d+8CISHUCPyXX0iImjShHrXNmtHD1paEuE4dwMoKePllAwIDBVJTaWDl\n3bvUCyI6mspnHRyoqKF7d8DDgyYEa+3pP0psLF1sFi2S24heU1h4TYFFtzIQGkpdyIKC6A9dz+Tl\nkSd8+TIdBMbGkqg+eEBxz4IC4NAhA4YMEahXj9LjbGxoSGfbtvSoW1fr76JsUlIo/9fXl5oVVWpY\neI2FRbeycOgQ/ZEfPEgZBeaMXsb1mMKDB3Sg2KUL5QPrzQOXAguvMbDoVib27KGT+59/ppJhc8Vc\nRTc9nUI8rVsDX3+tn9iyKrDwlpdSRVel1h+Mkrz2GmURDBxIp+bm7vGaE/fv0wSIdu0om8SiBBf4\nK4+3sDEIC6/RsOiaKaNHUz9YT09K4TLbZHwzIjGRsieeeYb6Y1ic4BZSmMfbvz99zcJrFJb6a1Mp\nGDqU8td9fCjkwMjjyhXKHunTx8IFtxAuGTYZS//VMXv696cGK5MnA0uWyB9uaYmEhpLYTp9OP2OL\nF9xCWHhNgg/SKgk3b5Ln6+xMubw1ami9oydjDgdpmzZROtg331AslykBPlwrCe4yVtlp1oyKEwCq\nCLP0EesVJSODyowXLyZnjgW3DNjjNQoW3UpEjRo0JcHXlyq5tmzhcIMpXL5MVXDZ2VSGrGUTHbOB\nhbfccHihkhIRQY3Qu3Shg5/69bXe0ePoLbyQn09tIT/5hB5vv20hRQ9KwqGGQji8YGl06UIdrxo0\noFldgYHs9ZZFVBTQrx818AkNpeITFlwTYI/3ibCnawEcP07jY9q0AdauVWfoZHnQg6ebkUFN0Fev\npjE/777L2QmKwB4ve7qWTL9+FG7o3p2GNS5YQKWslowQVFTSrh0QGUl3Be+9x4KrGOzxlgr/ilkI\nVasCH3xAB0NRUdTFa+1a7aY/aIUQpAV9+wKffgoEBJD4tmyp9c4qISy8JcLhBQslIgKYO5cEeNYs\nmu2ldm6vmuEFIahy1c8PuHMHmDeP+t9aWali3rKxzFADdxljSiYkhKqsTp8Gpkyhyja1hjqqIbo5\nOTQ7bc0aICmJxHb0aJpCwaiI5Qkviy5TNhcu0AjzwEDglVeoMKBvX7kxTpmie+MGsGEDVed16EAX\nlCFD2LPVFMsSXhZdpnzcuwds3UqDJ9PTgXHjgOHD6cBJ6RQqpUX33j3yardvp8Ox118nz719e8VM\nMBWlUHhHjwY+/FDr3ciERZcxDiFotHlAAI0HqlGD+vgOGULVbk89VXEbFRVdIYDff6ehlQcOAL/+\nStMcRo8GXnoJqFat4ntkJBAfT/GswYO13olMWHQZ0xECCA+n9pE//EDDI7t3p/BD377URP1Jk39L\nwljRzckBzp+nv9ewMJqc8dRTJLAeHvRvrVrG74NhJMCiyyhHUhJw4gQQHEyPyEjA3p4q3zp1Apyc\n/poA7OBAzdZLoiTRzcuj9WNjqYdtdDQ9Ll0iwW3dGnBzI297wABKfePKMUaHsOgy8iic/Hv+PD2u\nXPlrAvDt2+R91q1L3nDt2vQ15csa0KOHQG4ukJZGMdm0NCpdtrf/aypw27Yk5K6upnnUDKMBLLqM\nNhQUkOeank7zxdLTaZJulSrACy8YcPKkgJUVisawN2jAGQZMpYBFl9Efeui9wDCS4N4LDGPuxMTE\nICAgQOttGMWiRYuQY2m15k+ARZdhzICkpCTMmzcPY8aM0XorRuHj44MJEyZovQ1dweEFRjM4vFB+\nJk6ciMmTJ6NLly5ab8VoVqxYgfr16+ONN96QamfNmjWIioqCnZ0dIiMjsWDBAjg5OUm1WQalhhe4\nAp1hdM6lS5cQExNjloILABMmTECPHj3g6+uLp5SoqimBr7/+Glu3bkVYWBgA4ODBg/Dw8MDly5dR\nTWdVMhxeYBids2bNGowdO1brbZhMnTp14ObmhqCgIGk2Fi1aVOxn5OnpiZycHGzdulWaTVNh0WUY\nnXPw4EH06NFD621UiJ49e2LPnj1S1o6OjkZMTAw6PDJBtEOHDvjpp5+k2KwIHF5gGB1w6NAhbNu2\nDU5OTqhduzZ27dqFtWvXon79+khJSUHr1q0f+8yqVauQkZGB8PBw+Pn5ITAwEEIIJCcnY/ny5Yrs\nSykbbm5u8Pf3V2RPj/LHH3/AYDCgbt26xZ6vU6cOYmJipNisCOzpMozG7N69G++88w5Wr16NDz74\nANbW1ggNDUXz5s1x48YN2NraPvaZ1atXw9PTE3PnzoWHhwfc3d0xfvx4ZGdnY8uWLcXeGxERgenT\npxu9r/La2LlzJ1asWIGxY8di3bp1Ja7VuHFj3LhxA7m5uUbv40kkJycDAGo90nijdu3aRa/pCfZ0\nGUZDUlJSMHHiRKxbtw716tUDADRp0gRt27ZFgwYNcPfuXdSvX/+xz+Xn58PZ2RkAEBsbC1dXVzRt\n2hSTJk2Cr69v0fuWLl2K0NDQEtd4EuWxcfXqVaSnp2PatGnIzs6Gi4sLunbt+lg4pGHDhhBCICUl\nBY0bN37M1ogRI5D+5+C+kjJaCjNdDAYDZs2aBXd396LXrP/sSG/1SCljbm4u8vLyjP6+ZcOiyzAa\nsmnTJmRkZODVV18tei44OBi9evUCABQUFKBKCZ3kp06dWuz9Hh4eAAAHB4di75s5cya++eYbHD9+\n3Oi9lcfG+fPnMX/+fIwfPx7VqlWDm5sbTp48+ZjoWllZFYlmSezYscPo/RVSKOIFBQXFnn/w4IFJ\nFxvZcHiBYTQkJCQE3bp1Q82aNYueCw4ORs+ePQGQoCQlJZX6+ZycHISFhaFfv37S9liWDS8vL+zf\nv7/o61u3bsHFxeWx9yUmJsLa2ho2NjaK769NmzYQQiA+Pr7Y80lJSXj66acVt1dR2NNlGA3Jysoq\nJlIpKSk4f/58kafr4OCAxMTEYp/Jy8tDSEgI+vfvj9DQUAB0UAUACQkJOHToUIUr18prw9raGh07\ndgRAsWMAGFxCc/KkpCTY2dmVau/h8EJplBZeaNasGdq1a4dLly4V/dzy8vIQGRmJ8ePHl/+bVgsh\nRFkPhpEG/fpZNsuWLRMjRowo+nrChAnCxsam2HscHBzErVu3ir5et26dqF69usjIyBDTp08Xjo6O\nRa/Nnz9fJCcnF/v8pk2bxPjx4x+zHRQUJGxtbUV4ePhjrxlrIzMzU4wePVrcu3evxO9z8+bNYsiQ\nISW+pgTLly8XvXv3Lvp6y5YtolWrVuLBgwfSbD6BUnWVPV2G0ZB//OMfmDhxIvz8/FC1alWkpqai\ne/fuxd7j4eGBkJAQjBw5EgDQt29feHt7w9/fH97e3qhVqxamT5+OmjVrwsfHp9xxzIKCAuTm5iIw\nMPCxajdjbSxevBgrV66EjY0NYmJi0LJly2Kvh4SEwMvLy8ifTvmZOnUqUlNTMXHiRDg6OuLcuXM4\nfPhwsbCNbihLkTW5PjAWA9jTfYx+/foJf3//Ys8dPXpUDB061OQ1N23aJMaNG1fq6x9//LHJawsh\nxJdffilOnTol4uLixLVr18T27duLvZ6dnS2cnZ1FWlpaheyYGaXqKh+kMYxGxMXF4dSpU0Vf379/\nH6dPn37swMrd3R1ZWVmIjo422sbq1avx9ddf49ixY/Dz80NaWlqx12/fvl1iHnB5OXnyJKZMmYIe\nPXrA3t4ebdq0QbNmzYq9JyAgAGPGjEGdOnVMtlOZ4C5jjGZYepexESNG4Pr160XCO2fOHFy+fLnE\nHgXXr1/H7NmzsX379lLTrkxh6dKlGDduXIm5s0oQHx+PSZMmYceOHdKa3egUbmLOMHrjlVdegZOT\nE5YuXYpp06ahVq1a2LlzZ4nvbdGiBWbMmFFqxZcp3Lp1C7Vr15YmuADFetevX29pglsm7OkymmHp\nni5TqWFPl2EYRg+w6DIMw6gIiy7DMIyKsOgyDMOoCIsuwzCMirDoMgzDqAiLLsMwjIo8qeGNcqUv\nDPM4Avw7xlgYTyqOYBiGYRSEwwsMwzAqwqLLMAyjIiy6DMMwKsKiyzAMoyIsugzDMCry/78WEJ7z\nfmSFAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f6ba4d2fd50>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "an = np.linspace(0, 2*np.pi, 100)\n",
    "\n",
    "xx = np.linspace(-1, 2)\n",
    "yy = 1 - xx\n",
    "\n",
    "fig, ax = plt.subplots()\n",
    "\n",
    "for i in xrange(1, 4):\n",
    "    ax.plot(i / np.sqrt(8.0) * np.cos(an), i / np.sqrt(8.0) * np.sin(an), 'b')\n",
    "\n",
    "ax.plot(xx, yy, 'r')    \n",
    "\n",
    "ax.axis('equal')\n",
    "\n",
    "ax.spines['right'].set_color('none')\n",
    "ax.spines['top'].set_color('none')\n",
    "\n",
    "ax.xaxis.set_ticks_position('bottom')\n",
    "ax.spines['bottom'].set_position(('data',0))\n",
    "\n",
    "ax.yaxis.set_ticks_position('left')\n",
    "ax.spines['left'].set_position(('data',0))\n",
    "\n",
    "ax.set_xticks([])\n",
    "ax.set_yticks([])\n",
    "\n",
    "ax.text(2.6, -0.2, \"$x_1$\", fontsize=\"xx-large\")\n",
    "ax.text(-0.3, 1.8, \"$x_2$\", fontsize=\"xx-large\")\n",
    "ax.text(1, -1.3, \"$g(x_1, x_2) = 0$\", fontsize=\"xx-large\")\n",
    "\n",
    "ax.annotate(r\"$(x_1^\\star, x_2^\\star)$\", \n",
    "            fontsize=\"xx-large\",\n",
    "            xytext=(1, 1), \n",
    "            xy=(0.5, 0.5),\n",
    "            arrowprops=dict(arrowstyle=\"->\",\n",
    "                            connectionstyle=\"arc3\")\n",
    "           )\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 带不等式约束的拉格朗日乘子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现在考虑不等式约束的问题：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\max_{\\mathbf x}~& f(\\mathbf x) \\\\\n",
    "s.t.~& g(\\mathbf x) \\geq 0\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "分成两种情况考虑：\n",
    "\n",
    "- $g(\\mathbf x) < 0$，此时不等式约束不起作用（`inactive`），驻点的条件为 $\\triangledown f(\\mathbf x)=0$，因此必须有 $\\lambda=0$。\n",
    "\n",
    "\n",
    "- $g(\\mathbf x) = 0$，此时不等式约束起作用（`active`），驻点的条件为 $\\triangledown f(\\mathbf x) + \\lambda \\triangledown g(\\mathbf x)=0$，且 $\\lambda \\neq 0$。除此之外，$\\triangledown f(\\mathbf x)$ 应当与 $\\triangledown g(\\mathbf x)$ 的方向（指向 $g(\\mathbf x)>0$ 的区域）相反才能得到最大值（即 $f$ 的梯度方向要远离 $g(\\mathbf x)>0$ 的区域），因此我们必然有 $\\lambda > 0$。\n",
    "    \n",
    "在这两种情况下，我们都有 $\\lambda g(\\mathbf x) = 0$，因此问题转换为求解拉格朗日函数\n",
    "\n",
    "$$\n",
    "L(\\mathbf x, \\lambda) \\equiv f(\\mathbf x) + \\lambda g(\\mathbf x)\n",
    "$$\n",
    "\n",
    "在约束\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "g(\\mathbf x)&\\geq 0\\\\\n",
    "\\lambda &\\geq 0\\\\\n",
    "\\lambda g(\\mathbf x) &= 0\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "下的驻点，这些条件就是著名的 KKT 条件。\n",
    "\n",
    "对于最小化问题，我们只需要将拉格朗日函数变为：\n",
    "\n",
    "$$\n",
    "L(\\mathbf x, \\lambda) \\equiv f(\\mathbf x) - \\lambda g(\\mathbf x)\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAEACAYAAABI5zaHAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XmczWX/x/HXdQbZd1HKkkghKklKdaukqFul7ZYU2RUp\nLbf2ReouSTO2tNFCq6KFIiVka0MLsmTLPrYw5pzP74/v8TMzZndmvmfOvJ+Pxzw43/NdPue+857r\nXN/re13OzBARkdgS8LsAERGJPIW7iEgMUriLiMQghbuISAxSuIuIxCCFu4hIDFK4i4jEIIW7iEgM\nUriLiMQghbuISAxSuIuIxCCFu4hIDFK4i4jEIIW7iEgMUriLiMQghbuISAxSuIuIxCCFu4hIDFK4\ni4jEIIW7iEgMUriLSJ5xztVyzt2Sw2MGOeeK5VVNhYXCXUTyhHOuIvAk8FYOD30PeDnyFRUuCncR\nOWrOuRucc+Occx8555qGNw8BnjOzYE7OZWbLgJ+dc10iXmgh4szM7xpEpABzztUBlgK1gV+A24AV\nwHAza53Lc5YB5gJnmNnBSNVamKjlLiJH61pgsZltNLMqZjYFuAN4I7cnNLPdwALg6gjVWOgU8bsA\nEfGXc648UCkbux40s7/S2X4uMCfNtjbA80dZ2hygPfDuUZ6nUFLLXUROAH4HlgPL0vlZHv7plfIg\n59y1zrnxwBVAo3Cf+znOuZpAeTNbmWb/h5xzvznnQs65DeF95znngs65+c65G9PUtQBongeft1BQ\nn7uI4JyLByqYWcd03rsKGAWcbGb/pHmvDLATaGJmv4S3tQTGmNmp6ZyrPPAHXsPyVOA+IGBmd6ez\nb3VgDVBC/e45p5a7iAA8ArRxzp2fcmN4vPlQ4IG0wR7WCEjGa/kfciyQmN5FzCwRuAevG+hDoB0w\nKIOatgMOKJ/9jyGHKNxFBDPbBjwOJDjnXIq37gV2mFlGN0cbAH+aWVKKbQEglMm1xgMzgfOAF8xs\nfwa7BvHCXd0LuaBwF5FD4vEGWfQGcM6dgNdtcmcmxzQElqTZtgWomMW15uMFd3/nXEYDOyoByWa2\nNYtzSToU7iICQPhho7uBx51zlYHngE/MbG4mhzUEFqfZtp5MRt8455rgjYJ5ETgF79tBeioCm7JX\nvaSlG6oikopzbjJQAWgMnGpm6zLZdyvQzcw+SrN9HdDMzDak2V4UmIfX7z4H7+GnqkAjM1uVZt+b\ngQ5m1v7oP1Xho5a7iKR1N3A28L8sgr063i+BH9J5exrQMs3+w/DCvCHQGqgOxAElgK/CI3ZSagl8\nmsvPUOip5S4iR3DO9QdGZXKzE+dcW+BFMzs5nfcuAu40s2tyef1ieFMZnB1+WlVySC13kRjmnAs4\n5xKccwNzcpyZDcso2J1zjzvnmgNnAJ9lcPxMoLhzrm5Oaw67BXhLwZ57CneRGOWcqwp8jjf65ZQI\nnbMycD/ezc6LgBGZ7N4LeCLN0MrsXKMq0BZvVknJJYW7SAxyzl0O/Bh+uQJYHYnzhocljgJaAB+Z\n2e+Z7LsGb8RNnxxe5j6gh55KPTrqc49GvdxxJNGIJOpzgDokUZWDlCeZ8hykLAcpzQFKcoBjSCaO\nIAGScSQTIIgjGUcIh8MIAAGMuDR/L0qQYhykGEkU5QBF2E8R/iGO3RRhJ8ewlWJsoigbKcJ6irCG\nEqwmxCbi9R9NNAv3V38DPAa8jtd6/93MnvGzLslfCnc/9HFl2M8F7KUFe2jMHuqznarsoATbiAOg\nEkZlQlTBqIijNAHK4CgN//9TCiiG99jJoZ+i4Z84vGcEQ3jP+YXwHhI/9PoAsA/4J/xnyp/dhEgk\nxE5gF7CTALtw7MKRDFQiRHmSKMMeSrGd4mykOOs4hjWU4FdKMh/HCv0S8Jdz7iGgPrAZWGtmQ30u\nSfKRwj2v9XYV2MN1JHI52zibv6jGZuKoRoiahKhNgNoEqAlUA6rghXaOeinz0X5gG94ziFuAreE/\nNxNkM8YmAmwkQDJwLMlUYg9l2UxJVlGKPyjJfEowk5G23sdPEfOcc5XwJuhqDjQDNprZ1/5WJflJ\n4R5pfVwJdtGDv+nEGhqwlmOoRYjGGI2JoyFQC691Hcv2ABvwnlXcAGwgxBpC/EWAdQQoiVGNfVRi\nE6VZRhl+phRfU5yvSbAD/hZf8DnnngXKmllPv2sRfyjcI6GXq84WHmY9V7GUapxAkIsIcD6O04Di\nfhcYZQyvo2A13oSuqwnxJyFWEsdWHCeQRFU2UY5fKcd8SjONYsxWN0/2OOeOx5vvpZGZviEVVgr3\no3Gr+w+reZQfqMtZJHMJRWiJN+Gp5M4/wEoOLRsRYhkhVhDHPhwnsZtjWUY55lKWTynBl8TnbPHl\nwsA5NxLYY2Y5GtsusUXhnlN9nWMzQ/mFnuziGK7HuJYAVfwuLMZtA34DlmIsJsjvxJGIozZ7qcYf\nVGQG5XibMfZjVqeKZeHFqucB9TWbYuGmcM+Jzu5WFhJPiBLcSYALIDy2RfyQCPwK/IzxA0EWU4QS\nhKjN31TmeyowmdJMJMH2+V1qfgkve7fczB73uxbxl8I9O3q5mizhG/6gBv1wtEehHo0Mrx//Z+BH\ngvyA428C1CWR45lHJT6gNG/Gatg75xoBX+Eth6fH9gs5hXtWurrWfMmnnIfjHuIo5XdBkiM7gEXA\nPILMx7GeAHXZSXW+pzLjKM3EWOm3d85NAr7VeHYBhXvmOrr7+Jyn6Q9cH7UjzyUnEvHCfg5BZhNg\nN3Aq66nGZ1QhgZHeIs8FjXPuHOB9oG5mMzlK4aFwz0hn143JjOFFvJmtJTatB2YD35LMfIpwLEmc\nzEKq8jJlGF9QWvXOuenARDMb43ctEh0U7unp4erzMUt5mACt/C5G8k0y3gziMwgxA9iFoyErOI53\nqMAwRtgOnytMl3PuYrzJvE7TZFtyiMI9rb7OMZvtnE1ZBmjWzEJtNfA1xnRC/E4cDdlEDd6hMoMZ\nYVv8Lg8gPJ3u98ALZjbB73okeijc07rZDWAu/+NjAmS0JrsUPjuAGcBnBPmFOBryNzV5m6o8zYv+\njSd3zrUHHgXONLOQX3VI9FG4p9Xc/c1lVOUmvwuRqLUDb8Dh5ySzmCI0Zi21GEk5niMh/7pFnHNx\neB1J95qZ1hqVVBTuKXV3ZzGRhcwADXmUbNkOfIYxCWMzjib8wIk8xSv2UV5f2jnXCegJnG/6hyxp\nKNxTut4NYzt9iFeHjOTCn8DHhPgER1mSOI1JHMdARtraSF8qvCDH78CtZvZtpM8vBZ9uGKa0l3rU\n0P8mkkt1gAEEmI7jPo7hHzrwFn9xkVtBZ3crfXO2lmgWbgeWKdglI2q5p9TCraAldbjN70IkZmwF\nPsR4DyjOQU7nXU6kH8Nse25P6Zwribcu6pVmtiiDffoBJYEzgEeAa/CWgKlgZnfn9tpScKiVmtJc\n6rDK7yIkplQGuuOYiuN+irGNmxjHVtq4uXR3Z+XyrHcAszMJ9juBL8zsaWAaMBN4DTgGuDmX15QC\nRuGe0r/4nXp+FyExKQCcB4wijrdxVOJsJrKQ89xabnWdsnsa51x54B7g4Ux2izOzP8J/PwH40cw2\n4D3o1DKD85Z0zs3Obh0S/RTuKZVgDRvRWGHJW7WAh4jjS+B8qjOVN2jiErnZ3ZWNfvl7gMlm9ltG\nO5jZCyleXoDXcsfM1pvZsgwO6w+cEx5eKTFA4Z5SCVayQeEu+aQscFu4y+Z6yvEdzzODPdzknqTv\nkSHrnKsK9AIey87pwyNqmgPfZLHf2Xgz4ycBx+X0Y0h0UrinVIZv+ZU4dI9Z8lMxvNudn+LoQUl+\n4gG+4B9uco+nack/ALxpZmsyOpVzrohz7l/hl+eG/1wQfq+yc65j2v2B9mY2CdgEVI/QpxKfKdxT\nKsVE9mOs9LsQKZTigMuADwlwF8VYxCCms5eb3cCKxV0ZIAQMy+Is3YHPnHMlgCuBbWaWHH6vL5D2\nSda+wOjw3/8Gjo/ERxH/aShkWq3crzShPt01f7v4LAR8DrtexM7fjC09gIVgCdAyo5WWnHMN8Vr4\nfwJf4P26KI239Ph7Zofnq3fO1cMbJvkN3jDJ7sBrZhaflx9L8oeexEzrOMbxFU/SXQvpic8CQFtY\nWhX3W2dcCCgCp/dpwPXAK+kdYmZLgJRdL3PS2885FwBuAW4+NHWBc+401HKPGeqWSas8L7GeACv8\nLkTE88EMOLkmFC0Cp1XCPbGWsbRxc+nlcnXz0zl3IV6rvkaKYL8AaAxc7Jy7KGLFi2/ULZOetm4G\nRbmAIWq9i79+WArtesEPH8LqddCgLpTZDQwlyDwCXMhwjuUu4vUPWVJTuKenpzuJd/iTSWhgmPjq\n8u7Q7kLo0zGdN38AHiVEaXZxJtcx1r7K7/okeincM3Kp+5HjacQDar2LP75dAJ0fgD8+g2LFMtjp\nIPAmxhgc5zKL2lxOgu3NzzolOqnPPSO16cYk4oiKxdSksDGDQS/CY30zCXaAongPQn0E7KUFX7Cd\n29yN+VSmRDG13DPT2i2iJI3V9y757bNvYOD/4JePIS67//UZ8AnwDNCc76hNG7XiCy+13DNTh6uY\nQ4Af/S5ECpNQyGu1P9kvB8EO3kj1fwOTgL2cyzS2cbtrkzdVSrRTuGdmpK3nQkbxBCGCfhcjhcX7\nU6FIHLS/JJcnOBZv9smbKcYHfE4H92qEFwqRAkDhnpWq9CHAPt7XjDOS95KT4aHhMLg/HFUcO+AG\nHOOAn+nMD6yll9O8MYWIwj0r8WaczW0Mx7HZ72Ik1r0xCapXhUtaROiEdYH3CHAC1fiM1XR1l0fo\nzBLldEM1u65w37KTFowlTrPOSF7YfwDqXQ7vDoXmTfLgAh9gPA+05hkm2AN5cAWJImq5Z1dtLmMb\nSbxTcLtnVq+HcZNydsxToyApKW/qkdRGTYAzTs2jYAe4FscoHN9wH1e4WeqHj20K9+xKsH2cxzXE\n4wriOqvbE+HBF6HjlTk77rrLoFtmC7pJROzeC0PGeiNk8tTpwHs41tGCn1lFH1cqj68oPlG3TE5d\n7SaynA68Q4CifheTfd0fht43QZNTc37s0NehfBnocm3Ey0rlpTdh2WqoWgmWLIfH74B6tfP2mtHi\nyZHw+yp489l8uuA+4B6CbGEv53E6IzNeAEQKJrXcc6o6N1KMncQXnOX4fl/pdcnkJtgBul3nBfzB\ng+m/P+dH+OWP9N/Lrlfeh7cmw0sPwoO94NarofXtcKAQdAlt2wHDxsGjffLxoiWA4cTRmFJ8wXJu\nd6fn49UlHyjcc8obPdOSjwgvOxz9XnoTOrfP/fFlSsHZjeCjDKalqnGcd40bB8BPGS7bnLmnRqeu\nsU1LSDroBX6se/YV6HCZN61vvooDBhHHlcQxlUV0d83yuQLJQwr33BhtS2lDHwYB6/wuJmtffAfn\nHuVNuhZNYNL09N87oRq8/AQ8czeMeAeuv8ubqja7lq/2vlk0ODn19gYnw5fpLjUROzZshrHvw0O9\nfCyiNwFuIsAU5nC7u9DHSiSCFO65Nc5G0ZJPuJMQB/wuBqZ+B53v90a3vDgOWt4MP/8Oa9ZD4i44\n6cTD+z4xAk5tC4HT4PgLYN7PcM4NENcAml0PE9KusonXcv/+58xrqFkdxjwOzw2EMe9Bh36wcEnW\ntf+51ntgp2zp1NvLlPJCP5Y9OdK7l1G9qs+FdCHA7QT4lBl0c819rkYiQOF+NE6gPeXYxJP+Tk7w\nwTTo9RgMHwSDenqPrs/9yesu+WsjHFsp9f4P9Ya570CVinAwGerUgAuaQv9bYP67cGPbI69RpaJ3\nroz63VOqcTyMehReuN/rS7/mDpj/S8b779jl/VmqROrtpUsefi8W/fkXvPsF3H+735WE/QfHLcBU\nZtHNNfC7HDk6CvejEW9GU5oyH+NDf8a/J+7yRsIM7g/lynjbqlWBujWhQjnYvN0b6ZJW+bJeC3tb\nohe+U2bCU/0zvk7Fct40tInpLsucvhOPg5GPer90hrwM12Vw/iLhybHSTpJ1MBmSY3hOn0fj4c6b\noVIFvytJ4TYCtCPA1yyil8vvuwASQQr3o/WSbeBiruU5IItui7zw+kfwz364qtXhbd8uhPPO8P4e\nCkEgg/+XO/0bLmoGs3+EuzpD8WMyvk5cwAv3nD72snYjDB7t/f3erunvU6Xi4VpT2rsv/V9MsWDx\nMvhyLtx1q9+VpOMOAjSjCHP5mT6uRNYHSDRSuEfCq/YJl/EEd2BszN9Lz1oEZzWAkin+CX67EFqE\nw71KRdi+M+PjmzXyQnvYOG/SqoxsS4QiRaByNluZf22AXo9C/6e9PuUPX/L67dNT50Svhk3bUm/f\nvhNOrpG96xU0Dw2H+7p69xWijsMbRVOW0vzGj3qStWBSuEfKO/YIzfmcXoT4J/8uu/8A1E/xoE/i\nLq9VeN6Z3uvqx3rBnJ6ffvNGwPTrBH+s8obkZWT7Tu/hoqysXg89HoEBz3jj4z8YDk0bZn7MicfB\nqSd54/EPSU72HmS6NFITaEWR73+CRUuh101+V5KJOGAocaylHuv4wO9yJOcU7pFUg3Ycy2ruJZhf\njzi1au49un7Ivc9BhbJwSjjw69aCYkW9IXcpHTwIXQbBiIfh6QFQqzoMHgOrMhja+eNv3jeEjKxc\nC90egvueg143wvsvwpk5uCXXtQO8nmLem4mfe/38N6Vzc7eguuQ2CAa9hTge6Z15N1hUKA2MwjGL\nq+nkuvtdjuSMwj2S4s1oRBP+Zj/D8yfe7+gIJYrDYwnw9BjYuRuaN069T+vzYNbCw6/7D4YGV8KS\nFTBtNqzf5IXOvv1wSRfo+8SR15m1CNpekH4NEz+D/74Ad9wME1/I3ZOwd3WGVud4N4cfT/AemJo2\nNnV3U0FmBtO/h+lzvfsQndt726JedeBJ4CtG0tOdnNXuEj00t0xe6OFOYzKLGUCAdvl76Ytu8Z7u\nvL/b4W0z58Pw8V6/d24kJcHp7WHBe1HaR1wAJCfDMY29bz+3XAXvT4Pr20Dv//hdWTYNIcgSdtCc\nY4lXaBQEarnnhdH2K5fTgcEYC/LuMn9v8R5AOmT3XliwBC5smnq/i5p5ffPLV+fuOuM+ho7tFOxH\n42CyN+Jo8zZ4fKT3C7jHDX5XlQN3E8deKrKRsX6XItmjcM8rr9hHtOU++gN/5s0l7hzs/Rzy1Cho\n3QLOPePIfUc+4o3QyGmba9NW+PSb1N8EJOeSDnoBn3QQpoz0/vfM0eLXfisKPE2AGXShuzvL73Ik\na+qWyWvXuTHM4XYm4KgS2VOP/9jrMz/9FNi4xbuR+kB3b8hiehYu8aYQ6Nsx+9cYMMQLorRPuUrO\nhELQcSCMfuzIaRYKlHhCzGMHC6yy36VI5hTu+aGt+5pVXMB4AqhrQwqyJOAqjBY8ytv2uN/lSMbU\nLZMfatOKKqziLoJk8qCQSNQrBjyAYzYPaRWn6KZwzw/xZjSkEXvYxWMEC+4qrCLAhcCJONbxlt+l\nSMYU7vklwfZxDg34iWQS/J1FUuSo3Uscs7mK3k53Y6KUwj0/jbSNXEhTJgET1H4Xz+r1MG5S1vul\n9NQo7/kD39QDmhBiPZlMWiF+Urjnt7G2hDZcSgIwze9ixG/bE+HBF6HjlTk77rrLoNvDeVNTtvUh\njjlcRW9XzudKJB0Kdz+Mta9px394FGO+38WIn+4fCvfclvMx7/VqQ+P68KqfU3qdCtQlxGae9rEK\nyYDC3S+v2QSu4G76A7lcVFoKtt9Xel0yuZmLB7xZN4e+nr3VsfJMR+L4lc4+ViAZULj76U17gdYM\npQfGWr+Lkfz20pveBGK5VaaUN0f+R19FrqYcuxDYQQludQVpMoVCQQ8xRYNr3Dss5AbeivxTrBIZ\nibsynhc/paJFvDVks6NOa/jyldSLl+fUy+/C1/Ph7edyf46j9iLGCn7iSzvTxyokDYV7tGjnZrKc\nlownQFm/i5G0liyDM671pkZOb12iQ/+M7rvdmx//kKnfwdtToF4tb8Hv96dB/IPe8oFnXgvbvk99\nnidGwNufeounVKsMH73kzR+0cIk3o+SAzqkXMP/pN7jmTlj5ZcQ/cvYtA7oTogPFiDcN840S6paJ\nFrX4FzVYQvf8XclJsqdhPehxvbd4SHDpkT+T4r0wfrDn4WM+mAa9HvMWCB/U01sIfO5PUOM4+Gtj\n+vP1PNQb5r7jLY94MBnq1IALmkL/W2D+u6mDHbz9/troc797PaAUsIsMVskVPyjco0W8GadwJmX4\nizsJ4ucYZknXY33hi1nw3aLU25OSvGUFnx4ApUp62xJ3eQuPDO4P5cKLfFerAnVrQoVysHl7xot/\nly8Lzw30uoGuuQOmzISn+qe/b8Vy3reGxN0R+Yi5dymOzXTxuQpJQeEeTeItyOnUJ4lt3EtQz7FG\nl0oV4OHe0OeJ1FMnP/uKNyNnypujr38E/+yHq1od3vbtQjgvPB1zKASBTP71dfq3Nw//7B+9Vaoy\nWpIvLuDV4vsS1i1wrKFx1jtKflG4R5sEO0BT6rGRvTyqeWiiTd+O3qpKI972Xq/7G54ZC8P/m3q/\nWYu8PvKUywR+uxBahMO9SkVv0fHMNGvkBfewcd4107Mt0ZviuXKF3H2eiGkC/EVxurmaPlciYQr3\naDTCdtKC+iwmiefVfo8mcXHw/H3w8EuwdQfc86zXOk+7QMr+A1C/9uHXibtg8TI4LzyepPqxmY++\n+ek3mDQd+nXybq4+m8FD/tt3QtVomN2lGNCIZPZwm9+liEfhHq1G2kYu4nSmE2JM/iy2LdnTpqXX\nAm/f11ul6pm7j9ynVXNv2cND7n3O67o5JRz4dWtBsaKwYfORxx48CF0GwYiHvX78WtVh8BhYte7I\nfX/8zfuGEBUaEiCRDJZRl/ymcI9mo2wFl3IOEzHeVgdNNHn+XliwGAZ2gROqHfn+HR2hRHF4LAGe\nHgM7d0PzND3Src+DWQtTb+s/GBpcCUtWeKtsrd/kDb/ctx8u6QJ9n0i9/6xF0DZa4rQBAbbT0O8y\nxKNx7gVBN9eST5jJXTja4/etMwkb9gb0vDHjm50pXXSL1+JPuRbtzPkwfDx8+FLurp+UBKe3hwXv\nRcni5auAroTYYAVpddiYpZZ7QfCyzaIdV/EcmkkyivTPYBTL31tg3s+HX+/eCwuWwIVNU+93UTOv\nb3756txdf9zH0LFdlAQ7wAnAVgL0cSWy3FfynMK9oHjFPuXK8EyS3/ldjGTmzsHezyFPjYLWLY68\n6Qow8hF4aHjqoZXZsWmr19+f8puA74oClTCSaJrlvpLnFO4FyWs2gXb0ZiCwMMu9xSdXXgT1asL/\nXoEBQ6BUCXhvWPr71qwO93SBhLdzdo1nxsLox6Bo0aMuN7KOJ8Q+zva7DFGfe8F0sxvIZzzLGNDt\nK4kq/UimHCN41/r5XUphp5Z7QfSm/Y/WDKYn3qRNItGiLHCQyn6XIQr3gmuCDaIVI7gdY7XfxYiE\nlSVAEn4/Lyso3Au2d60PLXmTLhjr/S5GBChNgGS0pmoUULgXdB/YLTTjY27DSOdpR5F85SWKnsWI\nAgr3WDDJruZ0ZnAbxna/ixGRaKBwjxVT7BLqMZ+uhNjldzFSaGnwXdRQuMeSOpxLdZbSjRB7s95d\nJOIOAAH2+12GKNxjS7wZ9WlMBVbSk5D+iUm+202QomQxU73kB4V7rIk3owGncQzr6avl+iSf7cYo\nqjs/0UDhHosS7CCNqUsyW+hPED8XT5bCZRdQhK1+lyEK99iVYAc4i5PZRSIDtR6r5JPNOI7hD7/L\nEIV7bEuwvTSjDn+zh/8S1HpOkuc2EUcxfvK7DFG4xz5vPda6/Mk+HtOC25KHkoCdwDEs9rsUUbgX\nDiNsCy2pzy8kMUQBL3lkA1CFEAmmuzxRQOFeWIy09VzIacwhmWHqoJE8sBI4XsMgo4XCvTAZZatp\nRROmEWSEAl4i7E+gAqv8LkM8CvfCZrT9TmvOYhIhxirgJYKWkUxZfs56R8kPCvfCaLQtpg3NeQdj\nnAJeIuQPApTmW7/LEI/CvbAaY4u4ggt4DZigW6xylP4B1hKgNB/4XYp4FO6F2cs2h7ZcwkiMDxXw\nchSWArXYT4Lt9rsU8SjcC7ux9jXtaMswYIoCXnLpF+B4VvhdhhymcBd4xb6gHe0ZAkz1uxgpkBaS\nTEVm+l2GHKZwF8+r9gntuJHHMWb4XYwUKEFgEUWozGi/S5HDnJm+iUsKt7pOfMIbPI3jQr+LkQJh\nCXAvB1lpxfwuRQ5Ty11Se93GcyXdeABjtt/FSIEwF6O2ZoKMNgp3OdIb9grt6M1AjO/9Lkai3ixC\nHMvHfpchqSncJX3jbBRt6c9dwAK/i5GotQv4lTgq8ILfpUhqCnfJ2HgbTlsGcifwg9/FSFSaBZzK\nNkbYNr9LkdQU7pK5N+05rmAQfUGzhsgRppPMiXzmdxlyJIW7ZO0tG0wbHqE33sgIEfAW55hNESrz\nvN+lyJE0FFKy7yb3JNMYxBiggd/FiO+mA6PZwy9Wxu9S5EhquUv2vWMPcinP0AP41e9ixHeTSeYk\nPvG7DEmfwl1yZoLdzyX8j+7Ab34XI77Zi9clU4VH/S5F0qduGcmdG93zfMUAxgL1/S5G8t1kYAI7\nWGQV/S5F0qeWu+TOBLubi3mBbqBnEwuh9wlyMuP9LkMypnCX3JtoA2jFMG4HlvldjOSbtcAyAlTm\nQb9LkYwp3OXoTLS7aMVwuqKALyw+IERTFmthjuimcJejN9H68S/iuR1jud/FSJ5KBj7EcSKP+F2K\nZE43VCVybnDxzKAPY4FT/C5G8sRXwAj28auV9LsUyZxa7hI5E63v/3fRaJhkbHqDIA0Z63cZkjWF\nu0TWROvHJQylG96iyRI7/gDWEKAK9/ldimRN4S6RN8Hu5hKeoTuaiyaWjCPI2cwgwfb5XYpkTeEu\neWOC3U9rnqIH8IvfxchR2w58SRwn0NfvUiR7dENV8tZN7jGm8jAJwBl+FyO5NowQf7Ccr03PIxcQ\narlL3nrHHqEND9MHLfhRUO0GJhKgDj38LkWyTy13yR8d3f18ztMMBZr7XYzkyGhCLGAd31lNv0uR\n7FPLXfKIoCagAAAKKElEQVTHWzaEtvRjAMY3fhcj2bYPGE+AetzhdymSM2q5S/7q7LoyhZd5BEdr\nv4uRLL2GMZMtzLOqfpciOaOWu+SvN+wVruI/PI7xCWpZRLM9wFgcDdTXXhCp5S7+6OKuZAqT6IPj\nBpzf5Ug64gnxk/raCyq13MUfr9pkruJSRmG8QcjvciSNHcBbBKjPLX6XIrmjlrv4q5trzhd8xzU4\nehJQGz5KDCHIXyxnhp3qdymSO2q5i79etu+5nLOYTJBnCKoNHwVWAx8Txync4HcpkntquUt06OlO\nYha/UIfiPEUcRf0uqBDrRZDSfMVka+N3KZJ7arlLdBhlK7mQmqwnkT4E0dRU/pgNLAdqcJ3fpcjR\nUbhL9Bhh22jOiYRYTxdC7PS7oELmIDCYEOfzjJbQK/gU7hJdEmwfTTiJyiymE8ZmvwsqRN7EKMNu\nLXwdGxTuEn3iLcgpnMEpTOc/GKv9LqgQWAeMwXEm1xKvG3GxQDdUJbp1cOP5lo4k4GjkdzExyoCu\nBKnIdKbYZX6XI5GhlrtEt/etExczmB7AdL+LiVGTgc0EqUl7v0uRyFHLXQqGW10nPuMNumJ0VqMk\nYrYB/wbacQuv23i/y5HIUbhLwdHNteArZtKCAP8ljji/CyrgDOhJkOL8wFRr5nc5EllqAUnB8bLN\noQ11WcIeehNkr98FFXATMDZykJP5l9+lSOQp3KVgGWlrOJ/qGGvoREhDJXNpBTAcR0uuJsH0azIG\nqVtGCqa+zrGar/iBfxGP4zS/CypAkoDrCNGQt/nAOvldjuQNtdylYIo3Y4pdTEtepCveiA/JnqcI\nUoEtHKfpfGOZWu5S8HV11zCVd7kYGEgcRfwuKIpNxHiVIFdQi5G23u9yJO8o3CU29HQnMZ+FFKEc\nwwhQ0e+CotCPQB+Mq2nDKzbN73Ikb6lbRmLDKFvJuVSlIgvogLHU74KizGagH0YbHlewFw5quUvs\nudE9z1QGcB9Ge63txF7gFkLUZiZT7GK/y5H8oXCX2NTFXcVXfMAZOB4mjlJ+F+STA0B3QpRgBQ2p\nr0nBCg91y0hsetU+oR3Hs5NVXI3xs98F+SAZuJsgATbRgIbRHOzOuVrOuRyN3nHODXLOFcurmgo6\nhbvErhG2hZlWl3N5nt4YIwkR9LuofGLAIwTZxm7O5BQS7KDfJWXEOVcReBJ4K4eHvge8HPmKYoO6\nZaRw6O6aMo/pFKU0zxLgeL8LykNB4HGC/EISF1GbkbbJ75Iy45wbA4wws59ycewAINHMXo18Zamu\ncwdQD9gENAQeNrNleXnNo6Vwl8KjjyvKX0xmNpfxX6AtxNzt1iTgHoJsYi8tOC3ax7I75+oDw82s\ndS6PLwPMBc4wy5tvJ865rkA3M2seft0GGAWcYmYH8uKakaBuGSk8Euwgk60N/6YzI0miK0HW+F1U\nBO3Fu3m6iy2czwnRHuxhdwBv5PZgM9sNLACujlhFRxpEihrN7AugGNAxD6951BTuUvi8ZuNoQ3kq\nM5UbgQRCJPld1FHajDfcsQQrOIsaBWiB6zZ4Le+jMQfyZqER51xdoBYc8eTEUuDSvLhmpCjcpXBK\nsH18Ym3pwLnMYxv/xpjnd1G5NAfogFGbb2hA/Wi7eeqcu8w590Z4dEs/59ws51xj51xNoLyZrUyx\n70POud+ccyHn3Abn3DnOuXnOuaBzbr5z7sZ0LrEAaJ5H5dfBuz29K8323XihH7UU7lK4vWzfM9+O\n5Rye5n5CDCTIBr+LyqYgMJwQ92G05l6mWKtoG+7onLsWGAncaWZP4Q3QPBf4C6gBqSdtNrMnwu9v\nAYoCfwLfAsPMrJmZTUjnMluAGs65onnwESqE/0w7LfKeFO9FJU2xJAIwwQbRyw1nFZO4hua0IUhP\n4qjmd2EZ+Bu4lxAH2MM1nM9oW+x3SWk558oDY4A+ZrYzvPlvYLmZ7XDOHQskpj3OzBKdc/fg9XN/\nCFQBzsjkUtvxbo2Xxwv6lDW8C5Q+9DKdYy283YBnzWxmmveTw3+mHURblCjPz6guTiRfeUMGz6WH\nq89qxtOeplxBkB7EUdXv4sL2A68SYjwBzuMbanJZtHXDpHArUBL4JMW2C4DZ4b8HgFB6B5rZeOfc\nbcCFQC8z25/JdYIcDui057k+52WncuiXRdpejlKk84spmqhbRiSt0fY7U+1sbqABW/mZfwNPEGSt\njzUZMA1oizGfLXTgAqZYqygOdoCWwCIz+yfFtgvw7hKAF5yZzd85Hy+0+zvnMmuIVgKSzWzr0RSb\ngT/DNaT99V4Rbz2rqKWWu0hGRtuvwFn0cA1YxThu4AxOIsS1xNEa8mW+miRgOjCOIDsJ8S/u500b\nmg9XjoTiwO+HXoS7aRpxuOW+Hi+Yj+Cca4I3AuZF4E7gXmBwBtepiPdwUXrnSdktk5EMu2XMbK1z\n7jeg/qG6w79oGgKvZXFeX+khJpHs6uNKsY2H+JOu/EFlWhHkGuI4C4iL8LU2AO8S4gMCHMce6vMK\nVbiPhOh9aCYt59zdQDMzuyH8egxwtZlVSbHPuvA+G1JsKwrMA+7Ba+UvxWs5NzKzVelc52agg5nl\n1XDIAeG6W4ZfdwSeABqm+VYSVRTuIrnRwzVgI0P4ldZsphiNSKYZcZyJoxFemzUn9uItprEAYz4h\nVhHHWSyhJv/lVSuQiwiGJ/UaA6zC+w7SBChpZlem2OdVYKqZTQy/HgZcgTfMcCje3DHTgROB1cDn\nZtY3zXVGAwvNLE/mmXHOOeBR4DhgHXA6cL+ZRXW3jMJd5Gj1cPXZSWe2cRnrOJU1FOckglTFqAxU\nogiV8DoPQni34RKB7QTZgbEax2riOJm9HM9PVGIy5RjLCNvm58eKNOfcTOALMxuSYttFeMMkr8nl\nOYsBvwBnh59WlTCFu0ik9XZV2MO1HOBkDnACB6jKAaqyj0o4QhQnkaJs5Rg2U4xNlGQxZXizAD1V\nmiXnXDWgppnNC78ugzcM8hIzm5tm38+Afma2PBfXuR04Ljw+XlJQuItIxIVvZNY0s3PCr4fgTbR1\nxBww4SdVnwFushwEknOuKt4EXtfn1aRhBZnCXUQizjnXCWiN12VyHLADeNrMkjPYvynQ3Mzic3CN\nocAQM9uc5c6FkMJdRCQG6SEmEZEYpHAXEYlBCncRkRikcBcRiUEKdxGRGKRwFxGJQQp3EZEYpHAX\nEYlBCncRkRikcBcRiUEKdxGRGKRwFxGJQQp3EZEYpHAXEYlBCncRkRikcBcRiUEKdxGRGKRwFxGJ\nQQp3EZEYpHAXEYlBCncRkRikcBcRiUEKdxGRGKRwFxGJQQp3EZEYpHAXEYlBCncRkRikcBcRiUEK\ndxGRGKRwFxGJQQp3EZEYpHAXEYlBCncRkRikcBcRiUEKdxGRGKRwFxGJQQp3EZEYpHAXEYlBCncR\nkRikcBcRiUEKdxGRGKRwFxGJQQp3EZEYpHAXEYlBCncRkRikcBcRiUEKdxGRGPR/pwQl5HJuF28A\nAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f6ba4d4a710>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fig, ax = plt.subplots()\n",
    "\n",
    "an = np.linspace(0, 2*np.pi, 100)\n",
    "\n",
    "xx, yy = -20 / (3 - np.cos(an)), -7 / (2 + np.sin(an)) + np.cos(an)\n",
    "\n",
    "ax.plot(xx, yy, 'r')\n",
    "\n",
    "ax.fill(xx, yy, color='gold')\n",
    "\n",
    "ax.set_xlim(-11, -3)\n",
    "ax.set_ylim(-8, -1)\n",
    "\n",
    "x, y = xx[30], yy[30]\n",
    "\n",
    "ax.annotate(\"\",\n",
    "            xy=(x, y), \n",
    "            xytext=(x+0.4, y+1),\n",
    "            arrowprops=dict(arrowstyle=\"<-\",\n",
    "                            connectionstyle=\"arc3\")\n",
    "           )\n",
    "\n",
    "ax.annotate(\"\",\n",
    "            xy=(x, y), \n",
    "            xytext=(x-0.4, y-1),\n",
    "            arrowprops=dict(arrowstyle=\"<-\",\n",
    "                            connectionstyle=\"arc3\")\n",
    "           )\n",
    "\n",
    "ax.text(-5, -7, \"$g(\\mathbf{x}) = 0$\", fontsize=\"xx-large\")\n",
    "ax.text(-9, -3.5, \"$g(\\mathbf{x}) > 0$\", fontsize=\"xx-large\")\n",
    "\n",
    "ax.text(x+0.5, y+1, r\"$\\triangledown f(\\mathbf{x})$\", fontsize=\"xx-large\")\n",
    "ax.text(x-0.8, y-1.5, r\"$\\triangledown g(\\mathbf{x})$\", fontsize=\"xx-large\")\n",
    "ax.text(x+0.2, y, '$x_A$', fontsize=\"xx-large\")\n",
    "\n",
    "ax.plot([x], [y], 'k.', linewidth=30)\n",
    "\n",
    "ax.set_axis_off()\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 多约束问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "考虑这个问题：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\max_{\\mathbf x}~& f(\\mathbf x) &\\\\\n",
    "s.t.~& g_j(\\mathbf x) \\geq 0, &&j = 1,\\dots,J \\\\\n",
    "& h_k(\\mathbf x) \\geq 0, &&k = 1,\\dots,K \\\\\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "很容易推广得到，拉格朗日函数为：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "& L(\\mathbf {x, \\lambda, \\mu}) \\equiv f(\\mathbf x) + \\sum_{j=1}^J \\lambda_j g(\\mathbf x) + \\sum_{k=1}^K \\mu_k h(\\mathbf x) \\\\\n",
    "s.t.~& \\mu_k \\geq 0, \\mu_k h(\\mathbf x) = 0, k = 1,\\dots,K \n",
    "\\end{align}\n",
    "$$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}