la_20_equality_constrained_least_squares_kkt.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": [
        "#### Equality constrained least squares"
      ],
      "metadata": {
        "id": "s9JRN0lOHziu"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "$$\\begin{align*}\n",
        "\\text{minimize} \\,\\,& \\frac{1}{2}\\|Ax-b\\|^2\\\\\n",
        "\\text{s.t.} \\,\\, & Cx=d\n",
        "\\end{align*}$$"
      ],
      "metadata": {
        "id": "LPIeN-tCB2ps"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Write out `Lagrangian`\n",
        "\n",
        "$$\\begin{align*}\n",
        "L(x, \\lambda)&=\\frac{1}{2}\\|Ax-b\\|^2+\\lambda^T(Cx-d) \\\\\n",
        "&= \\frac{1}{2}x^TA^TAx-b^TAx+\\frac{1}{2}b^Tb+\\lambda^TCx-\\lambda^Td\n",
        "\\end{align*}$$"
      ],
      "metadata": {
        "id": "h0BW2ZGmByH2"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Write out `optimality condition`, first\n",
        "\n",
        "$$\\nabla_xL=A^TAx-A^Tb+C^T\\lambda=0$$\n",
        "\n",
        "then\n",
        "\n",
        "$$\\nabla_{\\lambda}L=Cx-d=0$$\n",
        "\n",
        "We write these two in matrix form\n",
        "\n",
        "$$\\begin{bmatrix}A^TA & C^T \\\\ C & 0\\end{bmatrix}\\begin{bmatrix}x \\\\ \\lambda\\end{bmatrix}=\\begin{bmatrix}A^Tb \\\\ d\\end{bmatrix}$$\n",
        "\n",
        "This is known as (Karush-Kuhn-Tucker) `KKT equations` for least squares with equality constraints"
      ],
      "metadata": {
        "id": "MV1TcoLfCSez"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### Invertibility of KKT matrix"
      ],
      "metadata": {
        "id": "JyibRmW2EslS"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "The matrix (known as KKT matrix)\n",
        "\n",
        "$$\\begin{bmatrix}A^TA & C^T \\\\ C & 0\\end{bmatrix}$$\n",
        "\n",
        "is invertible `if and only if`\n",
        "\n",
        "$C$ has linearly `independent rows` (i.e., $C$ is fat or square), and $\\begin{bmatrix}A\\\\C\\end{bmatrix}$ has linearly `independent columns`"
      ],
      "metadata": {
        "id": "eotfGxMHVI_K"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "To see this, we want to show that\n",
        "\n",
        "$$\\begin{bmatrix}A^TA & C^T \\\\ C & 0\\end{bmatrix}\\begin{bmatrix}x \\\\ \\lambda\\end{bmatrix}=0$$\n",
        "\n",
        "and\n",
        "\n",
        "$$\\begin{bmatrix}A\\\\C\\end{bmatrix}x=0, C^T\\lambda=0$$\n",
        "\n",
        "have the same `solution`\n",
        "\n",
        "With this, we can have the following\n",
        "\n",
        "1) if KKT matrix is invertible, we know the only solution is $x=\\lambda=0$, and thus this is also the only solution to\n",
        "\n",
        "$$\\begin{bmatrix}A\\\\C\\end{bmatrix}x=0, C^T\\lambda=0$$\n",
        "\n",
        "therefore, $C$ has linearly independent rows and $\\begin{bmatrix}A\\\\C\\end{bmatrix}$ has linearly independent columns\n",
        "\n",
        "2) if $C$ has linearly independent rows and $\\begin{bmatrix}A\\\\C\\end{bmatrix}$ has linearly independent columns, we know $x=\\lambda=0$ is the only solution to\n",
        "\n",
        "$$\\begin{bmatrix}A\\\\C\\end{bmatrix}x=0, C^T\\lambda=0$$\n",
        "\n",
        "and therefore, it is also the only solution to KKT equations\n",
        "\n",
        "Thus, KKT matrix is invertible"
      ],
      "metadata": {
        "id": "wp_3PScNn5RT"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "a) $$\\begin{bmatrix}A^TA & C^T \\\\ C & 0\\end{bmatrix}\\begin{bmatrix}x \\\\ \\lambda\\end{bmatrix}=0 \\Longrightarrow \\begin{bmatrix}A\\\\C\\end{bmatrix}x=0, C^T\\lambda=0$$"
      ],
      "metadata": {
        "id": "m70EdT7Bz08H"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "From top block of\n",
        "\n",
        "$$\\begin{bmatrix}A^TA & C^T \\\\ C & 0\\end{bmatrix}\\begin{bmatrix}x \\\\ \\lambda\\end{bmatrix}=0$$\n",
        "\n",
        "we have $$A^TAx+C^T\\lambda=0$$\n",
        "\n",
        "Multiply both side by $x^T$\n",
        "\n",
        "$$x^TA^TAx+x^TC^T\\lambda=\\|Ax\\|^2+x^TC^T\\lambda=0$$\n",
        "\n",
        "From second block equation, we have\n",
        "\n",
        "$$Cx=0 \\Longrightarrow x^TC^T=0 \\Longrightarrow x^TC^T\\lambda = 0$$\n",
        "\n",
        "Plug this into first block equation multiplied with $x^T$ and we have\n",
        "\n",
        "$$\\|Ax\\|^2=0 \\Longrightarrow Ax=0 \\Longrightarrow A^TAx=0$$\n",
        "\n",
        "Plug this into first block equation and we have\n",
        "\n",
        "$$C^T\\lambda=0$$\n",
        "\n",
        "Therefore, we have\n",
        "\n",
        "$$\\begin{bmatrix}A\\\\C\\end{bmatrix}x=0, C^T\\lambda=0$$"
      ],
      "metadata": {
        "id": "kG5F4UgHQWmm"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "b) $$ \\begin{bmatrix}A\\\\C\\end{bmatrix}x=0, C^T\\lambda=0 \\Longrightarrow \\begin{bmatrix}A^TA & C^T \\\\ C & 0\\end{bmatrix}\\begin{bmatrix}x \\\\ \\lambda\\end{bmatrix}=0 $$"
      ],
      "metadata": {
        "id": "RXKo5IfTpbhj"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "From\n",
        "\n",
        "$$\\begin{bmatrix}A\\\\C\\end{bmatrix}x=0, C^T\\lambda=0$$\n",
        "\n",
        "we have\n",
        "\n",
        "$$Ax=0\\Longrightarrow A^TAx=0, Cx=0, C^T\\lambda=0$$\n",
        "\n",
        "Therefore\n",
        "\n",
        "$$A^TAx+C^T\\lambda =0, Cx=0$$\n",
        "\n",
        "Write in matrix form and we have\n",
        "\n",
        "$$\\begin{bmatrix}A^TA & C^T \\\\ C & 0\\end{bmatrix}\\begin{bmatrix}x \\\\ \\lambda\\end{bmatrix}=0$$"
      ],
      "metadata": {
        "id": "JluUtHtaplMv"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "We see that\n",
        "\n",
        "$$\\begin{bmatrix}A^TA & C^T \\\\ C & 0\\end{bmatrix}\\begin{bmatrix}x \\\\ \\lambda\\end{bmatrix}=0$$\n",
        "\n",
        "and\n",
        "\n",
        "$$\\begin{bmatrix}A\\\\C\\end{bmatrix}x=0, C^T\\lambda=0$$\n",
        "\n",
        "have the same solution, and therefore, the if and only if condition holds"
      ],
      "metadata": {
        "id": "3uZJ2pGvqHEt"
      }
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "kjiE_A9WBe-l"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}