凸优化基础.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 一般优化问题\n",
    "# 无约束优化问题\n",
    "# 其实就分为两种：有约束的和无约束的，是凸函数只是说存在全局最优解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 自变量为矢量的函数$f: \\mathbb{R}^n→\\mathbb{R}$\n",
    "$$min\\hspace{0.2cm}f(\\mathbf{x})\\hspace{0.2cm}\\mathbf{x}∈\\mathbb{R}^n$$\n",
    "* 局部最优解常规解法\n",
    "* 直接法\n",
    "    - 梯度等于0，求得驻点，必要时Hessian矩阵再进一步判断\n",
    "* 迭代法\n",
    "    - 梯度下降法\n",
    "    - 牛顿法\n",
    "    - 拟牛顿法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 一般约束优化问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 约束优化问题一般形式：\n",
    "$$\\begin{align*}\n",
    "    minimize\\hspace{0.3cm}&f_0(\\mathbf{x}) \\\\\n",
    "    subject\\hspace{0.2cm}to\\hspace{0.3cm}&f_i(\\mathbf{x})\\le0\\hspace{0.2cm}for\\hspace{0.2cm}i = 1,2,\\dots,m \\\\ \n",
    "    &h_i(\\mathbf{x})=0\\hspace{0.2cm}for\\hspace{0.2cm}i = 1,2,\\dots,p\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 可行域：满足$f(\\mathbf{x})$定义域和约束条件的$\\mathbf{x}$的集合。$f_j(\\mathbf{x})=0$表明不等式约束被激活。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 可行域：是同时满足定义域和约束条件的x的集合，当fj(x)=0时，不等式约束被激活 也就是说满足某个条件fj(x)=0了\n",
    "# 一般约束优化问题的最优解不再是极值点，会被约束条件给改变掉"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 补充矩阵知识 Ax=b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "矩阵乘法\n",
    "$$\\underbrace{\\left[\n",
    "\\begin{matrix}\n",
    "    2 & -1 \\\\\n",
    "    1 & 1\n",
    "\\end{matrix}\n",
    "\\right]}_{\\mathbf{A}∈\\mathbb{R}^{2\\times2}}\n",
    "\\underbrace{\\left[\n",
    "\\begin{matrix}\n",
    "    x \\\\\n",
    "    y\n",
    "\\end{matrix}\n",
    "\\right]}_{\\mathbf{x}∈\\mathbb{R}^{2}} = \n",
    "\\underbrace{\\left[\n",
    "\\begin{matrix}\n",
    "    1 \\\\\n",
    "    5\n",
    "\\end{matrix}\n",
    "\\right]}_{\\mathbf{b}∈\\mathbb{R}^{2}}$$\n",
    "$$\\underbrace{\\left[\n",
    "\\begin{matrix}\n",
    "    2 & 1 & 1 \\\\\n",
    "    4 & -6 & 0 \\\\\n",
    "    -2 & 7 & 2\n",
    "\\end{matrix}\n",
    "\\right]}_{\\mathbf{A}∈\\mathbb{R}^{3\\times3}}\n",
    "\\underbrace{\\left[\n",
    "\\begin{matrix}\n",
    "    u \\\\\n",
    "    v \\\\\n",
    "    w\n",
    "\\end{matrix}\n",
    "\\right]}_{\\mathbf{x}∈\\mathbb{R}^{3}} = \n",
    "\\underbrace{\\left[\n",
    "\\begin{matrix}\n",
    "    5 \\\\\n",
    "    -2 \\\\\n",
    "    9\n",
    "\\end{matrix}\n",
    "\\right]}_{\\mathbf{b}∈\\mathbb{R}^{3}}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 说明：矩阵A是方程组的系数；x是参数列向量；b为结果列向量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Ax = b的行视图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 行视图-超平面\n",
    "$$\\begin{align*}\n",
    "    2x-y=1 \\\\\n",
    "    x+y=5\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 行视图：每个方程都是一个超平面\n",
    "# 列视图：参数系数构成的列向量的线性组合\n",
    "# n元n个方程组的解是超平面上交汇的一点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 凸集和凸函数基础"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 思考：对于无约束优化问题，梯度等于0这一条件是否可以成为充要条件？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 大部分情况，梯度为0只能求得极值，极大值、极小值，而鞍点既非极大值、又不是极小值，所以不能成为充要条件"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 思考：什么样的情况局部最小解可以成为全局最小解？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 凸函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 思考：约束优化问题怎么办？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 使用拉格朗日公式转换为无约束情况"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 思考：研究凸优化问题对于非凸问题又有什么帮助？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 根据其对偶问题，求得原问题最小值的对偶问题最大值情况的下界"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 凸集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "仿射集和凸集\n",
    "* 如果一个集合$C∈\\mathbb{R}^n$是仿射的，则$C$中两点间的直线也在$C$中，例如$\\mathbf{x}=θ\\mathbf{x_1}+(1-θ)\\mathbf{x_2}∈C，θ∈\\mathbb{R}$，即是$\\mathbf{Ax = b}$的解"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 说明：x=θx1+(1−θ)x2表示的恰好是一条直线，其上有无数个点是方程组Ax=b的解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 一个集合$C∈\\mathbb{R^n}$是凸的，则对于任意的$\\mathbf{x,y}∈C$，有$θ\\mathbf{x}+(1-θ)\\mathbf{y}∈C\\hspace{0.2cm}0\\leθ\\le1$ "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# θx+(1−θ)y表示的是超平面的一个线段\n",
    "# 是凸集的，肯定是仿射集，但凸集与仿射集并不是包含的关系"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "常见的凸集\n",
    "* 所有$\\mathbb{R}^n$，给定任意$\\mathbf{x,y}∈\\mathbb{R}^n$，则有$θ\\mathbf{x} + (1-θ)\\mathbf{y}∈\\mathbb{R}^n$\n",
    "* 所有$\\mathbb{R}_+^n$\n",
    "* 超平面：既是仿射集又是凸集\n",
    "$$C=\\{\\mathbf{x}\\hspace{0.1cm}\\vert\\hspace{0.1cm}\\mathbf{a^Tx}=b\\}$$\n",
    "* 半空间：只是凸集"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 超平面a^Tx=b 半空间：a^Tx>=b或者a^Tx<=b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 向量范数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $2-norm$：$$\\|\\mathbf{x}\\|_2 = \\sqrt{\\sum_{i=1}^n|x_i|^2} = \\mathbf{(x^Tx)^{1/2}}$$\n",
    "* $1-norm$：$$\\|\\mathbf{x}\\|_1 = \\sum_{i=1}^n|x_i|$$\n",
    "* $∞-norm$：$$\\|\\mathbf{x}\\|_∞ = \\max\\limits_{i=1,2,\\dots,n}|x_i|$$\n",
    "* $p-norm, p\\ge1$：$$\\|\\mathbf{x}\\| = \\left(\\sum_{i=1}^n|x_i|^p\\right)^{\\frac{1}{p}}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 2-norm，每个元素绝对值平方和的平方根，也就是我们所说的向量模长；\n",
    "# 1-norm，每个元素绝对值的和；\n",
    "# ∞范数：求元素中的最大绝对值；\n",
    "# p-norm：范数的一种通用表达式，当p=1是，就是1-norm，当p=2时，为2-norm\n",
    "# 0范数可以近似看成范数，但并不是欧几里得范数\n",
    "# 2范数的平方：||w||_2^2\n",
    "# 可参考：https://www.zhihu.com/question/20473040"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "常见的凸集\n",
    "* 范数球，例如$\\|\\mathbf{x}\\|_2\\le1$。给定任意$\\mathbf(x,y∈\\mathbb{R}^n)$，且$\\|\\mathbf{x}\\|_2\\le1$，$\\|\\mathbf{y}\\|_2\\le1$，则有$\\|θ\\mathbf{x}+(1-θ)\\mathbf{y}\\|_2\\leθ\\|\\mathbf{x}\\|_2 + (1-θ)\\|\\mathbf{y}\\|_2\\le1$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ||x||p = 1，当p>=1时，能够描述范数的所有情况，1-norm\\2-norm\\p-norm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "凸集的性质\n",
    "* **凸集的交集是凸集**，例如：$S = \\{\\|\\mathbf{x}\\|\\le1, \\mathbf{x}\\ge\\mathbf{0}\\}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 该性质的证明可以从凸集的定义出发，集合Si{i=1,2,...,k}都是凸的，有任意x,y∈∩Si{i=1,2,...,k}，则满足θx+(1-θ)y∈∩Si{i=1,2,...,k}，\n",
    "# 正得S集合也是凸集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 凸集的并集不一定是凸集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "常见的凸集\n",
    "* 多面体：有限个半空间和半平面的交集\n",
    "$$P = \\{\\mathbf{x}\\hspace{0.1cm}\\vert\\hspace{0.1cm}\\mathbf{Ax}\\le\\mathbf{b}, \\mathbf{Cx} = \\mathbf{d}\\}$$\n",
    "其中$\\mathbf{A}∈\\mathbb{R}^{m \\times n}, \\mathbf{b}∈\\mathbb{R}^{m}, \\mathbf{C}∈\\mathbb{R}^{p \\times n}, \\mathbf{d}∈\\mathbb{R}^{p}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 说明：Ax<=b表示的是多个半空间，Cx=d表示的是多个半平面，合起来组成一个空间"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 凸函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 一个函数 $f:\\mathbb{R}^n\\to\\mathbb{R}$ 被称为凸函数，如果\n",
    "\n",
    "    * $dom{(f)}$($f$的定义域)是凸集\n",
    "    * 对于任何$\\mathbf{x,y}∈dom{(f)}$和$0\\leθ\\le1$，有\n",
    "    $$f(θ\\mathbf{x}+(1-θ)\\mathbf{y})\\leθf(\\mathbf{x})+(1-θ)f(\\mathbf{y})$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 几何解释：上式可理解为对于凸函数有，在定义域内任意两点连接成的线段上的点的函数值要小于等于对应这两点的函数值连接成的线段上的点的值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "凸函数的一阶二阶条件\n",
    "* 一阶充要条件(不好用)：$f(\\mathbf{x_1}) \\ge f(\\mathbf{x})+\\nabla^Tf(\\mathbf{x})(\\mathbf{x_1}-\\mathbf{x})$对于所有$\\mathbf{x_1},\\mathbf{x}$均成立\n",
    "* 二阶充要条件(好用)：如果函数$f$二阶可导，则凸函数充要条件：\n",
    "\n",
    "$$\\mathbf{H(x)}\\succeq\\mathbf{0}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 说明：以上式子f(x1)≥f(x)+∇Tf(x)(x1−x)属于拉格朗日中值定理\n",
    "# 一般用二阶导，也就是hessian矩阵半正定证明是凸函数\n",
    "# 可以想象二阶导其实就是在极值点，这个点切线斜率固然为0，而其他点二阶导比如大于0，所以就有>=0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "常见的凸函数\n",
    "* 一元函数举例\n",
    "    * $ax + b$ 直线 - 即是凸函数又是凹函数\n",
    "    * $x^2$ 是凸函数\n",
    "    * $e^{αx}$ 是凸函数\n",
    "    * $-logx$ 在$x>0$时是凸函数\n",
    "    * $xlogx$ 在$x\\ge0$时是凸函数\n",
    "\n",
    "* 二元函数举例\n",
    "    * $f(\\mathbf{x})=\\mathbf{a^Tx}+\\mathbf{b}$ 平面 - 即是凸函数又是凹函数\n",
    "    * $f(\\mathbf{x})=\\mathbf{x^TPx}+2\\mathbf{q^Tx}+\\mathbf{r}$是凸函数当且仅当$\\mathbf{P}\\succeq\\mathbf{0}$\n",
    "    * 如最小二乘最简形式：$f(\\mathbf{x})=\\|\\mathbf{x}\\|_2^2=\\mathbf{x^Tx}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "保凸运算\n",
    "* $f$凸，则$f(\\mathbf{Ax+b})$凸，例如$\\|\\mathbf{y-Ax}\\|_2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 说明：函数f是凸的，Ax+b也超平面也是凸的，经过函数f后，还是凸的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $g$凸，$h$凸，扩展的$h$非递减，则$f(\\mathbf{x})=h(g(\\mathbf{x}))$凸。例如$f(\\mathbf{x})=\\|\\mathbf{y}-\\mathbf{Ax}\\|_2^2$凸，$f(\\mathbf{x})=\\|\\mathbf{y}-\\mathbf{Ax}\\|_2$，$h(x)=x^2$在$x\\ge0$的部分非递减"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 嵌套函数的保凸性质"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $f_1,\\dots,f_m$凸，$w_1,\\dots,w_m\\ge0$，则$\\sum_{i=1}^mw_if_i$凸。例如$f(\\mathbf{x})=\\|\\mathbf{y}-\\mathbf{Ax}\\|_2^2 + γ\\|\\mathbf{x}\\|_2^2$凸，$γ\\ge0$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 函数加法的保凸性质"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 逐点最大：$f_1,\\dots,f_m$凸，则$f(\\mathbf{x})=\\max\\{f_1(\\mathbf{x}),\\dots,f_m(\\mathbf{x})\\}$凸。$f(\\mathbf{x,y})$对于每个$y∈A$凸，则$sup_{y∈A}f(\\mathbf{x,y})$凸"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 可参考《凸优化》中的逐点最大和逐点上确界"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 凸函数和凸集的关系"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$α$水平集\n",
    "* 一元函数$f$的$α$水平集为\n",
    "$$S_α=\\{x\\hspace{0.1cm}|\\hspace{0.1cm}f(x)\\leα\\}$$\n",
    "* 则有$f$凸函数$\\Rightarrow S_α$对于每个$α$是凸集，反之不成立。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 说明：若f函数是凸函数，则由f(x)<=α对应的x构成的Sα集合是凸集，只是充分条件，不是必要条件"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 凸函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "凸函数问题标准形式\n",
    "\n",
    "* 凸优化问题\n",
    "$$\\begin{align*}\n",
    "    minimize\\hspace{0.3cm}&f_0(\\mathbf{x}) \\\\\n",
    "    subject\\hspace{0.2cm}to\\hspace{0.3cm}&f_i(\\mathbf{x})\\le0\\hspace{0.2cm}for\\hspace{0.2cm}i = 1,2,\\dots,m \\\\ \n",
    "    &h_i(\\mathbf{x})=0\\hspace{0.2cm}for\\hspace{0.2cm}i = 1,2,\\dots,p\n",
    "\\end{align*}$$\n",
    "\n",
    "* 则有$f_0(\\mathbf{x})$是凸函数，可行域是凸集\n",
    "    * 目标函数是凸的\n",
    "    * 不等式约束函数必须是凸的\n",
    "    * 等式约束函数必须是仿射的"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 说明：满足等式和不等式约束条件对应的x取值与定义域构成的可行域要是凸集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 在一个凸集上极小化一个凸的目标函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 可以理解为时在一个凸集上极小化一个凸的目标函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 最优值(目标函数在可行域上的最小值)：\n",
    "$p^*=\\min \\{f_0(\\mathbf{x}):f_i(\\mathbf{x}\\le0),h_i(\\mathbf{x})=0\\}$\n",
    "\n",
    "    * $p^* = +∞$ 不可行 (可行域是空集)\n",
    "    * $p^* = -∞$ unbounded below (存在可行点使得$f_0(x)\\Rightarrow-∞$)\n",
    "    * $f_0(\\mathbf{x^*}) = p^*$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 说明：当p*等于正负∞时，其可行点都无法确定，只有在拐点处才能找到最优解x*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 凸优化问题的重要结论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "凸优化问题局部最优 = 全局最优\n",
    "\n",
    "* 局部最优x，存在 $R > 0$，对于所有可行点z，具有$\\|x-z\\|_2 \\le R$，满足$f_0(x) \\le f_0(z)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 说明：R相当于是满足在某个区间内所有可行点z与x差的模长的集合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 全局最优x，对于所有可行点z，有$f_0(x) \\le f_0(z)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 全局最优，只有定义域限制，无一个个区间的限定条件"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 函数若存在全局最优x，说明该函数是凸函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 特别对于无约束问题\n",
    "    * 梯度等于0\n",
    "    * 迭代法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "典型的凸优化问题\n",
    "\n",
    "* 线性规划\n",
    "\n",
    "$$\\begin{align*}\n",
    "    minimize\\hspace{0.2cm}&\\mathbf{c^Tx} + d \\\\\n",
    "    subject\\hspace{0.2cm}to\\hspace{0.2cm}&\\mathbf{Gx} \\le \\mathbf{h} \\\\\n",
    "    & \\mathbf{Ax} = \\mathbf{b}\n",
    "\\end{align*}$$\n",
    "\n",
    "* 二次规划(QP)($\\mathbf{P}$和$\\mathbf{Q_i}$均为半正定)\n",
    "\n",
    "$$\\begin{align*}\n",
    "    minimize\\hspace{0.2cm}&\\frac{1}{2}\\mathbf{x^TPx} + \\mathbf{c^Tx} + d \\\\\n",
    "    subject\\hspace{0.2cm}to\\hspace{0.2cm}&\\mathbf{Gx} \\le \\mathbf{h} \\\\\n",
    "    & \\mathbf{Ax} = \\mathbf{b}\n",
    "\\end{align*}$$\n",
    "\n",
    "* 二次规划(QCQP)($\\mathbf{P}$为半正定)\n",
    "\n",
    "$$\\begin{align*}\n",
    "    minimize\\hspace{0.2cm}&\\frac{1}{2}\\mathbf{x^TPx} + \\mathbf{c^Tx} + d \\\\\n",
    "    subject\\hspace{0.2cm}to\\hspace{0.2cm}&\\frac{1}{2}\\mathbf{x^TQ_ix} + \\mathbf{r_i^Tx} + s_i \\le 0, i = 1,\\dots,m, \\mathbf{Ax} = \\mathbf{b}\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "案例1：凸优化问题转成标准型\n",
    "\n",
    "* 给定下列问题\n",
    "\n",
    "$$\\begin{align*}\n",
    "    minimize\\hspace{0.2cm}&\\frac{1}{2}\\|\\mathbf{w}\\|_2^2 + C\\sum_{i=1}^m\\varepsilon_i \\\\\n",
    "    subject\\hspace{0.2cm}to\\hspace{0.2cm}&y_i(\\mathbf{w^Tx_i}+b) \\ge 1 - \\varepsilon_i，i = 1,\\dots,m \\\\\n",
    "    &\\varepsilon_i \\ge 0\n",
    "\\end{align*}$$\n",
    "\n",
    "其中$\\mathbf{w}∈\\mathbb{R}^n,\\mathbf{\\varepsilon}=[\\varepsilon_1,\\dots,\\varepsilon_m]^T∈\\mathbb{R}^m,b∈\\mathbb{R}$。定义$k = m + n + 1$\n",
    "\n",
    "* 变量\n",
    "\n",
    "$$\\mathbf{x}∈\\mathbb{R}^k = \n",
    "\\begin{bmatrix}\n",
    "    \\mathbf{w} \\\\\n",
    "    \\mathbf{\\varepsilon} \\\\\n",
    "    b\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "* 定义$\\mathbf{X}∈\\mathbb{R}^{m \\times n} = \n",
    "\\begin{bmatrix}\n",
    "    \\mathbf{x_1}^T \\\\\n",
    "    \\vdots \\\\\n",
    "    \\mathbf{x_m}^T\n",
    "\\end{bmatrix}$，\n",
    "$\\mathbf{y}∈\\mathbb{R}^m = \n",
    "\\begin{bmatrix}\n",
    "    y_1 \\\\\n",
    "    \\vdots \\\\\n",
    "    y_m\n",
    "\\end{bmatrix}$\n",
    "\n",
    "* 再来看下QP规划\n",
    "\n",
    "$$\\begin{align*}\n",
    "    minimize\\hspace{0.2cm}&\\frac{1}{2}\\mathbf{x^TPx} + \\mathbf{c^Tx} + d \\\\\n",
    "    subject\\hspace{0.2cm}to\\hspace{0.2cm}&\\mathbf{Gx} \\le \\mathbf{h} \\\\\n",
    "    & \\mathbf{Ax} = \\mathbf{b}\n",
    "\\end{align*}$$\n",
    "\n",
    "* 定义\n",
    "\n",
    "$$\\mathbf{P}∈\\mathbb{R}^{k \\times k} =\n",
    "\\begin{bmatrix}\n",
    "    \\mathbf{I} & 0 & 0 \\\\\n",
    "    0 & 0 & 0 \\\\\n",
    "    0 & 0 & 0\n",
    "\\end{bmatrix}，\\mathbf{c}∈\\mathbb{R}^k = \n",
    "\\begin{bmatrix}\n",
    "    0 \\\\\n",
    "    C\\cdot\\mathbf{1} \\\\\n",
    "    0\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "$$\\mathbf{G}∈\\mathbf{R}^{2m \\times k} =\n",
    "\\begin{bmatrix}\n",
    "    -diag(\\mathbf{y})\\mathbf{X} & -\\mathbf{I} & -\\mathbf{y} \\\\\n",
    "    0 & -\\mathbf{I} & 0\n",
    "\\end{bmatrix}，\\mathbf{h}∈\\mathbb{R}^{2m} =\n",
    "\\begin{bmatrix}\n",
    "    -\\mathbf{1} \\\\\n",
    "    0\n",
    "\\end{bmatrix}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 上述优化的目标函数是SVM软间隔下的损失函数\n",
    "# 通过自定义一些向量和矩阵，可以实现目标函数到标准QP问题的转换"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}