最优化问题数学基础 为了便于学习最优化方法,本章将对与 优化方法密切有关的数学知识作一简要介绍 而有些数学知识将在讲解各种算法时,随之
最优化问题数学基础 为了便于学习最优化方法,本章将对与 优化方法密切有关的数学知识作一简要介绍 而有些数学知识将在讲解各种算法时,随之 介绍.
§1.1二次型与正定矩阵 次型与实对称矩阵 次型理论在最优化设计中应用十分 泛.应用矩阵的乘法运算,二次型与实 对称矩阵紧密地联系在一起了,从而二次 型的基本问题又可转化成实对称矩阵问 题 二次型理论问题起源于化二次 曲线和二次曲面的方程为标准形式的问 题.推广到n维空间中,二次超曲面的一般 方程为
§1.1 二次型与正定矩阵 一、二次型与实对称矩阵 二次型理论在最优化设计中应用十分 广泛.应用矩阵的乘法运算,二次型与实 对称矩阵紧密地联系在一起了,从而二次 型的基本问题又可转化成实对称矩阵问 题. 二次型理论问题起源于化二次 曲线和二次曲面的方程为标准形式的问 题.推广到n维空间中,二次超曲面的一般 方程为
f(x1,x2,…,xn)=a1x1+a12x1x2+…+a12x1xn x1+a2x2+…+a2nx2xn+ axx+ tax ∑∑ax D
•• , , , , = = =+ + + + + + + = + + + + ni nj i j i j n n n n n n n n n n n n a x x a x x a x x a x a x x a x a x x f x x x a x a x x a x x 1 1 2 1 1 2 2 2 2 2 2 1 2 1 2 2 2 1 2 1 2 1 1 2 1 2 1 1 1 ( )
用矩阵表示为 f(x,x…x)=∑4x,=x…x1 X AX 其中,矩阵A的元素。=(正是二次型的 项的系数的一半,是二次型的项 的系数.因此,二次型和它的矩阵A是相互 唯一决定的,且A4
用矩阵表示为 其中,矩阵A的元素 正是二次型的 项的系数的一半, 是二次型的 项 的系数.因此,二次型和它的矩阵A是相互 唯一决定的,且 . , , , , , , , X AX x x x f x x x a x x x x x A T n i n j n n i j i j n = = = =1 =1 2 1 1 2 1 2 ( ) [ ] a a (i j) ij = ji i j x x ii a 2 i x T A = A
正定矩阵 定义2.1如果二次型 )=A 对于任何一组不全为零的数x恒有 f( x1,X2y……yX XAX>O 则称xx)正定,且二次型矩阵A也称为正 定 简言之,一个对称矩阵A如果是正定的,则二次型 X对于所有非零向量X其值总为 正.类似可以给出定义,若二次型xx)=XAX20 则A为半正定矩阵;若xAX≤0,则A为半负定矩 阵;若二次型既不是半正定又不是半负定,就称 矩阵A为不定的 D
• 二、正定矩阵 • 定义2.1 如果二次型 • • 对于任何一组不全为零的数 恒有 • 则称 正定,且二次型矩阵A也称为正 定. • 简言之,一个对称矩阵A如果是正定的,则二次型 • 对于所有非零向量X其值总为 正.类似可以给出定义,若二次型 • 则A为半正定矩阵;若 ,则A为半负定矩 阵;若二次型既不是半正定又不是半负定,就称 矩阵A为不定的. = = = = n i n j T f x x xn ai j xi x j X AX 1 1 1 2 ( , ,, ) n x,x ,,x 1 2 f (x1 x2 x ) = X AX 0 T , ,,n ( ) 1 2 n f x ,x ,,x ( ) 1 2 n f x ,x ,,x X AX T = ( ) 0 1 2 f x x x = X AX T , ,,n X AX 0 T
矩阵A为正定的充要条件是它的行列式的顺序主子式 全部大于零,即 a1,> 由此可见,正定矩阵必然是非奇异的 例2.1判断矩阵2是否正定 解 4>0 =8>0,230=13>0 A是正定的
矩阵A为正定的充要条件是它的行列式的顺序主子式 全部大于零,即 • 由此可见,正定矩阵必然是非奇异的. • • 例2.1 判断矩阵 是否正定. • • • 解 ∵ , • • ∴ A是正定的. 11 12 1 11 12 21 22 2 11 21 22 1 2 0 0 0 n n n n nn a a a a a a a a a a a a a a , , , = 1 0 2 2 3 0 4 2 1 A 4 2 1 4 2 4 0 8 0 2 3 0 13 0 2 3 102 = = ,
§22方向导数与梯度 方向导数 所谓方向导数的概念是作为偏导数的一个推广 引入,它主要研究函数沿任一给定方向的变 定义22设R→R在点处可微,P是固定 不变的非零向量,是方向P上的单位向量,则 称极限 (=hm/x+)=/(x)(21) aP 1->0 为函数X在点处沿P方向的方向导数,式中 是它的记号
• 一、方向导数 • 所谓方向导数的概念是作为偏导数的一个推广 而引入,它主要研究函数沿任一给定方向的变 化率. • 定义2.2 设 在点 处可微,P是固定 不变的非零向量, 是方向P上的单位向量,则 称极限 • (2.1) • • • 为函数 在点 处沿P方向的方向导数,式中 是它的记号. §2.2 方向导数与梯度 1 f : R R n → X 0 e t f X t e f X P f X t ( ) ( ) lim ( ) 0 0 0 0 + − = → + f (X) X 0 P f X ( ) 0
定义23设→是连续函数, 且P≠0,若存在。0,当时都有, 则称P为在点处的下降方 向.若x+m>x,则称P为在点处的 上升方向 由以上两个定义可立刻得到如下的结论: 若 ,则从出发在附近沿P 方向是下降;若0,则从出发在附 近沿P方向是上升0
• 定义2.3 设 是连续函数, , 且 ,若存在 ,当 时都有, • 则称P为在点处的下降方 • 向.若 ,则称P为在点处的 上升方向. • 由以上两个定义可立刻得到如下的结论: • 若 ,则 从 出发在 附近沿P 方向是下降;若 ,则从出发在附 近沿P方向是上升. 1 f : R R n → X 0 P 0 0 t (0, ) ( ) ( ) 0 X 0 f X + tP f ( ) ( ) 0 X 0 f X + tP f 0 ( ) 0 P f X f (X) X 0 X 0 0 ( ) 0 P f X
梯度 定义24以的n个偏导数为分量的向量称为在X处的梯度, 记为 V(= 0(X)0(X)Of(X) 梯度也可以称为函数关于向量Y的一阶导数 以下几个特殊类型函数的梯度公式是常用的: 1)若x=(常数),则x=0,即c=0 (2)bx)=b 证设b=bb,b。X ∑b 于是Wx的第个分量是 (b X) a(bx)=b 1,2,…,n 所以vbx)=b (3)v(XX)=2X (4)若O是对称矩阵,则xOX=20Y
• 二、梯度 • 定义2.4 以 的n个偏导数为分量的向量称为 在X处的梯度, 记为 • . • • 梯度也可以称为函数 关于向量 的一阶导数. • 以下几个特殊类型函数的梯度公式是常用的: • (1)若 (常数),则 ,即 ; • (2) . • 证 设 ,则 • 于是 的第 个分量是 • . • • 所以 • (3) . • (4)若Q是对称矩阵,则 f (X) f (X) 1 2 ( ) ( ) ( ) ( ) T n f X f X f X f X x x x = , , , f (X) X f (X) = c f (X) = 0 c = 0 b X b T ( ) = 1 2 1 2 [ ] [ ] T T n n b b b b X x x x = = ,, , , , , , = = n i i i T b X b x (b X) 1 T j 1 ( ) ( ) 1 2 n T i i j i j j b X b x b j n x x = = = = , ,, , b X b T ( ) = X X X T ( ) = 2 X QX QX T ( ) = 2
三、梯度与方向导数之间的关系 定理2.1设在点处可微,则 0(X0) Vf(Xo) 其中c是P方向上的单位向量 由这个定理容易得到下列结论: 1)若(X)P,则的方向是函数在点 处的上升方向 方向导数的正负决定了函数值的升降,而升降 的快慢就由它的绝对值大小决定.绝对值越大, 升降的速度就越快,目
• 三、梯度与方向导数之间的关系 • 定理2.1 设 在点 处可微,则 • , • 其中 是 方向上的单位向量. 由这个定理容易得到下列结论: • (1)若 ,则P的方向是函数在点 处 的下降方向; • (2) 若 ,则 的方向是函数在点 处的上升方向. • 方向导数的正负决定了函数值的升降,而升降 的快慢就由它的绝对值大小决定.绝对值越大, 升降的速度就越快,即1 f : R R n → X 0 f X e P f X T ( ) ( ) 0 0 = e P f (X0 ) P 0 T f (X0 ) P 0 T X 0 P X 0