第22章 凸优化问题.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "第22章 凸优化问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "22.1 引言"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "把优化问题的可行域限定为凸集。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "22.2 凸函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义22.1 函数$f:\\Omega\\to\\mathbb{R},\\Omega\\subset\\mathbb{R}^n$的图像为集合$\\Omega\\times\\mathbb{R}\\subset\\mathbb{R}^{n+1}$中的点集：\n",
    "$$\\left\\{\\begin{bmatrix}  \\mathbf{x} \\\\ f\\left(\\mathbf{x}\\right) \\end{bmatrix}:\\mathbf{x}\\in\\Omega\\right\\}$$  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "函数$f$的图像可以描绘成$f\\left(\\mathbf{x}\\right)$关于$\\mathbf{x}$的图形上的点集。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义22.2 函数$f:\\Omega\\to\\mathbb{R},\\Omega\\subset\\mathbb{R}^n$的上图（epigraph），记为$epi\\left(f\\right)$，是集合$\\Omega\\times\\mathbb{R}$中的点集：\n",
    "$$epi\\left(f\\right)=\\left\\{\\begin{bmatrix}  \\mathbf{x} \\\\ \\beta \\end{bmatrix}:\\mathbf{x}\\in\\Omega,\\beta\\in\\mathbb{R},\\beta\\geqslant f\\left(\\mathbf{x}\\right)\\right\\}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "函数$f$的上图$epi\\left(f\\right)$是位于集合$\\Omega\\times\\mathbb{R}$中、在函数$f$的图像上和图像上方的点集。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义22.3 如果函数$f:\\Omega\\to\\mathbb{R},\\Omega\\subset\\mathbb{R}^n$的上图是凸集，则函数$f$是集合$\\Omega$上的凸函数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定理22.1 如果函数$f:\\Omega\\to\\mathbb{R},\\Omega\\subset\\mathbb{R}^n$是集合$\\Omega$上的凸函数，则集合$\\Omega$是凸集。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定理22.2 对于定义在凸集$\\Omega\\subset\\mathbb{R}^n$上的函数$f:\\Omega\\to\\mathbb{R}$，$f$是凸函数当且仅当对于任意$\\mathbf{x},\\mathbf{y}\\in\\Omega$和任意$\\alpha\\in\\left(0,1\\right)$，都有\n",
    "$$f\\left(\\alpha\\mathbf{x}+\\left(1-\\alpha\\right)\\mathbf{y}\\right)\\leqslant\\alpha f\\left(\\mathbf{x}\\right)+\\left(1-\\alpha\\right)f\\left(\\mathbf{y}\\right)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果函数$f:\\Omega\\to\\mathbb{R}$是定义在凸集$\\Omega$上的凸函数，那么对于任意$\\mathbf{x},\\mathbf{y}\\in\\Omega$，在空间$\\mathbb{R}^{n+1}$中连接两点$\\left[\\mathbf{x}^\\top,f\\left(\\mathbf{x}\\right)\\right]^\\top$和$\\left[\\mathbf{y}^\\top,f\\left(\\mathbf{y}\\right)\\right]^\\top$之间线段上的所有点，都位于函数$f$的图像或上图。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定理22.3 设函数$f,f_1,f_2$都是凸函数，则对于$\\forall a\\geqslant0$,函数$af$也是凸函数；$f_1+f_2$也是凸函数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一组凸函数$f_1,\\dots,f_\\ell$和一组非负实数$c_1,\\dots,c_\\ell$，函数$c_1 f_1+\\dots+c_\\ell f_\\ell$也是凸函数；函数$\\max\\{f_1,\\dots,f_\\ell\\}$也是凸函数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义22.4 对于定义在凸集$\\Omega\\subset\\mathbb{R}^n$上的函数$f:\\Omega\\to\\mathbb{R}$，如果对于任意$\\mathbf{x},\\mathbf{y}\\in\\Omega，\\mathbf{x}\\neq\\mathbf{y}$和任意$\\alpha\\in\\left(0,1\\right)$，都有\n",
    "$$f\\left(\\alpha\\mathbf{x}+\\left(1-\\alpha\\right)\\mathbf{y}\\right)<\\alpha f\\left(\\mathbf{x}\\right)+\\left(1-\\alpha\\right)f\\left(\\mathbf{y}\\right)$$\n",
    "则函数$f$是$\\Omega$上的严格凸函数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于严格凸函数，连接两点$\\left[\\mathbf{x}^\\top,f\\left(\\mathbf{x}\\right)\\right]^\\top$和$\\left[\\mathbf{y}^\\top,f\\left(\\mathbf{y}\\right)\\right]^\\top$之间线段上的所有点（不包括两个断点），都严格位于函数$f$的上图。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定义22.5 对于定义在凸集$\\Omega\\subset\\mathbb{R}^n$上的函数$f:\\Omega\\to\\mathbb{R}$，当$-f$是（严格）凸函数时，$f$是（严格）凹函数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "命题22.1 如果函数$f:\\Omega\\to\\mathbb{R},\\Omega\\subset\\mathbb{R}^n$是二次型函数$f\\left(\\mathbf{x}\\right)=\\mathbf{x}^\\top\\mathbf{Q}\\mathbf{x},\\mathbf{Q}\\in\\mathbb{R}^{n\\times n},\\mathbf{Q}=\\mathbf{Q}^\\top$，那么$f$是$\\Omega$上的凸函数，当且仅当对所有$\\mathbf{x},\\mathbf{y}\\in\\Omega$，恒有$\\left(\\mathbf{x}-\\mathbf{y}\\right)^\\top\\mathbf{Q}\\left(\\mathbf{x}-\\mathbf{y}\\right)\\geqslant0$成立。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定理22.4 设$f:\\Omega\\to\\mathbb{R},f\\in\\mathcal{C}^1$是定义在开凸集$\\Omega\\in\\mathbb{R}^n$上的可微函数，那么$f$是$\\Omega$上的凸函数，当且仅当对于任意$\\mathbf{x},\\mathbf{y}\\in\\Omega$，有\n",
    "$$f\\left(\\mathbf{y}\\right)\\geqslant f\\left(\\mathbf{x}\\right)+Df\\left(\\mathbf{x}\\right)\\left(\\mathbf{y}-\\mathbf{x}\\right)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "令$x_0\\in\\Omega$，函数$\\ell\\left(\\mathbf{x}\\right)=f\\left(\\mathbf{x}_0\\right)+Df\\left(\\mathbf{x}_0\\right)\\left(\\mathbf{x}-\\mathbf{x}_0\\right)$是函数$f$在点$\\mathbf{x}_0$处的线性近似。  \n",
    "函数$f$的图像总是位于线性近似函数的上方，即在定义域内任意一点处，凸函数$f$的线性近似总是位于其上图$epi\\left(f\\right)$的下方。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "函数$f:\\Omega\\to\\mathbb{R}$定义在开凸集$\\Omega\\subset\\mathbb{R}^n$上，如果对于所有$\\mathbf{y}\\in\\Omega$，都有\n",
    "$$f\\left(\\mathbf{y}\\right)\\geqslant f\\left(\\mathbf{x}\\right)+\\mathbf{g}^\\top\\left(\\mathbf{y}-\\mathbf{x}\\right)$$\n",
    "则称向量$\\mathbf{g}\\in\\mathbb{R}^n$为函数$f$定义在点$\\mathbf{x}\\in\\Omega$处的次梯度。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果$\\mathbf{g}$是次梯度，那么对于给定的$\\mathbf{x}_0\\in\\Omega$函数$\\ell\\left(\\mathbf{x}_0\\right)=f\\left(\\mathbf{x}_0\\right)+\\mathbf{g}^\\top\\left(\\mathbf{y}-\\mathbf{x}_0\\right)$位于上图$epi\\left(\\mathbf{x}\\right)$的下方。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定理22.5 函数$f:\\Omega\\to\\mathbb{R},f\\in\\mathcal{C}^2$定义在开凸集$\\Omega\\subset\\mathbb{R}^n$上的凸函数，当且仅当对于任意$\\mathbf{x}\\in\\Omega$，函数$f$在点$\\mathbf{x}$处的黑塞矩阵$\\mathbf{F}\\left(\\mathbf{x}\\right)$半正定。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "22.3 凸优化问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "凸优化问题（凸规划）是目标函数是凸函数、约束集是凸集的优化问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定理22.6 已知$f:\\Omega\\to\\mathbb{R}$是定义在凸集$\\Omega\\in\\mathbb{R}^n$上的凸函数，集合$\\Omega$中某一点是$f$的全局极小点，当且仅当它是$f$的局部极小点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "引理22.2 函数$f:\\Omega\\to\\mathbb{R}$是定义在凸集$\\Omega\\in\\mathbb{R}^n$上的凸函数，$f\\in\\mathcal{C}^1$定义在包含$\\Omega$的开集上。选定点$\\mathbf{x}^*\\in\\Omega$，如果对于任意$\\mathbf{x}\\in\\Omega,\\mathbf{x}\\neq\\mathbf{x}^*$，都有\n",
    "$$Df\\left(\\mathbf{x}^*\\right)\\left(\\mathbf{x}-\\mathbf{x}^*\\right)\\geqslant0$$\n",
    "则$\\mathbf{x}^*$是在$\\Omega$上的全局极小点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定理22.7 函数$f:\\Omega\\to\\mathbb{R}$是定义在凸集$\\Omega\\in\\mathbb{R}^n$上的凸函数，$f\\in\\mathcal{C}^1$定义在包含$\\Omega$的开集上。$\\mathbf{x}^*\\in\\Omega$，对于点$\\mathbf{x}^*$处的任意可行方向$\\mathbf{d}$，有\n",
    "$$\\mathbf{d}^\\top\\nabla f\\left(\\mathbf{x}^*\\right)\\geqslant0$$\n",
    "则$\\mathbf{x}^*$是在$\\Omega$上的全局极小点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "推论22.2 函数$f:\\Omega\\to\\mathbb{R}$是定义在凸集$\\Omega\\in\\mathbb{R}^n$上的凸函数，$f\\in\\mathcal{C}^1$定义在包含$\\Omega$的开集上。存在点$\\mathbf{x}^*\\in\\Omega$，使得\n",
    "$$\\nabla f\\left(\\mathbf{x}^*\\right)=\\mathbf{0}$$\n",
    "则$\\mathbf{x}^*$是在$\\Omega$上的全局极小点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定理22.8 函数$f:\\mathbf{R}^n\\to\\mathbf{R},f\\in\\mathcal{C}^1$是可行域\n",
    "$$\\Omega=\\{\\mathbf{x}\\in\\mathbb{R}^n:\\mathbf{h}\\left(\\mathbf{x}\\right)=\\mathbf{0}\\}$$\n",
    "上的凸函数。$\\mathbf{h}:\\mathbb{R}^n\\to\\mathbb{R}^m,\\mathbf{h}\\in\\mathcal{C}^1$，且$\\Omega$是凸集。假设存在点$\\mathbf{x}^*\\in\\Omega$和$\\boldsymbol{\\lambda}^*\\in\\mathbb{R}^m$，使得\n",
    "$$Df\\left(\\mathbf{x}^*\\right)+\\boldsymbol{\\lambda}^{*\\top}D\\mathbf{h}\\left(\\mathbf{x}^*\\right)=\\mathbf{0}^\\top$$\n",
    "则$\\mathbf{x}^*$是在$\\Omega$上的全局极小点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "定理22.9 函数$f:\\mathbf{R}^n\\to\\mathbf{R},f\\in\\mathcal{C}^1$是可行域\n",
    "$$\\Omega=\\{\\mathbf{x}\\in\\mathbb{R}^n:\\mathbf{h}\\left(\\mathbf{x}\\right)=\\mathbf{0},\\mathbf{g}\\left(\\mathbf{x}\\right)\\leqslant\\mathbf{0}\\}$$\n",
    "上的凸函数。$\\mathbf{h}:\\mathbb{R}^n\\to\\mathbb{R}^m,\\mathbf{g}:\\mathbb{R}^n\\to\\mathbb{R}^p,\\mathbf{h},\\mathbf{g}\\in\\mathcal{C}^1$，且$\\Omega$是凸集。假设存在点$\\mathbf{x}^*\\in\\Omega$和$\\boldsymbol{\\lambda}^*\\in\\mathbb{R}^m,\\boldsymbol{\\mu}^*\\in\\mathbb{R}^p$，使得\n",
    "1. $\\boldsymbol{\\mu}\\geqslant\\mathbf{0}$\n",
    "2. $Df\\left(\\mathbf{x}^*\\right)+\\boldsymbol{\\lambda}^{*\\top}D\\mathbf{h}\\left(\\mathbf{x}^*\\right)+\\boldsymbol{\\mu}^{*\\top}D\\mathbf{g}\\left(\\mathbf{x}^*\\right)=\\mathbf{0}^\\top$\n",
    "3. $\\boldsymbol{\\mu}^{*\\top}\\mathbf{g}\\left(\\mathbf{x}^*\\right)=\\mathbf{0}$\n",
    "\n",
    "则$\\mathbf{x}^*$是在$\\Omega$上的全局极小点。"
   ]
  }
 ],
 "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.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}