{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-constrained-optimization-duality-md-1 fw=all -->\n",
    "\n",
    "# Constrained Optimization and Duality\n",
    "\n",
    "Constraints and their multipliers are everywhere in deep learning, even when they\n",
    "are not written down as such: projected and clipped updates, trust regions, the\n",
    "support-vector machine and attention recast as optimization, and the\n",
    "regularization-as-constraint equivalence behind weight decay. This is the\n",
    "Boyd-style section of the chapter [@Boyd.Vandenberghe.2004]. It teaches you\n",
    "to *read* a constrained problem and its dual: to recognize that a multiplier\n",
    "is a shadow price, that complementary slackness pins down which constraints are\n",
    "active, and that a hard problem sometimes becomes easy when viewed from the dual\n",
    "side. We build from Lagrange multipliers for equalities, to the full Lagrangian\n",
    "and KKT conditions for inequalities, then make constraints *algorithmic* with\n",
    "projections and projected gradient descent, develop Lagrangian duality and the\n",
    "strong-duality guarantee, and ground it all in worked examples: the SVM dual\n",
    "solved by projected gradient ascent, water-filling solved by bisection, and a\n",
    "tiny non-convex problem whose duality gap you can see.\n",
    "\n",
    "One idea powers everything in this section. At an unconstrained minimum the\n",
    "gradient vanishes; at a *constrained* minimum it need not, but there must be\n",
    "**no feasible descent direction**: no infinitesimal move that both respects the\n",
    "constraints and decreases the objective. Lagrange multipliers, the KKT\n",
    "conditions, and the fixed points of projected gradient descent are this one\n",
    "sentence translated into equations for three kinds of constraint sets.\n",
    "\n",
    "We lean on that section (gradients, level sets, and\n",
    "the tangency teaser we are about to grow), that section\n",
    "(stationarity and the descent lemma), and that section (convex\n",
    "sets and functions, required for KKT sufficiency and strong duality). The\n",
    "standard reference is @Boyd.Vandenberghe.2004, chapter 5;\n",
    "@Nocedal.Wright.2006 gives the numerical view. The code in\n",
    "this section is plain NumPy, because every algorithm is a handful of\n",
    "lines; we load the `d2l` module once for plotting."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "constrained-imports"
   },
   "source": [
    "%matplotlib inline\n",
    "from d2l import mxnet as d2l\n",
    "import numpy as np"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-constrained-optimization-duality-md-2 fw=all -->\n",
    "\n",
    "## Equality Constraints and Lagrange Multipliers\n",
    "\n",
    "### The Geometry: No Feasible Descent\n",
    "\n",
    "Consider the simplest constrained problem: minimize a smooth\n",
    "$f : \\mathbb{R}^n \\to \\mathbb{R}$ over the surface carved out by one smooth\n",
    "equality constraint,\n",
    "\n",
    "$$\n",
    "\\min_{\\mathbf{x}}\\; f(\\mathbf{x}) \\quad \\textrm{subject to} \\quad g(\\mathbf{x}) = 0.\n",
    "$$\n",
    "\n",
    "that section already showed us the picture: the\n",
    "admissible moves from a feasible point are, to first order, the directions\n",
    "*tangent* to the surface $\\{g = 0\\}$, and at a constrained optimum the level\n",
    "curves of $f$ *kiss* the constraint surface. the figure\n",
    "shows why tangency is forced. At a feasible point where a level curve of $f$\n",
    "*crosses* the constraint curve, the gradient $\\nabla f$ has a nonzero component\n",
    "along the constraint, so sliding along the constraint against that component\n",
    "decreases $f$ while staying feasible. A feasible descent direction exists, and\n",
    "the point cannot be optimal. Only where the level curve is *tangent* to the\n",
    "constraint does every feasible direction become neutral to first order, and\n",
    "tangency of the curves is parallelism of their normals: $\\nabla f$ must be a\n",
    "multiple of $\\nabla g$.\n",
    "\n",
    "![Minimizing $f$ along the constraint curve $g(\\mathbf{x})=0$. At a non-optimal feasible point the gradient $\\nabla f$ has a component along the constraint, so sliding along the curve descends. At the optimum $\\mathbf{x}^\\star$ the level set of $f$ is tangent to the constraint and the two gradients are parallel: $\\nabla f = -\\nu\\,\\nabla g$.](../img/mdl-opt-lagrange-tangency.svg)\n",
    "\n",
    "**Proposition (Lagrange condition).** *Let $f$ and $g$ be continuously\n",
    "differentiable, and let $\\mathbf{x}^\\star$ be a local minimum of $f$ on\n",
    "$\\{\\mathbf{x} : g(\\mathbf{x}) = 0\\}$ at which $\\nabla g(\\mathbf{x}^\\star) \\neq \\mathbf{0}$.\n",
    "Then there is a unique scalar $\\nu^\\star$, the* **Lagrange multiplier**,\n",
    "*with*\n",
    "\n",
    "$$\n",
    "\\nabla f(\\mathbf{x}^\\star) + \\nu^\\star\\,\\nabla g(\\mathbf{x}^\\star) = \\mathbf{0}.\n",
    "$$\n",
    "\n",
    "**Proof.** The first-order feasible directions at $\\mathbf{x}^\\star$ are the\n",
    "tangent directions $\\mathbf{v}$ with $\\nabla g(\\mathbf{x}^\\star)^\\top\\mathbf{v} = 0$.\n",
    "Because $\\nabla g(\\mathbf{x}^\\star) \\neq \\mathbf{0}$, the implicit function\n",
    "theorem (stated in that section, and taken on faith at\n",
    "this chapter's level of rigor) makes the feasible set a genuine smooth surface\n",
    "near $\\mathbf{x}^\\star$:\n",
    "every such $\\mathbf{v}$ is the velocity of some curve $\\mathbf{x}(t)$ that stays\n",
    "on the surface with $\\mathbf{x}(0) = \\mathbf{x}^\\star$,\n",
    "$\\dot{\\mathbf{x}}(0) = \\mathbf{v}$. Since $\\mathbf{x}^\\star$ minimizes $f$ along\n",
    "each such curve, and the curve can be traversed in *both* directions $\\pm\\mathbf{v}$,\n",
    "the derivative at $t = 0$ must vanish rather than merely be nonnegative:\n",
    "\n",
    "$$\n",
    "\\left.\\frac{d}{dt} f(\\mathbf{x}(t))\\right|_{t=0} = \\nabla f(\\mathbf{x}^\\star)^\\top \\mathbf{v} = 0\n",
    "\\quad\\textrm{for every } \\mathbf{v} \\perp \\nabla g(\\mathbf{x}^\\star).\n",
    "$$\n",
    "\n",
    "So $\\nabla f(\\mathbf{x}^\\star)$ is orthogonal to the entire tangent hyperplane\n",
    "$\\{\\mathbf{v} : \\nabla g^\\top\\mathbf{v} = 0\\}$, whose orthogonal complement is\n",
    "the line spanned by $\\nabla g(\\mathbf{x}^\\star)$\n",
    "(that section). Hence\n",
    "$\\nabla f(\\mathbf{x}^\\star) = -\\nu^\\star \\nabla g(\\mathbf{x}^\\star)$ for exactly\n",
    "one scalar $\\nu^\\star$. $\\blacksquare$\n",
    "\n",
    "This is the tangency condition of that section,\n",
    "which wrote it as $\\nabla f = \\lambda\\,\\nabla g$; the two conventions agree\n",
    "with $\\nu = -\\lambda$, and the plus sign here is the one the Lagrangian below\n",
    "makes natural.\n",
    "\n",
    "The hypothesis $\\nabla g(\\mathbf{x}^\\star) \\neq \\mathbf{0}$ is called a\n",
    "**constraint qualification**, and it can fail. Minimize $f(\\mathbf{x}) = x_1$\n",
    "subject to $g(\\mathbf{x}) = x_1^2 + x_2^2 = 0$: the feasible set is the single\n",
    "point $\\mathbf{0}$, which is therefore the minimum, yet\n",
    "$\\nabla f(\\mathbf{0}) = (1, 0)$ while $\\nabla g(\\mathbf{0}) = \\mathbf{0}$: no\n",
    "multiplier exists. The constraint set has collapsed to a point, the \"surface\" is\n",
    "not a surface, and the tangent-space argument has nothing to stand on. Whenever\n",
    "you invoke multipliers, you are implicitly certifying that the constraint\n",
    "gradients do not degenerate at the optimum.\n",
    "\n",
    "### The Lagrangian\n",
    "\n",
    "The two optimality requirements (parallel gradients *and* feasibility)\n",
    "package into stationarity of a single function of more variables, the\n",
    "**Lagrangian**\n",
    "\n",
    "$$\n",
    "\\mathcal{L}(\\mathbf{x}, \\nu) = f(\\mathbf{x}) + \\nu\\, g(\\mathbf{x}),\n",
    "$$\n",
    "\n",
    "since\n",
    "\n",
    "$$\n",
    "\\nabla_{\\mathbf{x}} \\mathcal{L} = \\nabla f + \\nu \\nabla g = \\mathbf{0}\n",
    "\\qquad\\textrm{and}\\qquad\n",
    "\\frac{\\partial \\mathcal{L}}{\\partial \\nu} = g(\\mathbf{x}) = 0\n",
    "$$\n",
    "\n",
    "are exactly the equation and the constraint. A\n",
    "constrained problem in $\\mathbf{x}$ became an unconstrained stationarity problem\n",
    "in $(\\mathbf{x}, \\nu)$; the multiplier is a *coordinate* of\n",
    "the optimality condition. With several equality constraints\n",
    "$h_j(\\mathbf{x}) = 0$, $j = 1, \\ldots, p$, each gets its own multiplier,\n",
    "$\\mathcal{L} = f + \\sum_j \\nu_j h_j$, and the same argument (now requiring the\n",
    "$\\nabla h_j(\\mathbf{x}^\\star)$ to be linearly independent) puts\n",
    "$\\nabla f(\\mathbf{x}^\\star)$ in the *span* of the constraint gradients: the\n",
    "objective's gradient is balanced by a combination of the constraint normals,\n",
    "with nothing left over along any feasible direction.\n",
    "\n",
    "### Worked Example: Closest Point on a Hyperplane\n",
    "\n",
    "Minimize $f(\\mathbf{x}) = \\mathbf{x}^\\top\\mathbf{x}$ subject to\n",
    "$h(\\mathbf{x}) = \\mathbf{a}^\\top\\mathbf{x} - b = 0$: the point of a hyperplane\n",
    "nearest the origin. Stationarity of $\\mathcal{L} = \\mathbf{x}^\\top\\mathbf{x} + \\nu(\\mathbf{a}^\\top\\mathbf{x} - b)$\n",
    "gives $2\\mathbf{x} + \\nu\\mathbf{a} = \\mathbf{0}$, so $\\mathbf{x} = -\\tfrac{\\nu}{2}\\mathbf{a}$:\n",
    "the solution is forced to lie *along the normal* $\\mathbf{a}$, which is the\n",
    "geometry doing the work. Feasibility fixes the scale,\n",
    "$\\nu^\\star = -2b/\\|\\mathbf{a}\\|^2$, hence\n",
    "\n",
    "$$\n",
    "\\mathbf{x}^\\star = \\frac{b}{\\|\\mathbf{a}\\|^2}\\,\\mathbf{a},\n",
    "$$\n",
    "\n",
    "recovering the projection formula of\n",
    "that section. The multiplier already carries\n",
    "a quantitative meaning: the optimal value is $p^\\star(b) = b^2/\\|\\mathbf{a}\\|^2$,\n",
    "and $\\partial p^\\star / \\partial b = 2b/\\|\\mathbf{a}\\|^2 = -\\nu^\\star$. The\n",
    "multiplier measures *how much the optimum moves when the constraint moves*: a\n",
    "shadow price. We will prove this in general in\n",
    "that section.\n",
    "\n",
    "## Inequality Constraints and the KKT Conditions\n",
    "\n",
    "### Active and Inactive Constraints\n",
    "\n",
    "Most constraints in practice are one-sided: a norm *at most* $r$, a probability\n",
    "*at least* $0$, a budget *not exceeded*. Consider\n",
    "\n",
    "$$\n",
    "\\min_{\\mathbf{x}}\\; f(\\mathbf{x}) \\quad \\textrm{subject to} \\quad g_i(\\mathbf{x}) \\le 0,\\; i = 1, \\ldots, m.\n",
    "$$\n",
    "\n",
    "At the optimum each inequality is in one of two regimes. Either\n",
    "$g_i(\\mathbf{x}^\\star) < 0$: the constraint is **inactive**, the optimum sits\n",
    "strictly inside its region, and locally the constraint might as well not exist.\n",
    "Or $g_i(\\mathbf{x}^\\star) = 0$: the constraint is **active** and behaves\n",
    "like an equality, pushing back against the objective.\n",
    "\n",
    "A worked example shows both regimes at once. Project a point onto a ball:\n",
    "minimize $\\tfrac12\\|\\mathbf{x} - \\mathbf{x}_0\\|^2$ subject to\n",
    "$g(\\mathbf{x}) = \\tfrac12(\\|\\mathbf{x}\\|^2 - r^2) \\le 0$. Stationarity of\n",
    "$\\mathcal{L} = \\tfrac12\\|\\mathbf{x} - \\mathbf{x}_0\\|^2 + \\lambda g(\\mathbf{x})$\n",
    "gives $(\\mathbf{x} - \\mathbf{x}_0) + \\lambda\\mathbf{x} = \\mathbf{0}$, i.e.\n",
    "$\\mathbf{x} = \\mathbf{x}_0 / (1 + \\lambda)$: the constraint can only pull the\n",
    "answer *radially inward*. If $\\|\\mathbf{x}_0\\| \\le r$ the constraint is inactive,\n",
    "$\\lambda^\\star = 0$ and $\\mathbf{x}^\\star = \\mathbf{x}_0$; if\n",
    "$\\|\\mathbf{x}_0\\| > r$ it is active, $\\|\\mathbf{x}^\\star\\| = r$ forces\n",
    "$\\lambda^\\star = \\|\\mathbf{x}_0\\|/r - 1 > 0$, and\n",
    "\n",
    "$$\n",
    "\\mathbf{x}^\\star = \\frac{\\mathbf{x}_0}{\\max\\left(1,\\; \\|\\mathbf{x}_0\\|/r\\right)}.\n",
    "$$\n",
    "\n",
    "You have used this formula: *gradient clipping* is exactly this projection\n",
    "applied to the update vector [@Pascanu.Mikolov.Bengio.2013]. And note the\n",
    "sign of the active multiplier:\n",
    "$\\lambda^\\star > 0$, never negative. An inequality constraint can only push\n",
    "*one way*, into its feasible side, so its multiplier carries a sign\n",
    "constraint that an equality multiplier does not.\n",
    "\n",
    "### The Karush--Kuhn--Tucker Conditions\n",
    "\n",
    "Assembling the general problem with both kinds of constraints,\n",
    "\n",
    "$$\n",
    "\\min_{\\mathbf{x}}\\; f(\\mathbf{x}) \\quad \\textrm{subject to} \\quad\n",
    "g_i(\\mathbf{x}) \\le 0,\\; i = 1, \\ldots, m, \\qquad h_j(\\mathbf{x}) = 0,\\; j = 1, \\ldots, p,\n",
    "$$\n",
    "\n",
    "the **Lagrangian** acquires a multiplier per constraint,\n",
    "\n",
    "$$\n",
    "\\mathcal{L}(\\mathbf{x}, \\boldsymbol{\\lambda}, \\boldsymbol{\\nu})\n",
    "= f(\\mathbf{x}) + \\sum_{i=1}^m \\lambda_i\\, g_i(\\mathbf{x}) + \\sum_{j=1}^p \\nu_j\\, h_j(\\mathbf{x}),\n",
    "\\qquad \\lambda_i \\ge 0,\n",
    "$$\n",
    "\n",
    "and the first-order optimality conditions are the four\n",
    "**Karush--Kuhn--Tucker (KKT) conditions** [@Karush.1939; @Kuhn.Tucker.1951]:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "&\\textrm{stationarity:}\n",
    "&& \\nabla f(\\mathbf{x}^\\star) + \\textstyle\\sum_i \\lambda_i^\\star \\nabla g_i(\\mathbf{x}^\\star) + \\sum_j \\nu_j^\\star \\nabla h_j(\\mathbf{x}^\\star) = \\mathbf{0}, \\\\\n",
    "&\\textrm{primal feasibility:}\n",
    "&& g_i(\\mathbf{x}^\\star) \\le 0, \\qquad h_j(\\mathbf{x}^\\star) = 0, \\\\\n",
    "&\\textrm{dual feasibility:}\n",
    "&& \\lambda_i^\\star \\ge 0, \\\\\n",
    "&\\textrm{complementary slackness:}\n",
    "&& \\lambda_i^\\star\\, g_i(\\mathbf{x}^\\star) = 0 \\quad \\textrm{for every } i.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "Three of the four you have already met: stationarity is the balanced-gradient\n",
    "condition, primal feasibility is the problem statement, dual feasibility is the\n",
    "one-way push. The fourth, **complementary slackness**, says that\n",
    "for each constraint, *at least one of* $\\lambda_i^\\star$ and\n",
    "$g_i(\\mathbf{x}^\\star)$ is zero: a constraint is either active\n",
    "($g_i = 0$, multiplier free to be positive) or priced at zero\n",
    "($\\lambda_i = 0$, constraint slack and locally irrelevant). It is the equation\n",
    "that *finds the active set*: solve a KKT system and the pattern of zero\n",
    "multipliers tells you which constraints actually shaped the answer. In the ball\n",
    "projection, complementary slackness is precisely the case split we did by hand.\n",
    "\n",
    "the figure draws stationarity plus dual feasibility:\n",
    "at the optimum, $-\\nabla f$ must be a *nonnegative combination of the active\n",
    "constraints' outward normals*. The objective pushes against the wall of active\n",
    "constraints, and the wall, which can only push back outward, absorbs it\n",
    "exactly; inactive constraints contribute nothing.\n",
    "\n",
    "![Geometry of the KKT conditions on a feasible region cut out by two inequality constraints. At the optimum $\\mathbf{x}^\\star$ one constraint is active and one is inactive: $-\\nabla f$ points along the active constraint's outward normal with $\\lambda_1 > 0$, while the inactive constraint has $\\lambda_2 = 0$. At a corner where two constraints are active, $-\\nabla f$ must lie in the cone spanned by both normals.](../img/mdl-opt-kkt-active-set.svg)\n",
    "\n",
    "How strong are these conditions? In general they are **necessary**: at any local\n",
    "minimum satisfying a constraint qualification (the standard one, *LICQ*, asks\n",
    "the active constraints' gradients to be linearly independent, the inequality\n",
    "analogue of $\\nabla g \\neq \\mathbf{0}$ above), multipliers satisfying\n",
    "the equation exist; see @Nocedal.Wright.2006, chapter 12,\n",
    "for the proof. They are not sufficient: a non-convex problem can have KKT points that\n",
    "are saddles or maxima (Exercise 3). Under convexity, however, the implication\n",
    "reverses, with a proof short enough to be memorable.\n",
    "\n",
    "**Proposition (KKT sufficiency under convexity).** *In problem\n",
    "the equation, let $f$ and every $g_i$ be convex and\n",
    "differentiable and every $h_j$ affine. If\n",
    "$(\\mathbf{x}^\\star, \\boldsymbol{\\lambda}^\\star, \\boldsymbol{\\nu}^\\star)$\n",
    "satisfies the KKT conditions the equation, then $\\mathbf{x}^\\star$ is\n",
    "a global minimum.*\n",
    "\n",
    "**Proof.** The function\n",
    "$\\varphi(\\mathbf{x}) = \\mathcal{L}(\\mathbf{x}, \\boldsymbol{\\lambda}^\\star, \\boldsymbol{\\nu}^\\star)$\n",
    "is convex: it is a nonnegative combination of convex functions plus affine terms\n",
    "(that section). Stationarity says\n",
    "$\\nabla\\varphi(\\mathbf{x}^\\star) = \\mathbf{0}$, so $\\mathbf{x}^\\star$ is a\n",
    "*global* minimizer of $\\varphi$. Now take any feasible $\\mathbf{x}$. Since\n",
    "$\\lambda_i^\\star \\ge 0$, $g_i(\\mathbf{x}) \\le 0$, and $h_j(\\mathbf{x}) = 0$,\n",
    "\n",
    "$$\n",
    "f(\\mathbf{x}) \\;\\ge\\; f(\\mathbf{x}) + \\sum_i \\lambda_i^\\star g_i(\\mathbf{x}) + \\sum_j \\nu_j^\\star h_j(\\mathbf{x})\n",
    "= \\varphi(\\mathbf{x}) \\;\\ge\\; \\varphi(\\mathbf{x}^\\star)\n",
    "= f(\\mathbf{x}^\\star),\n",
    "$$\n",
    "\n",
    "where the last equality uses complementary slackness\n",
    "($\\sum_i \\lambda_i^\\star g_i(\\mathbf{x}^\\star) = 0$) and feasibility\n",
    "($h_j(\\mathbf{x}^\\star) = 0$). $\\blacksquare$\n",
    "\n",
    "So for convex problems the KKT system *is* the answer: necessary (under a\n",
    "constraint qualification we will meet as Slater's condition) and sufficient.\n",
    "This is the bridge from \"set the gradient to zero\" to constrained problems, and\n",
    "it is how every example in the rest of this section will be solved.\n",
    "\n",
    "## Projections and Projected Gradient Descent\n",
    "\n",
    "The KKT conditions characterize the answer; this subsection turns them into an\n",
    "*algorithm*. Take the ordinary gradient step,\n",
    "and if it leaves the feasible set, snap back to the nearest feasible point.\n",
    "\n",
    "### Projection onto a Convex Set\n",
    "\n",
    "For a closed convex set $C \\subseteq \\mathbb{R}^n$, the **projection** of\n",
    "$\\mathbf{y}$ onto $C$ is the nearest feasible point,\n",
    "\n",
    "$$\n",
    "\\Pi_C(\\mathbf{y}) = \\mathop{\\mathrm{argmin}}_{\\mathbf{x} \\in C}\\; \\tfrac12 \\|\\mathbf{x} - \\mathbf{y}\\|^2.\n",
    "$$\n",
    "\n",
    "A minimizer exists whenever $C$ is nonempty: we may restrict the search to the\n",
    "intersection of $C$ with a large closed ball around $\\mathbf{y}$, which is\n",
    "compact because $C$ is closed, and the continuous objective attains its minimum\n",
    "there. It is unique because the objective is strictly convex. So\n",
    "$\\Pi_C$ is a well-defined map. Both examples we have computed are projections:\n",
    "onto a hyperplane in that section, onto a ball\n",
    "(the clipping formula) in that section.\n",
    "\n",
    "What makes projections tractable is their first-order characterization. The\n",
    "point $\\hat{\\mathbf{x}} = \\Pi_C(\\mathbf{y})$ minimizes the convex function\n",
    "$\\tfrac12\\|\\mathbf{x} - \\mathbf{y}\\|^2$ over the convex set $C$, and \"no\n",
    "feasible descent\" over a convex set takes an especially simple form: for any\n",
    "$\\mathbf{x} \\in C$ the whole segment from $\\hat{\\mathbf{x}}$ to $\\mathbf{x}$ is\n",
    "feasible, so the directional derivative along it must be nonnegative, giving\n",
    "$(\\hat{\\mathbf{x}} - \\mathbf{y})^\\top(\\mathbf{x} - \\hat{\\mathbf{x}}) \\ge 0$,\n",
    "i.e.\n",
    "\n",
    "$$\n",
    "\\left(\\mathbf{y} - \\Pi_C(\\mathbf{y})\\right)^\\top \\left(\\mathbf{x} - \\Pi_C(\\mathbf{y})\\right) \\;\\le\\; 0\n",
    "\\qquad \\textrm{for all } \\mathbf{x} \\in C.\n",
    "$$\n",
    "\n",
    "Geometrically: the *residual* $\\mathbf{y} - \\Pi_C(\\mathbf{y})$ makes an obtuse\n",
    "angle with every feasible direction; the set $C$ lies entirely on the far\n",
    "side of the supporting hyperplane through $\\Pi_C(\\mathbf{y})$ with normal\n",
    "$\\mathbf{y} - \\Pi_C(\\mathbf{y})$. The inequality is also *sufficient*: if\n",
    "$\\hat{\\mathbf{x}} \\in C$ satisfies it, apply the first-order convexity\n",
    "condition the equation to\n",
    "$\\varphi(\\mathbf{x}) = \\tfrac12\\|\\mathbf{x} - \\mathbf{y}\\|^2$, whose gradient\n",
    "at $\\hat{\\mathbf{x}}$ is $\\hat{\\mathbf{x}} - \\mathbf{y}$: for every\n",
    "$\\mathbf{x} \\in C$,\n",
    "$\\varphi(\\mathbf{x}) \\ge \\varphi(\\hat{\\mathbf{x}}) + (\\hat{\\mathbf{x}} - \\mathbf{y})^\\top(\\mathbf{x} - \\hat{\\mathbf{x}}) \\ge \\varphi(\\hat{\\mathbf{x}})$,\n",
    "so $\\hat{\\mathbf{x}} = \\Pi_C(\\mathbf{y})$. Thus\n",
    "the equation *characterizes* the projection. From this\n",
    "single inequality follows the property that makes projected methods safe.\n",
    "\n",
    "**Proposition (projections are nonexpansive).** *For a closed convex set $C$\n",
    "and all $\\mathbf{x}, \\mathbf{y} \\in \\mathbb{R}^n$,*\n",
    "\n",
    "$$\n",
    "\\|\\Pi_C(\\mathbf{x}) - \\Pi_C(\\mathbf{y})\\| \\;\\le\\; \\|\\mathbf{x} - \\mathbf{y}\\|.\n",
    "$$\n",
    "\n",
    "**Proof.** Write $\\mathbf{u} = \\Pi_C(\\mathbf{x})$, $\\mathbf{v} = \\Pi_C(\\mathbf{y})$.\n",
    "Apply the equation twice: at $\\mathbf{x}$ with test\n",
    "point $\\mathbf{v}$, and at $\\mathbf{y}$ with test point $\\mathbf{u}$:\n",
    "\n",
    "$$\n",
    "(\\mathbf{x} - \\mathbf{u})^\\top(\\mathbf{v} - \\mathbf{u}) \\le 0,\n",
    "\\qquad\n",
    "(\\mathbf{y} - \\mathbf{v})^\\top(\\mathbf{u} - \\mathbf{v}) \\le 0.\n",
    "$$\n",
    "\n",
    "Adding them gives\n",
    "$(\\mathbf{x} - \\mathbf{y} - (\\mathbf{u} - \\mathbf{v}))^\\top(\\mathbf{v} - \\mathbf{u}) \\le 0$,\n",
    "which rearranges to\n",
    "\n",
    "$$\n",
    "\\|\\mathbf{u} - \\mathbf{v}\\|^2 \\;\\le\\; (\\mathbf{x} - \\mathbf{y})^\\top (\\mathbf{u} - \\mathbf{v})\n",
    "\\;\\le\\; \\|\\mathbf{x} - \\mathbf{y}\\|\\, \\|\\mathbf{u} - \\mathbf{v}\\|\n",
    "$$\n",
    "\n",
    "by the Cauchy--Schwarz inequality the equation; divide by\n",
    "$\\|\\mathbf{u} - \\mathbf{v}\\|$ (the claim is trivial when it is zero). $\\blacksquare$\n",
    "\n",
    "Projecting can only shrink distances. Convexity is essential: projecting onto a\n",
    "*non*-convex set (say, a pair of points) can tear nearby inputs far apart, which\n",
    "is one more reason convex feasible sets are the tractable ones.\n",
    "\n",
    "### Projected Gradient Descent\n",
    "\n",
    "**Projected gradient descent** (PGD) interleaves a gradient step with a\n",
    "projection:\n",
    "\n",
    "$$\n",
    "\\mathbf{x}_{t+1} = \\Pi_C\\left(\\mathbf{x}_t - \\eta\\, \\nabla f(\\mathbf{x}_t)\\right).\n",
    "$$\n",
    "\n",
    "Everything we know about plain gradient descent\n",
    "(that section) survives. Nonexpansiveness is\n",
    "the intuition: the appended map $\\Pi_C$ cannot amplify the distance between\n",
    "iterates. The proof needs slightly more (the projection is in fact *firmly*\n",
    "nonexpansive) and we do not give it: for convex $L$-smooth $f$ with\n",
    "$\\eta = 1/L$, PGD converges at the same\n",
    "$O(1/k)$ rate as the unconstrained method [@Nesterov.2018]. Just as\n",
    "important, it stops in the right place: the fixed points of\n",
    "the equation are exactly the points with no feasible descent\n",
    "direction. Indeed, $\\mathbf{x}^\\star = \\Pi_C(\\mathbf{x}^\\star - \\eta \\nabla f(\\mathbf{x}^\\star))$\n",
    "holds iff plugging $\\mathbf{y} = \\mathbf{x}^\\star - \\eta\\nabla f(\\mathbf{x}^\\star)$\n",
    "into the equation does, which after cancelling\n",
    "$\\mathbf{x}^\\star$ reads\n",
    "\n",
    "$$\n",
    "\\nabla f(\\mathbf{x}^\\star)^\\top (\\mathbf{x} - \\mathbf{x}^\\star) \\;\\ge\\; 0\n",
    "\\qquad \\textrm{for all } \\mathbf{x} \\in C\n",
    "$$\n",
    "\n",
    "This is the constrained first-order condition, reducing to $\\nabla f = \\mathbf{0}$\n",
    "when $C = \\mathbb{R}^n$, and, under a constraint qualification such as Slater's\n",
    "(introduced below), equivalent to the KKT conditions when $C$ is given\n",
    "by convex inequalities. Deep-learning practice is full of disguised PGD steps:\n",
    "gradient clipping is the ball projection of that section,\n",
    "non-negativity is enforced by\n",
    "clamping (projection onto the orthant), and max-norm weight constraints project\n",
    "each row back onto a ball after the update. The method is practical whenever\n",
    "$\\Pi_C$ is cheap, which brings us to the projection behind sparse attention.\n",
    "\n",
    "### Projection onto the Simplex\n",
    "\n",
    "The **probability simplex**\n",
    "$\\Delta = \\{\\mathbf{x} : \\mathbf{x} \\ge 0,\\; \\sum_i x_i = 1\\}$ is where\n",
    "distributions live, and projecting onto it,\n",
    "\n",
    "$$\n",
    "\\min_{\\mathbf{x}}\\; \\tfrac12\\|\\mathbf{x} - \\mathbf{y}\\|^2\n",
    "\\quad \\textrm{subject to} \\quad \\textstyle\\sum_i x_i = 1, \\;\\; -x_i \\le 0,\n",
    "$$\n",
    "\n",
    "is a small **quadratic program** (QP: convex quadratic objective, affine\n",
    "constraints) that the KKT conditions solve *in closed form up to one scalar*.\n",
    "With multiplier $\\tau$ for the sum and $\\lambda_i \\ge 0$ for each sign\n",
    "constraint, stationarity reads $x_i - y_i + \\tau - \\lambda_i = 0$.\n",
    "Complementary slackness splits the coordinates: where $x_i > 0$ we get\n",
    "$\\lambda_i = 0$ and $x_i = y_i - \\tau$; where $x_i = 0$, dual feasibility\n",
    "$\\lambda_i = \\tau - y_i \\ge 0$ says exactly that $y_i \\le \\tau$. Both cases\n",
    "compress into one formula,\n",
    "\n",
    "$$\n",
    "x_i^\\star = \\max(y_i - \\tau,\\, 0),\n",
    "\\qquad \\textrm{with } \\tau \\textrm{ set by } \\sum_i \\max(y_i - \\tau,\\, 0) = 1.\n",
    "$$\n",
    "\n",
    "*Soft-threshold, then renormalize via the threshold*: every coordinate is\n",
    "shifted down by the same $\\tau$ and clipped at zero. The left side of the\n",
    "$\\tau$-equation is continuous, piecewise linear, and strictly decreasing where\n",
    "positive, so the threshold is unique and found by sorting: with\n",
    "$u_1 \\ge \\cdots \\ge u_n$ the sorted entries of $\\mathbf{y}$, the active set is a\n",
    "top-$k$ prefix, and $\\tau = (\\sum_{j \\le k} u_j - 1)/k$ for the largest $k$\n",
    "keeping $u_k > \\tau$, an $O(n \\log n)$ algorithm\n",
    "[@Held.Wolfe.Crowder.1974; @Duchi.Shalev-Shwartz.Singer.ea.2008]. This map,\n",
    "applied to scores instead of a softmax, is exactly *sparsemax*\n",
    "[@Martins.Astudillo.2016]: unlike softmax it produces genuinely\n",
    "sparse attention weights, with complementary slackness deciding which entries\n",
    "are zeroed. More broadly, attention itself can be read as a *regularized\n",
    "argmax* over the simplex: softmax arises from an entropy regularizer, and\n",
    "sparsemax from the squared Euclidean distance used here\n",
    "[@Niculae.Blondel.2017]. The cell below implements the sort-and-threshold\n",
    "projection,\n",
    "reconstructs all the multipliers, and checks every KKT residual numerically,\n",
    "plus a sanity check that no random feasible point does better."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "constrained-simplex-projection"
   },
   "source": [
    "def project_simplex(y):\n",
    "    \"\"\"Project y onto the probability simplex by sort-and-threshold.\"\"\"\n",
    "    u = np.sort(y)[::-1]                       # sorted descending\n",
    "    css = np.cumsum(u) - 1.0                   # cumulative sums minus budget\n",
    "    k = np.nonzero(u * np.arange(1, len(y) + 1) > css)[0][-1]\n",
    "    tau = css[k] / (k + 1.0)                   # multiplier of sum(x) = 1\n",
    "    return np.maximum(y - tau, 0.0), tau\n",
    "\n",
    "rng = np.random.default_rng(0)\n",
    "y = rng.normal(size=6)\n",
    "x, tau = project_simplex(y)\n",
    "lam = np.maximum(0.0, tau - y)                 # multipliers of x >= 0\n",
    "print('x* =', x.round(4), ' sum =', f'{x.sum():.6f}')\n",
    "print('KKT residuals: stationarity', f'{np.abs(x - y + tau - lam).max():.1e}',\n",
    "      '| comp. slack', f'{np.abs(lam * x).max():.1e}',\n",
    "      '| dual feas.', f'{lam.min():.1e}')\n",
    "# Optimality check: x* beats 10^5 random feasible points\n",
    "z = rng.exponential(size=(100000, len(y)))\n",
    "z /= z.sum(axis=1, keepdims=True)              # random points on the simplex\n",
    "print('f(x*) =', f'{0.5 * ((x - y)**2).sum():.6f}',\n",
    "      '<= best random feasible', f'{(0.5 * ((z - y)**2).sum(axis=1)).min():.6f}')"
   ],
   "execution_count": 2,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "x* = [0.0676 0.     0.5823 0.0467 0.     0.3034]  sum = 1.000000\nKKT residuals: stationarity 5.6e-17 | comp. slack 0.0e+00 | dual feas. 0.0e+00\nf(x*) = 0.158962 <= best random feasible 0.162139\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-constrained-optimization-duality-md-3 fw=all -->\n",
    "\n",
    "The stationarity, complementary-slackness, and dual-feasibility residuals all\n",
    "sit at machine precision, and two of the six coordinates came back exactly\n",
    "zero: the active sign constraints, each carrying a strictly positive\n",
    "multiplier. KKT's case analysis *was* the algorithm, and its residuals certify\n",
    "the answer.\n",
    "\n",
    "## The Dual Problem\n",
    "\n",
    "### The Lagrange Dual Function\n",
    "\n",
    "So far multipliers were unknowns solved for alongside $\\mathbf{x}$. Duality\n",
    "promotes them to *variables in their own right*. Fix\n",
    "$(\\boldsymbol{\\lambda}, \\boldsymbol{\\nu})$ with $\\boldsymbol{\\lambda} \\succeq 0$\n",
    "(elementwise, in the vector sense of the $\\succeq$ convention of\n",
    "that section)\n",
    "and minimize the Lagrangian the equation over $\\mathbf{x}$\n",
    "*unconstrained*:\n",
    "\n",
    "$$\n",
    "g(\\boldsymbol{\\lambda}, \\boldsymbol{\\nu}) = \\inf_{\\mathbf{x}}\\; \\mathcal{L}(\\mathbf{x}, \\boldsymbol{\\lambda}, \\boldsymbol{\\nu}).\n",
    "$$\n",
    "\n",
    "The infimum is over all of $\\mathbb{R}^n$ and need not be attained or even\n",
    "finite: for many multiplier values the Lagrangian is unbounded below and\n",
    "$g(\\boldsymbol{\\lambda}, \\boldsymbol{\\nu}) = -\\infty$. The dual problem below\n",
    "implicitly maximizes over the region where $g$ is finite (its *effective\n",
    "domain*); in the SVM dual we will watch exactly this mechanism produce an\n",
    "equality constraint.\n",
    "\n",
    "This **Lagrange dual function** has two universal properties, universal\n",
    "meaning they require *no* assumptions on $f$, $g_i$, $h_j$ whatsoever.\n",
    "\n",
    "**Proposition (the dual function is concave).** *For any primal problem,\n",
    "$g(\\boldsymbol{\\lambda}, \\boldsymbol{\\nu})$ in the equation\n",
    "is concave.*\n",
    "\n",
    "**Proof.** For each fixed $\\mathbf{x}$, the map\n",
    "$(\\boldsymbol{\\lambda}, \\boldsymbol{\\nu}) \\mapsto \\mathcal{L}(\\mathbf{x}, \\boldsymbol{\\lambda}, \\boldsymbol{\\nu})$\n",
    "is *affine*: the multipliers enter linearly. The dual function is the\n",
    "pointwise infimum of this family of affine functions, and a pointwise infimum\n",
    "of affine functions is concave: its **hypograph** (the set of points on or\n",
    "below its graph, the mirror image of the epigraph of\n",
    "that section) is the intersection of the\n",
    "half-spaces below the affine functions, an intersection of convex sets.\n",
    "$\\blacksquare$\n",
    "\n",
    "**Proposition (weak duality).** *If $\\mathbf{x}$ is feasible for\n",
    "the equation and $\\boldsymbol{\\lambda} \\succeq 0$, then\n",
    "$g(\\boldsymbol{\\lambda}, \\boldsymbol{\\nu}) \\le f(\\mathbf{x})$. Consequently*\n",
    "\n",
    "$$\n",
    "d^\\star \\;=\\; \\sup_{\\boldsymbol{\\lambda} \\succeq 0,\\, \\boldsymbol{\\nu}} g(\\boldsymbol{\\lambda}, \\boldsymbol{\\nu})\n",
    "\\;\\le\\; \\inf_{\\mathbf{x}\\ \\textrm{feasible}} f(\\mathbf{x}) \\;=\\; p^\\star.\n",
    "$$\n",
    "\n",
    "**Proof.** For feasible $\\mathbf{x}$: each $\\lambda_i g_i(\\mathbf{x}) \\le 0$\n",
    "(nonnegative times nonpositive) and each $\\nu_j h_j(\\mathbf{x}) = 0$, so\n",
    "\n",
    "$$\n",
    "g(\\boldsymbol{\\lambda}, \\boldsymbol{\\nu})\n",
    "\\;\\le\\; \\mathcal{L}(\\mathbf{x}, \\boldsymbol{\\lambda}, \\boldsymbol{\\nu})\n",
    "\\;=\\; f(\\mathbf{x}) + \\sum_i \\lambda_i g_i(\\mathbf{x}) + \\sum_j \\nu_j h_j(\\mathbf{x})\n",
    "\\;\\le\\; f(\\mathbf{x}).\n",
    "$$\n",
    "\n",
    "Take the supremum over $(\\boldsymbol{\\lambda}, \\boldsymbol{\\nu})$ on the left\n",
    "and the infimum over feasible $\\mathbf{x}$ on the right. $\\blacksquare$\n",
    "\n",
    "The\n",
    "**dual problem**, maximizing $g$ over $\\boldsymbol{\\lambda} \\succeq 0$, is\n",
    "*always* a convex optimization problem (maximizing a concave function over a\n",
    "convex set), even when the primal is non-convex. And its optimal\n",
    "value $d^\\star$ is always a *certified lower bound* on the primal optimum.\n",
    "Every dual feasible point is a certificate: if you exhibit some\n",
    "$(\\boldsymbol{\\lambda}, \\boldsymbol{\\nu})$ with\n",
    "$g(\\boldsymbol{\\lambda}, \\boldsymbol{\\nu}) = 17$, no one can ever find a\n",
    "feasible $\\mathbf{x}$ with $f(\\mathbf{x}) < 17$. The difference\n",
    "$p^\\star - d^\\star \\ge 0$ is the **duality gap**: the slack between the best\n",
    "bound the dual can certify and the truth.\n",
    "\n",
    "### Strong Duality and Slater's Condition\n",
    "\n",
    "When is the gap zero? For convex problems, almost always; the standard\n",
    "sufficient condition asks only for one strictly feasible point.\n",
    "\n",
    "**Proposition (Slater's condition implies strong duality).** *Suppose the\n",
    "problem the equation is convex ($f$, $g_i$ convex,\n",
    "$h_j$ affine) and there exists a strictly feasible point: some\n",
    "$\\bar{\\mathbf{x}}$ with $g_i(\\bar{\\mathbf{x}}) < 0$ for all $i$ and\n",
    "$h_j(\\bar{\\mathbf{x}}) = 0$. Then $d^\\star = p^\\star$, and the dual optimum is\n",
    "attained.* The condition is due to @Slater.1950; for the proof see\n",
    "@Boyd.Vandenberghe.2004, section 5.3.2. In the refined form of the\n",
    "condition, strictness is required only of the non-affine $g_i$: affine\n",
    "inequality constraints may hold with equality at $\\bar{\\mathbf{x}}$.\n",
    "\n",
    "The geometric idea can be sketched without the proof. Map every\n",
    "$\\mathbf{x}$ to the pair $(g(\\mathbf{x}), f(\\mathbf{x}))$ of constraint value\n",
    "and objective value, and consider the resulting region in the plane (with one\n",
    "constraint, for drawing's sake). The primal optimum $p^\\star$ is the lowest\n",
    "objective value in the left half-plane $g \\le 0$. Evaluating the dual function\n",
    "at $\\lambda$ amounts to lowering a line of slope $-\\lambda$ until it *supports*\n",
    "the region from below; its height at $g = 0$ is $g(\\lambda)$, a lower bound on\n",
    "$p^\\star$: that is weak duality drawn as a picture. For a *convex* problem\n",
    "the region is convex (more precisely, the set of points above and to the right\n",
    "of it is), so some supporting line passes through the boundary point at\n",
    "$(0, p^\\star)$; this existence of a supporting line at a boundary point of a\n",
    "convex set is the granted fact of that section, the same one\n",
    "that gives convex functions their subgradients. Slater's strictly feasible\n",
    "point guarantees the region pokes\n",
    "into the open left half-plane, ruling out the one failure mode: a *vertical*\n",
    "supporting line, which no finite $\\lambda$ can represent. Then the touching\n",
    "line's $\\lambda$ achieves $g(\\lambda) = p^\\star$: strong duality. For\n",
    "non-convex problems the region can be dented, every supporting line passes\n",
    "*below* the dent where $p^\\star$ lives, and a gap opens;\n",
    "the figure shows both situations, and we will compute\n",
    "a dented example exactly at the end of this section.\n",
    "\n",
    "![The supporting-line geometry of duality. Every $x$ maps to the pair $(g(x), f_0(x))$ of constraint and objective value; the shaded region $G$ collects them. Evaluating the dual at $\\lambda$ lowers a line of slope $-\\lambda$ until it supports $G$ from below, and its height over $g = 0$ is the dual value. (a) For a convex problem with Slater's condition the best line is tangent at $(0, p^\\star)$: strong duality. (b) For this section's non-convex example the region is dented; every supporting line passes under the dent, and the best certifies only $d^\\star < p^\\star$: a visible duality gap.](../img/mdl-opt-primal-dual-gap.svg)\n",
    "\n",
    "Three practical reasons to care. First, *the dual may be the\n",
    "easier problem*: fewer variables, simpler constraints (the SVM dual below has\n",
    "only sign constraints, where the primal couples all margins). Second, *the dual\n",
    "certifies*: any feasible dual point bounds your suboptimality, which is how\n",
    "solvers know when to stop. Third, when strong duality holds, the KKT conditions\n",
    "the equation are satisfied by the primal--dual optimal pair, so\n",
    "solving the (convex) dual *is* solving the primal: recover $\\mathbf{x}^\\star$\n",
    "as the minimizer of\n",
    "$\\mathcal{L}(\\cdot, \\boldsymbol{\\lambda}^\\star, \\boldsymbol{\\nu}^\\star)$. One\n",
    "more connection rounds out the toolkit: for linearly constrained problems the\n",
    "dual function is a *convex conjugate* in disguise. For\n",
    "$\\min f(\\mathbf{x})$ s.t. $A\\mathbf{x} \\preceq \\mathbf{b}$, the Lagrangian is\n",
    "$f(\\mathbf{x}) + \\boldsymbol{\\lambda}^\\top(A\\mathbf{x} - \\mathbf{b})$, and\n",
    "grouping the terms in $\\mathbf{x}$,\n",
    "\n",
    "$$\n",
    "g(\\boldsymbol{\\lambda})\n",
    "= \\inf_{\\mathbf{x}} \\left[ f(\\mathbf{x}) + (A^\\top\\boldsymbol{\\lambda})^\\top\\mathbf{x} \\right] - \\mathbf{b}^\\top\\boldsymbol{\\lambda}\n",
    "= -\\sup_{\\mathbf{x}} \\left[ (-A^\\top\\boldsymbol{\\lambda})^\\top\\mathbf{x} - f(\\mathbf{x}) \\right] - \\mathbf{b}^\\top\\boldsymbol{\\lambda}\n",
    "= -f^*(-A^\\top\\boldsymbol{\\lambda}) - \\mathbf{b}^\\top\\boldsymbol{\\lambda},\n",
    "$$\n",
    "\n",
    "with $f^*$ the conjugate of that section. Tables\n",
    "of conjugates are tables of duals.\n",
    "\n",
    "### Duality as a Saddle Point\n",
    "\n",
    "Strong duality has an equivalent formulation, and it\n",
    "is the shape of several modern training objectives. Notice first that the\n",
    "primal problem itself is a sup-inf statement in disguise: for any $\\mathbf{x}$,\n",
    "\n",
    "$$\n",
    "\\sup_{\\boldsymbol{\\lambda} \\succeq 0,\\, \\boldsymbol{\\nu}} \\mathcal{L}(\\mathbf{x}, \\boldsymbol{\\lambda}, \\boldsymbol{\\nu})\n",
    "= \\begin{cases} f(\\mathbf{x}) & \\textrm{if } \\mathbf{x} \\textrm{ is feasible}, \\\\ +\\infty & \\textrm{otherwise}, \\end{cases}\n",
    "$$\n",
    "\n",
    "since any violated constraint lets the corresponding multiplier drive the\n",
    "supremum to $+\\infty$, while for feasible $\\mathbf{x}$ the best the multipliers\n",
    "can do is vanish on every slack constraint. So\n",
    "$p^\\star = \\inf_{\\mathbf{x}} \\sup_{\\boldsymbol{\\lambda} \\succeq 0, \\boldsymbol{\\nu}} \\mathcal{L}$\n",
    "and, by definition,\n",
    "$d^\\star = \\sup_{\\boldsymbol{\\lambda} \\succeq 0, \\boldsymbol{\\nu}} \\inf_{\\mathbf{x}} \\mathcal{L}$:\n",
    "weak duality is the universal inequality $\\sup \\inf \\le \\inf \\sup$ (playing\n",
    "second is an advantage), and strong duality says that for this particular game\n",
    "*the order of play does not matter*. The certificate of that indifference is a\n",
    "saddle point.\n",
    "\n",
    "**Proposition (strong duality is a saddle point).** *Suppose strong duality\n",
    "holds for the equation with both optima attained, at a\n",
    "primal optimum $\\mathbf{x}^\\star$ and a dual optimum\n",
    "$(\\boldsymbol{\\lambda}^\\star, \\boldsymbol{\\nu}^\\star)$. Then\n",
    "$(\\mathbf{x}^\\star, \\boldsymbol{\\lambda}^\\star, \\boldsymbol{\\nu}^\\star)$ is a*\n",
    "**saddle point** *of the Lagrangian: for all $\\mathbf{x}$ and all\n",
    "$\\boldsymbol{\\lambda} \\succeq 0$, $\\boldsymbol{\\nu}$,*\n",
    "\n",
    "$$\n",
    "\\mathcal{L}(\\mathbf{x}^\\star, \\boldsymbol{\\lambda}, \\boldsymbol{\\nu})\n",
    "\\;\\le\\; \\mathcal{L}(\\mathbf{x}^\\star, \\boldsymbol{\\lambda}^\\star, \\boldsymbol{\\nu}^\\star)\n",
    "\\;\\le\\; \\mathcal{L}(\\mathbf{x}, \\boldsymbol{\\lambda}^\\star, \\boldsymbol{\\nu}^\\star).\n",
    "$$\n",
    "\n",
    "*Conversely, any saddle point of $\\mathcal{L}$ over\n",
    "$\\mathbf{x} \\times (\\boldsymbol{\\lambda} \\succeq 0, \\boldsymbol{\\nu})$ closes\n",
    "the duality gap, with saddle value $p^\\star = d^\\star$.*\n",
    "\n",
    "**Proof.** Chain together what we have already proved:\n",
    "\n",
    "$$\n",
    "d^\\star\n",
    "= g(\\boldsymbol{\\lambda}^\\star, \\boldsymbol{\\nu}^\\star)\n",
    "= \\inf_{\\mathbf{x}} \\mathcal{L}(\\mathbf{x}, \\boldsymbol{\\lambda}^\\star, \\boldsymbol{\\nu}^\\star)\n",
    "\\;\\le\\; \\mathcal{L}(\\mathbf{x}^\\star, \\boldsymbol{\\lambda}^\\star, \\boldsymbol{\\nu}^\\star)\n",
    "\\;\\le\\; f(\\mathbf{x}^\\star)\n",
    "= p^\\star,\n",
    "$$\n",
    "\n",
    "where the last inequality holds because $\\lambda_i^\\star \\ge 0$ and\n",
    "$g_i(\\mathbf{x}^\\star) \\le 0$ make every added term nonpositive. Strong duality\n",
    "squeezes the whole chain to equality. Equality in the first inequality says\n",
    "$\\mathbf{x}^\\star$ minimizes\n",
    "$\\mathcal{L}(\\cdot, \\boldsymbol{\\lambda}^\\star, \\boldsymbol{\\nu}^\\star)$,\n",
    "the right half of the equation. Equality in the second\n",
    "forces $\\sum_i \\lambda_i^\\star g_i(\\mathbf{x}^\\star) = 0$ (complementary\n",
    "slackness, re-derived), whence for any $\\boldsymbol{\\lambda} \\succeq 0$ and\n",
    "$\\boldsymbol{\\nu}$,\n",
    "$\\mathcal{L}(\\mathbf{x}^\\star, \\boldsymbol{\\lambda}, \\boldsymbol{\\nu})\n",
    "= f(\\mathbf{x}^\\star) + \\sum_i \\lambda_i g_i(\\mathbf{x}^\\star)\n",
    "\\le f(\\mathbf{x}^\\star)\n",
    "= \\mathcal{L}(\\mathbf{x}^\\star, \\boldsymbol{\\lambda}^\\star, \\boldsymbol{\\nu}^\\star)$,\n",
    "the left half. For the converse, a saddle point gives\n",
    "\n",
    "$$\n",
    "\\inf_{\\mathbf{x}} \\sup_{\\boldsymbol{\\lambda} \\succeq 0,\\, \\boldsymbol{\\nu}} \\mathcal{L}\n",
    "\\;\\le\\; \\sup_{\\boldsymbol{\\lambda} \\succeq 0,\\, \\boldsymbol{\\nu}} \\mathcal{L}(\\mathbf{x}^\\star, \\boldsymbol{\\lambda}, \\boldsymbol{\\nu})\n",
    "= \\mathcal{L}(\\mathbf{x}^\\star, \\boldsymbol{\\lambda}^\\star, \\boldsymbol{\\nu}^\\star)\n",
    "= \\inf_{\\mathbf{x}} \\mathcal{L}(\\mathbf{x}, \\boldsymbol{\\lambda}^\\star, \\boldsymbol{\\nu}^\\star)\n",
    "\\;\\le\\; \\sup_{\\boldsymbol{\\lambda} \\succeq 0,\\, \\boldsymbol{\\nu}} \\inf_{\\mathbf{x}} \\mathcal{L},\n",
    "$$\n",
    "\n",
    "i.e. $p^\\star \\le d^\\star$; weak duality supplies the reverse inequality.\n",
    "$\\blacksquare$\n",
    "\n",
    "The saddle-point reading is the bridge from this section to a family of\n",
    "*minimax* training objectives. Generative adversarial networks\n",
    "(that section) and adversarial\n",
    "training are $\\min_{\\boldsymbol{\\theta}} \\max_{\\boldsymbol{\\phi}}$ problems in\n",
    "exactly this mold\n",
    "[@Goodfellow.Pouget-Abadie.Mirza.ea.2014; @Madry.Makelov.Schmidt.ea.2018],\n",
    "and the question of whether the order of play matters, that is, whether a\n",
    "duality gap separates $\\min\\max$ from $\\max\\min$, is the question\n",
    "of whether a saddle point exists at all. It is also the geometry behind\n",
    "**primal--dual methods**, which descend in $\\mathbf{x}$ and ascend in\n",
    "$\\boldsymbol{\\lambda}$ simultaneously, converging (for convex problems) to the\n",
    "saddle rather than to a minimum.\n",
    "\n",
    "### Multipliers Are Shadow Prices\n",
    "\n",
    "The last universal fact explains *what the numbers\n",
    "$\\boldsymbol{\\lambda}^\\star$ mean*, and it is the reading that economics,\n",
    "operations research, and machine learning all share. Perturb the constraints:\n",
    "for $\\mathbf{u} \\in \\mathbb{R}^m$ let\n",
    "\n",
    "$$\n",
    "p^\\star(\\mathbf{u}) = \\inf\\,\\{ f(\\mathbf{x}) : g_i(\\mathbf{x}) \\le u_i,\\; h_j(\\mathbf{x}) = 0 \\},\n",
    "$$\n",
    "\n",
    "so $p^\\star(\\mathbf{0})$ is our original optimum and $u_i > 0$ *relaxes*\n",
    "constraint $i$.\n",
    "\n",
    "**Proposition (multipliers are shadow prices).** *Suppose strong duality holds\n",
    "with dual optimum $(\\boldsymbol{\\lambda}^\\star, \\boldsymbol{\\nu}^\\star)$. Then\n",
    "for every $\\mathbf{u}$,*\n",
    "\n",
    "$$\n",
    "p^\\star(\\mathbf{u}) \\;\\ge\\; p^\\star(\\mathbf{0}) - \\boldsymbol{\\lambda}^{\\star\\top} \\mathbf{u},\n",
    "$$\n",
    "\n",
    "*and if $p^\\star(\\cdot)$ is differentiable at $\\mathbf{0}$, then\n",
    "$\\lambda_i^\\star = -\\partial p^\\star / \\partial u_i$.*\n",
    "\n",
    "**Proof.** Let $\\mathbf{x}$ be feasible for the perturbed problem:\n",
    "$g_i(\\mathbf{x}) \\le u_i$, $h_j(\\mathbf{x}) = 0$. Then\n",
    "\n",
    "$$\n",
    "p^\\star(\\mathbf{0}) = g(\\boldsymbol{\\lambda}^\\star, \\boldsymbol{\\nu}^\\star)\n",
    "\\;\\le\\; f(\\mathbf{x}) + \\sum_i \\lambda_i^\\star g_i(\\mathbf{x}) + \\sum_j \\nu_j^\\star h_j(\\mathbf{x})\n",
    "\\;\\le\\; f(\\mathbf{x}) + \\boldsymbol{\\lambda}^{\\star\\top}\\mathbf{u},\n",
    "$$\n",
    "\n",
    "using strong duality, the definition of $g$ as an infimum, and\n",
    "$\\lambda_i^\\star g_i(\\mathbf{x}) \\le \\lambda_i^\\star u_i$. Taking the infimum\n",
    "over all such $\\mathbf{x}$ gives\n",
    "$p^\\star(\\mathbf{0}) \\le p^\\star(\\mathbf{u}) + \\boldsymbol{\\lambda}^{\\star\\top}\\mathbf{u}$,\n",
    "which is the equation. If $p^\\star$ is differentiable at\n",
    "$\\mathbf{0}$, then the equation says the affine function\n",
    "$p^\\star(\\mathbf{0}) - \\boldsymbol{\\lambda}^{\\star\\top}\\mathbf{u}$ minorizes\n",
    "$p^\\star(\\mathbf{u})$ and touches it at $\\mathbf{u} = \\mathbf{0}$, so it is\n",
    "the tangent there, and matching gradients gives\n",
    "$\\nabla p^\\star(\\mathbf{0}) = -\\boldsymbol{\\lambda}^\\star$. $\\blacksquare$\n",
    "\n",
    "Read $\\lambda_i^\\star$ as the **price of constraint $i$**: relax it by a unit\n",
    "and the achievable optimum improves by about $\\lambda_i^\\star$. Complementary\n",
    "slackness becomes an economic platitude: slack constraints are free\n",
    "($\\lambda_i = 0$); only binding constraints command a positive price. In the\n",
    "ball projection, $\\lambda^\\star = \\|\\mathbf{x}_0\\|/r - 1$ prices the radius; in\n",
    "the hyperplane example, $-\\nu^\\star$ priced the offset $b$; and in the\n",
    "water-filling problem below, the equality multiplier is *literally* the\n",
    "marginal value of transmit power, which we will verify by finite differences.\n",
    "\n",
    "### Weight Decay Is a Constraint\n",
    "\n",
    "The most consequential shadow price in deep learning is one you set every day.\n",
    "Weight decay (that section) adds a penalty to the training loss,\n",
    "\n",
    "$$\n",
    "\\min_{\\mathbf{w}}\\; L(\\mathbf{w}) + \\lambda \\|\\mathbf{w}\\|^2 ,\n",
    "$$\n",
    "\n",
    "and this section's machinery says exactly what that penalty *is*: the\n",
    "Lagrangian of a norm **constraint**,\n",
    "\n",
    "$$\n",
    "\\min_{\\mathbf{w}}\\; L(\\mathbf{w}) \\quad \\textrm{subject to} \\quad \\|\\mathbf{w}\\|^2 \\le r^2 .\n",
    "$$\n",
    "\n",
    "Compare stationarity conditions. The penalized problem asks\n",
    "$\\nabla L(\\mathbf{w}) + 2\\lambda \\mathbf{w} = \\mathbf{0}$; the constrained\n",
    "problem's KKT stationarity, with multiplier $\\lambda \\ge 0$ on\n",
    "$g(\\mathbf{w}) = \\|\\mathbf{w}\\|^2 - r^2$, asks\n",
    "$\\nabla L(\\mathbf{w}) + 2\\lambda \\mathbf{w} = \\mathbf{0}$: the *same\n",
    "equation*, with the weight-decay coefficient playing the multiplier's role.\n",
    "For **convex** $L$ the correspondence is exact in both directions: the\n",
    "minimizer $\\mathbf{w}_\\lambda$ of the penalized problem is the solution of the\n",
    "constrained problem with budget $r = \\|\\mathbf{w}_\\lambda\\|$ (it is feasible,\n",
    "and KKT sufficiency certifies it), and conversely any active budget $r > 0$\n",
    "with attained minimizer has a\n",
    "multiplier $\\lambda^\\star(r)$ whose penalized problem returns the same point;\n",
    "this direction uses KKT necessity, which applies because Slater's condition\n",
    "holds for every $r > 0$ ($\\mathbf{w} = \\mathbf{0}$ is strictly feasible).\n",
    "Sweeping $\\lambda$ and sweeping $r$ trace the *same* regularization path, just\n",
    "parameterized differently, and the shadow-price proposition gives the exchange\n",
    "rate: $\\lambda^\\star = -\\partial p^\\star / \\partial (r^2)$, the marginal loss\n",
    "reduction the next unit of squared-norm budget would buy. When the weight\n",
    "budget is slack (the unregularized minimizer already satisfies\n",
    "$\\|\\mathbf{w}\\| \\le r$), complementary slackness prices it at\n",
    "$\\lambda^\\star = 0$: decay that binds nothing costs nothing.\n",
    "\n",
    "Two caveats. First, for the *non-convex* losses of deep networks the\n",
    "correspondence is local and heuristic, not exact: a stationary point of the\n",
    "penalized problem is a KKT point of the matching constrained problem, but\n",
    "without convexity KKT points need not be global minima and the two problems'\n",
    "solution sets need not coincide; the same gap that separates $p^\\star$ from\n",
    "$d^\\star$ in the example below can separate the two formulations. Second, the\n",
    "same number has a third, statistical reading:\n",
    "that section derives the penalty\n",
    "$\\lambda\\|\\mathbf{w}\\|^2$ as the log of a Gaussian prior (MAP estimation),\n",
    "so one and the same $\\lambda$ is simultaneously a Lagrange multiplier, a\n",
    "price on model complexity, and a prior belief about scale. The cell below\n",
    "verifies the equivalence numerically on ridge regression\n",
    "($L(\\mathbf{w}) = \\|A\\mathbf{w} - \\mathbf{b}\\|^2$, convex, so the theorem\n",
    "applies in full): for each $\\lambda$ it solves the penalized problem in closed\n",
    "form, hands the resulting norm to the *constrained* problem as the budget $r$,\n",
    "solves that by projected gradient descent onto the $r$-ball, and recovers the\n",
    "multiplier from the KKT stationarity residual:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "constrained-weight-decay"
   },
   "source": [
    "rng = np.random.default_rng(3)\n",
    "A, b = rng.normal(size=(30, 5)), rng.normal(size=30)\n",
    "grad = lambda w: 2 * A.T @ (A @ w - b)           # gradient of L = |Aw - b|^2\n",
    "step = 1.0 / (2 * np.linalg.eigvalsh(A.T @ A).max())\n",
    "print(' lambda    r = |w_pen|   |w_con - w_pen|   recovered multiplier')\n",
    "for lam in [0.1, 1.0, 10.0]:\n",
    "    w_pen = np.linalg.solve(A.T @ A + lam * np.eye(5), A.T @ b)  # penalty form\n",
    "    r = np.linalg.norm(w_pen)                    # its norm becomes the budget\n",
    "    w = np.zeros(5)                              # constraint form: PGD, radius r\n",
    "    for _ in range(5000):\n",
    "        w -= step * grad(w)\n",
    "        w *= min(1.0, r / np.linalg.norm(w))     # project onto the r-ball\n",
    "    lam_rec = -(w @ grad(w)) / (2 * r * r)       # KKT: grad L + 2*lam*w = 0\n",
    "    print(f'{lam:7.2f}  {r:11.4f}  {np.linalg.norm(w - w_pen):15.2e}  '\n",
    "          f'{lam_rec:17.4f}')"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      " lambda    r = |w_pen|   |w_con - w_pen|   recovered multiplier\n   0.10       0.4460         9.23e-17             0.1000\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "   1.00       0.4235         9.64e-17             1.0000\n  10.00       0.2840         5.55e-17            10.0000\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-constrained-optimization-duality-md-4 fw=all -->\n",
    "\n",
    "Three different decay strengths, and in every row the constrained solution\n",
    "matches the penalized one to $10^{-16}$ while the multiplier recovered from\n",
    "the constrained problem's own KKT residual reproduces $\\lambda$ to four\n",
    "decimals. Penalty and constraint are one problem wearing two parameterizations,\n",
    "and the multiplier is the dictionary between them.\n",
    "\n",
    "## Worked Duals: SVM, Water-Filling, and a Visible Gap\n",
    "\n",
    "### The Support Vector Machine Dual\n",
    "\n",
    "The support-vector machine [@Cortes.Vapnik.1995] is the canonical example\n",
    "where the dual is the better problem. Given linearly separable data\n",
    "$(\\mathbf{x}_i, y_i)$ with labels $y_i \\in \\{\\pm 1\\}$, the *maximum-margin*\n",
    "separating hyperplane $\\mathbf{w}^\\top\\mathbf{x} + b = 0$ solves\n",
    "\n",
    "$$\n",
    "\\min_{\\mathbf{w}, b}\\; \\tfrac12 \\|\\mathbf{w}\\|^2\n",
    "\\quad \\textrm{subject to} \\quad y_i\\,(\\mathbf{w}^\\top \\mathbf{x}_i + b) \\ge 1, \\;\\; i = 1, \\ldots, n,\n",
    "$$\n",
    "\n",
    "since, by the signed-distance formula of\n",
    "that section (a point $\\mathbf{x}$ lies at\n",
    "distance $|\\mathbf{w}^\\top\\mathbf{x} + b| / \\|\\mathbf{w}\\|$ from the\n",
    "hyperplane), the two margin hyperplanes\n",
    "$\\mathbf{w}^\\top\\mathbf{x} + b = \\pm 1$ sit at distance $1/\\|\\mathbf{w}\\|$ on\n",
    "either side of the boundary, $2/\\|\\mathbf{w}\\|$ apart:\n",
    "minimizing $\\|\\mathbf{w}\\|$ *is* maximizing the margin. This is a convex QP\n",
    "with one inequality per data point; Slater holds for strictly separable data\n",
    "(scale any separating $(\\mathbf{w}, b)$ up until all margins exceed $1$), so\n",
    "strong duality is guaranteed. Form the Lagrangian with multipliers\n",
    "$\\alpha_i \\ge 0$,\n",
    "\n",
    "$$\n",
    "\\mathcal{L}(\\mathbf{w}, b, \\boldsymbol{\\alpha})\n",
    "= \\tfrac12\\|\\mathbf{w}\\|^2 + \\sum_i \\alpha_i \\left(1 - y_i(\\mathbf{w}^\\top\\mathbf{x}_i + b)\\right),\n",
    "$$\n",
    "\n",
    "and compute the dual function\n",
    "$g(\\boldsymbol{\\alpha}) = \\inf_{\\mathbf{w}, b} \\mathcal{L}$. The Lagrangian is\n",
    "*affine in $b$*, with coefficient $-\\sum_i \\alpha_i y_i$: unless that\n",
    "coefficient vanishes, sending $b$ to $\\pm\\infty$ drives $\\mathcal{L}$ to\n",
    "$-\\infty$, so $g(\\boldsymbol{\\alpha}) = -\\infty$ whenever\n",
    "$\\sum_i \\alpha_i y_i \\neq 0$. This is the effective-domain mechanism promised\n",
    "at the equation: multipliers with\n",
    "$\\sum_i \\alpha_i y_i \\neq 0$ can never win the dual's maximization, so the\n",
    "vanishing condition reappears as the dual's *equality constraint*. On that\n",
    "domain the $b$-term drops out of $\\mathcal{L}$ entirely, leaving a strictly\n",
    "convex quadratic in $\\mathbf{w}$ whose infimum is attained at its stationary\n",
    "point,\n",
    "\n",
    "$$\n",
    "\\mathbf{w} = \\sum_i \\alpha_i y_i\\, \\mathbf{x}_i,\n",
    "\\qquad\\textrm{on the domain}\\qquad\n",
    "\\sum_i \\alpha_i y_i = 0.\n",
    "$$\n",
    "\n",
    "The weight vector is a combination *of the data*, with coefficients the\n",
    "multipliers. Substituting back yields the **SVM dual**:\n",
    "\n",
    "$$\n",
    "\\max_{\\boldsymbol{\\alpha} \\succeq 0,\\ \\sum_i \\alpha_i y_i = 0}\\;\\;\n",
    "\\sum_i \\alpha_i \\;-\\; \\tfrac12 \\sum_{i,j} \\alpha_i \\alpha_j\\, y_i y_j\\, \\mathbf{x}_i^\\top \\mathbf{x}_j.\n",
    "$$\n",
    "\n",
    "Two structural payoffs before any algorithm. *Complementary slackness*,\n",
    "$\\alpha_i (1 - y_i(\\mathbf{w}^\\top\\mathbf{x}_i + b)) = 0$, says\n",
    "$\\alpha_i > 0$ only for points sitting *exactly on the margin*: the\n",
    "**support vectors**, the active constraints of the active-set picture in\n",
    "the figure. All other points have $\\alpha_i = 0$ and\n",
    "could be deleted without moving the answer. And the data enter\n",
    "the equation only through inner products\n",
    "$\\mathbf{x}_i^\\top\\mathbf{x}_j$: replace them by a kernel evaluation\n",
    "$k(\\mathbf{x}_i, \\mathbf{x}_j)$ and the same dual trains a nonlinear\n",
    "classifier, an option the primal formulation does not expose.\n",
    "\n",
    "Now let us *solve* the dual, with the tools of this section and nothing else.\n",
    "One simplification first: the equality constraint $\\sum_i \\alpha_i y_i = 0$\n",
    "entered only because the unpenalized offset $b$ made the Lagrangian affine in\n",
    "one direction. If we instead fold the\n",
    "offset into the weights (append a constant feature,\n",
    "$\\tilde{\\mathbf{x}}_i = (\\mathbf{x}_i, 1)$ and\n",
    "$\\tilde{\\mathbf{w}} = (\\mathbf{w}, b)$, so the primal becomes\n",
    "$\\min \\tfrac12\\|\\tilde{\\mathbf{w}}\\|^2$ subject to\n",
    "$y_i \\tilde{\\mathbf{w}}^\\top \\tilde{\\mathbf{x}}_i \\ge 1$), then the Lagrangian\n",
    "is strictly convex in every primal variable, its infimum is finite for every\n",
    "$\\boldsymbol{\\alpha}$, the equality constraint never appears, and the\n",
    "dual feasible set is the plain nonnegative orthant\n",
    "$\\boldsymbol{\\alpha} \\succeq 0$, on which projection is a coordinate-wise clip.\n",
    "(One caveat in labeling: this variant also regularizes the offset, so\n",
    "its maximum-margin boundary can differ slightly from\n",
    "the equation's; the duality structure is identical.) Writing\n",
    "$Q_{ij} = y_i y_j \\tilde{\\mathbf{x}}_i^\\top \\tilde{\\mathbf{x}}_j$, the dual is\n",
    "\n",
    "$$\n",
    "\\max_{\\boldsymbol{\\alpha} \\succeq 0}\\;\\; \\mathbf{1}^\\top \\boldsymbol{\\alpha} - \\tfrac12 \\boldsymbol{\\alpha}^\\top Q\\, \\boldsymbol{\\alpha},\n",
    "$$\n",
    "\n",
    "a concave quadratic over the orthant, exactly the setting of\n",
    "the equation. Projected gradient *ascent* iterates\n",
    "$\\boldsymbol{\\alpha} \\leftarrow \\max(\\mathbf{0},\\, \\boldsymbol{\\alpha} + \\eta\\,(\\mathbf{1} - Q\\boldsymbol{\\alpha}))$\n",
    "with $\\eta = 1/\\lambda_{\\max}(Q)$, the dual's own descent-lemma step size. The\n",
    "cell below runs it on a small 2-D toy problem and then checks this\n",
    "section's claims: the recovered $(\\mathbf{w}^\\star, b^\\star)$ separates the\n",
    "data, complementary slackness holds to machine precision, and the dual value\n",
    "meets the primal value: strong duality, observed."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "constrained-svm-dual"
   },
   "source": [
    "X = np.array([[1.0, 1.5], [2.0, 0.5], [2.5, 2.0], [1.5, 3.0],\n",
    "              [-1.0, -0.5], [-2.0, 1.0], [-1.5, -2.0], [0.5, -1.5]])\n",
    "y_pm = np.array([1.0, 1.0, 1.0, 1.0, -1.0, -1.0, -1.0, -1.0])\n",
    "Xa = np.hstack([X, np.ones((len(X), 1))])     # fold the offset b into w\n",
    "G = y_pm[:, None] * Xa\n",
    "Q = G @ G.T                                   # Q_ij = y_i y_j x_i^T x_j\n",
    "alpha = np.zeros(len(X))\n",
    "eta = 1.0 / np.linalg.eigvalsh(Q).max()       # 1/L for the dual objective\n",
    "for _ in range(5000):                         # projected gradient ascent\n",
    "    alpha = np.maximum(0.0, alpha + eta * (1.0 - Q @ alpha))\n",
    "w = G.T @ alpha                               # w* = sum_i alpha_i y_i x_i\n",
    "margins = y_pm * (Xa @ w)\n",
    "dual = alpha.sum() - 0.5 * alpha @ Q @ alpha\n",
    "primal = 0.5 * w @ w\n",
    "print('alpha* =', alpha.round(4))\n",
    "print('w* =', w[:2].round(4), ' b* =', w[2].round(4),\n",
    "      ' separates data:', bool((np.sign(Xa @ w) == y_pm).all()))\n",
    "print('margins y_i (w^T x_i + b) =', margins.round(4))\n",
    "print('KKT: comp. slack', f'{np.abs(alpha * (margins - 1.0)).max():.1e}',\n",
    "      '| worst primal feas.', f'{(1.0 - margins).max():.1e}')\n",
    "print(f'primal = {primal:.6f}, dual = {dual:.6f}, gap = {abs(primal - dual):.1e}')"
   ],
   "execution_count": 4,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "alpha* = [0.1309 0.0732 0.     0.     0.     0.2442 0.     0.3885]\nw* = [0.5714 0.5714]  b* = -0.4286  separates data: True\nmargins y_i (w^T x_i + b) = [1.     1.     2.1429 2.1429 1.2857 1.     2.4286 1.    ]\nKKT: comp. slack 3.0e-16 | worst primal feas. 7.8e-16\nprimal = 0.418367, dual = 0.418367, gap = 4.4e-16\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-constrained-optimization-duality-md-5 fw=all -->\n",
    "\n",
    "Read the printout against the theory. Four of the eight multipliers are\n",
    "strictly positive, and *exactly those four points* have margin $1.0000$: the\n",
    "support vectors, pinned to the margin by complementary slackness; the other\n",
    "four points sit at margins $1.29$--$2.43$ with $\\alpha_i = 0$. The solution is\n",
    "exact enough to recognize:\n",
    "$\\mathbf{w}^\\star = (\\tfrac47, \\tfrac47)$, $b^\\star = -\\tfrac37$, with\n",
    "$p^\\star = d^\\star = \\tfrac{41}{98} \\approx 0.418367$ and a primal--dual gap at\n",
    "$10^{-16}$: five thousand fixed-step projected-ascent iterations, and the gap\n",
    "(the certificate of optimality duality hands us for free) has closed to\n",
    "machine precision. As a bonus, the printout\n",
    "verifies an identity you will prove in Exercise 6:\n",
    "$\\sum_i \\alpha_i^\\star = \\|\\tilde{\\mathbf{w}}^\\star\\|^2$ at the optimum, which\n",
    "is why the dual and primal values coincide line for line.\n",
    "\n",
    "### Water-Filling\n",
    "\n",
    "Our second dual is a closed form with a famous picture. A transmitter splits a\n",
    "power budget $P$ across $n$ independent channels; channel $i$ has noise level\n",
    "$n_i > 0$, and the achievable communication rate is\n",
    "$\\sum_i \\log(1 + p_i / n_i)$ [@Cover.Thomas.1999]. The allocation problem,\n",
    "\n",
    "$$\n",
    "\\max_{\\mathbf{p}}\\; \\sum_{i=1}^n \\log\\left(1 + \\frac{p_i}{n_i}\\right)\n",
    "\\quad \\textrm{subject to} \\quad \\mathbf{p} \\succeq 0, \\;\\; \\sum_i p_i = P,\n",
    "$$\n",
    "\n",
    "is convex (concave objective, affine constraints) with Slater trivially\n",
    "satisfied, so KKT pins down the global optimum. With multiplier $\\mu$ for the\n",
    "budget and $\\lambda_i \\ge 0$ for $p_i \\ge 0$, stationarity reads\n",
    "\n",
    "$$\n",
    "\\frac{1}{n_i + p_i} = \\mu - \\lambda_i.\n",
    "$$\n",
    "\n",
    "On channels with $p_i > 0$, complementary slackness kills $\\lambda_i$ and\n",
    "forces $n_i + p_i = 1/\\mu$: *the same constant for every active channel*.\n",
    "On dry channels, $p_i = 0$ requires $\\lambda_i = \\mu - 1/n_i \\ge 0$, i.e.\n",
    "$n_i \\ge 1/\\mu$. Writing $w = 1/\\mu$ for that constant:\n",
    "\n",
    "$$\n",
    "p_i^\\star = \\max(w - n_i,\\, 0),\n",
    "\\qquad \\textrm{with } w \\textrm{ set by } \\sum_i \\max(w - n_i,\\, 0) = P.\n",
    "$$\n",
    "\n",
    "This is the **water-filling** solution:\n",
    "picture each channel as a basin whose floor sits at height $n_i$ and pour in\n",
    "$P$ units of water. As the figure shows, the water\n",
    "settles at a common level $w$, filling the deep (quiet) channels most, and\n",
    "never reaching basins whose floor is above the waterline. The level is the\n",
    "unique root of a continuous, nondecreasing, piecewise-linear function of $w$,\n",
    "so *bisection* finds it. The threshold structure is the same KKT case split\n",
    "as the simplex projection's $\\tau$, with a different objective.\n",
    "\n",
    "![Water-filling, drawn with the same noise floors and budget as the cell below. Complementary slackness in a picture: pouring $P = 3$ units of power into basins with floors at the noise levels $n_i$ fills the three quiet channels to the common level $w = 1/\\mu \\approx 1.43$, allocating $p_i^\\star = w - n_i$ to each, while the two channels whose floors sit above the waterline stay dry with $p_i^\\star = 0$.](../img/mdl-opt-water-filling.svg)\n",
    "\n",
    "The\n",
    "shadow-price proposition gives the multiplier its engineering meaning:\n",
    "$\\mu^\\star = 1/w$ is the marginal rate bought by the *next* watt of power,\n",
    "which the cell checks by re-solving at $P \\pm 10^{-4}$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "constrained-water-filling"
   },
   "source": [
    "noise = np.array([0.1, 0.4, 0.8, 1.6, 2.5])   # channel noise floors\n",
    "P = 3.0                                       # total power budget\n",
    "\n",
    "def water_fill(P, noise, steps=60):\n",
    "    lo, hi = noise.min(), noise.min() + P     # bracket for the water level\n",
    "    for _ in range(steps):                    # bisection on the level\n",
    "        mid = 0.5 * (lo + hi)\n",
    "        lo, hi = (mid, hi) if np.maximum(0, mid - noise).sum() < P else (lo, mid)\n",
    "    level = 0.5 * (lo + hi)\n",
    "    return level, np.maximum(0.0, level - noise)\n",
    "\n",
    "level, p = water_fill(P, noise)\n",
    "print('water level w =', f'{level:.6f}', ' p* =', p.round(4),\n",
    "      ' total =', f'{p.sum():.6f}')\n",
    "print('wet channels filled to common level:', (noise + p)[p > 0].round(6))\n",
    "print('dry channels above the waterline:   ', bool((noise[p == 0] >= level).all()))\n",
    "rate = lambda q: np.log(1.0 + q / noise).sum()\n",
    "dP = 1e-4                                     # shadow price, two ways\n",
    "mu = 1.0 / level\n",
    "sens = (rate(water_fill(P + dP, noise)[1])\n",
    "        - rate(water_fill(P - dP, noise)[1])) / (2 * dP)\n",
    "print(f'mu = 1/w = {mu:.6f} vs finite-difference dU*/dP = {sens:.6f}')"
   ],
   "execution_count": 5,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "water level w = 1.433333  p* = [1.3333 1.0333 0.6333 0.     0.    ]  total = 3.000000\nwet channels filled to common level: [1.433333 1.433333 1.433333]\ndry channels above the waterline:    True\nmu = 1/w = 0.697674 vs finite-difference dU*/dP = 0.697674\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-constrained-optimization-duality-md-6 fw=all -->\n",
    "\n",
    "The budget is met to ten digits, the three wet channels are filled to the\n",
    "*identical* level $w = 1.4333$, the two channels with floors $1.6$ and $2.5$\n",
    "stay dry exactly as dual feasibility demands, and the multiplier\n",
    "$\\mu = 1/w = 0.6977$ matches the finite-difference sensitivity of the optimal\n",
    "rate to the budget through six digits. The shadow price is a number you can\n",
    "measure by perturbing the constraint.\n",
    "\n",
    "### A Duality Gap You Can See\n",
    "\n",
    "Weak duality never fails; strong duality can. To watch it fail, take a problem\n",
    "small enough to solve by looking at it: on the interval $x \\in [0, 1]$,\n",
    "\n",
    "$$\n",
    "\\min_x\\; f_0(x) = -x^2\n",
    "\\quad \\textrm{subject to} \\quad f_1(x) = x - \\tfrac12 \\le 0.\n",
    "$$\n",
    "\n",
    "The objective is *concave* (this is a non-convex problem) and the\n",
    "feasible region is $[0, \\tfrac12]$, so the primal optimum is at the boundary:\n",
    "$p^\\star = f_0(\\tfrac12) = -\\tfrac14$. The dual function is computable by hand:\n",
    "$\\mathcal{L}(x, \\lambda) = -x^2 + \\lambda(x - \\tfrac12)$ is concave in $x$, so\n",
    "its minimum over $[0, 1]$ is at an endpoint, giving\n",
    "$g(\\lambda) = \\min(-\\lambda/2,\\; \\lambda/2 - 1)$: piecewise linear, concave\n",
    "(as it must be), and maximized at $\\lambda = 1$ with\n",
    "$d^\\star = -\\tfrac12 < -\\tfrac14 = p^\\star$: a duality gap of exactly\n",
    "$\\tfrac14$. The cell verifies all of it numerically and plots the dual function\n",
    "topping out strictly below $p^\\star$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "constrained-duality-gap"
   },
   "source": [
    "xs = np.linspace(0.0, 1.0, 4001)              # the domain D = [0, 1]\n",
    "f0, f1 = -xs**2, xs - 0.5                     # objective and constraint\n",
    "p_star = f0[f1 <= 0.0].min()                  # primal optimum: -1/4\n",
    "lams = np.linspace(0.0, 3.0, 601)\n",
    "g = np.array([(f0 + lam * f1).min() for lam in lams])  # dual function\n",
    "d_star, lam_star = g.max(), lams[g.argmax()]\n",
    "print(f'p* = {p_star:.4f},  d* = {d_star:.4f} at lambda = {lam_star:.2f},'\n",
    "      f'  gap = {p_star - d_star:.4f}')\n",
    "print('weak duality g(lambda) <= p* everywhere:',\n",
    "      bool((g <= p_star + 1e-12).all()))\n",
    "d2l.plot(lams, [g, np.full_like(lams, p_star)], 'lambda', 'value',\n",
    "         legend=['dual function g(lambda)', 'primal optimum p*'])"
   ],
   "execution_count": 6,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "p* = -0.2500,  d* = -0.5000 at lambda = 1.00,  gap = 0.2500\nweak duality g(lambda) <= p* everywhere: True\n"
     ]
    },
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"261.023438pt\" height=\"183.35625pt\" viewBox=\"0 0 261.023438 183.35625\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2026-07-19T14:01:50.687093</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.10.8, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M 0 183.35625 \nL 261.023438 183.35625 \nL 261.023438 0 \nL 0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"patch_2\">\n    <path d=\"M 58.523438 145.8 \nL 253.823438 145.8 \nL 253.823438 7.2 \nL 58.523438 7.2 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <path d=\"M 67.40071 145.8 \nL 67.40071 7.2 \n\" clip-path=\"url(#p8f45e31ed6)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"mc2571a5b0d\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mc2571a5b0d\" x=\"67.40071\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- 0 -->\n      <g transform=\"translate(64.21946 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \nQ 1547 4250 1301 3770 \nQ 1056 3291 1056 2328 \nQ 1056 1369 1301 889 \nQ 1547 409 2034 409 \nQ 2525 409 2770 889 \nQ 3016 1369 3016 2328 \nQ 3016 3291 2770 3770 \nQ 2525 4250 2034 4250 \nz\nM 2034 4750 \nQ 2819 4750 3233 4129 \nQ 3647 3509 3647 2328 \nQ 3647 1150 3233 529 \nQ 2819 -91 2034 -91 \nQ 1250 -91 836 529 \nQ 422 1150 422 2328 \nQ 422 3509 836 4129 \nQ 1250 4750 2034 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_3\">\n      <path d=\"M 126.582528 145.8 \nL 126.582528 7.2 \n\" clip-path=\"url(#p8f45e31ed6)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#mc2571a5b0d\" x=\"126.582528\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- 1 -->\n      <g transform=\"translate(123.401278 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_5\">\n      <path d=\"M 185.764347 145.8 \nL 185.764347 7.2 \n\" clip-path=\"url(#p8f45e31ed6)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#mc2571a5b0d\" x=\"185.764347\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 2 -->\n      <g transform=\"translate(182.583097 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \nL 3431 531 \nL 3431 0 \nL 469 0 \nL 469 531 \nQ 828 903 1448 1529 \nQ 2069 2156 2228 2338 \nQ 2531 2678 2651 2914 \nQ 2772 3150 2772 3378 \nQ 2772 3750 2511 3984 \nQ 2250 4219 1831 4219 \nQ 1534 4219 1204 4116 \nQ 875 4013 500 3803 \nL 500 4441 \nQ 881 4594 1212 4672 \nQ 1544 4750 1819 4750 \nQ 2544 4750 2975 4387 \nQ 3406 4025 3406 3419 \nQ 3406 3131 3298 2873 \nQ 3191 2616 2906 2266 \nQ 2828 2175 2409 1742 \nQ 1991 1309 1228 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-32\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_7\">\n      <path d=\"M 244.946165 145.8 \nL 244.946165 7.2 \n\" clip-path=\"url(#p8f45e31ed6)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#mc2571a5b0d\" x=\"244.946165\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 3 -->\n      <g transform=\"translate(241.764915 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-33\" d=\"M 2597 2516 \nQ 3050 2419 3304 2112 \nQ 3559 1806 3559 1356 \nQ 3559 666 3084 287 \nQ 2609 -91 1734 -91 \nQ 1441 -91 1130 -33 \nQ 819 25 488 141 \nL 488 750 \nQ 750 597 1062 519 \nQ 1375 441 1716 441 \nQ 2309 441 2620 675 \nQ 2931 909 2931 1356 \nQ 2931 1769 2642 2001 \nQ 2353 2234 1838 2234 \nL 1294 2234 \nL 1294 2753 \nL 1863 2753 \nQ 2328 2753 2575 2939 \nQ 2822 3125 2822 3475 \nQ 2822 3834 2567 4026 \nQ 2313 4219 1838 4219 \nQ 1578 4219 1281 4162 \nQ 984 4106 628 3988 \nL 628 4550 \nQ 988 4650 1302 4700 \nQ 1616 4750 1894 4750 \nQ 2613 4750 3031 4423 \nQ 3450 4097 3450 3541 \nQ 3450 3153 3228 2886 \nQ 3006 2619 2597 2516 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-33\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_5\">\n     <!-- lambda -->\n     <g transform=\"translate(137.4375 174.076563) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-6c\" d=\"M 603 4863 \nL 1178 4863 \nL 1178 0 \nL 603 0 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-61\" d=\"M 2194 1759 \nQ 1497 1759 1228 1600 \nQ 959 1441 959 1056 \nQ 959 750 1161 570 \nQ 1363 391 1709 391 \nQ 2188 391 2477 730 \nQ 2766 1069 2766 1631 \nL 2766 1759 \nL 2194 1759 \nz\nM 3341 1997 \nL 3341 0 \nL 2766 0 \nL 2766 531 \nQ 2569 213 2275 61 \nQ 1981 -91 1556 -91 \nQ 1019 -91 701 211 \nQ 384 513 384 1019 \nQ 384 1609 779 1909 \nQ 1175 2209 1959 2209 \nL 2766 2209 \nL 2766 2266 \nQ 2766 2663 2505 2880 \nQ 2244 3097 1772 3097 \nQ 1472 3097 1187 3025 \nQ 903 2953 641 2809 \nL 641 3341 \nQ 956 3463 1253 3523 \nQ 1550 3584 1831 3584 \nQ 2591 3584 2966 3190 \nQ 3341 2797 3341 1997 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6d\" d=\"M 3328 2828 \nQ 3544 3216 3844 3400 \nQ 4144 3584 4550 3584 \nQ 5097 3584 5394 3201 \nQ 5691 2819 5691 2113 \nL 5691 0 \nL 5113 0 \nL 5113 2094 \nQ 5113 2597 4934 2840 \nQ 4756 3084 4391 3084 \nQ 3944 3084 3684 2787 \nQ 3425 2491 3425 1978 \nL 3425 0 \nL 2847 0 \nL 2847 2094 \nQ 2847 2600 2669 2842 \nQ 2491 3084 2119 3084 \nQ 1678 3084 1418 2786 \nQ 1159 2488 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1356 3278 1631 3431 \nQ 1906 3584 2284 3584 \nQ 2666 3584 2933 3390 \nQ 3200 3197 3328 2828 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-62\" d=\"M 3116 1747 \nQ 3116 2381 2855 2742 \nQ 2594 3103 2138 3103 \nQ 1681 3103 1420 2742 \nQ 1159 2381 1159 1747 \nQ 1159 1113 1420 752 \nQ 1681 391 2138 391 \nQ 2594 391 2855 752 \nQ 3116 1113 3116 1747 \nz\nM 1159 2969 \nQ 1341 3281 1617 3432 \nQ 1894 3584 2278 3584 \nQ 2916 3584 3314 3078 \nQ 3713 2572 3713 1747 \nQ 3713 922 3314 415 \nQ 2916 -91 2278 -91 \nQ 1894 -91 1617 61 \nQ 1341 213 1159 525 \nL 1159 0 \nL 581 0 \nL 581 4863 \nL 1159 4863 \nL 1159 2969 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-64\" d=\"M 2906 2969 \nL 2906 4863 \nL 3481 4863 \nL 3481 0 \nL 2906 0 \nL 2906 525 \nQ 2725 213 2448 61 \nQ 2172 -91 1784 -91 \nQ 1150 -91 751 415 \nQ 353 922 353 1747 \nQ 353 2572 751 3078 \nQ 1150 3584 1784 3584 \nQ 2172 3584 2448 3432 \nQ 2725 3281 2906 2969 \nz\nM 947 1747 \nQ 947 1113 1208 752 \nQ 1469 391 1925 391 \nQ 2381 391 2643 752 \nQ 2906 1113 2906 1747 \nQ 2906 2381 2643 2742 \nQ 2381 3103 1925 3103 \nQ 1469 3103 1208 2742 \nQ 947 2381 947 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-6c\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(27.783203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(89.0625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-62\" transform=\"translate(186.474609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(249.951172 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(313.427734 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_9\">\n      <path d=\"M 58.523438 139.5 \nL 253.823438 139.5 \n\" clip-path=\"url(#p8f45e31ed6)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_10\">\n      <defs>\n       <path id=\"m443796a5d7\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m443796a5d7\" x=\"58.523438\" y=\"139.5\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- −1.50 -->\n      <g transform=\"translate(20.878125 143.299219) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-2212\" d=\"M 678 2272 \nL 4684 2272 \nL 4684 1741 \nL 678 1741 \nL 678 2272 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-2e\" d=\"M 684 794 \nL 1344 794 \nL 1344 0 \nL 684 0 \nL 684 794 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-35\" d=\"M 691 4666 \nL 3169 4666 \nL 3169 4134 \nL 1269 4134 \nL 1269 2991 \nQ 1406 3038 1543 3061 \nQ 1681 3084 1819 3084 \nQ 2600 3084 3056 2656 \nQ 3513 2228 3513 1497 \nQ 3513 744 3044 326 \nQ 2575 -91 1722 -91 \nQ 1428 -91 1123 -41 \nQ 819 9 494 109 \nL 494 744 \nQ 775 591 1075 516 \nQ 1375 441 1709 441 \nQ 2250 441 2565 725 \nQ 2881 1009 2881 1497 \nQ 2881 1984 2565 2268 \nQ 2250 2553 1709 2553 \nQ 1456 2553 1204 2497 \nQ 953 2441 691 2322 \nL 691 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-2212\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(83.789062 0)\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(147.412109 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(179.199219 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(242.822266 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_11\">\n      <path d=\"M 58.523438 114.3 \nL 253.823438 114.3 \n\" clip-path=\"url(#p8f45e31ed6)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_12\">\n      <g>\n       <use xlink:href=\"#m443796a5d7\" x=\"58.523438\" y=\"114.3\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- −1.25 -->\n      <g transform=\"translate(20.878125 118.099219) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-2212\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(83.789062 0)\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(147.412109 0)\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(179.199219 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(242.822266 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_13\">\n      <path d=\"M 58.523438 89.1 \nL 253.823438 89.1 \n\" clip-path=\"url(#p8f45e31ed6)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#m443796a5d7\" x=\"58.523438\" y=\"89.1\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- −1.00 -->\n      <g transform=\"translate(20.878125 92.899219) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-2212\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(83.789062 0)\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(147.412109 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(179.199219 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(242.822266 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_15\">\n      <path d=\"M 58.523438 63.9 \nL 253.823438 63.9 \n\" clip-path=\"url(#p8f45e31ed6)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_16\">\n      <g>\n       <use xlink:href=\"#m443796a5d7\" x=\"58.523438\" y=\"63.9\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- −0.75 -->\n      <g transform=\"translate(20.878125 67.699219) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-37\" d=\"M 525 4666 \nL 3525 4666 \nL 3525 4397 \nL 1831 0 \nL 1172 0 \nL 2766 4134 \nL 525 4134 \nL 525 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-2212\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(83.789062 0)\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(147.412109 0)\"/>\n       <use xlink:href=\"#DejaVuSans-37\" transform=\"translate(179.199219 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(242.822266 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_17\">\n      <path d=\"M 58.523438 38.7 \nL 253.823438 38.7 \n\" clip-path=\"url(#p8f45e31ed6)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_18\">\n      <g>\n       <use xlink:href=\"#m443796a5d7\" x=\"58.523438\" y=\"38.7\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- −0.50 -->\n      <g transform=\"translate(20.878125 42.499219) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-2212\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(83.789062 0)\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(147.412109 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(179.199219 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(242.822266 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_19\">\n      <path d=\"M 58.523438 13.5 \nL 253.823438 13.5 \n\" clip-path=\"url(#p8f45e31ed6)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_20\">\n      <g>\n       <use xlink:href=\"#m443796a5d7\" x=\"58.523438\" y=\"13.5\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_11\">\n      <!-- −0.25 -->\n      <g transform=\"translate(20.878125 17.299219) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-2212\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(83.789062 0)\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(147.412109 0)\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(179.199219 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(242.822266 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_12\">\n     <!-- value -->\n     <g transform=\"translate(14.798437 90.157813) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-76\" d=\"M 191 3500 \nL 800 3500 \nL 1894 563 \nL 2988 3500 \nL 3597 3500 \nL 2284 0 \nL 1503 0 \nL 191 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-75\" d=\"M 544 1381 \nL 544 3500 \nL 1119 3500 \nL 1119 1403 \nQ 1119 906 1312 657 \nQ 1506 409 1894 409 \nQ 2359 409 2629 706 \nQ 2900 1003 2900 1516 \nL 2900 3500 \nL 3475 3500 \nL 3475 0 \nL 2900 0 \nL 2900 538 \nQ 2691 219 2414 64 \nQ 2138 -91 1772 -91 \nQ 1169 -91 856 284 \nQ 544 659 544 1381 \nz\nM 1991 3584 \nL 1991 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-65\" d=\"M 3597 1894 \nL 3597 1613 \nL 953 1613 \nQ 991 1019 1311 708 \nQ 1631 397 2203 397 \nQ 2534 397 2845 478 \nQ 3156 559 3463 722 \nL 3463 178 \nQ 3153 47 2828 -22 \nQ 2503 -91 2169 -91 \nQ 1331 -91 842 396 \nQ 353 884 353 1716 \nQ 353 2575 817 3079 \nQ 1281 3584 2069 3584 \nQ 2775 3584 3186 3129 \nQ 3597 2675 3597 1894 \nz\nM 3022 2063 \nQ 3016 2534 2758 2815 \nQ 2500 3097 2075 3097 \nQ 1594 3097 1305 2825 \nQ 1016 2553 972 2059 \nL 3022 2063 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-76\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(59.179688 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(120.458984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(148.242188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(211.621094 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_21\">\n    <path d=\"M 67.40071 89.1 \nL 126.582528 38.7 \nL 244.946165 139.5 \nL 244.946165 139.5 \n\" clip-path=\"url(#p8f45e31ed6)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_22\">\n    <path d=\"M 67.40071 13.5 \nL 244.946165 13.5 \nL 244.946165 13.5 \n\" clip-path=\"url(#p8f45e31ed6)\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 58.523438 145.8 \nL 58.523438 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 253.823438 145.8 \nL 253.823438 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 58.523438 145.8 \nL 253.823438 145.8 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 58.523438 7.2 \nL 253.823438 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"legend_1\">\n    <g id=\"patch_7\">\n     <path d=\"M 65.523438 140.8 \nL 217.94375 140.8 \nQ 219.94375 140.8 219.94375 138.8 \nL 219.94375 110.44375 \nQ 219.94375 108.44375 217.94375 108.44375 \nL 65.523438 108.44375 \nQ 63.523438 108.44375 63.523438 110.44375 \nL 63.523438 138.8 \nQ 63.523438 140.8 65.523438 140.8 \nz\n\" style=\"fill: #ffffff; opacity: 0.8; stroke: #cccccc; stroke-linejoin: miter\"/>\n    </g>\n    <g id=\"line2d_23\">\n     <path d=\"M 67.523438 116.542188 \nL 77.523438 116.542188 \nL 87.523438 116.542188 \n\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n    </g>\n    <g id=\"text_13\">\n     <!-- dual function g(lambda) -->\n     <g transform=\"translate(95.523438 120.042188) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-20\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-66\" d=\"M 2375 4863 \nL 2375 4384 \nL 1825 4384 \nQ 1516 4384 1395 4259 \nQ 1275 4134 1275 3809 \nL 1275 3500 \nL 2222 3500 \nL 2222 3053 \nL 1275 3053 \nL 1275 0 \nL 697 0 \nL 697 3053 \nL 147 3053 \nL 147 3500 \nL 697 3500 \nL 697 3744 \nQ 697 4328 969 4595 \nQ 1241 4863 1831 4863 \nL 2375 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6e\" d=\"M 3513 2113 \nL 3513 0 \nL 2938 0 \nL 2938 2094 \nQ 2938 2591 2744 2837 \nQ 2550 3084 2163 3084 \nQ 1697 3084 1428 2787 \nQ 1159 2491 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1366 3272 1645 3428 \nQ 1925 3584 2291 3584 \nQ 2894 3584 3203 3211 \nQ 3513 2838 3513 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-63\" d=\"M 3122 3366 \nL 3122 2828 \nQ 2878 2963 2633 3030 \nQ 2388 3097 2138 3097 \nQ 1578 3097 1268 2742 \nQ 959 2388 959 1747 \nQ 959 1106 1268 751 \nQ 1578 397 2138 397 \nQ 2388 397 2633 464 \nQ 2878 531 3122 666 \nL 3122 134 \nQ 2881 22 2623 -34 \nQ 2366 -91 2075 -91 \nQ 1284 -91 818 406 \nQ 353 903 353 1747 \nQ 353 2603 823 3093 \nQ 1294 3584 2113 3584 \nQ 2378 3584 2631 3529 \nQ 2884 3475 3122 3366 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \nL 1172 3500 \nL 2356 3500 \nL 2356 3053 \nL 1172 3053 \nL 1172 1153 \nQ 1172 725 1289 603 \nQ 1406 481 1766 481 \nL 2356 481 \nL 2356 0 \nL 1766 0 \nQ 1100 0 847 248 \nQ 594 497 594 1153 \nL 594 3053 \nL 172 3053 \nL 172 3500 \nL 594 3500 \nL 594 4494 \nL 1172 4494 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-69\" d=\"M 603 3500 \nL 1178 3500 \nL 1178 0 \nL 603 0 \nL 603 3500 \nz\nM 603 4863 \nL 1178 4863 \nL 1178 4134 \nL 603 4134 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6f\" d=\"M 1959 3097 \nQ 1497 3097 1228 2736 \nQ 959 2375 959 1747 \nQ 959 1119 1226 758 \nQ 1494 397 1959 397 \nQ 2419 397 2687 759 \nQ 2956 1122 2956 1747 \nQ 2956 2369 2687 2733 \nQ 2419 3097 1959 3097 \nz\nM 1959 3584 \nQ 2709 3584 3137 3096 \nQ 3566 2609 3566 1747 \nQ 3566 888 3137 398 \nQ 2709 -91 1959 -91 \nQ 1206 -91 779 398 \nQ 353 888 353 1747 \nQ 353 2609 779 3096 \nQ 1206 3584 1959 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-67\" d=\"M 2906 1791 \nQ 2906 2416 2648 2759 \nQ 2391 3103 1925 3103 \nQ 1463 3103 1205 2759 \nQ 947 2416 947 1791 \nQ 947 1169 1205 825 \nQ 1463 481 1925 481 \nQ 2391 481 2648 825 \nQ 2906 1169 2906 1791 \nz\nM 3481 434 \nQ 3481 -459 3084 -895 \nQ 2688 -1331 1869 -1331 \nQ 1566 -1331 1297 -1286 \nQ 1028 -1241 775 -1147 \nL 775 -588 \nQ 1028 -725 1275 -790 \nQ 1522 -856 1778 -856 \nQ 2344 -856 2625 -561 \nQ 2906 -266 2906 331 \nL 2906 616 \nQ 2728 306 2450 153 \nQ 2172 0 1784 0 \nQ 1141 0 747 490 \nQ 353 981 353 1791 \nQ 353 2603 747 3093 \nQ 1141 3584 1784 3584 \nQ 2172 3584 2450 3431 \nQ 2728 3278 2906 2969 \nL 2906 3500 \nL 3481 3500 \nL 3481 434 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-28\" d=\"M 1984 4856 \nQ 1566 4138 1362 3434 \nQ 1159 2731 1159 2009 \nQ 1159 1288 1364 580 \nQ 1569 -128 1984 -844 \nL 1484 -844 \nQ 1016 -109 783 600 \nQ 550 1309 550 2009 \nQ 550 2706 781 3412 \nQ 1013 4119 1484 4856 \nL 1984 4856 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-29\" d=\"M 513 4856 \nL 1013 4856 \nQ 1481 4119 1714 3412 \nQ 1947 2706 1947 2009 \nQ 1947 1309 1714 600 \nQ 1481 -109 1013 -844 \nL 513 -844 \nQ 928 -128 1133 580 \nQ 1338 1288 1338 2009 \nQ 1338 2731 1133 3434 \nQ 928 4138 513 4856 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-64\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(63.476562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(126.855469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(188.134766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(215.917969 0)\"/>\n      <use xlink:href=\"#DejaVuSans-66\" transform=\"translate(247.705078 0)\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(282.910156 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(346.289062 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(409.667969 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(464.648438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(503.857422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(531.640625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(592.822266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(656.201172 0)\"/>\n      <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(687.988281 0)\"/>\n      <use xlink:href=\"#DejaVuSans-28\" transform=\"translate(751.464844 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(790.478516 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(818.261719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(879.541016 0)\"/>\n      <use xlink:href=\"#DejaVuSans-62\" transform=\"translate(976.953125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(1040.429688 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(1103.90625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-29\" transform=\"translate(1165.185547 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_24\">\n     <path d=\"M 67.523438 131.220313 \nL 77.523438 131.220313 \nL 87.523438 131.220313 \n\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_14\">\n     <!-- primal optimum p* -->\n     <g transform=\"translate(95.523438 134.720313) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-70\" d=\"M 1159 525 \nL 1159 -1331 \nL 581 -1331 \nL 581 3500 \nL 1159 3500 \nL 1159 2969 \nQ 1341 3281 1617 3432 \nQ 1894 3584 2278 3584 \nQ 2916 3584 3314 3078 \nQ 3713 2572 3713 1747 \nQ 3713 922 3314 415 \nQ 2916 -91 2278 -91 \nQ 1894 -91 1617 61 \nQ 1341 213 1159 525 \nz\nM 3116 1747 \nQ 3116 2381 2855 2742 \nQ 2594 3103 2138 3103 \nQ 1681 3103 1420 2742 \nQ 1159 2381 1159 1747 \nQ 1159 1113 1420 752 \nQ 1681 391 2138 391 \nQ 2594 391 2855 752 \nQ 3116 1113 3116 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-72\" d=\"M 2631 2963 \nQ 2534 3019 2420 3045 \nQ 2306 3072 2169 3072 \nQ 1681 3072 1420 2755 \nQ 1159 2438 1159 1844 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1341 3275 1631 3429 \nQ 1922 3584 2338 3584 \nQ 2397 3584 2469 3576 \nQ 2541 3569 2628 3553 \nL 2631 2963 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-2a\" d=\"M 3009 3897 \nL 1888 3291 \nL 3009 2681 \nL 2828 2375 \nL 1778 3009 \nL 1778 1831 \nL 1422 1831 \nL 1422 3009 \nL 372 2375 \nL 191 2681 \nL 1313 3291 \nL 191 3897 \nL 372 4206 \nL 1422 3572 \nL 1422 4750 \nL 1778 4750 \nL 1778 3572 \nL 2828 4206 \nL 3009 3897 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-70\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(63.476562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(104.589844 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(132.373047 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(229.785156 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(291.064453 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(318.847656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(350.634766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(411.816406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(475.292969 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(514.501953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(542.285156 0)\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(639.697266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(703.076172 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(800.488281 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(832.275391 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2a\" transform=\"translate(895.751953 0)\"/>\n     </g>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p8f45e31ed6\">\n   <rect x=\"58.523438\" y=\"7.2\" width=\"195.3\" height=\"138.6\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=mdl-constrained-optimization-duality-md-7 fw=all -->\n",
    "\n",
    "Note the trap this example disarms. A strictly feasible point exists\n",
    "($x = 0$ has $f_1 = -\\tfrac12 < 0$), yet the gap is real: Slater's\n",
    "condition certifies strong duality *only for convex problems*, and $f_0 = -x^2$\n",
    "is not convex. In the supporting-line picture of\n",
    "the figure, the curve\n",
    "$\\{(f_1(x), f_0(x))\\} = \\{(u, -(u + \\tfrac12)^2)\\}$ is dented from below, every\n",
    "supporting line passes under the dent at $u = 0$, and the best of them\n",
    "(slope $-1$, our $\\lambda^\\star = 1$) certifies only $-\\tfrac12$. This is the\n",
    "general situation for deep learning's loss surfaces: duals of non-convex\n",
    "training problems still give valid *lower bounds* (and are the engine of\n",
    "verification and relaxation methods), but the bound need not be tight.\n",
    "\n",
    "### Coda: A Map of Problem Classes\n",
    "\n",
    "The examples above were all quadratic programs, but they sit inside a standard\n",
    "hierarchy of convex problem classes [@Boyd.Vandenberghe.2004]; the class\n",
    "tells you which off-the-shelf solver applies:\n",
    "\n",
    "| Class | Template | Deep-learning sightings |\n",
    "|---|---|---|\n",
    "| **LP** (linear program) | linear $f$, constraints $A\\mathbf{x} \\preceq \\mathbf{b}$ | $\\ell_1$ / $\\ell_\\infty$ reformulations, optimal transport |\n",
    "| **QP** (quadratic program) | convex quadratic $f$, affine constraints | ridge, lasso, SVM dual, simplex projection, trust-region step |\n",
    "| **SOCP** (second-order cone program) | cones $\\|A\\mathbf{x} + \\mathbf{b}\\| \\le \\mathbf{c}^\\top\\mathbf{x} + d$ | max-norm weight constraints, robust losses |\n",
    "| **SDP** (semidefinite program) | matrix variable $X \\succeq 0$, the semidefinite sense of $\\succeq$ (that section) | spectral-norm bounds, nuclear-norm relaxations |\n",
    "\n",
    "Each class contains the previous ($\\mathrm{LP} \\subseteq \\mathrm{QP} \\subseteq\n",
    "\\mathrm{SOCP} \\subseteq \\mathrm{SDP}$), and all are solvable to high accuracy\n",
    "in polynomial time by interior-point methods, which replace the constraints by\n",
    "a barrier and follow the smoothed problems' solutions to the boundary\n",
    "[@Boyd.Vandenberghe.2004; @Nesterov.2018; @Nocedal.Wright.2006]. Training a\n",
    "deep network lies\n",
    "*outside* the hierarchy, since the composition of layers destroys convexity\n",
    "(that section); but many of its\n",
    "*sub-problems* live inside, where multipliers, KKT, and duality do exact work:\n",
    "projections, clipped updates, last-layer fits, and the trust-region step,\n",
    "which minimizes a local quadratic model of the objective within a ball around\n",
    "the current iterate [@Nocedal.Wright.2006].\n",
    "\n",
    "## Summary\n",
    "\n",
    "* A constrained optimum is a point with **no feasible descent direction**. For\n",
    "  one equality constraint with $\\nabla g(\\mathbf{x}^\\star) \\neq \\mathbf{0}$\n",
    "  this forces $\\nabla f = -\\nu \\nabla g$; the Lagrangian\n",
    "  $\\mathcal{L} = f + \\nu g$ packages the condition and the constraint as joint\n",
    "  stationarity.\n",
    "* With inequalities, the **KKT conditions** govern: stationarity, primal and\n",
    "  dual feasibility ($\\lambda_i \\ge 0$), and **complementary slackness**\n",
    "  $\\lambda_i g_i = 0$, which finds the active set. KKT is necessary under a\n",
    "  constraint qualification and *sufficient* for global optimality in convex\n",
    "  problems.\n",
    "* **Projections** onto closed convex sets are unique and **nonexpansive**, and\n",
    "  **projected gradient descent** $\\mathbf{x} \\leftarrow \\Pi_C(\\mathbf{x} - \\eta\\nabla f)$\n",
    "  inherits gradient descent's guarantees; its fixed points are exactly the\n",
    "  constrained first-order optima. The simplex projection is a KKT-derived\n",
    "  sort-and-threshold (sparsemax).\n",
    "* The **dual function** $g(\\boldsymbol{\\lambda}, \\boldsymbol{\\nu}) = \\inf_{\\mathbf{x}} \\mathcal{L}$\n",
    "  is *always concave*, and **weak duality** $d^\\star \\le p^\\star$ *always*\n",
    "  holds: dual points are certificates. **Slater's condition** (convexity plus a\n",
    "  strictly feasible point) closes the gap; without convexity a gap can survive\n",
    "  even with strictly feasible points.\n",
    "* Strong duality is the same statement as a **saddle point** of the\n",
    "  Lagrangian ($\\inf \\sup = \\sup \\inf$, the order of play does not matter),\n",
    "  which is the geometry behind primal--dual methods and minimax\n",
    "  objectives such as GANs and adversarial training. **Weight decay** is the\n",
    "  flagship application: the penalty\n",
    "  $\\lambda\\|\\mathbf{w}\\|^2$ and the constraint $\\|\\mathbf{w}\\|^2 \\le r^2$\n",
    "  share one KKT stationarity equation. Under convexity and suitable regularity,\n",
    "  an active constraint and its optimal multiplier connect corresponding\n",
    "  solutions; inactive constraints, zero multipliers, and nonunique solutions\n",
    "  prevent a one-to-one correspondence. For deep networks the analogy is local\n",
    "  and heuristic.\n",
    "* Multipliers are **shadow prices**: $\\lambda_i^\\star = -\\partial p^\\star/\\partial u_i$\n",
    "  measures what relaxing constraint $i$ is worth: $1/w$ in\n",
    "  water-filling, and the reason slack constraints cost nothing.\n",
    "* The SVM dual (support vectors = active constraints, kernels via inner\n",
    "  products) and water-filling (pour to a common level, bisection on the level)\n",
    "  show the full pipeline; LP/QP/SOCP/SDP is the solver map for the convex\n",
    "  sub-problems of deep learning.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Derive the Lagrange condition for *two* equality constraints: if\n",
    "   $\\mathbf{x}^\\star$ is a local minimum of $f$ on\n",
    "   $\\{h_1 = 0\\} \\cap \\{h_2 = 0\\}$ and $\\nabla h_1(\\mathbf{x}^\\star)$,\n",
    "   $\\nabla h_2(\\mathbf{x}^\\star)$ are linearly independent, show\n",
    "   $\\nabla f(\\mathbf{x}^\\star) \\in \\mathrm{span}\\{\\nabla h_1, \\nabla h_2\\}$ by\n",
    "   the no-feasible-descent argument. Then revisit the counterexample\n",
    "   ($\\min x_1$ s.t. $x_1^2 + x_2^2 = 0$) and identify exactly which step of\n",
    "   your proof fails there.\n",
    "2. Maximize the entropy $-\\sum_i p_i \\log p_i$ over the probability simplex\n",
    "   using one multiplier for $\\sum_i p_i = 1$, and show the optimum is the\n",
    "   uniform distribution. Where did you use that the $p_i > 0$ constraints are\n",
    "   inactive at the optimum? (Compare that section, which reaches\n",
    "   the same conclusion through Jensen's inequality.)\n",
    "3. Write all four KKT conditions for\n",
    "   $\\min\\, \\tfrac12\\|\\mathbf{x} - \\mathbf{x}_0\\|^2$ s.t. $\\|\\mathbf{x}\\|^2 \\le r^2$\n",
    "   and verify the clipping solution and $\\lambda^\\star = \\max(0, \\|\\mathbf{x}_0\\|/r - 1)$.\n",
    "   Then exhibit a one-dimensional *non-convex* problem with a KKT point that is\n",
    "   a local maximum: necessity without sufficiency.\n",
    "4. Show that $\\mathbf{x}^\\star$ is a fixed point of the projected gradient\n",
    "   update the equation with $C = \\{\\mathbf{x} : \\mathbf{x} \\succeq 0\\}$\n",
    "   if and only if for each coordinate either $\\partial f/\\partial x_i = 0$ and\n",
    "   $x_i^\\star \\ge 0$, or $\\partial f/\\partial x_i > 0$ and $x_i^\\star = 0$;\n",
    "   then check this is precisely KKT for the constraints $-x_i \\le 0$.\n",
    "5. Prove from the definitions that the dual function of *any* primal problem\n",
    "   is concave, and that weak duality holds (reproduce the proofs without\n",
    "   looking). Then compute the dual of the equality-constrained QP\n",
    "   $\\min\\, \\tfrac12\\mathbf{x}^\\top A \\mathbf{x} - \\mathbf{b}^\\top\\mathbf{x}$\n",
    "   s.t. $C\\mathbf{x} = \\mathbf{d}$ with $A \\succ 0$ in closed form, and verify\n",
    "   $d^\\star = p^\\star$ by solving both sides for\n",
    "   $A = \\mathrm{diag}(1, 2)$, $\\mathbf{b} = (1, 1)$, $C = (1\\;\\; 1)$, $d = 1$.\n",
    "6. For the offset-folded SVM dual\n",
    "   $\\max_{\\boldsymbol{\\alpha} \\succeq 0} \\mathbf{1}^\\top\\boldsymbol{\\alpha} - \\tfrac12 \\boldsymbol{\\alpha}^\\top Q \\boldsymbol{\\alpha}$,\n",
    "   show that at the optimum\n",
    "   $\\sum_i \\alpha_i^\\star = \\|\\tilde{\\mathbf{w}}^\\star\\|^2$ where\n",
    "   $\\tilde{\\mathbf{w}}^\\star = \\sum_i \\alpha_i^\\star y_i \\tilde{\\mathbf{x}}_i$.\n",
    "   (*Hint:* multiply the KKT stationarity condition\n",
    "   $(\\mathbf{1} - Q\\boldsymbol{\\alpha}^\\star)_i = -\\lambda_i^\\star \\le 0$ by\n",
    "   $\\alpha_i^\\star$, sum, and use complementary slackness.) Conclude that the\n",
    "   dual optimal value equals $\\tfrac12\\|\\tilde{\\mathbf{w}}^\\star\\|^2$, as the\n",
    "   `#constrained-svm-dual` cell observed numerically.\n",
    "7. In water-filling the equation, show that the optimal\n",
    "   rate $U^\\star(P)$ is concave and piecewise smooth in $P$, that the water\n",
    "   level $w(P)$ is piecewise linear and increasing, and that the shadow price\n",
    "   $\\mu = 1/w$ therefore *decreases* with the budget: diminishing returns.\n",
    "   At which values of $P$ (for the noise floors in the\n",
    "   `#constrained-water-filling` cell) does the slope change, and why?\n",
    "8. Rerun the duality-gap demo with the objective $f_0(x) = +x^2$ in place of\n",
    "   $-x^2$ (everything else unchanged). Compute $p^\\star$ and $d^\\star$ by hand\n",
    "   and numerically, and explain in terms of Slater's condition why the gap is\n",
    "   now zero.\n",
    "\n",
    "## Discussions\n",
    "\n",
    "This section is the chapter's bridge to the main book. The penalty form of\n",
    "regularization (add $\\lambda\\|\\mathbf{w}\\|^2$ to the loss) and the\n",
    "constraint form (minimize the loss subject to $\\|\\mathbf{w}\\|^2 \\le r^2$)\n",
    "are linked precisely by the Lagrangian: the weight-decay coefficient of\n",
    "that section is the multiplier of the norm constraint, and\n",
    "sweeping one traces out the solutions of the other. Projections power gradient\n",
    "clipping and constrained updates, and the simplex projection is\n",
    "sparsemax. Within\n",
    "this part, the section leans on that section (convexity, the\n",
    "conjugate) and that section (descent lemma,\n",
    "rates), and its conditioning consequences continue in\n",
    "that section.\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/constrained-optimization-duality)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-mxnet",
   "display_name": "d2l (MXNet)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
