第一章 最优化问题与数学预备知识1. 最优化问题的一般形式给定目标函数，满足不等式约束及等式约束，记为：)(min x f X Ω∈，其中[]Tn x x x x ,...,,21=)(,...2,10)(,...,2,10)(..n l l j x h mi x s t s j i <===≥满足所有约束的向量X 称为容许解或容许点，容许点集合称为容许集。

从最优化问题的一般形式可以看出，最优化要解决的问题就是在容许集中找一点*x ，使目标函数)(x f ，在该点取极小。

这样*x 称为问题的最优点，而相应的目标函数值)(*x f 称为最优值。

2.最优化问题分类最优化问题可分为静态问题和动态问题两大类，本书只讨论静态问题。

静态最优化问题又可分为无约束问题和约束问题两类。

例：求Rosenbrock 函数大极小点，即{}212212)1()(100min x x x -+-。

这是一个无约束二维问题。

例：求优化问题{}3214min x x x ++ 422..321=+-x x x t s0,0,0321≥≥≥x x x 的最优解。

这是一个约束最优化问题。

无约束问题又可分为一维问题及n 维问题，求解一维问题的方法称为一维搜索或直线搜索，在最优化方法中起着十分重要的作用，故单独列出。

约束问题又分为线性规划和非线性规划。

3.二次函数1)二次函数的一般形∑∑∑===++==n i nj ni i i j i ij n c x b x x q x x x f x f 1112121),...,,()(它的矩阵形式是c x b Qx x x f T T ++=21)(其中⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡= (2)12222111211nn n n n n q q q q q qq q q Q ,⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=n b b b b (21)这里Q 是对称矩阵。

我们称特殊的二次函数Qx x x f T 21)(=为二次型。

（无一次项和常数项）2)正定矩阵设Q 是n n ⨯阶对称矩阵。

若n R x ∈∀且0≠x 时都有0>Qx x T ，则称矩阵Q 是正定的；若n R x ∈∀都有0≥Qx x T ，则称矩阵Q 是半正定的； 若n R x ∈∀且0≠x 时都有0<Qx x T ，则称矩阵Q 是负定的。

若n R x ∈∀都有0≤Qx x T ，则称矩阵Q 是半负定的。

一个对称矩阵是不是正定的，可用sylvester 定理判定，该定理内容是。

一个n n ⨯阶对称矩阵Q 是正定矩阵的充分必要条件是，矩阵Q 的各阶主子式都是正的。

3)二次函数的最优解析解如矩阵Q 是正定矩阵c x b Qx x x f T T ++=21)(，)(x f 的等值面是同心椭球面族。

其中心是b Q x 1*--=，还可证明b Q x 1*--=恰是二次目标函数的唯一极小点。

综上所述，对于二次目标函数有有效的求极小点的算法。

该算法也可用于一般目标函数小范围内的最优解搜寻，即当搜索区域位于最优点附近时，该方法是一种有效算法。

最优化理论中判定一个算法的好坏标准之一，就是把该算法用于Q 为正定的二次目标函数，如果能迅速地找到极小点，那就是好的算法；否则就是不好的或不太好的算法。

特别地，当把一个算法应用于Q 为正定的二次目标函数时，如果在有限步内就能求出极小点来，那么这种算法称为二次收敛算法，或具有二次收敛性。

4.梯度与Hessian 矩阵 1)多元函数的可微性与梯度定义1:对于函数)(x f ，如果存在n 维向量l ，对于任意n 维向量p ,有：0)()(lim 000=--+→pp l x f p x f T p ，则称)(x f 在0x 处可微。

显而易见，如)(x f 在0x 处可微，则有：)()()(00p O p l x f p x f T +=-+实际上l 就是)(x f 的偏导数向量Tn x x f x x f x x f l ⎥⎦⎤⎢⎣⎡∂∂∂∂∂∂=)(...)(,)(02010 证明如下： 令[]n l l l l ...,,21=；取i i e p p =，其中i p 是无穷小变量，i e 是第i 个坐标轴上的单位向量，即：Tii e ⎥⎦⎤⎢⎣⎡=0...,0,1,0...,0i i i i x i i i p i i p x x f l x x f x x f p x f e p x f p x f e p x f i i ∂∂==∇-∇+=-+=-+→∇→→)()()()()()()(0000000000lim lim lim定义2: 以)(x f 的n 个偏导数为分量的向量称为)(x f 在x 处的梯度，记为Tn x x f x x f x x f x f ⎥⎦⎤⎢⎣⎡∂∂∂∂∂∂=∇)(...,,)(,)()(21因此)()()()(000p O p x f x f p x f T +∇+=+，这个公式与一元函数的Taylor 展开式是相对应的。

2)方向导数定义: 设f 是定义在n R 中区域上的实值函数，f 在点0x 处可微，p 是固定不变的常量，e 是方向p 上的单位向量，则称极限tx f te x f p x f t )()(lim )(0000-+=∂∂+→为函数)(x f 在点0x 处沿p 方向的方向导数。

若0)(0<∂∂px f ，则)(x f 从0x 出发在其附近沿p 方向是下降的。

若0)(0>∂∂px f ，则)(x f 从0x 出发在其附近沿p 方向是上升。

事实上，若0)(0<∂∂px f ，则当0>t 且充分小时，必有0)()(00<-+t x f te x f ，即)()(0x f x f <，即)(x f 是下降的。

同理可说明，若0)(0>∂∂px f ，)(x f 是上升的。

定理：设f 是定义在n R 中区域上的实值函数，f 在点0x 处可微，则e xf px f T )()(00∇=∂∂，其中e 是p 方向的单位向量。

证明：因为)()()()(000p O p x f x f p x f T +∇=-+e xf tt o e x f t t x f te x f p x f T T t t )()()(lim )()(lim )(0000000∇=+∇=-+=∂∂+→+→推论：若0)(0<∇p x f T ，则p 方向是函数)(x f 在点0x 处的下降方向；若0)(0>∇p x f T ，则p 方向是函数)(x f 在点0x 处的上升方向；方向导数的正负决定了函数的升降，其绝对值的大小决定函数值升降的快慢。

绝对值越大，升降的速度就越快。

3)最速下降方向βcos )()()(000x f e x f px f T ∇=∇=∂∂ 其中β是梯度与p 方向的夹角。

因此，函数负梯度方向就是函数的最速下降方向。

4)梯度的性质①函数在某点的梯度若不为零，则必与过该点的等值面垂直。

②梯度方向是函数具有最大变化率的方向。

③若C x f =)(，则0)(=∇x f ，即0=∇C ④b x b T =∇)( ⑤x x x T 2)(=∇ ⑥Qx Qx x T 2)(=∇ 5) Hessian 矩阵(1)向量值函数的导数设g 是定义在n R 中区域上的向量值函数,如果)(x g 的所有分量)(),...(),(21x g x g x g m 在0x 点都可微，那么向量值函数)(x g 在点0x 处称为可微。

若)(x g 在点0x 处可微，则对于任意的n 维向量p 都有0)()()(lim 0000=∇--+→pp x g x g p x g T i i i p因为向量的极限是通过它所有分量的极限来定义的，所以上式等价于0)()()(lim0000=∇--+→ppx g x g p x g p其中)(0x g ∇称为函数)(x g 在点0x 处的导数。

也称函数)(x g 在点0x 处的Jacobi 矩阵。

⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡∇∇∇=∇n m m m n n m x x g x x g x x g x x g x x g xx g x x g x x g x x g g g g x g )(...)()(............)(...)()()(...)()(...)(020100220210012011012102 设n m =，并且)()(x f x g ∇=，其中)(x f 是n 元函数，假定它具有二阶连续偏导数。

则：⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂=∇∇=∇22221222222212121222122)(...)()(............)(...)()()(...)()())(()(n nnn n x x f x x x f x x x f x x x f x x f xx x f x x x f x x x f x x f x f x f在微积分中已经证明过，当)(x f 的所有二阶偏导数连续时，有ij j i x x x f x x x f ∂∂∂=∂∂∂)()(22，在这种情况下，Hessen 矩阵是对称的。

(2)几个特殊向量的导数①O c =∇,其中c 是分量全为常数的n 维向量，O 是n n ⨯阶零矩阵。

②I x =∇， ③Q Qx =∇)(3))()(0tp x f t +=ϕ的一二阶导数设[])0()0(2)0(10...,,nx x x x = )...,,()()0(2)0(21)0(1n n tp x tp x tp x f t +++=ϕp tp x f p x tp x f t T i ni i)()()(010'+∇=∂+∂=∑=ϕ p tp x f p p p x x tp x f p x tp x f dt d t T ni n i nj i j i j i i )()()()(02111020''+∇=∂∂+∂=⎥⎦⎤⎢⎣⎡∂+∂=∑∑∑===ϕ 5.多元函数的Taylor 展开式定理: 设f 是定义在n R 中区域上的实值函数，具有二阶连续偏导数，则：p x f p p x f x f p x f T T )(21)()()(2∇+∇+=+ 其中p x x θ+=，而10<<θ 证明：设)()(tp x f t +=ϕ，于是)()1(),()0(p x f x f +==ϕϕ按一元函数Taylor 展开定理把)(t ϕ在0=t 点展开，得到2''')(21)0()0()(t t t t θϕϕϕϕ++=，其中10<<θ。