第一章

1、多元函数的梯度及性质

梯度函数：

定义1：
如果f(x)在任意点x\in \R^n处处一阶可导，则称下面的向量函数：

\nabla f (x^*)=\left(\frac{\partial f(x)}{\partial x_1},\frac{\partial f(x)}{\partial x_2},......,\frac{\partial f(x)}{\partial x_n}\right)^T


为f(x)的梯度函数，也称为一阶导函数。

定义2：
满足\nabla f (x^*)=0的点x^*称为f(x)的稳定点或驻点。\\ 设x^k为第k步的迭代点。\\ 若f(x)具有一阶连续偏导数，只需要验证一下条件成立：

\begin{Vmatrix} \nabla f (x^k) \end{Vmatrix}_2=0

定义3：

设函数f：\Omega \subset\R^n\to\R在x^0处可导，p \in \R^n为0维非零向量，如果存在实数\delta>0，使得任意的\alpha \in (0,\delta)有：

f(x^0+\alpha p)<f(x^0)

则称p为f(x)在x^0处的一个下降方向，即f(x)从x^0出发沿p方向函数值是下降的。

定理1：

若函数f(x)定义在\Omega\subset\R^n，并具有一阶连续偏导数，x^*是\Omega的一个内点，若x^*是f(x)的极值点，则：

\nabla f (x^*)=0

注意：此定理是极值点的一阶必要条件。

定理2：

设函数f：\Omega \subset \R^n \to \R在点x^k处一阶可导，p\in \R^n为n维非零向量，如果满足：

\nabla f (x^k)^Tp<0

则p必为f(x)在x^k处的下降方向。

定理3：

梯度的反方向(负梯度方向)-\nabla f (x^k)是f(x)从x^k出发下降最快的方向，因此，也称-\nabla f (x^k)为该点处的最速下降方向。

Hessian矩阵：

定义4：

设f：\R^n \to \R,\bar{x}\in\R^n,如果f(x)在点\bar{x}处关于变量x的各分量的二阶偏导数都存在。\\ 则称f(x)在点\bar{x}处二阶可导，并称如下矩阵为f(x)在点\bar{x}处的Hessian矩阵或二阶导数。

\nabla^2f(\bar{x})=\left(\frac{\partial^2 f(\bar{x})}{\partial x_i\partial x_j}\right)_{n\times n}\\ \nabla^2f(\bar{x})= \begin{pmatrix} \frac{\partial^2 f(\bar{x})}{\partial x_1^2} & \frac{\partial^2 f(\bar{x})}{\partial x_1\partial x_2} &... &\frac{\partial^2 f(\bar{x})}{\partial x_1\partial x_n} \\ \frac{\partial^2 f(\bar{x})}{\partial x_2\partial x_1} &\frac{\partial^2 f(\bar{x})}{\partial x_2^2} &... &\frac{\partial^2 f(\bar{x})}{\partial x_2\partial x_n}\\ ... &... &... &...\\ \frac{\partial^2 f(\bar{x})}{\partial x_n\partial x_1} & \frac{\partial^2 f(\bar{x})}{\partial x_n\partial x_2} &... &\frac{\partial^2 f(\bar{x})}{\partial x_n^2} \end{pmatrix}

Taylor展式：

定理4：

设f:\R^n \to \R,x_0\in \R^n，如果f(x)在x_0的某个邻域N_\delta(x_0)具有一阶连续偏导数，则：

f(x)=f(x_0)+\nabla f(x_0)^T(x-x_0)+o(\begin{Vmatrix} x-x_0 \end{Vmatrix}),x\in N_\delta(x_0)

定理5：

设f：\R^n \to \R,x_0 \in \R^n。如果f(x)在x_）的某邻域N_\delta(x_0)具有二阶连续偏导数，则：

f(x)=f(x_0)+\nabla f(x_0)^T(x-x_0)+\frac{1}{2}(x-x_0)^T\nabla^2f(x_0)(x-x_0)+o(\begin{Vmatrix} x-x_0 \end{Vmatrix}^2),x\in N_\delta(x_0)

2、凸集和凸函数

凸集：

定义1：

设集合\Omega \subset \R^n，若对于任意两点x,y\in \Omega及实数\lambda(0≤\lambda≤1),都有：

\lambda x +(1-\lambda)y\in \Omega

则称集合\Omega为凸集。

凸函数：

定义6：

设函数f(x)定义在凸集\Omega \subset \R^n上。若对于任意两点x,y\in \Omega及任意的\lambda(0≤\lambda≤1),都有：

f(\lambda x +(1-\lambda)y)≤\lambda f(x)+(1-\lambda)f(y)

则称函数f(x)为凸集合\Omega上的凸函数。

凸函数的性质：

(1)设f(x)是凸集\Omega\subset\R^n上的凸函数，实数k\ge0，则kf(x)也是\Omega上的凸函数。

(2)设f_1(x),f_2(x)是凸集\Omega\subseteq\R^n上的凸函数，则f_1(x)+f_2(x)也是\Omega上的凸函数。\\

(3)设f_1(x),...，f_m(x)是凸集\Omega\subseteq\R^n上的凸函数，实数\omega_i\ge0,则\sum_{i=1}^m\omega_if_i(x)也是\Omega上的凸函数。

(4)设f(x)是凸集\Omega\subseteq\R^n上的凸函数，c是实数，则水平集\Omega_c=\{x\in \Omega|f(x)\le c\}是凸集。

(5)设f_i(x)(i=1,2,...,p)为凸集\Omega\subseteq\R^n上的凸函数，实数c_i(i=1,2,...,p)为实常数，则\widehat{\Omega}=\{x|x\in\Omega,f_1(x)\le c_1,...,f_p(x)\le c_p\}也是凸集。

判断凸函数的一阶条件：

定理6：

设在凸集\Omega\subseteq\R^n上f(x)可微，则f(x)在\Omega上为凸函数的充要条件是对任意的x_1,x_2\in \Omega，都有： \\f(x_2)\ge f(x_1)+\nabla f(x_1)^T(x_2-x_1)

定理7：

凸函数(充要条件)：可微函数为凸函数的充要条件是在其定义域凸集中任一点处的切平面(切线)都不在曲面(曲线)的上方。

判断凸函数的二阶条件:

定理8：

设在开凸集\Omega\subseteq\R^n内f(x)二阶连续可微，则f(x)是\Omega内凸函数的充要条件为:在\Omega内任一点x处，f(x)的Hessian矩阵半正定，其中：

\nabla^2 f(x)=\begin{pmatrix} \frac{\partial^2 f(\bar{x})}{\partial x_1^2} & \frac{\partial^2 f(\bar{x})}{\partial x_1\partial x_2} &... &\frac{\partial^2 f(\bar{x})}{\partial x_1\partial x_n} \\ \frac{\partial^2 f(\bar{x})}{\partial x_2\partial x_1} &\frac{\partial^2 f(\bar{x})}{\partial x_2^2} &... &\frac{\partial^2 f(\bar{x})}{\partial x_2\partial x_n}\\ ... &... &... &...\\ \frac{\partial^2 f(\bar{x})}{\partial x_n\partial x_1} & \frac{\partial^2 f(\bar{x})}{\partial x_n\partial x_2} &... &\frac{\partial^2 f(\bar{x})}{\partial x_n^2} \end{pmatrix}

补充：

A是n阶实对称矩阵，则A半正定\Harr A的所有主子式\ge 0\Harr A的所有特征值都\ge 0

定理9：

设在开凸集\Omega\subseteq\R^n内二阶可微，若在\Omega内\nabla^2 f(x)正定，则f(x)在\Omega内是严格凸函数。(注：反之不成立)

补充：

A是n阶实对称矩阵，则A正定\Harr A的所有顺序主子式\ge0\Harr A的n个特征值都\ge0

重要结论：

定理10：
若函数f(x)是定义在\R^n上的凸函数，且具有一阶连续偏导数，则x^*是f(x)的极小值点的充要条件是：\nabla f(x^*)=0

定理11：(极值点的二阶充分条件)

若函数 f(x) 定义在 \Omega \subseteq \mathbb{R}^{n} 并具有二阶连续偏导数, 且 x^{*} 是 \Omega 内的一点, \nabla f\left(x^{*}\right)=0, \nabla^{2} f\left(x^{*}\right) 正定, 则 x^{*} 是 f(x) 的极小值点。

凸规划：

\mathbf { { \bar { 2 } } } . { \mathbf { \bar { 7 } } }D = \{ x \in \mathbb R ^ { n } | h _ { i } ( x ) = 0 , g _ { j } ( x ) \leq 0 , i = 1 , \cdots , l ; j = 1 , \cdots , m \}

{ \mathit { f } } ( { \boldsymbol { x } } )

1 LP标准型

2 LP基本原理

3 单纯形法(Simplex method)

4 大M法(人工变量法一)

5 二阶段法(人工变量法二)

6 线性规划的对偶理论

第三章 无约束优化

1 迭代法概述

2 一维搜索方法(线搜索方法)

3 最速下降法(梯度下降法)

4 共轭梯度法

5 牛顿法(牛顿法和阻尼牛顿法)

6 拟牛顿法(变尺度法)

7 信赖域法