{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "假设$f\\left(x\\right)$是$R^{n}$上具有一阶连续偏导数的函数。求解  \n",
    "\\begin{align*} \\\\ & \\min_{x \\in R^{n}} f \\left( x \\right) \\end{align*} \n",
    "无约束最优化问题。$f^{*}$表示目标函数$f\\left(x\\right)$的极小点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由于$f\\left(x\\right)$具有一阶连续偏导数，若第$k$次迭代值为$x^{\\left(k\\right)}$，则可将$f\\left(x\\right)$在$x^{\\left(k\\right)}$附近进行一阶泰勒展开\n",
    "\\begin{align*} \\\\ & f\\left(x\\right) ＝ f\\left(x^{\\left(k\\right)}\\right) + g_{k}^{T} \\left(x-x^{\\left(k\\right)}\\right)\\end{align*}\n",
    "其中，$g_{k}=g\\left( x^{\\left(k\\right)} \\right)=\\nabla f \\left( x^{\\left(k\\right)}\\right)$是$f\\left(x\\right)$在$x^{\\left(k\\right)}$的梯度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "第$k+1$次迭代值\n",
    "\\begin{align*} \\\\ & x^{\\left( k+1 \\right)} \\leftarrow x^{\\left( k \\right)} + \\lambda_{k} p_{k} \\end{align*} \n",
    "其中，$p_{k}$是搜索方向，取负梯度方向$p_{k}= - \\nabla f \\left( x^{\\left(k\\right)} \\right)$，$\\lambda_{k}$是步长，由一维搜索确定，即$\\lambda_{k}$使得\n",
    "\\begin{align*} \\\\ & f \\left( x^{\\left(k\\right)}+\\lambda_{k}p_{k} \\right)=\\min_{\\lambda \\geq 0} f \\left( x^{\\left(k\\right)}+\\lambda p_{k} \\right) \\end{align*} "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "梯度下降算法：  \n",
    "输入：目标函数$f \\left( x \\right) $，梯度函数$g\\left( x^{\\left(k\\right)} \\right)=\\nabla f \\left( x^{\\left(k\\right)}\\right)$，计算精度$\\varepsilon$  \n",
    "输出：$f \\left( x \\right) $的极小点$x^{*}$\n",
    "1. 取初值$x^{\\left(0\\right)} \\in R^{n}$，置$k=0$\n",
    "2. 计算$f \\left( x^{\\left(k\\right)}\\right)$\n",
    "3. 计算梯度$g_{k}=g\\left( x^{\\left(k\\right)} \\right)$，当$\\| g_{k} \\|  < \\varepsilon $时，停止迭代，令$x^{*}=x^{\\left(k\\right)}$；否则，令$p_{k}=-g\\left(x^{\\left(k\\right)}\\right)$，求$\\lambda_{k}$，使\n",
    "\\begin{align*} \\\\ & f \\left( x^{\\left(k\\right)}+\\lambda_{k}p_{k} \\right)=\\min_{\\lambda \\geq 0} f \\left( x^{\\left(k\\right)}+\\lambda p_{k} \\right) \\end{align*} \n",
    "4. 置$x^{\\left(k+1\\right)}= x^{\\left(k\\right)}+\\lambda_{k}p_{k}$，计算$f \\left( x^{\\left(k＋1\\right)} \\right)$  \n",
    "当$\\| f \\left( x^{\\left(k＋1\\right)} \\right) - f \\left( x^{\\left(k\\right)} \\right) \\| < \\varepsilon $或$\\|  x^{\\left(k＋1\\right)} -  x^{\\left(k\\right)}  \\| < \\varepsilon $时，停止迭代，令$x^{*}=x^{k+1}$\n",
    "5. 否则，置$k=k+1$，转3."
   ]
  },
  {
   "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
}