{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# Noncommutative variables"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "**Adapted from**: Examples 2.11 and 2.2 of [BKP16]\n",
    "\n",
    "[BKP16] Sabine Burgdorf, Igor Klep, and Janez Povh.\n",
    "*Optimization of polynomials in non-commuting variables*.\n",
    "Berlin: Springer, 2016."
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Example 2.11\n",
    "\n",
    "We consider the Example 2.11 of [BKP16] in which the polynomial with noncommutative variables\n",
    "$(x * y + x^2)^2 = x^4 + x^3y + xyx^2 + xyxy$ is tested to be sum-of-squares."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "xyxy + xyx² + x³y + x⁴",
      "text/latex": "$$ xyxy + xyx^{2} + x^{3}y + x^{4} $$"
     },
     "metadata": {},
     "execution_count": 1
    }
   ],
   "cell_type": "code",
   "source": [
    "using DynamicPolynomials\n",
    "@ncpolyvar x y\n",
    "p = (x * y + x^2)^2"
   ],
   "metadata": {},
   "execution_count": 1
  },
  {
   "cell_type": "markdown",
   "source": [
    "We first need to pick an SDP solver, see [here](https://jump.dev/JuMP.jl/v1.12/installation/#Supported-solvers) for a list of the available choices."
   ],
   "metadata": {}
  },
  {
   "outputs": [],
   "cell_type": "code",
   "source": [
    "using SumOfSquares\n",
    "import CSDP\n",
    "optimizer_constructor = optimizer_with_attributes(CSDP.Optimizer, MOI.Silent() => true)\n",
    "model = Model(optimizer_constructor)\n",
    "con_ref = @constraint(model, p in SOSCone())\n",
    "\n",
    "optimize!(model)"
   ],
   "metadata": {},
   "execution_count": 2
  },
  {
   "cell_type": "markdown",
   "source": [
    "We see that both the monomials `xy` and `yx` are considered separately, this is a difference with the commutative version."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "MonomialBasis([xy, x²])"
     },
     "metadata": {},
     "execution_count": 3
    }
   ],
   "cell_type": "code",
   "source": [
    "certificate_basis(con_ref)"
   ],
   "metadata": {},
   "execution_count": 3
  },
  {
   "cell_type": "markdown",
   "source": [
    "We see that the solution correctly uses the monomial `xy` instead of `yx`. We also identify that only the monomials `x^2` and `xy` would be needed. This would be dectected by the Newton chip method of [Section 2.3, BKP16]."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "2×2 SymMatrix{Float64}:\n 1.0  1.0\n 1.0  1.0"
     },
     "metadata": {},
     "execution_count": 4
    }
   ],
   "cell_type": "code",
   "source": [
    "gram_matrix(con_ref).Q"
   ],
   "metadata": {},
   "execution_count": 4
  },
  {
   "cell_type": "markdown",
   "source": [
    "When asking for the SOS decomposition, the numerically small entries makes the solution less readable."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(-1.0000000000000002*x*y - x^2)^2 + (-6.265166515512128e-9*x*y + 6.265166515512127e-9*x^2)^2"
     },
     "metadata": {},
     "execution_count": 5
    }
   ],
   "cell_type": "code",
   "source": [
    "sos_decomposition(con_ref)"
   ],
   "metadata": {},
   "execution_count": 5
  },
  {
   "cell_type": "markdown",
   "source": [
    "They are however easily discarded by using a nonzero tolerance:"
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(-1.0000000000000002*x*y - x^2)^2"
     },
     "metadata": {},
     "execution_count": 6
    }
   ],
   "cell_type": "code",
   "source": [
    "sos_decomposition(con_ref, 1e-6)"
   ],
   "metadata": {},
   "execution_count": 6
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Example 2.2\n",
    "\n",
    "We consider now the Example 2.2 of [BKP16] in which the polynomial with noncommutative variables\n",
    "$(x + x^{10}y^{20}x^{10})^2$ is tested to be sum-of-squares."
   ],
   "metadata": {}
  },
  {
   "outputs": [],
   "cell_type": "code",
   "source": [
    "using DynamicPolynomials\n",
    "@ncpolyvar x y\n",
    "n = 10\n",
    "p = (x + x^n * y^(2n) * x^n)^2\n",
    "\n",
    "using SumOfSquares\n",
    "model = Model(optimizer_constructor)\n",
    "con_ref = @constraint(model, p in SOSCone())\n",
    "\n",
    "optimize!(model)"
   ],
   "metadata": {},
   "execution_count": 7
  },
  {
   "cell_type": "markdown",
   "source": [
    "Only two monomials were considered for the basis of the gram matrix thanks to the Augmented Newton chip method detailed in [Section 2.4, BKP16]."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "(-1.0000000000000002*x - x^10*y^20*x^10)^2"
     },
     "metadata": {},
     "execution_count": 8
    }
   ],
   "cell_type": "code",
   "source": [
    "certificate_basis(con_ref)\n",
    "\n",
    "gram_matrix(con_ref).Q\n",
    "\n",
    "sos_decomposition(con_ref, 1e-6)"
   ],
   "metadata": {},
   "execution_count": 8
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "*This notebook was generated using [Literate.jl](https://github.com/fredrikekre/Literate.jl).*"
   ],
   "metadata": {}
  }
 ],
 "nbformat_minor": 3,
 "metadata": {
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.10.3"
  },
  "kernelspec": {
   "name": "julia-1.10",
   "display_name": "Julia 1.10.3",
   "language": "julia"
  }
 },
 "nbformat": 4
}