第2章 最优化问题的数学基础

最优化问题的数学基础

第二章 最优化问题数学基础为了便于学习最优化方法，本章将对与 优化方法密切有关的数学知识作一简要介绍 而有些数学知识将在讲解各种算法时，随之 介绍.

最优化问题的数学基础

§1.1 二次型与正定矩阵

一、二次型与实对称矩阵 二次型理论在最优化设计中应用十分 广泛.应用矩阵的乘法运算，二次型与实 对称矩阵紧密地联系在一起了，从而二次 型的基本问题又可转化成实对称矩阵问 题. 二次型理论问题起源于化二次 曲线和二次曲面的方程为标准形式的问 题.推广到n维空间中，二次超曲面的一般 方程为

最优化问题的数学基础

f ( x1, 2, , n ) a11 x12 a12 x1 x 2 a1n x1 x n x x

a 21 x 2 x1 a 22 x a 2 n x 2 x n 2 2

n n

2 a n1 x n x1 a n 2 x n x 2 a nn x n

aij xi x j ,i 1 j 1

最优化问题的数学基础

用矩阵表示为 x1 x n n f ( x1, 2, , n ) aij xi x j [ x1, 2, , n ] A 2 x x x x i 1 j 1 xn X T AX ,

其中，矩阵A的元素 a a (i j)正是二次型的 aii 是二次型的 xi2 项 xi x j项的系数的一半， 的系数.因此，二次型和它的矩阵A是相互 唯一决定的，且 A AT .ij ji

最优化问题的数学基础

二、正定矩阵 定义2.1 如果二次型 n n f ( x1, 2, , n ) aij xi x j X T AX x x i 1 j 1 x x 对于任何一组不全为零的数 x1,2, ,n 恒有x x 则称 f ( x1,2, ,n ) 正定，且二次型矩阵A也称为正 定. 简言之，一个对称矩阵A如果是正定的，则二次型 x x f ( x1,2, ,n ) X T AX 对于所有非零向量X其值总为 x x 正.类似可以给出定义，若二次型 f (x1,2, ,n ) X T AX 0 则A为半正定矩阵；若 X T AX 0 ,则A为半负定矩 阵；若二次型既不是半正定又不是半负定，就称 矩阵A为不定的.

f ( x1, 2, , n ) X T AX 0 x x

最优化问题的数学基础

矩阵A为正定的充要条件是它的行列式的顺序主子式 全部大于零，即a11 0, a11 a21 a12 a22 a11 a 0, , 21 an1 a12 a22 an 2 a1n a2 n 0 ann

由此可见，正定矩阵必然是非奇异的. 例2.1 4 2 1 判断矩阵A 2 3 0 是否正定. 1 0 2

解

4 2 1 4 2 ∵ 4 0, 2 3 8 0, 2 3 0 13 0 1 0 2

,

∴ A是正定的.

最优化问题的数学基础

§2.2 方向导数与梯度

一、方向导数 所谓方向导数的概念是作为偏导数的一个推广 而引入，它主要研究函数沿任一给定方向的变 化率. 定义2.2 设 f : R n R1 在点 X 0 处可微，P是固定 e 不变的非零向量， 是方向P上的单位向量，则 称极限 (2.1) f ( X 0 ) f ( X 0 te) f ( X 0 ) lim t 0 P t

为函数 f (X )在点 X 0 处沿P方向的方向导数，式中

f ( X 0 ) P

是它的记号.

最优化问题的数学基础

定义2.3 且 P 0 ,若存在 0 ,当t (0, ) 时都有， f ( X 0 tP) f ( X 0 ) 则称P为在点处的下降方 向.若 f ( X 0 tP) f ( X 0 ),则称P为在点处的 上升方向. 由以上两个定义可立刻得到如下的结论： 若 ，则 从 出发在 附近沿P f ( X 0 ) f( X0 0 方向是下降；若X ) X 0 ,则从出发在附 P f ( X ) 近沿P方向是上升. 0 P 0

X f : R n R1 是连续函数， 0 , 设

最优化问题的数学基础

二、梯度 定义2.4 以 f ( X )的n个偏导数为分量的向量称为f ( X )在X处的梯度， 记为 T f ( X ) f ( X ) f ( X ) . f ( X ) , ,, x1 x2 xn 梯度也可以称为函数f ( X )关于向量X 的一阶导数. 以下几个特殊类型函数的梯度公式是常用的： c (1)若 f ( X ) (常数),则 f ( X ) 0 ,即 c 0 ; (2) (bT X ) b . n T T T 证 设 b [b1,2, ,n ] ,X [ x1,2, ,n ],则 b X bi xi b b x x T i 1 于是 (b X ) 的第 j 个分量是 T n . (b X ) ( bi xi ) b j, j 1,, , 2 n x j x j i 1 所以 (bT X ) b (3) ( X T X ) 2 X . (4)若Q是对称矩阵，则 ( X T QX ) 2QX

最优化问题的数学基础

三、梯度与方向导数之间的关系 f : R n R1在点 X 0 处可微，则 定理2.1 设 f ( X 0 ) f ( X 0 )T e, P 其中 e 是 P 方向上的单位向量. 由这个定理容易得到下列结论： (1)若 f ( X 0 )T P 0 ,则P的方向是函数在点 X 0 处 的下降方向； (2) 若 f ( X 0 )T P 0,则 P 的方向是函数在点 X 0 处的上升方向. 方向导数的正负决定了函数值的升降，而升降 的快慢就由它的绝对值大小决定.绝对值越大， 升降的速度就越快，即

最优化问题的数学基础

f ( X 0 ) P

f ( X 0 )T e

= f ( X 0 ) · ( cos( f ( X 0 ) , e )) f ( X 0 ) 1·

上式中的等号，当且仅当的方向与的方向相同时才成 立. 由此可得如下重要结论(如图2.1所示): (1)梯度方向是函数值的最速上升方向； (2)函数在与其梯度正交的方向上变化率为零； (3)函数在与其梯度成锐角的方向上是上升的，而在与 其梯度成钝角的方向上是下降的； (4)梯度反方向是函数值最速下降方向.· 1·

最优化问题的数学基础

对于一个最优化问题，为了尽快得到最 优解，在每一步迭代过程中所选取的搜 索方向总是希望它等于或者是靠近于目 标函数的负梯度-----图2.1的方向，这样 才能使函数值下降的最快.

最优化问题的数学基础

例2.2 试求目标函数在点处的最速下降方向， 并求沿这个方向移动一个单位

长后新点的目标 函数值. f f 2 x1 2 x2 解 因为 x x2 1 2 x1 0 f ( X 0 )= 所以最速下降方向是- = . 2 x2 x 0 6 x 3 这个方向上的单位向量是1 2

故新点是 X1 X 0 e 对应目标函数值为f ( X1 ) 02 22 1 5

f ( X 0 ) 0 e f ( X 0 ) 1

0 0 0 3 1 2

最优化问题的数学基础

§2.3 海色矩阵及泰勒展式 一、海色(Hesse)矩阵 前面说过，梯度 f ( X )是 f ( X )关于 X 的一阶 导数，现在要问 f ( X ) 关于 X 的二阶导数是 什么？ n 定义 2.5 设： :R n R1 , 0 R ,如果在点 f X 处对于自变量的各分量的二阶偏导数 都存在，则称函数在点处二阶可导，并 且称矩阵

最优化问题的数学基础

2 f ( X 0 ) x12 2 f ( X 0 ) 2 f ( X 0 ) x2 x12

2 f ( X 0 ) 2 f ( X 0 ) x1 x2 x1 xn 2 f ( X 0 ) 2 f ( X 0 ) 2 x2 x2 xn2 2

f (X ) f (X ) f (X ) x x x x x 是 f 在点 X 0 处的Hesse矩阵. 在数学分析中已经知道，当 f 在点X 0 处的所有 二阶偏导数为连续时有 2 f ( X ) 2 f ( X ) 0 0 i, 1,, , j 2 n xi x j x j xi 因此，在这种情况下Hesse矩 …… 此处隐藏：2065字，全部文档内容请下载后查看。喜欢就下载吧 ……