{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "假设$f \\left( x \\right), c_{i} \\left( x \\right), h_{j} \\left( x \\right)$是定义在$R^{n}$上的连续可微函数。  \n",
    "称约束最优化问题\n",
    "\\begin{align*} \\\\&  \\min_{x \\in R^{n}} \\quad f \\left( x \\right) \n",
    "\\\\ & s.t. \\quad c_{i} \\left( x \\right) \\leq 0, \\quad i = 1,2, \\cdots, k\n",
    "\\\\ & \\quad \\quad h_{j} \\left( x \\right) = 0, \\quad j=1,2, \\cdots, l\\end{align*}   \n",
    "为原始最优化问题或原始问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "引入拉格朗日函数\n",
    "\\begin{align*} \\\\&  L \\left( x, \\alpha, \\beta \\right) = f \\left( x \\right) + \\sum_{i=1}^{k} \\alpha_{i} c_{i} \\left( x \\right) + \\sum_{j=1}^{l} \\beta_{j} h_{j}\\left( x \\right) \\end{align*}     \n",
    "其中，$x=\\left(x^{\\left( 1 \\right)}, x^{\\left( 2 \\right)}, \\cdots, x^{\\left( n \\right) } \\right)^{T} \\in R^{n}, \\alpha_{i}, \\beta_{j}$是拉格朗日乘子，$\\alpha_{i} \\geq 0$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "构建关于$x$的函数\n",
    "\\begin{align*} \\\\&  \\theta_{P} \\left( x \\right) = \\max_{\\alpha, \\beta; \\alpha_{i} \\geq 0} L \\left( x, \\alpha, \\beta \\right) \\end{align*}    \n",
    "假设给定某个违反原始问题约束条件的$x$，即存在某个$i$使得$c_{i} \\left( x \\right) > 0$或$h_{j} \\left( x \\right) \\neq 0$。若$c_{i} \\left( x \\right) > 0$，可令$\\alpha_{i} \\to +\\infty$，使得$\\theta_{P} \\left( x \\right)=+\\infty$；若$h_{j} \\left( x \\right) \\neq 0$，可令$\\beta_{j}$使$ \\beta_{j} h_{j} \\left( x \\right) \\to +\\infty$，使得$\\theta_{P} \\left( x \\right)=+\\infty$。将其余$\\alpha_{i}, \\beta_{j}$均取值为0。    \n",
    "即\n",
    "\\begin{align*} \\\\&  \\theta_{P} \\left( x \\right) = \\max_{\\alpha, \\beta; \\alpha_{i} \\geq 0} \\left[ f \\left( x \\right) + \\sum_{i=1}^{k} \\alpha_{i} c_{i} \\left( x \\right) + \\sum_{j=1}^{l} \\beta_{j} h_{j}\\left( x \\right)\\right] = +\\infty \\end{align*} \n",
    "假设给定某个符合原始问题约束条件的$x$，即$c_{i} \\left( x \\right) \\leq 0$且$h_{j} \\left( x \\right) = 0$，  \n",
    "则\n",
    "\\begin{align*} \\\\&  \\theta_{P} \\left( x \\right) =\\max_{\\alpha, \\beta; \\alpha_{i} \\geq 0} \\left[ f \\left( x \\right) + \\sum_{i=1}^{k} \\alpha_{i} c_{i} \\left( x \\right) + \\sum_{j=1}^{l} \\beta_{j} h_{j}\\left( x \\right)\\right]= f \\left( x \\right) \\end{align*}   \n",
    "由以上，得\n",
    "\\begin{align*} \\theta_{P} \\left( x \\right) = \\left\\{\n",
    "\\begin{aligned} \n",
    "\\ &  f \\left( x \\right), x满足原始问题约束\n",
    "\\\\ & +\\infty, 否则\n",
    "\\end{aligned}\n",
    "\\right.\\end{align*}  \n",
    "则极小化问题\n",
    "\\begin{align*} \\\\&  \\min_{x} \\theta_{P} \\left( x \\right) = \\min_{x} \\max_{\\alpha, \\beta; \\alpha_{i} \\geq 0} L \\left( x, \\alpha, \\beta \\right)\\end{align*}   \n",
    "与原始最优化问题等价，即有相同的解。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\begin{align*} \\\\&  \\min_{x} \\max_{\\alpha, \\beta; \\alpha_{i} \\geq 0} L \\left( x, \\alpha, \\beta \\right)\\end{align*} 称为广义拉格朗日函数的极小极大问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义原始问题的最优值\n",
    "\\begin{align*} \\\\&  p^{*} = \\min_{x} \\theta_{P} \\left( x \\right) \\end{align*} \n",
    "称为原始问题的值。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "构建关于$\\alpha, \\beta$的函数\n",
    "\\begin{align*} \\\\&   \\theta_{D} \\left( \\alpha, \\beta \\right) =  \\min_{x} L \\left( x, \\alpha, \\beta \\right)\\end{align*} \n",
    "则极大化问题\n",
    "\\begin{align*} \\\\& \\max_{\\alpha,\\beta;\\alpha_{i} \\geq 0} \\theta_{D} \\left( \\alpha, \\beta \\right) = \\max_{\\alpha,\\beta;\\alpha_{i} \\geq 0}  \\min_{x} L \\left( x, \\alpha, \\beta \\right) \\end{align*}   \n",
    "称为广义拉格朗日函数的极大极小问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "将广义拉格朗日函数的极大极小问题表示为约束最优化问题\n",
    "\\begin{align*} \\\\& \\max_{\\alpha,\\beta;\\alpha_{i} \\geq 0} \\theta_{D} \\left( \\alpha, \\beta \\right) = \\max_{\\alpha,\\beta;\\alpha_{i} \\geq 0}  \\min_{x} L \\left( x, \\alpha, \\beta \\right) \n",
    "\\\\ & \\quad s.t. \\quad \\alpha_{i} \\geq 0, \\quad i =1,2, \\cdots, k \\end{align*}   \n",
    "称为原始问题的对偶问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义对偶问题的最优值\n",
    "\\begin{align*} \\\\&  d^{*} = \\max_{\\alpha, \\beta;\\alpha_{i} \\geq 0} \\theta_{D} \\left( \\alpha, \\beta \\right) \\end{align*} \n",
    "称为对偶问题的值。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "若原始问题与对偶问题都有最优解，则\n",
    "\\begin{align*} \\\\&  d^{*} =  \\max_{\\alpha,\\beta;\\alpha_{i} \\geq 0}  \\min_{x} L \\left( x, \\alpha, \\beta \\right) \\leq  \\min_{x} \\max_{\\alpha, \\beta; \\alpha_{i} \\geq 0} L \\left( x, \\alpha, \\beta \\right) = p^{*}\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于原始问题及其对偶问题，假设函数$f \\left( x \\right)$和$c_{i} \\left( x \\right)$是凸函数，$h_{j} \\left( x \\right)$是仿射函数，且不等式约束$c_{i} \\left( x \\right)$是严格可行的，即存在$x$，对所有$i$有$c_{i} \\left( x \\right) < 0$，则存在$x^{*}, \\alpha^{*}, \\beta^{*}$，使$x^{*}$是原始问题的解，$\\alpha^{*}, \\beta^{*}$是对偶问题的解，并且\n",
    "\\begin{align*} \\\\&  p^{*}=d^{*} = L \\left( x^{*}, \\alpha^{*}, \\beta^{*} \\right) \\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于原始问题及其对偶问题，假设函数$f \\left( x \\right)$和$c_{i} \\left( x \\right)$是凸函数，$h_{j} \\left( x \\right)$是仿射函数，且不等式约束$c_{i} \\left( x \\right)$是严格可行的，即存在$x$，对所有$i$有$c_{i} \\left( x \\right) < 0$，则存在$x^{*}, \\alpha^{*}, \\beta^{*}$，使$x^{*}$是原始问题的解，$\\alpha^{*}, \\beta^{*}$是对偶问题的解的充分必要条件是$x^{*}, \\alpha^{*}, \\beta^{*} $满足下面的Karush-Kuhn-Tucker(KKT)条件：\n",
    "\\begin{align*} \\\\&  \\nabla _{x} L \\left( x^{*}, \\alpha^{*}, \\beta^{*} \\right) = 0 \n",
    "\\\\ & \\nabla _{\\alpha} L \\left( x^{*}, \\alpha^{*}, \\beta^{*} \\right) = 0 \n",
    "\\\\ & \\nabla _{\\beta} L \\left( x^{*}, \\alpha^{*}, \\beta^{*} \\right) = 0 \n",
    "\\\\ & \\alpha_{i}^{*} c_{i} \\left( x^{*} \\right) = 0,\\quad i= 1, 2, \\cdots, k \n",
    "\\\\ & c_{i} \\left( x^{*} \\right) \\leq 0, \\quad i=1,2, \\cdots, k\n",
    "\\\\ & \\alpha_{i}^{*} \\geq 0, \\quad i=1,2, \\cdots, k\n",
    "\\\\ & h_{j} \\left( x^{*} \\right) = 0, \\quad j=1,2, \\cdots, l\\end{align*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}