凸优化进阶之对偶理论.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 凸优化问题分为有约束的和无约束的凸优化问题\n",
    "# 无约束的凸优化问题：局部最优解即全局最优解\n",
    "# 有约束的凸优化问题：需根据可行域确定最优解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一般优化问题\n",
    "\n",
    "$$\\begin{align*}\n",
    "    minimize\\hspace{0.2cm}&f_0(\\mathbf{x}) \\\\                 \n",
    "    subject\\hspace{0.2cm}to\\hspace{0.2cm}&f_i(\\mathbf{x})\\le0\\hspace{0.1cm}for\\hspace{0.1cm}i = 1,2,\\dots,m \\\\\n",
    "    &h_i(\\mathbf{x}) = 0\\hspace{0.1cm}for\\hspace{0.1cm}i = 1,2,\\dots,p\n",
    "\\end{align*}$$\n",
    "    \n",
    "问题定义域$D=(\\cap_{i=0}^mdom f_i)\\cap(\\cap_{i=0}^pdom h_i)$，注意与可行域区分\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 拉格朗日"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "合并目标函数和约束\n",
    "\n",
    "* Lagrangian\n",
    "$$L(\\mathbf{x,λ,v})=f_0(\\mathbf{x})+\\sum_{i=1}^mλ_if_i(\\mathbf{x})+\\sum_{i=1}^pv_ih_i(\\mathbf{x})$$\n",
    "\n",
    "* 主变量：$\\mathbf{x}$\n",
    "\n",
    "* 对偶变量：$λ\\ge0,v$\n",
    "\n",
    "* 意义解释：目标函数是求$f_0(\\mathbf{x})$的极小值，因$f_i(\\mathbf{x})\\le0$，$h_i(\\mathbf{x})=0$，要与原目标函数等价，只能$\\mathbf{λ}\\ge0$；如何才能使得目标函数变得极小，只能减去一个极大值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 拉格朗日函数的意义：是加惩罚项，使得满足约束条件\n",
    "# λ>=0代表了λ的方向性要求，v则没有方向性\n",
    "# 拉格朗日就是将有约束问题转换为无约束问题的，是一个桥梁，将约束条件合并到目标函数中\n",
    "# 等式约束是在筛选x变量的值，不等式约束是x的范围"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "主问题\n",
    "\n",
    "* Lagrangian\n",
    "$$L(\\mathbf{x,λ,v})=f_0(\\mathbf{x})+\\sum_{i=1}^mλ_if_i(\\mathbf{x})+\\sum_{i=1}^pv_ih_i(\\mathbf{x})$$\n",
    "\n",
    "* 主问题\n",
    "$$p^*=\\min_{\\mathbf{x}}\\left(\\max_{\\mathbf{λ,v}}L(\\mathbf{x,λ,v})\\right)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 说明：先对λ,v求使得L(x,λ,v)最大，再对x求使得L(x,λ,v)最小"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 分开看\n",
    "$$\\max_{\\mathbf{λ,v}}\\hspace{0.1cm}L(\\mathbf{x,λ,v}) = f_0(\\mathbf{x})+\\max_{\\mathbf{λ,v}}\\left(\\sum_{i=1}^mλ_if_i(\\mathbf{x})+\\sum_{i=1}^pv_ih_i(\\mathbf{x})\\right)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对偶函数\n",
    "\n",
    "* Lagrangian\n",
    "$$g(\\mathbf{λ,v})=\\min_{\\mathbf{x}∈D}L(\\mathbf{x,λ,v})=\\min_{\\mathbf{x}∈D}\\left\\{f_0(\\mathbf{x})+\\sum_{i=1}^mλ_if_i(\\mathbf{x})+\\sum_{i=1}^pv_ih_i(\\mathbf{x})\\right\\}$$"
   ]
  },
  {
   "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$凸，则$\\max_{y∈A}f(\\mathbf{x,y})$凸。$g$是($\\mathbf{λ,v)}$)的仿射函数的逐点下确界(min)，总是凹的，即使原问题非凸"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 原函数f0(x)不知道是否是凸函数\n",
    "# 而关于λi的∑i=1mλifi(x)函数是凸函数：fi(x)不知道是否是凸函数，而关系λi的线性函数求最大，首先线性函数是凸函=函数，也是凹函数，在此假设\n",
    "# 是凸函数，根据凸函数的保凸性质，可能凸函数的加和也是凸函数，而要在这组函数中找最大值(因存在不同的λ，那肯定存在不同的∑i=1mλifi(x)值，自然\n",
    "# 可以找到逐点最大)再次满足凸函数的逐点最大是凹函数，是个凸函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 因原函数在求极小值，根据保凸性质，逐点最大是凸的，存在上确界，而逐点最小，则相应的存在下确界，是凹的\n",
    "# 这边原函数f0(x)和fi(x)都不知道是不是凸函数，但是其对偶函数g(λ,v)确是凹函数\n",
    "# 最优值的下界是针对原函数的最优值的下界说的，而上界则是对偶函数的最优值说的\n",
    "# 凸函数=>上镜图是凸集；凹函数=>亚图是凸集\n",
    "# 在fi(x)不知道是否是凸函数的情况下，我们可得一组λ值，对应一个函数∑i=1mλifi(x)的值，从这些值中取出最大值，也就对应这个最大值的λ，\n",
    "# fi(x)不知道是否是凸函数，而函数∑i=1mλifi(x)<=0，则是逐点最大的情况，一个关于λi的线性函数是凸函数，也是凹函数，再此当做凸函数考虑\n",
    "# 所以我们有，在不知道f0(x)和fi(x)是否是凸函数的情况，判断出其对偶函数确是凹函数，是个凸优化问题，其实真的很妙！！！"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 对偶"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对偶函数\n",
    "\n",
    "* Lagrangian\n",
    "\n",
    "$$g(\\mathbf{λ,v})=\\min_{\\mathbf{x}∈D}L(\\mathbf{x,λ,v})=\\min_{\\mathbf{x}∈D}\\left\\{f_0(\\mathbf{x})+\\sum_{i=1}^mλ_if_i(\\mathbf{x})+\\sum_{i=1}^pv_ih_i(\\mathbf{x})\\right\\}$$\n",
    "\n",
    "* 如果$\\widetilde{\\mathbf{x}}$是一个可行点，则\n",
    "\n",
    "$$g(\\mathbf{λ,v})=\\min_{\\mathbf{x}∈D}L(\\mathbf{x,λ,v}) \\le L(\\mathbf{\\widetilde{x},λ,v})$$\n",
    "$$L(\\mathbf{\\widetilde{x},λ,v})=f_0(\\widetilde{\\mathbf{x}})+\\sum_{i=1}^mλ_if_i(\\widetilde{\\mathbf{x}})+\\sum_{i=1}^pv_ih_i(\\widetilde{\\mathbf{x}}) \\le f_0(\\widetilde{\\mathbf{x}})$$\n",
    "\n",
    "* 因此$g(\\mathbf{λ,v}) \\le f_0(\\mathbf{x^*}) = p^*$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lagrange对偶问题\n",
    "\n",
    "* Lagrange对偶问题\n",
    "\n",
    "$$\\begin{align*}\n",
    "    maximize\\hspace{0.2cm}&g(\\mathbf{λ,v}) \\\\\n",
    "    subject\\hspace{0.2cm}to\\hspace{0.2cm}&\\mathbf{λ \\ge 0}\n",
    "\\end{align*}$$\n",
    "\n",
    "* 目标函数：$\\max_{\\mathbf{λ\\ge0,v}}\\min_{\\mathbf{x}∈D}L(\\mathbf{x,λ,v})$\n",
    "\n",
    "* 凹函数在凸集上最大化，这是一凸优化问题，设最优解为$d^*$，对应的极值点是$\\mathbf{λ^*,v^*}$\n",
    "\n",
    "* 对偶几何解释：原函数的最小值$p^*$大于等于对偶函数的最大值$d^*$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "强弱对偶解释\n",
    "\n",
    "* 弱对偶：$d^* \\ge p^*$，无论凸或非凸问题总成立\n",
    "* 强对偶：$d^* = p^*$\n",
    "\n",
    "    * 该条件通常不成立\n",
    "    * 对于凸优化问题通常成立\n",
    "    * 凸优化问题可以写成\n",
    "    $$\\begin{align*}\n",
    "        minimize\\hspace{0.2cm}&f_0(\\mathbf{x}) \\\\                 \n",
    "        subject\\hspace{0.2cm}to\\hspace{0.2cm}&f_i(\\mathbf{x})\\le0\\hspace{0.1cm}for\\hspace{0.1cm}i = 1,2,\\dots,m \\\\\n",
    "        &\\mathbf{Ax}=\\mathbf{b}\n",
    "    \\end{align*}$$\n",
    "    * 满足Slater条件：存在内点$\\mathbf{x}$，使得$f_i(\\mathbf{x})<0\\hspace{0.2cm}for\\hspace{0.2cm}i=1,2,...,m均成立$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 因原函数在对x求最小，而对偶函数在对λ,v求最大，而在强对偶的情况下，求对偶函数的最大，其实就是原函数的最小，所以其对偶函数，就可以写成原函数\n",
    "# 的极小化的形式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从对偶问题解主问题\n",
    "\n",
    "* 假定强对偶成立，$\\mathbf(x^*,λ^*,v^*)$是主对最优解，有\n",
    "\n",
    "$$\\begin{align*}\n",
    "    p^*=f_0(\\mathbf{x}^*)\n",
    "    &=d^*=g(λ^*,v^*) \\\\\n",
    "    &=\\min_{\\mathbf{x}}\\left(f_0(\\mathbf{x})+\\sum_{i=1}^mλ_i^*f_i(\\mathbf{x})+\\sum_{i=1}^pv_i^*h_i(\\mathbf{x})\\right) \\\\\n",
    "    &\\le f_0(\\mathbf{x}^*)+\\sum_{i=1}^mλ_i^*f_i(\\mathbf{x}^*)+\\sum_{i=1}^pv_i^*h_i(\\mathbf{x}^*) \\\\\n",
    "    &\\le f_0(\\mathbf{x}^*)\n",
    "\\end{align*}$$\n",
    "\n",
    "* 结论1：$λ_i^*f_i(\\mathbf{x}^*)$ = 0\n",
    "\n",
    "* 结论2：$L(\\mathbf{x,λ^*,v^*})$关于$\\mathbf{x}^*$处取极小值，$\\nabla_\\mathbf{x}L(\\mathbf{x^*,λ^*,v^*}) = 0$\n",
    "    * $g(λ^*,v^*)$ = $L(\\mathbf{x^*,λ^*,v^*})$\n",
    "    * $g(λ^*,v^*)$ = $\\min_{\\mathbf{x}}L(\\mathbf{x,λ^*,v^*})$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "KKT条件\n",
    "\n",
    "* 凸优化问题\n",
    "\n",
    "$$\\begin{align*}\n",
    "    minimize\\hspace{0.2cm}&f_0(\\mathbf{x}) \\\\                 \n",
    "    subject\\hspace{0.2cm}to\\hspace{0.2cm}&f_i(\\mathbf{x})\\le0\\hspace{0.1cm}for\\hspace{0.1cm}i = 1,2,\\dots,m \\\\\n",
    "    &h_i(\\mathbf{x}) = 0\\hspace{0.1cm}for\\hspace{0.1cm}i = 1,2,\\dots,p\n",
    "\\end{align*}$$\n",
    "\n",
    "* Lagrangian\n",
    "\n",
    "$$L(\\mathbf{x,λ,v})=f_0(\\mathbf{x})+\\sum_{i=1}^mλ_if_i(\\mathbf{x})+\\sum_{i=1}^pv_ih_i(\\mathbf{x})$$\n",
    "\n",
    "* 凸优化问题强对偶成立，充要条件\n",
    "\n",
    "    * $f_i(\\mathbf{x}^*)\\le0，i = 1,2,\\dots,m$\n",
    "    $(\\nabla_\\mathbf{λ}L(\\mathbf{x^*,λ,v}) \\le \\mathbf{0})$\n",
    "    * $h_i(\\mathbf{x}^*) = 0，i = 1,2,\\dots,p$ $(\\nabla_\\mathbf{v}L(\\mathbf{x^*,λ,v}) = \\mathbf{0})$\n",
    "    * $λ_i^*\\ge0,i=1,2,\\dots,m$\n",
    "    * $λ_i^*f_i(\\mathbf{x}^*)$ = 0, $i=1,2,\\dots,m$\n",
    "    * $\\nabla f_0({\\mathbf{x}^*})+\\sum_iλ_i^*\\nabla f_i(\\mathbf{x}^*)+\\sum_iv_i^*\\nabla h_i(\\mathbf{x}^*)=0$ $(\\nabla_\\mathbf{x}L(\\mathbf{x^*,λ^*,v^*}) = 0)$\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 说明：对于KKT条件中的λ∗ifi(x∗)=0，λ*和fi(x*)不能同时为0，只能当λ*=0时，fi(x*)<0；而当λ*>0时，fi(x*)=0\n",
    "# 同时为0，就达不到约束的目的了"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "KKT条件\n",
    "\n",
    "* 非凸问题弱对偶，KKT局部极小解的一阶必要条件\n",
    "* 求解KKT\n",
    "* 在某些情况下可以得到闭合解\n",
    "* 求解凸优化问题方法可以认为求解KKT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 说明：1、类似无约束梯度分析中的一阶梯度为0，需要二阶导数判断是否是局部极小解 弱对偶不知道是否是凸还是非凸问题 对应着这边的一阶只有最小值\n",
    "# 的下确界\n",
    "# 2、如果是凸优化问题 强对偶 则为KKT全局极小解\n",
    "# 3、特别需要注意λ*ifi(x*)=0条件，能够帮助我们筛选解\n",
    "# 4、对于原函数不知道是不是凸优化问题的情况下 它的对偶问题在强对偶下是凸优化问题，既然是凸优化问题，则求解KKT，就是在求解凸优化问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "主对问题思考\n",
    "\n",
    "* 主问题 $$p^*=\\min_{\\mathbf{x}}\\left(\\max_{\\mathbf{λ\\ge0,v}}L(\\mathbf{x,λ,v})\\right)$$\n",
    "* 对偶问题 $$d^*=\\max_{\\mathbf{λ\\ge0,v}}\\left(\\min_{\\mathbf{x}}L(\\mathbf{x,λ,v})\\right)$$\n",
    "\n",
    "主对关系(强对偶成立 max min可以交换)\n",
    "\n",
    "$$\\max_{\\mathbf{λ\\ge0,v}}\\left(\\min_{\\mathbf{x}}L(\\mathbf{x,λ,v})\\right)\\le\\min_{\\mathbf{x}}\\left(\\max_{\\mathbf{λ\\ge0,v}}L(\\mathbf{x,λ,v})\\right)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# SVM前奏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "最小2范数解问题\n",
    "\n",
    "* 求解下列问题\n",
    "$$p^*=\\min_{\\mathbf{x}}\\|\\mathbf{x}\\|_2^2$$\n",
    "$$s.t. \\mathbf{Ax=b}$$\n",
    "\n",
    "* Lagrangian\n",
    "$$L(\\mathbf{x,v})=\\mathbf{x^Tx}+\\mathbf{v^T(Ax-b)}$$\n",
    "\n",
    "* 对偶函数\n",
    "$$g(\\mathbf{v})=\\min_{\\mathbf{x}}L(\\mathbf{x,v})$$\n",
    "\n",
    "* $\\nabla_{\\mathbf{x}}L(\\mathbf{x,v})=0$ $\\Rightarrow$ $2\\mathbf{x}+\\mathbf{A^Tx}=0$ $\\Rightarrow$ $\\mathbf{x^*(v)}=-\\frac{1}{2}\\mathbf{A^Tv}$\n",
    "\n",
    "* $g(\\mathbf{v})=L(\\mathbf{x^*(v),v})=-\\frac{1}{4}\\mathbf{v^T(AA^T)v-v^Tb}$\n",
    "\n",
    "* 对偶问题\n",
    "$$d^*=\\max_{\\mathbf{v}}-\\frac{1}{4}\\mathbf{v^T(AA^T)v-v^Tb}$$\n",
    "\n",
    "* 可求得\n",
    "$$\\mathbf{v}^*=-2(\\mathbf{AA^T})^{-1}\\mathbf{b}$$\n",
    "$$d^*=\\mathbf{b^T(AA^T)}^{-1}\\mathbf{b}$$\n",
    "\n",
    "* 由于$p^*=d^*$，则\n",
    "$$\\mathbf{x}^*=\\mathbf{x}^*(\\mathbf{v}^*)=\\mathbf{A^T(AA^T)^{-1}b}$$\n",
    "\n",
    "* 下确界(Lower bound)\n",
    "$$p^* \\ge -\\frac{1}{4}\\mathbf{v^T(AA^T)v-v^Tb}\\hspace{0.1cm}for\\hspace{0.1cm}all\\mathbf{v}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "LP\n",
    "\n",
    "* 求解下列问题\n",
    "\n",
    "$$p^*=\\min_{\\mathbf{x}}\\mathbf{c^Tx}$$\n",
    "$$s.t.\\mathbf{Ax}\\le\\mathbf{b}$$\n",
    "\n",
    "* Lagrangian\n",
    "\n",
    "$$L(\\mathbf{x,λ})=\\mathbf{c^Tx}+\\mathbf{λ^T(Ax-b)}=-\\mathbf{b^Tλ}+(\\mathbf{A^Tλ+c})^T\\mathbf{x}$$\n",
    "\n",
    "* 对偶函数\n",
    "\n",
    "$$g(\\mathbf{λ})=\\min_{\\mathbf{x}}L(\\mathbf{x,λ})=-\\mathbf{b^Tλ}+\\min_{\\mathbf{x}}(\\mathbf{A^Tλ+c})^T\\mathbf{x}$$\n",
    "\n",
    "* 可以发现\n",
    "\n",
    "$$g(\\mathbf{λ})=\n",
    "\\begin{cases}\n",
    "    -\\mathbf{b^Tλ} & \\mathbf{A^Tλ+c=0}\\\\\n",
    "    -∞ & others\n",
    "\\end{cases}$$\n",
    "\n",
    "* 对偶问题\n",
    "\n",
    "$$d^*=\\max_{\\mathbf{λ}} -\\mathbf{b^Tλ}$$\n",
    "$$s.t. \\mathbf{A^Tλ+c=0}$$\n",
    "$$\\mathbf{λ\\ge0}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 说明：对于LP线性规划问题，原问题是求对于x的最小化值，而它的对偶问题变成了求对于λ最大化值\n",
    "# 对偶的对偶肯定是求对于v的最小化值，还是LP线性规划问题\n",
    "# g(λ)=-∞是无意义的，要使其有意义，只能当ATλ+c=0的条件\n",
    "# 内点法求极值：是一种求多维空间中的极值的方法，如采用线搜索，则比较耗时，思想就是跑到物体内部取观察\n",
    "# 如多面体 不是采用棱角点的搜索方法-不全面，而是跑到多面体里面去一览全貌"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 说明：使用对偶函数来求解极值的两个方面：\n",
    "# 1、一个是原函数即使是凸优化问题，但是求解p*很难，比如在SVM中涉及到要所有元素的梯度求解法；\n",
    "# 2、原函数不知道是不是凸优化问题，只能通过其对偶函数来求得其下界"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 总结：有无约束问题求解方法\n",
    "# 1、无约束的凸优化问题求极值：梯度为0\n",
    "# 2、无约束的一般问题求极值：梯度为0 二阶导数>0 <0（hessian矩阵正定性）\n",
    "# 3、有约束的凸优化问题：在凸集上极小化目标函数(也就是在可行域内找满足目标函数的极小值)\n",
    "# 4、有约束的不知道是否是凸优化(一般问题)问题：转换成的对偶函数是凸优化问题，通过其求最大值的强对偶条件下，从而求得原函数的极小值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 局部最优：只是在某个范围内，所有的可行点的取值大于等于这个局部最优点\n",
    "# 全局最优：是所有的可行点都满足取值大于等于这个全局最优点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 总结：一般约束问题的求解\n",
    "# 1、将有约束的一般问题写成拉格朗日函数(合并目标函数和约束条件) λi是针对fi(x)不等式的对偶变量 而vi则是针对等式约束的hi(x)的对偶变量\n",
    "# 2、主问题是求对x的极小值，什么时候拉格朗日函数取得极小，只能是该函数值等于f0(x)无约束情形，所以就变成了对λ,v求拉格朗日函数的极大值，所以有g(λ,v)=min(x)L(x,λ,v)\n",
    "# 3、由保凸性质，f1,...,fm逐点最大是凸函数，则f(x)=max{f1(x),...,fm(x)}也是凸函数，对于max(x∈D)f(x,y)也满足是凸函数，所有就变成了不知道原函数是否是凸函数的情况，变成了求其对偶函数是凹函数g(λ,v)的凸优化问题，求其极大值。根据对偶函数，进一步推论，针λ,v求对g(λ,v)的极大值d*始终小于等于f0(x)的极小值p*，由此组成的极值点对(x*,λ*,v*)\n",
    "# 4、弱对偶就是d*<=p*，那什么时候d*=p*呢，就是强对偶的情况，也就是g(λ,v)的凸优化情形，且满足slater条件，fi(x)<0，不能等于0\n",
    "# 5、从强对偶问题解主问题可得到结论：λ*ifi(x*)=0；L(x,λ*,v*)关于x*处取极小值，有∇xL(x*,λ*,v*)，换句话理解就是在λ,v处取得极大值时对于x取得极小值（梯度为0时求得的极值点x*）\n",
    "# 6、由此推导出的KKT条件(针对强对偶凸优化问题)：5个条件，其中前三个是约束条件，第4个λ*ifi(x*)=0；第5个是是对拉格朗日函数求极小值∇f0(x*)+Σiλ*i∇fi(x*)+Σiv*i∇hi(x*)=0\n",
    "# 7、对于凸优化强对偶，满足KKT条件，则有全局极小解，对于非凸弱对偶，有局部最小解，不能推出满足KKT条件，因为原函数不一定是凸函数，可能是由极小解，极大解，和鞍点（就类似我们的线性优化中一阶求导为0，能够求得极小 极大和鞍点 还需要二阶导数判定极大 极小）\n",
    "# 8、对x求极小值和对λ,v求极大值，总有max(λ,v)(min(x)L(x,λ,v))<=min(x)(max(λ,v)L(x,λ,v))，强对偶成立，max和min可互换"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 求解步骤：\n",
    "# 1、将一般问题函数写成拉格朗日函数\n",
    "# 2、通过对x求原函数的极小值，求得其对偶函数\n",
    "# 3、再对(λ,v)求对偶函数的极大值d*，对应的(λ*,v*)\n",
    "# 4、有d*=p*，求得取函数极小值时的x*\n",
    "# 5、最终得到(d*,p*)和对应(x*,λ*,v*)和p*的下确界(在弱对偶情况下)"
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}