la_19_constrained_least_squares_Lagrange_multiplier.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "#### Constrained least squares"
      ],
      "metadata": {
        "id": "s9JRN0lOHziu"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "We have seen least squares problem that is unconstrained\n",
        "\n",
        "$$\\begin{align*}\n",
        "\\min \\,\\,& \\|Fx-g\\|^2\\\\\n",
        "\\end{align*}$$\n",
        "\n",
        "But often times we also require that $x$ satisfy some linear `equalities` or `inequalities`\n",
        "\n",
        "We only focus on linear `equalities` here\n",
        "\n",
        "$$\\begin{align*}\n",
        "\\min \\,\\,& \\|Fx-g\\|^2\\\\\n",
        "\\text{s.t.} \\,\\, & Ax=y\n",
        "\\end{align*}$$"
      ],
      "metadata": {
        "id": "LPIeN-tCB2ps"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Least norm\n"
      ],
      "metadata": {
        "id": "fTzyvvwS7nft"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "One special case is the least norm problem\n",
        "\n",
        "$$\\begin{align*}\n",
        "\\min \\,\\,& x^Tx\\\\\n",
        "\\text{s.t.} \\,\\, & Ax=y\n",
        "\\end{align*}$$\n",
        "\n",
        "That is, for a `fat` matrix $A\\in \\mathbf{R}^{m \\times n}$, $m<n$, `full rank`, find the solution $x$ that has the smallest `norm`"
      ],
      "metadata": {
        "id": "i2eTCdMzCXyc"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Right inverse"
      ],
      "metadata": {
        "id": "2vBj6NdS8mKu"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "The solution to this problem is through `right inverse` of $A$\n",
        "\n",
        "$$x_{ln}=A^T(AA^T)^{-1}y$$"
      ],
      "metadata": {
        "id": "PqtAaNkv8o1m"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "First, we can verify that $x_{ln}$ indeed has the `smallest` norm of all solutions\n",
        "\n",
        "Assume there is another $x$ such that $Ax=y$, then (with $A(x-x_{ln})=0)$\n",
        "\n",
        "$$\\begin{align*}\n",
        "(x-x_{ln})^Tx_{ln}&=(x-x_{ln})^TA^T(AA^T)^{-1}y\\\\\n",
        "&=(A(x-x_{ln}))^T(AA^T)^{-1}y\\\\\n",
        "&=0\n",
        "\\end{align*}$$\n",
        "\n",
        "Therefore, $(x-x_{ln})\\perp x_{ln}$, so\n",
        "\n",
        "$$\\|x\\|^2=\\|x_{ln}+x-x_{ln}\\|^2=\\|x_{ln}\\|^2+\\|x-x_{ln}\\|^2\\geq\\|x_{ln}\\|^2$$\n",
        "\n",
        "That is, $x_{ln}$ has the `smallest norm of all solutions`\n",
        "\n",
        "Since $x-x_{ln}$ is in nullspace $N(A)$, we also have\n",
        "\n",
        "$$x_{ln}\\perp N(A)$$"
      ],
      "metadata": {
        "id": "XoqLHDrS9FRp"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Solving least norm via Lagrange multipliers"
      ],
      "metadata": {
        "id": "f40qZl1v_OaJ"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "For\n",
        "\n",
        "$$\\begin{align*}\n",
        "\\min \\,\\,& x^Tx\\\\\n",
        "\\text{s.t.} \\,\\, & Ax=y\n",
        "\\end{align*}$$\n",
        "\n",
        "introduce the method of Lagrange multipliers $\\lambda$ and Lagrangian $L$\n",
        "\n",
        "$$L(x, \\lambda)=x^Tx+\\lambda^T(Ax-y)$$\n",
        "\n",
        "$x$ is the optimal solution $\\Longrightarrow$ the gradient of $L$ is zero (`necessary condition` for constrained optimization)\n",
        "\n",
        "$$\\nabla L =\\begin{bmatrix}\\frac{\\partial L}{\\partial x} \\\\\n",
        "\\frac{\\partial L}{\\partial \\lambda}\\end{bmatrix}=\\begin{bmatrix}2x+A^T\\lambda \\\\\n",
        "Ax-y\\end{bmatrix}=0$$\n",
        "\n",
        "From the first equation, we have\n",
        "\n",
        "$$x=-\\frac{1}{2}A^T\\lambda$$\n",
        "\n",
        "Plug into second equation\n",
        "\n",
        "$$\\lambda=-2(AA^T)^{-1}y$$\n",
        "\n",
        "Hence\n",
        "\n",
        "$$x=A^T(AA^T)^{-1}y$$"
      ],
      "metadata": {
        "id": "QWnMLFxh_oQu"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Intuition behind method of Lagrange multipliers"
      ],
      "metadata": {
        "id": "1ro8ULID_o5-"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "For constrained optimization problem\n",
        "\n",
        "$$\\begin{align*}\n",
        "\\min \\,\\,& f(x)\\\\\n",
        "\\text{s.t.} \\,\\, & g(x)=0\n",
        "\\end{align*}$$\n",
        "\n",
        "we write out the Lagrangian as\n",
        "\n",
        "$$L(x, \\lambda)=f(x)+\\lambda g(x)$$\n",
        "\n",
        "We see that $L(x,\\lambda)=f(x)$ holds `in the region` where $x$ satisfies the constraint $g(x)=0$\n",
        "\n",
        "To find maximum or minimum of $L(x,\\lambda)$ in `unconstrained` setting, we have\n",
        "\n",
        "$$\\nabla_x L=0, \\nabla_{\\lambda} L=0$$\n",
        "\n",
        "The first equation $\\nabla_x L=0$ gives\n",
        "\n",
        "$$\\nabla f + \\lambda \\nabla g=0$$\n",
        "\n",
        "and the second equation $\\nabla_{\\lambda} L=0$ gives $g(x)=0$, making $L(x,\\lambda)=f(x)$\n",
        "\n",
        "Therefore, by satisfying both\n",
        "\n",
        "$$\\nabla_x L=0, \\nabla_{\\lambda} L=0$$\n",
        "\n",
        "we find the (unconstrained) maximum or minimum of $L$, which is guaranteed to be in the region where $g(x)=0$ and thus $L(x,\\lambda)=f(x)$\n",
        "\n",
        "Therefore, it is equivalent to finding maximum or minimum of $f(x)$ itself, subject to constraint $g(x)=0$"
      ],
      "metadata": {
        "id": "LvV0zBHL_vA7"
      }
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "sLaPBGjmhiiG"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}