notebooks/CVX_weakly_convex_and_Moreau_envelope.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Weakly convexとモーロー包\n",
    "\n",
    "参考：\n",
    "* [Policy Gradient in Robust MDPs with Global Convergence Guarantee](https://arxiv.org/abs/2212.10439)\n",
    "\n",
    "\n",
    "---\n",
    "\n",
    "関数$h: \\mathcal{X} \\to \\mathbb{R}$は次を満たすときに$L$-リプシッツといいます．\n",
    "任意の$x_1, x_2 \\in \\mathcal{X}$に対して，$\\|h(x_1) - h(x_2)\\| \\leq L \\|x_1 - x_2\\|$．\n",
    "\n",
    "また，任意の$x_1, x_2 \\in \\mathcal{X}$に対して\n",
    "$\\left\\|\\nabla h\\left(\\boldsymbol{x}_1\\right)-\\nabla h\\left(\\boldsymbol{x}_2\\right)\\right\\| \\leq \\ell\\left\\|\\boldsymbol{x}_1-\\boldsymbol{x}_2\\right\\|$のときに$\\ell$-smoothといいます．\n",
    "\n",
    "---\n",
    "\n",
    "**定義：Weakly convexとSmoothness**\n",
    "\n",
    "次を満たすときに関数$h: \\mathcal{X} \\to \\mathbb{R}$は$\\ell$-weakly convexであるといいます．\n",
    "任意の$\\boldsymbol{g} \\in \\partial h(\\boldsymbol{x})$と $\\boldsymbol{x}, \\boldsymbol{x}^{\\prime} \\in \\mathcal{X}$について，\n",
    "\n",
    "$$\n",
    "h\\left(\\boldsymbol{x}^{\\prime}\\right)-h(\\boldsymbol{x}) \\geq\\left\\langle\\boldsymbol{g}, \\boldsymbol{x}^{\\prime}-\\boldsymbol{x}\\right\\rangle-\\frac{\\ell}{2}\\left\\|\\boldsymbol{x}^{\\prime}-\\boldsymbol{x}\\right\\|^2\n",
    "$$\n",
    "\n",
    "ここで$\\partial h(\\boldsymbol{x})$はフレシェ劣微分を表します．\n",
    "ちなみにフレシェ劣微分は次の集合のことです：\n",
    "\n",
    "$$\n",
    "\\partial h(\\boldsymbol{x})=\n",
    "\\left\\{u \\mid \\liminf _{\\boldsymbol{x}^{\\prime} \\rightarrow \\boldsymbol{x}} h\\left(\\boldsymbol{x}^{\\prime}\\right)-h(\\boldsymbol{x})-\\left\\langle\\boldsymbol{u}, \\boldsymbol{x}^{\\prime}-\\boldsymbol{x}\\right\\rangle /\\left\\|\\boldsymbol{x}^{\\prime}-\\boldsymbol{x}\\right\\| \\geq 0\\right\\}\n",
    "$$\n",
    "\n",
    "また，上で定義したweakly-convexな$h(x)$は，\n",
    "$\\tilde{h}(\\boldsymbol{x})=h(\\boldsymbol{x}) + \\frac{\\ell}{2} \\|\\boldsymbol{x}\\|^2$とすると，$\\tilde{h}$が凸関数になります．\n",
    "１次元のときを考えてみると，$g + \\ell x \\in \\partial \\tilde{h}(x)$であり，\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\tilde{h}\\left(\\boldsymbol{x}^{\\prime}\\right)-\\tilde{h}(\\boldsymbol{x}) \n",
    "&=\n",
    "h\\left(\\boldsymbol{x}^{\\prime}\\right)-h(\\boldsymbol{x}) \n",
    "+ \\frac{\\ell}{2} {x}'^2 - \\frac{\\ell}{2} x^2\\\\\n",
    "&\\geq\\left\\langle\\boldsymbol{g}, \\boldsymbol{x}^{\\prime}-\\boldsymbol{x}\\right\\rangle - \\frac{\\ell}{2}(x' - x)^2+\\frac{\\ell}{2} x'^2 - \\frac{\\ell}{2}x^2 \\\\\n",
    "&=\\left\\langle\\boldsymbol{g}, \\boldsymbol{x}^{\\prime}-\\boldsymbol{x}\\right\\rangle + \\ell x' x - \\ell x^2 \\\\\n",
    "&=\\left\\langle\\boldsymbol{g} + \\ell x, \\boldsymbol{x}^{\\prime}-\\boldsymbol{x}\\right\\rangle\\;.\n",
    "\\end{aligned}\n",
    "$$\n",
    "なので，$\\tilde{h}$は凸関数です．\n",
    "\n",
    "---\n",
    "\n",
    "**補題: $\\ell$-smoothな関数は$\\ell$-weakly convex**\n",
    "\n",
    "証明しましょう．\n",
    "\n",
    "$r(t):=h\\left(x+t\\left(x^{\\prime}-x\\right)\\right)$とします．ここで$h(x)=r(0)$かつ$h(x')=r(1)$です．\n",
    "\n",
    "ここで，\n",
    "\n",
    "$$\n",
    "\\nabla_t r(t)=\\nabla_x h\\left(x+t\\left(x^{\\prime}-x\\right)\\right)^{\\top}\\left(x^{\\prime}-x\\right)\n",
    "$$\n",
    "\n",
    "とすると\n",
    "\n",
    "$$\n",
    "h\\left(x^{\\prime}\\right)-h(x)=r(1)-r(0)=\\int_0^1 \\nabla_t r(t) d t\n",
    "$$\n",
    "です．\n",
    "あとは\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\| h\\left(x^{\\prime}\\right)-h(x)- & \\nabla h(x)^{\\top}\\left(x^{\\prime}-x\\right) \\| \\\\\n",
    "& =\\left\\|\\int_0^1 \\nabla r(t) d t-\\nabla h(x)^{\\top}\\left(x^{\\prime}-x\\right)\\right\\| \\\\\n",
    "& \\leq \\int_0^1\\left\\|\\nabla r(t)-\\nabla h(x)^{\\top}\\left(x^{\\prime}-x\\right)\\right\\| d t \\\\\n",
    "& =\\int_0^1\\left\\|\\nabla h\\left(x+t\\left(x^{\\prime}-x\\right)\\right)^{\\top}\\left(x^{\\prime}-x\\right)-\\nabla h(x)^{\\top}\\left(x^{\\prime}-x\\right)\\right\\| d t \\\\\n",
    "& \\leq \\int_0^1\\left\\|\\nabla h\\left(x+t\\left(x^{\\prime}-x\\right)\\right)-\\nabla h(x)\\right\\| \\cdot\\left\\|\\left(x^{\\prime}-x\\right)\\right\\| d t \\\\\n",
    "& \\leq \\int_0^1 t \\ell\\left\\|x^{\\prime}-x\\right\\|^2 d t=\\frac{\\ell}{2}\\left\\|x^{\\prime}-x\\right\\|^2 .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "---\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "最適化の解析では近似停留点（approximate stationary point）に達したときの解析などをします．\n",
    "近似停留点は$\\xi \\in \\partial h(x)$について$\\min _{\\xi \\in \\partial f(\\mathbf{x})}\\|\\xi\\| \\leq \\epsilon$で一般に定義されますが，これはnonsmoothな関数ではうまく働かない可能性があります．\n",
    "（この辺の話は[On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://proceedings.mlr.press/v119/lin20a.html)に書いてあります）．\n",
    "\n",
    "例えば$h(\\cdot) = |\\cdot|$を考えてみましょう．\n",
    "このとき$\\varepsilon$-停留点は任意の$\\varepsilon \\in [0, 1)$について$x=0$です．\n",
    "つまり，この表記において近似停留点を見つけるのは，問題をそのまま解くのと同じくらい難しいことになります．\n",
    "\n",
    "そこで，weakly convexな関数の最適化には次のモーロー包を考えることが多いです．\n",
    "\n",
    "---\n",
    "\n",
    "**定義：モーロー包**\n",
    "\n",
    "関数$h: \\mathcal{X} \\to \\mathbb{R}$ と$\\lambda > 0$について，\n",
    "\n",
    "$$\n",
    "h_\\lambda(x):=\\min _{x^{\\prime} \\in \\mathcal{X}}\\left\\{h\\left(x^{\\prime}\\right)+\\frac{1}{2 \\lambda}\\left\\|x-x^{\\prime}\\right\\|^2\\right\\}\n",
    "$$\n",
    "\n",
    "をモーロー包と呼びます．\n",
    "これは$\\lambda$によって，$h(x)$のminimizerを返すか？，それとも$x$に十分近い点を返すか？を調整しています．\n",
    "$\\lambda$が小さい時$x'\\approx x$がminimizerなので，ほぼ$h(x)$と同じ値になります．一方で$\\lambda$が大きければほぼ$h(x')$の最小値を返すわけですね．\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "e7770d894bfc488b9612f48b898b2f3a",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(FloatSlider(value=2.4010000000000002, description='lam', max=5.0, min=0.001), Output()),…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "<function __main__.plot_conjugate(lam)>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from ipywidgets import interact\n",
    "\n",
    "# 適当な関数（非凸）を用意します\n",
    "x = np.linspace(-0.6, 0.5, 30)\n",
    "h = x ** 4 - 0.7 * x **2 + 0.1 * x + 1.5 * np.cos(10 * x) * 0.1 + 0.3\n",
    "\n",
    "def plot_conjugate(lam):\n",
    "    moreau = np.array([h[i] + (x - x[i]) ** 2 / (2 * lam) for i in range(len(x))]).min(axis=0)\n",
    "    plt.figure(figsize=(12, 6))\n",
    "    plt.subplot(1, 1, 1)\n",
    "\n",
    "    plt.plot(x, h, label=r\"$h$\")\n",
    "    plt.plot(x, moreau, label=r\"$h_\\lambda$\")\n",
    "\n",
    "    plt.grid()\n",
    "    plt.legend()\n",
    "    plt.ylim(-0.8, 0.8)\n",
    "    plt.xlabel(\"x\")\n",
    "\n",
    "    plt.show()\n",
    "\n",
    "interact(plot_conjugate, lam=(0.001, 5.0, 0.1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "このモーロー包を使って停留点を定義しましょう．\n",
    "\n",
    "---\n",
    "\n",
    "**定義：モーロー包の勾配についての停留点**\n",
    "\n",
    "$\\ell$-weakly convex関数$h$について，$x^\\star$は次を満たすときに$\\epsilon$-first order stationary point ($\\epsilon$-FOSP)と呼びます：\n",
    "\n",
    "$$\\left\\|\\nabla h_{\\frac{1}{2 \\ell}}\\left(x^{\\star}\\right)\\right\\| \\leq \\epsilon$$\n",
    "\n",
    "ここで$h_{\\frac{1}{2 \\ell}}(x)$は$\\lambda=1 / 2\\ell$のモーロー包です．\n",
    "\n",
    "---\n",
    "\n",
    "**補題：モーロー包の勾配**\n",
    "\n",
    "また，モーロー包の勾配は次で与えられます．\n",
    "\n",
    "$h$を$\\ell$-weakly convex関数とします．$\\lambda < \\ell$について，$h_\\lambda$は$C^1$-smoothであり，\n",
    "\n",
    "$$\n",
    "\\nabla h_\\lambda(x)=\\lambda^{-1}\\left(x-\\underset{x^{\\prime}}{\\arg \\min }\\left(h\\left(x^{\\prime}\\right)+\\frac{1}{2 \\lambda}\\left\\|x-x^{\\prime}\\right\\|^2\\right)\\right)\n",
    "$$\n",
    "\n",
    "が成立します．証明は略．\n",
    "\n",
    "---\n",
    "\n",
    "**補題：strongly convex**\n",
    "\n",
    "$h$を$\\ell$-strongly convex functionとします．このとき，任意の$\\boldsymbol{x}, \\boldsymbol{y} \\in \\mathcal{X}, h(\\boldsymbol{x})$について，\n",
    "\n",
    "$$\n",
    "h(\\boldsymbol{y})-h(\\boldsymbol{x}) \\leq \\nabla h(\\boldsymbol{y})^{\\top}(\\boldsymbol{y}-\\boldsymbol{x})-\\frac{\\ell}{2}\\|\\boldsymbol{x}-\\boldsymbol{y}\\|^2\n",
    "$$\n",
    "\n",
    "です．さらに$\\boldsymbol{y}=\\boldsymbol{x}^{\\star}:=\\arg \\min _{\\boldsymbol{x} \\in \\mathcal{X}} h(\\boldsymbol{x})$とすれば，\n",
    "\n",
    "$$\n",
    "h(\\boldsymbol{x})-\\min _{\\boldsymbol{x} \\in \\mathcal{X}} h(\\boldsymbol{x}) \\geq \\frac{\\ell}{2}\\left\\|\\boldsymbol{x}-\\boldsymbol{x}^{\\star}\\right\\|^2\n",
    "$$\n",
    "\n",
    "が成り立ちます．\n",
    "\n",
    "**証明**\n",
    "\n",
    "１つ目はStrongly convex functionの定義とほぼ変わりません．また，２つ目は一次の最適性からすぐにわかります．\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "---\n",
    "\n",
    "**補題：Weakly convex functionのFrechet劣微分の上界について**\n",
    "\n",
    "$h: \\mathcal{X} \\subseteq \\mathbb{R}^n \\to \\mathbb{R}$ が$\\ell$-weakly convexとします．\n",
    "$\\lambda < 1 /\\ell$および\n",
    "$$\n",
    "\\hat{\\boldsymbol{x}}_\\lambda=\\arg \\min _{\\boldsymbol{x}^{\\prime} \\in \\mathcal{X}} h\\left(\\boldsymbol{x}^{\\prime}\\right)+\\frac{1}{2 \\lambda}\\left\\|\\boldsymbol{x}-\\boldsymbol{x}^{\\prime}\\right\\|^2\n",
    "$$\n",
    "とします．このとき，次を満たす$\\boldsymbol{\\xi} \\in \\partial h\\left(\\hat{\\boldsymbol{x}}_\\lambda\\right)$が存在します：\n",
    "\n",
    "$$\n",
    "-\\boldsymbol{\\xi} - \\frac{1}{\\lambda}\\left(\\hat{\\boldsymbol{x}}_\\lambda-\\boldsymbol{x}\\right) \\in \\mathcal{N}_{\\mathcal{X}}\\left(\\hat{\\boldsymbol{x}}_\\lambda\\right)\n",
    "$$\n",
    "\n",
    "ここで$\\mathcal{N}_\\mathcal{X}(\\hat{x}_\\lambda)$は$\\mathcal{X}$における$\\hat{x}_\\lambda$でのnormal coneです．\n",
    "Normal coneの定義から，任意の$\\boldsymbol{y} \\in \\mathcal{X}$について\n",
    "$$\n",
    "\\langle\\boldsymbol{\\xi}, \\hat{\\boldsymbol{x}}_\\lambda - \\boldsymbol{y}\\rangle \\leq\\left\\langle \\nabla h_\\lambda (x), \\hat{\\boldsymbol{x}}_\\lambda - \\boldsymbol{y}\\right\\rangle, \\forall \\boldsymbol{y} \\in \\mathcal{X} \n",
    "$$\n",
    "が成立します．\n",
    "\n",
    "**証明**\n",
    "\n",
    "$f(\\boldsymbol{x})=h(\\boldsymbol{x})+\\mathbb{I}_{\\mathcal{X}}(\\boldsymbol{x})$とします．\n",
    "ここで$\\mathbb{I}$は指示関数です．\n",
    "\n",
    "このとき$f(x)$のモーロー包は\n",
    "$$\n",
    "\\begin{aligned}\n",
    "f_\\lambda(\\boldsymbol{x}) & =\\min _{\\boldsymbol{x}^{\\prime} \\in \\mathbb{R}^n}\\left\\{h\\left(\\boldsymbol{x}^{\\prime}\\right)+\\mathbb{I}_{\\mathcal{X}}\\left(\\boldsymbol{x}^{\\prime}\\right)+\\frac{1}{2 \\lambda}\\left\\|\\boldsymbol{x}-\\boldsymbol{x}^{\\prime}\\right\\|^2\\right\\}, \\quad \\forall \\boldsymbol{x} \\in \\mathbb{R}^n \\\\\n",
    "& =\\min _{\\boldsymbol{x}^{\\prime} \\in \\mathcal{X}}\\left\\{h\\left(\\boldsymbol{x}^{\\prime}\\right)+\\frac{1}{2 \\lambda}\\left\\|\\boldsymbol{x}-\\boldsymbol{x}^{\\prime}\\right\\|^2\\right\\}, \\quad \\forall \\boldsymbol{x} \\in \\mathbb{R}^n .\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "になります．ここで\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\hat{\\boldsymbol{x}}_\\lambda: & \n",
    "=\\underset{\\boldsymbol{x}' \\in \\mathcal{X}}{\\arg \\min }\\left(h(\\boldsymbol{x}')+\\frac{1}{2 \\lambda}\\|\\boldsymbol{x}-\\boldsymbol{x}'\\|^2\\right)\\\\\n",
    "& =\\underset{\\boldsymbol{x}' \\in \\mathbb{R}^n}{\\arg \\min }(\\underbrace{h(\\boldsymbol{x}')+\\mathbb{I}_{\\mathcal{X}}(\\boldsymbol{x}')+\\frac{1}{2 \\lambda}\\|\\boldsymbol{x}-\\boldsymbol{x}'\\|^2}_{:=\\phi_{\\boldsymbol{x}}(\\boldsymbol{x}')}) \n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "として書けます．すると，モーロー包の勾配は$\\nabla f_\\lambda(\\boldsymbol{x})=\\lambda^{-1}(\\boldsymbol{x}-\\hat{\\boldsymbol{x}}_\\lambda)$です．$\\phi_{\\boldsymbol{x}}(\\boldsymbol{y})=h(\\boldsymbol{y})+\\mathbb{I}_{\\mathcal{X}}(\\boldsymbol{y})+\\frac{1}{2 \\lambda}\\|\\boldsymbol{x}-\\boldsymbol{y}\\|^2$とすると，$\\hat{x}_\\lambda$は$\\phi_x(\\cdot)$の極小値であることがすぐわかります．\n",
    "\n",
    "極小値では$0$になる劣微分が必ず存在するので（[これなど](https://web.stanford.edu/class/ee364b/lectures/subgradients_notes.pdf)），\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "&\\phi_{\\boldsymbol{x}}(\\hat{\\boldsymbol{x}}_\\lambda(\\boldsymbol{x}))=\\min _{\\boldsymbol{y} \\in \\mathbb{R}^n} \\phi_{\\boldsymbol{x}}(\\boldsymbol{y}) =\\min _{\\boldsymbol{y} \\in \\mathbb{R}^n} h(\\boldsymbol{y})+\\mathbb{I}_{\\mathcal{X}}(\\boldsymbol{y})+\\frac{1}{2 \\lambda}\\|\\boldsymbol{x}-\\boldsymbol{y}\\|^2 \\\\\n",
    "& \\left.\\Longleftrightarrow 0 \\in \\partial\\left(h(\\boldsymbol{y})+\\mathbb{I}_{\\mathcal{X}}(\\boldsymbol{y})+\\frac{1}{2 \\lambda}\\|\\boldsymbol{x}-\\boldsymbol{y}\\|^2\\right)\\right|_{\\boldsymbol{y}=\\hat{\\boldsymbol{x}}_\\lambda}\\\\\n",
    "& \\Longleftrightarrow -\\frac{1}{\\lambda}(\\hat{\\boldsymbol{x}}_\\lambda-\\boldsymbol{x}) \\in \\left.\\partial\\left(h(\\boldsymbol{y})+\\mathbb{I}_{\\mathcal{X}}(\\boldsymbol{y})\\right)\\right|_{\\boldsymbol{y}=\\hat{\\boldsymbol{x}}_\\lambda}\n",
    "% & \\Longleftrightarrow -\\frac{1}{\\lambda}(\\hat{\\boldsymbol{x}}_\\lambda-\\boldsymbol{x}) \\in \\boldsymbol{\\xi}+\\mathcal{N}_{\\mathcal{X}}(\\hat{\\boldsymbol{x}}_\\lambda) \\\\\n",
    "% & \\Longleftrightarrow-\\boldsymbol{\\xi} \\in \\mathcal{N}_{\\mathcal{X}}(\\hat{\\boldsymbol{x}}_\\lambda)+\\frac{1}{\\lambda}(\\hat{\\boldsymbol{x}}_\\lambda-\\boldsymbol{x}) .\n",
    "\\end{aligned}\n",
    "$$\n",
    "が成り立ちます．\n",
    "ここで$N_\\mathcal{X}(x)$を$x$における$\\mathcal{X}$についてのNormal coneとします．\n",
    "これは\n",
    "$$\n",
    "N_\\mathcal{X}(x) = \\{g \\in \\mathbb{R}^n \\mid g^\\top y \\leq g^\\top x \\quad \\forall y \\in \\mathcal{X}\\}\n",
    "$$\n",
    "です．指示関数の劣微分はnormal coneになるので，次を満たす劣微分$\\xi \\in \\partial h(\\hat{x}_\\lambda)$が存在します．\n",
    "\n",
    "$$\n",
    "-\\xi -\\frac{1}{\\lambda}(\\hat{\\boldsymbol{x}}_\\lambda-\\boldsymbol{x}) \\in N_\\mathcal{X}(\\hat{x}_\\lambda)\n",
    "$$\n",
    "\n",
    "$N_\\mathcal{X}(\\hat{x}_\\lambda)$の中のベクトル$g$は任意の$y \\in \\mathcal{X}$に対して$g^\\top (y - \\hat{x}_\\lambda) \\leq 0$を満たすので，任意の$y \\in \\mathcal{X}$に対して，\n",
    "$$\n",
    "\\begin{aligned}\n",
    "&\\left\\langle-\\boldsymbol{\\xi}-\\frac{1}{\\lambda}(\\hat{\\boldsymbol{x}}_\\lambda-\\boldsymbol{x}), \\boldsymbol{y} - \\hat{x}_\\lambda \\right\\rangle\n",
    "\\leq 0\\\\\n",
    "\\Longleftrightarrow &\\langle-\\boldsymbol{\\xi}, \\boldsymbol{y}-\\hat{\\boldsymbol{x}}_\\lambda \\rangle \\leq\\left\\langle\\frac{1}{\\lambda}(\\hat{\\boldsymbol{x}}_\\lambda-\\boldsymbol{x}), \\boldsymbol{y}-\\hat{\\boldsymbol{x}}_\\lambda\\right\\rangle, \\forall \\boldsymbol{y} \\in \\mathcal{X} \\\\\n",
    "\\Longleftrightarrow &\\langle\\boldsymbol{\\xi}, \\hat{\\boldsymbol{x}}_\\lambda - \\boldsymbol{y}\\rangle \\leq\\left\\langle \\nabla h_\\lambda (x), \\hat{\\boldsymbol{x}}_\\lambda - \\boldsymbol{y}\\right\\rangle, \\forall \\boldsymbol{y} \\in \\mathcal{X} \\\\\n",
    "% & \\Longrightarrow\\langle-\\boldsymbol{\\xi}, \\boldsymbol{y}-\\hat{\\boldsymbol{x}}_\\lambda\\rangle \\leq \\frac{1}{\\lambda}\\|\\hat{\\boldsymbol{x}}_\\lambda-\\boldsymbol{x}\\| \\cdot\\|\\boldsymbol{y}-\\hat{\\boldsymbol{x}}_\\lambda\\|, \\forall \\boldsymbol{y} \\in \\mathcal{X}\n",
    "% & \\Longleftrightarrow\\langle-\\boldsymbol{\\xi}, \\boldsymbol{y}-\\hat{\\boldsymbol{x}}_\\lambda\\rangle \\leq \\frac{1}{\\lambda}\\|\\hat{\\boldsymbol{x}}_\\lambda-\\boldsymbol{x}\\|, \\forall \\boldsymbol{y} \\in \\mathcal{X},\\|\\boldsymbol{y}-\\hat{\\boldsymbol{x}}_\\lambda\\|=1 .\n",
    "\\end{aligned}\n",
    "$$\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}