最优化方法：二、数学基础

主要参考书目：
1. 最优化方法及其应用/郭科，陈聆，魏友华.-北京：高等教育出版社,2007.7(2013.7重印)

1、二次型与正定矩阵

2、方向导数与梯度

3、Hesse矩阵及泰勒展式

• Hesse(/ˈhɛsə/)矩阵
  
  ▽2f(X0)=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢∂2f(X0)∂x21∂2f(X0)∂x2∂x1⋯∂2f(X0)∂xn∂x1∂2f(X0)∂x1∂x2∂2f(X0)∂x22⋯∂2f(X0)∂xn∂x2⋯⋯⋯⋯∂2f(X0)∂x1∂xn∂2f(X0)∂x2∂xn⋯∂2f(X0)∂x2n⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥$${▽}^{2}f(X_0)=\left[\begin{array}{cccc}{\displaystyle \frac{{\mathrm{\partial }}^{2}f(X_0)}{\mathrm{\partial }{x}_1^2}}& {\displaystyle \frac{{\mathrm{\partial }}^{2}f(X_0)}{\mathrm{\partial }{x}_1\mathrm{\partial }{x}_2}}& \cdots & {\displaystyle \frac{{\mathrm{\partial }}^{2}f(X_0)}{\mathrm{\partial }{x}_1\mathrm{\partial }{x}_n}}\\ {\displaystyle \frac{{\mathrm{\partial }}^{2}f(X_0)}{\mathrm{\partial }{x}_2\mathrm{\partial }{x}_1}}& {\displaystyle \frac{{\mathrm{\partial }}^{2}f(X_0)}{\mathrm{\partial }{x}_2^2}}& \cdots & {\displaystyle \frac{{\mathrm{\partial }}^{2}f(X_0)}{\mathrm{\partial }{x}_2\mathrm{\partial }{x}_n}}\\ \cdots & \cdots & \cdots & \cdots \\ {\displaystyle \frac{{\mathrm{\partial }}^{2}f(X_0)}{\mathrm{\partial }{x}_n\mathrm{\partial }{x}_1}}& {\displaystyle \frac{{\mathrm{\partial }}^{2}f(X_0)}{\mathrm{\partial }{x}_n\mathrm{\partial }{x}_2}}& \cdots & {\displaystyle \frac{{\mathrm{\partial }}^{2}f(X_0)}{\mathrm{\partial }{x}_n^2}}\end{array}\right]$$
  
  容易发现，当f在X0$X_0$处二阶偏导连续时，Hesse矩阵对称。
• 多元向量函数的导数
  设H:Rn→Rm,X0∈Rn$H:R^n\to R^m,X_0\in R^n$，记H(X)=[h1(X),h2(X),⋯,hm(X)]T$H(X)=[h_1(X),h_2(X),\cdots ,h_m(X){]}^T$,在存在的前提下，其导数为：
  
  ▽m×nH(X0)=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢∂h1(X0)∂x1∂h2(X0)∂x1⋯∂hn(X0)∂x1∂h1(X0)∂x2∂h2(X0)∂x2⋯∂hn(X0)∂x2⋯⋯⋯⋯∂h2(X0)∂xn∂h2(X0)∂xn⋯∂hn(X0)∂xn⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥$${▽}_{m\times n}H(X_0)=\left[\begin{array}{cccc}{\displaystyle \frac{\mathrm{\partial }{h}_1(X_0)}{\mathrm{\partial }{x}_1}}& {\displaystyle \frac{\mathrm{\partial }{h}_1(X_0)}{\mathrm{\partial }{x}_2}}& \cdots & {\displaystyle \frac{\mathrm{\partial }{h}_2(X_0)}{\mathrm{\partial }{x}_n}}\\ {\displaystyle \frac{\mathrm{\partial }{h}_2(X_0)}{\mathrm{\partial }{x}_1}}& {\displaystyle \frac{\mathrm{\partial }{h}_2(X_0)}{\mathrm{\partial }{x}_2}}& \cdots & {\displaystyle \frac{\mathrm{\partial }{h}_2(X_0)}{\mathrm{\partial }{x}_n}}\\ \cdots & \cdots & \cdots & \cdots \\ {\displaystyle \frac{\mathrm{\partial }{h}_n(X_0)}{\mathrm{\partial }{x}_1}}& {\displaystyle \frac{\mathrm{\partial }{h}_n(X_0)}{\mathrm{\partial }{x}_2}}& \cdots & {\displaystyle \frac{\mathrm{\partial }{h}_n(X_0)}{\mathrm{\partial }{x}_n}}\end{array}\right]$$
• 泰勒展开
  设f:Rn→R1$f:R^n\to R^1$具有二阶连续偏导数，则
  
  f(X+P)=f(X)+▽f(X)T+12PT▽2f(X)P+o(||P||2).$$f(X+P)=f(X)+▽f(X{)}^T+\frac{1}{2}{P}^T{▽}^{2}f(X)P+o(||P|{|}^2).$$
  
  或
  
  f(X+P)=f(X)+▽f(X)T+12PT▽2f(X¯¯¯¯)P.$$f(X+P)=f(X)+▽f(X{)}^T+\frac{1}{2}{P}^T{▽}^{2}f(\overline{X})P.$$
  
  其中X¯¯¯¯=X+θP$\overline{X}=X+\theta P$,而0<θ<1$0<\theta <1$.
• 几个公式
  
  1. n元函数求导和1元函数求导在形式上是一致的：
     例如：
     
     f(X)=12XTAX+bTX+c$$f(X)=\frac{1}{2}{X}^{T}AX+b^{T}X+c$$
     
     则
     
     ▽f(X)=AX+b▽2f(X)=A$$\begin{gathered} ▽f(X)=AX+b \\ {▽}^{2}f(X)=A \end{gathered}$$
  2. 函数梯度的Jacobi矩阵即为此函数的Hesse矩阵。
     
     ▽n×n▽f(X)=▽2f(X)$${▽}_{n\times n}▽f(X)={▽}^{2}f(X)$$
  3. 设ϕ(t)=f(X0+tP)$\varphi (t)=f(X_0+tP)$，其中f:Rn→R1,ϕ:R1→R1$f:R^n\to R^1,\varphi :R^1\to R^1$。
     则：
     ϕ′(t)=▽f(X0+tP)TP${\varphi }^{{}^{\prime }}(t)=▽f(X_0+tP{)}^{T}P$，ϕ′′(t)=PT▽2f(X0+tP)TP${\varphi }^{{}^{″}}(t)=P^T{▽}^{2}f(X_0+tP{)}^{T}P$

4、极小点的判定条件

• X∗$X^{\ast }$是局部极小点+X∗$X^{\ast }$是内点⇔▽f(X∗)=0$\iff ▽f(X^{\ast })=0$
• ▽f(X∗)=0$▽f(X^{\ast })=0$+X∗$X^{\ast }$是内点⇔X∗$\iff X^{\ast }$是驻点

5、锥、凸集、凸锥

• 锥
  设集合C⊂Rn.$C\subset R^n.$若∀X∈C$\mathrm{\forall }X\in C$及任意的数λ≥0$\lambda \ge 0$，均由λX∈C$\lambda X\in C$,则称C为锥。
• 凸组合
  
  更多有关内容
• 凸集
  
  特别地，规定空集是凸集。
  更多有关内容
• 半空间
  设a∈Rn$a\in R^n$且a≠0,b∈R1$a\ne 0,b\in R^1$，则集合{X|aTX>b,X∈Rn}$\{X|a^{T}X>b,X\in R^n\}$称为Rn$R^n$中的半空间。
  也就是广义平面分割全空间产生的两部分。
• 几个定理
  
  1. 凸集的交集仍是凸集。
  2. 首先引入三个概念：
     锥+凸集=凸锥；凸集+闭集=闭凸集；凸锥+闭集=闭凸锥；
     有定理：
     Ⅰ C为凸集⇔$\iff$∀Xi∈C,$\mathrm{\forall }{X}_i\in C,$及∀λi≥0(i=1,2,⋯,k,k≥2),∑ki=1λi=1,$\mathrm{\forall }{\lambda }_i\ge 0(i=1,2,\cdots ,k,k\ge 2),\sum _{i=1}^k{\lambda }_i=1,$有∑ki=1λiXi∈C.$\sum _{i=1}^k{\lambda }_i{X}_i\in C.$
     Ⅱ C为凸锥⇔∀Xi∈C,$\iff \mathrm{\forall }{X}_i\in C,$及∀λi≥0(i=1,2,⋯,k,k≥2),$\mathrm{\forall }{\lambda }_i\ge 0(i=1,2,\cdots ,k,k\ge 2),$有∑ki=1λiXi∈C.$\sum _{i=1}^k{\lambda }_i{X}_i\in C.$
     Ⅲ 有限个半空间的交为多面集。
     
• 极点
  设C为非空凸集，X∈C$X\in C$，若X不能表示成C中两个不同点的凸组合，换言之，若能表示成两点的凸组合，必有X1=X2=X$X_1=X_2=X$，则称X是凸集C的极点。
  *类似平面凸多边形的顶点。
• 极方向
  设C为Rn$R^n$中的闭凸集，P为非零向量，如果对C中的每一个X都有射线{X+λP|λ≥0}⊂C$\{X+\lambda P|\lambda \ge 0\}\subset C$，则称向量P为C的方向。又设P1$P_1$和P2$P_2$是C的两个方向，若对任何正数λ$\lambda$，有P1≠λP2$P_1\ne \lambda P_2$，则称P1$P_1$和P2$P_2$是两个不同的方向。若C的方向P不能表示成该集合的两个不同方向的正的线性组合，则称P为C的极方向。
  -几个定理
  Ⅰ 设C={X|AX=b,X≥0}$C=\{X|AX=b,X\ge 0\}$为非空集合，P是非零向量，P为C的方向的充要条件是P≥0$P\ge 0$且AP=0$AP=0$。
  Ⅱ
• 凸集分离定理
  

6、凸函数

• 一系列定义与性质
  
  
  下半连续
  
• 凸函数与凸集的关系
  
  
  
• 凸规划
  
  这个结论很强的，但就是条件太苛刻。
  
  则称为二次凸规划问题。（补图上不全处）

约束问题的最优性条件

• 约束优化问题的分类
  (1) IP型
  
  minf(X),s.t.gi(X)≥0,i=1,2,⋯,l.$$\begin{gathered} minf(X), \\ s.t.g_i(X)\ge 0,i=1,2,\cdots ,l. \end{gathered}$$
  
  (2) EP型
  
  minf(X),s.t.hj(X)=0,j=1,2,⋯,m.$$\begin{gathered} minf(X), \\ s.t.h_j(X)=0,j=1,2,\cdots ,m. \end{gathered}$$
  
  (3) GP型
  
  minf(X),s.t.{gi(X)≥0,i=1,2,⋯,l.hj(X)=0,j=1,2,⋯,m.$$\begin{gathered} minf(X), \\ s.t.\{\begin{array}{c}{g}_i(X)\ge 0,i=1,2,\cdots ,l.\\ h_j(X)=0,j=1,2,\cdots ,m.\end{array} \end{gathered}$$
• 一阶必要条件
  (1)起作用的约束与不起作用的约束
  
  (2)GP型问题的一阶必要条件（IP和EP可以看做GP的特殊情况)
  
  λ∗igi(X∗)=0${\lambda }_i^{\ast }{g}_i(X^{\ast })=0$巧妙地体现了只考虑起作用的约束。
  (3)Kuhn-Tucker条件
  
• 二阶充分条件
  
  事实上我们遇到的函数基本没法这样去验证。