工程最优化设计 第3章优化方法的数学基础.pdf

3 1 3 1 矩阵矩阵 矩阵是研究优化方法的一个有力工具 矩阵是研究优化方法的一个有力工具 1 矩阵及其主要形式 矩阵及其主要形式 mnmm n n aaa aaa aaa A 21 22221 11211 系数矩阵 系数矩阵 mnmnmm nn nn bxaxaxa bxaxaxa bxaxaxa 2211 22222121 11212111 方程组 方程组 2 2 矩阵的形式 矩阵的形式 3 3 矩阵的运算 矩阵的运算 矩阵的加 减 乘 矩阵的转置 逆矩阵等矩阵的加 减 乘 矩阵的转置 逆矩阵等 43 21 A 0246 A 1 A 2 1 2 3 12 13 24 2 1 13 24 43 21 1 43 21 1 例 求矩阵例 求矩阵 解 因为解 因为A的行列式的行列式 所以矩阵所以矩阵A为非奇异矩阵 其逆矩阵存在为非奇异矩阵 其逆矩阵存在 的逆矩阵 的逆矩阵 3 2 向量向量 1 基本概念 基本概念 x1 o X Y X Y X Y C x2 A x1A x2A T B x1B x2B T 向量向量 A A x x X 2 1 为二维平面列向量为二维平面列向量 三维空间向量三维空间向量 n维向量维向量 超越空间向量超越空间向量 向量和点都可用矩阵表示为 向量和点都可用矩阵表示为 n x x x X 2 1 向量与分量关系向量与分量关系 单位向量 单位向量 不能单独的说单位向量 只能说某个向量 的单位向量 单位向量就是指模是一的向量 它有 方向 其方向与原来的那个向量相同 其求法是用原 来的那个向量除以它的模 向量向量X的长度称为模 记作的长度称为模 记作 n i in xxxxX 1 222 1 2 1 XX 2 2 向量的运算 向量的运算 向量的加减向量的加减 数与向量相乘数与向量相乘 向量的点积 也称内积 数积 向量的点积 也称内积 数积 n i iinn yxyxyxyxYX 1 2211 COSYXYX XYYXYX TT 或 向量的正交向量的正交 2 0cos YXYX0 YX T 若两个非零向量若两个非零向量X Y的夹角的夹角 为正交向量 为正交向量 或或 正交向量必有 正交向量必有 则称它们则称它们 K XXX 21 0jiXX ji 设设为为k个非零向量 若对于所有向量有 个非零向量 若对于所有向量有 则称该向量系为正交向量系 则称该向量系为正交向量系 3 3 向量的线性相关和线性独立 向量的线性相关和线性独立 n aaa 21 n 21 0 2211 nna aa 若有非零向量系若有非零向量系 存在一组不全为零的实数存在一组不全为零的实数 使使成立 则称该向量成立 则称该向量 系系线性相关线性相关 只有当只有当 0 21 n 则该向量系为则该向量系为线性无关 线性无关 时时 上式才能成立 则称上式才能成立 则称 如果如果n n个向量系个向量系 n aaa 21 其它其它n 1个向量的线性组合表示出来 则称这个向量的线性组合表示出来 则称这n n个向量是个向量是 线性相关的 否则就是线性无关 线性相关的 否则就是线性无关 中 至少有一个向量可以用中 至少有一个向量可以用 TTT aaa 0 1 1 1 0 1 2 1 3 321 321 2aaa 例 讨论向量系例 讨论向量系 解 很显然 由于此向量系中 第一个向量可以用解 很显然 由于此向量系中 第一个向量可以用 其他两个向量的线性组合形式表示出来 即其他两个向量的线性组合形式表示出来 即 故此向量系是线性相关的 故此向量系是线性相关的 的线性相关性 的线性相关性 2 2 一阶导数和方向导数 一阶导数和方向导数 一阶导数 一阶导数 n kkk x Xf x Xf x Xf 2 1 对于一个连续可微函数对于一个连续可微函数f x 在某一点的偏导数为 在某一点的偏导数为 xf k X它表示函数它表示函数处沿各坐标轴方向的变化率 处沿各坐标轴方向的变化率 在点在点 xf k X 处沿各坐标轴的斜率 处沿各坐标轴的斜率 即函数即函数在点在点 O x2 x1x10 x20 x0 x1 x2 s x S 1 2 方向导数 方向导数 为了描述函数沿任一为了描述函数沿任一 方向方向S的函数的变化率 的函数的变化率 引入方向导数概念 引入方向导数概念 二元函数在点二元函数在点x0 0处沿处沿s 方向的方向导数 方向的方向导数 2 2 0 2 0 12 0 2 0 11 1 2 0 2 0 12 0 21 0 1 0 0 2 0 12 0 21 0 1 0 0 lim lim x x xxfxxxfx x xxxfxxxxf xxfxxxxf S Xf 2 2 0 1 1 0 cos cos x Xf x Xf 特例 特例 1 0 0 x Xf S Xf 2 0 0 x Xf S Xf 90 0 21 0 90 21 方向导数的计算公式方向导数的计算公式 偏导数是方向导数的特例偏导数是方向导数的特例 2 2 0 1 1 0 0 cos cos x Xf x Xf S Xf 8 23 4 cos 44 cos 2 2 121 0 xxx S Xf 4 2 2 1 2 21 1 x x Xfxx x Xf 解 因为解 因为 Xf 0 X所以 所以 在点在点 处沿处沿S S方向的方向导数为 方向的方向导数为 2 2 1 4 1 xxXf Xf T X 1 1 0 4 21 例 设函数例 设函数 求求在点在点 的方向导数 向量的方向导数 向量S S的方向为的方向为 处沿处沿S S方向方向 3 3 梯度梯度 目的 判断函数在给定点目的 判断函数在给定点X 0 处沿哪个方向的变化率处沿哪个方向的变化率 最大 最大 0 1 0 2 2 1 0 co c s os f X x f X x gh 0 0 0 12 12 0 0 1 0 12 2 coscos cos cos T f Xf Xf X Sxx f Xf X g h xx 0 0 0 12 0 0 0 1 2 cos cos cos cos f Xf Xf X xx f Xf Xf s hXh 梯度的模 梯度的模 22 0 0 0 12 ff f xx XX X 梯度方向和梯度方向和s方向重合时 方向导数值最大方向重合时 方向导数值最大 0 0 01 0 2 f X f x f x f X XXgrad 称为函数在称为函数在X 0 0 处的 处的梯度梯度 方向导数方向导数 梯度梯度 O x2 x1 x0 变化率为零的方向 最速下降方向 下降方向 上升方向 最速上升方向 f x0 f x0 梯度方向是函数值变化最快的方向 梯度方向是函数值变化最快的方向 而梯度的模而梯度的模 就是函数变化率的最大值就是函数变化率的最大值 梯度方向与等值线的关系梯度方向与等值线的关系 多元函数的梯度多元函数的梯度 0 1 0 0 0 0 2 12 0 T n n f x f ffF xf xxx f x X X XX X X 0 0 0 0 1 cos cos n T i i i ff fhf sx XX XX 1 0 2 0 2 1 n i i f f x X X 0 f X 梯度梯度模 模 1 1 函数的梯度方向与函数等值面相垂直 也就是函数的梯度方向与函数等值面相垂直 也就是 和等值面上过和等值面上过x0 0的一切曲线相垂直 的一切曲线相垂直 即 函数在即 函数在 给定点的梯度方向是函数等值线或等值面在该点的给定点的梯度方向是函数等值线或等值面在该点的 法线方向法线方向 2 2 由于梯度的模因点而异 即函数在不同点处的最 由于梯度的模因点而异 即函数在不同点处的最 大变化率是不同的 因此 梯度是函数的一种大变化率是不同的 因此 梯度是函数的一种局部局部 性质 性质 函数梯度的几个特征 函数梯度的几个特征 3 梯度大小是函数在该点的方向梯度大小是函数在该点的方向 导数的最大值 梯导数的最大值 梯 度方向是函数具有最大变化率的方向 它的正向是函度方向是函数具有最大变化率的方向 它的正向是函 数值最速上升的方向 负向是最速下降方向 数值最速上升的方向 负向是最速下降方向 cos 0 0 Xf S Xf 1cos 2 与其相差与其相差的方向 必为该点的法线方向 这时的方向 必为该点的法线方向 这时 使得函数的变化率最大 此时使得函数的变化率最大 此时S的方向就是函数在该点的方向就是函数在该点 的梯度方向 的梯度方向 2 S Xf 0 当当时时 函数的变化率函数的变化率为零 此时为零 此时S 0 X的方向就是函数的等值线或等值面在的方向就是函数的等值线或等值面在 点处的切线方向点处的切线方向 4 例例 求函数求函数在点在点 3 2 T的梯度的梯度 22 121 44fxxx x 11 2 2 24 2 f xx f xf x x 1 1 1 2 242 24 x x f x x 在点在点x 1 3 2 T处的梯度为 处的梯度为 解 解 1212 12 64 42 fXfX xxxx xx 1 2 1 2 1120 0 12 1 0 2 1 644 422x x x x fX xxx PfX xxfX x 例例2 2 试求目标函数 试求目标函数在点在点 处的最速下降方向 并求沿这个方向移动一个单位长处的最速下降方向 并求沿这个方向移动一个单位长 度后新点的目标函数值 度后新点的目标函数值 2 221 2 121 43 xxxxxxf 0 0 1 T X 0 0 1 T X 则函数在则函数在处的最速下降方向是处的最速下降方向是 解解 由于由于 10 22 55 0 55 111 515 55 XXe 0 022 4 2 5 2 5 1 42 5 5 fX e fX 0 122 1122 26 34 2 5 5 X fXxx xx 新点是新点是 这个方向上的单位向量是 这个方向上的单位向量是 几种特殊类型函数求梯度的公式 几种特殊类型函数求梯度的公式 一般二次函数的梯度公式为一般二次函数的梯度公式为 BXAXf CXBXAX fxdxdcxxbxax fxdxdcxxbxxaXf TT 2 1 222 2 1 2211 2 221 2 1 2211 2 221 2 1 BXfXBXf XXfXXXf XAXfXAXXf T T T 2 2 3 4 函数的二阶导数矩阵 Hessian 海森矩阵 nnnn n n xx Xf xx Xf xx Xf xx Xf xx Xf xx Xf xx Xf xx Xf xx Xf 2 2 2 1 2 2 2 22 2 12 2 1 2 21 2 11 2 2 1 2 nji xx Xf ji nnnn n n xx Xf xx Xf xx Xf xx Xf xx Xf xx Xf xx Xf xx Xf xx Xf H 2 2 2 1 2 2 2 22 2 12 2 1 2 21 2 11 2 2 1 2 2 nji xx Xf XfH ji 二阶二阶 偏导数偏导数 Hessian 海森矩阵 222 2 1121 222 22 2122 222 2 12 n kkk kk n kkk nnn FFF xx xx x f xf xf x x xxx xf xH x f xf xf x x xx xx Xf k X 称为函数称为函数在点在点 处的处的Hessian矩阵 矩阵 220 222 022 2 Xf 2 2 2 0 2 2 2 3 2 32 2 2 2 2 31 2 21 2 2 1 2 x f xx f x f xx f xx f x f T xxxxxxxXf 2331221 22 3222 22 23 3 22xx x Xf 21 1 22xx x Xf 3222 312 2 xxx x Xf 222 1231 2233 223xxxx xx xx 例例1 求目标函数 求目标函数f X 的梯度和的梯度和Hessian矩阵矩阵 解 解 则则 又因为又因为 故故Hessian矩阵为矩阵为 3 5 多元函数的泰勒展开式多元函数的泰勒展开式 2 0 0 0 0 0 2 1 xxxfxxxfxfxf 一元函数的泰勒展开式为 一元函数的泰勒展开式为 ji n ji ji i n i i xx xx Xf x x Xf XfXf 1 0 2 1 0 0 2 1 0 X Xf多元函数多元函数 在在点的泰勒展开式为点的泰勒展开式为 n T x Xf x Xf x Xf Xf 0 2 0 1 0 0 n x x x X 2 1 2 1 0 2 0 nji xx XF H ji 0 T f XX 0 T X HX 2 0 0 0 0 0 2 1 xxxfxxxfxfxf 3 3 3 1 2 2 1 3 0 0 3 2 0 0 3 2 0 0 3 3 0 0 3 2 0 0 0 0 2 0 0 0 0 0 0 0 0 3 223 yyxf yxyxfyxyxfxyxf yyxfyxyxfxyxf yyxfxyxfyxfyxf y yxyxx yyxyxx yx 一元函数一元函数 二元函数二元函数 ji n ji ji i n i i xx xx Xf x x Xf XfXf 1 0 2 1 0 0 2 1 多元函数多元函数 XXfXXXfXfXf TT 2 1 0 2 0 0 1 3f x 1 2 11 1 2 22 0369 336 xx f xx x x 1 1 1 T x 3322 12121 339fxxxxx x 例 用泰勒展开将函数例 用泰勒展开将函数 在点在点 简化成线性函数与二次函数简化成线性函数与二次函数 1 x解 函数在点解 函数在点 的函数值 梯度和二阶导数矩阵的函数值 梯度和二阶导数矩阵 XHXXXfXfXf T T 0 0 0 2 1 1 12 1 2 660120 06600 x f x x x 11 1 22 11 11 xx X xx xx 简化的简化的线性函数线性函数 1 1 22 33 1 36 T fffX xx xxx 简化的简化的二次函数二次函数 1 1 2 1 1 2 TT fffXXfX xxxx 22 21112 366 1 6123xxxxx 4 4 函数的二次型及矩阵的正定 函数的二次型及矩阵的正定 1 1 函数的二次型 函数的二次型 cxbxbxpxnxmxf 221121 2 2 2 1 X c x x bb x x np pm xxf 2 1 21 2 1 21 2 2 2 1 X 2 1 2221 1211 2 1 2 2 b b B np pm aa aa A x x X CXBAXXf TT 2 1 X 2 22212212112 2 111 xaxxaxxaxaXf 2 1 2221 1211 21 x x aa aa xxXf AXXXf T 二元函数的二次型二元函数的二次型 的矩阵形式是 的矩阵形式是 即即 323121 2 3 2 2 2 1 48455 xxxxxxxxxXf Xf AXXXf T T xxxX 321 524 212 425 A 例 试把函数例 试把函数 化成矩阵形式 化成矩阵形式 是一个三元二次齐次函数 可以写成二次是一个三元二次齐次函数 可以写成二次 其中 其中 是一个是一个3 3阶对称方阵 阶对称方阵 解 解 型的矩阵表达式型的矩阵表达式 AXXXf T T n xxxX 21 0 Xf Xf 2 正定二次型 正定二次型 若对于任意不为零的 若对于任意不为零的 总有 总有 则称 则称 二次型 并称其相应的矩阵二次型 并称其相应的矩阵A A为正定矩阵 为正定矩阵 设有二次型设有二次型 为正定为正定 正定的判断条件正定的判断条件 0 0 0 21 22221 11211 2221 1211 11 nnnn n n aaa aaa aaa aa aa a 0 AXXXf T 若若 则称则称 Xf为半正定二次型 为半正定二次型 并称其相应的矩阵并称其相应的矩阵A A为半正定矩阵 为半正定矩阵 各阶顺序主子式均大于零各阶顺序主子式均大于零 512 152 225 A 021 52 25 05 2221 1211 11 aa aa a 088 112 152 225 333231 232221 131211 aaa aaa aaa 例 已知实对称矩阵例 已知实对称矩阵 解 此矩阵的顺序各阶主子式为 解 此矩阵的顺序各阶主子式为 所以矩阵所以矩阵A A是正定的是正定的 判断判断A A是否正定 是否正定 正定二次函数 若二次型矩阵A是正定的 则称函数f x 为正定二次函数 最优化理论中 正定二次函数有特殊作用 所有对正定二次函数适用并有效的优化算法 经证明 对一般非线性函数也是适用和有效 的 3 6 微分学中求极值微分学中求极值 主要内容 主要内容 一元函数的极值 一元函数的极值 二元函数的极值 二元函数的极值 多元函数极值问题 多元函数极值问题 无约束最优化问题 无约束最优化问题 等式约束最优化问题 等式约束最优化问题 不等式约束最优化问题 不等式约束最优化问题 解决解决 1 一元函数极值的求法与判别 一元函数极值的求法与判别 必要条件必要条件 0fx 连续可导 连续可导 求驻点求驻点 充分条件 充分条件 0 xf 0fx 若若 则 则 0fx时 函数时 函数f x 取极小值 取极小值 2 二元函数极值的求法与判别 二元函数极值的求法与判别 0 0 2 0 0 00 1 2 1 2 T T TT f Xf Xf XXXf XX f XgXX HX 二元函数的泰勒展开式为 二元函数的泰勒展开式为 f x 在在处取得极值的处取得极值的必要条件必要条件是是 0 x 0 0 12 0 T ff f xx x x 即在极值点处函数的梯度为即在极值点处函数的梯度为二二维零向量 维零向量 f x 在在处取得极值的处取得极值的充分条件充分条件是是 0 x 梯度梯度 2 Hf X 0gf X且且Hessian矩阵矩阵正定 正定 则有极小值 则有极小值 2 Hf X负定 负定 则有极大值 则有极大值 2 Hf X正定的条件 正定的条件 2 2 1 22 2 112 22 2 212 0 0 f x ff xxx ff xxx 或记为 或记为 11 0 det0 a H 函数的梯度为零的条件仅为必要的 而不是充分的 函数的梯度为零的条件仅为必要的 而不是充分的 0 x 22 42 2 1 2 1 x x x f x f f 解 解 1 求驻点 求驻点 524 21 2 2 2 121 xxxxxxf例题 求函数例题 求函数 的极值的极值 1 2 20 10 0 x x x 20 02 2 2 2 21 2 21 2 2 1 2 0 x f xx f xx f x f xH 得驻点为 得驻点为 2 判断是否为极值点 判断是否为极值点 02 0 2 1 2 x x f 04 20 02 0 xH 1 2 0 x 极值点极值点0 0 xf函数极值函数极值 作业 作业 22 121 32 44 20 f XxxxXX 12 求在和是否有极值 3 多元函数的极值 多元函数的极值 12 0 T n fff f xxx x x 即在极值点处函数的梯度为即在极值点处函数的梯度为n维零向量 维零向量 必要条件 必要条件 222 2 1121 222 22 2122 222 2 12 n n nnn FFF xx xx x FFF x xxx xF FFF x xx xx 正定或负定 x x Hessian矩阵矩阵正定正定 则 则X 为为极小点极小点 Hessian矩阵矩阵负定负定 则 则X 为为极大点极大点 充分条件 充分条件 3 6 凸函数凸函数 函数极值点是局部区域中各点相比较而言的函数极值点是局部区域中各点相比较而言的 XXXXffff 或 X Xf称称和和分别为局部极小点和局部极小值 分别为局部极小点和局部极小值 引入函数凸性的目的 引入函数凸性的目的 判断所找到的点是否是全域最小点判断所找到的点是否是全域最小点 1 凸性 凸性 函数的凸性表现为函数的凸性表现为单峰性单峰性 xf ba xf ba x 在在内只存在一个唯一内只存在一个唯一 这个极小点也是最小点 这个极小点也是最小点 设一元函数设一元函数定义在定义在区间内 若其图形为区间内 若其图形为 如图所示 则如图所示 则下凸的 下凸的 的极小点的极小点 这样的函数称为单峰函数 这样的函数称为单峰函数 或具有凸性的函数 或具有凸性的函数 o x f x a b x 2 凸集凸集 设设D为为n维欧氏空间中的一个集合维欧氏空间中的一个集合 若其中任若其中任 意两点意两点X 1 1 X 2 2 之间的联接直线都属于之间的联接直线都属于D 则称则称 集合集合D为为n维欧氏空间的一个凸集维欧氏空间的一个凸集 a 是凸集 是凸集 b 不是凸集 不是凸集 凸集用数学式表示为凸集用数学式表示为 1 2 1 XXX 式中式中为由为由0 0到到1 1 0 10 1 间的任意实数 间的任意实数 凸集的性质 凸集的性质 1 1 若若D D为凸集为凸集 是一个实数是一个实数 则集合则集合D D仍是凸集 仍是凸集 2 2 若若D和和F均为凸集均为凸集 则其和则其和 或并或并 仍是凸集 仍是凸集 3 3 任何一组凸集的积任何一组凸集的积 或交或交 仍是凸集仍是凸集 3 凸函数凸函数 设设 f X 为定义在 为定义在n维欧氏空间中的一个凸集维欧氏空间中的一个凸集D 上的函数 如果对任何实数上的函数 如果对任何实数a 0 0 a 10 则则af X 也必是在凸集也必是在凸集D D上的凸函数 上的凸函数 3 若若f1 1 X f2 2 X 为定义在凸集为定义在凸集D上的两个凸函上的两个凸函 数数 和和 为两个任意正数为两个任意正数 则函数则函数afl l X f2 2 X 仍仍 为为D上的凸函数上的凸函数 2 定义在凸集定义在凸集D D上的两个凸函数上的两个凸函数f1 X f2 X 其和其和 f X f1 X f2 X 亦必为该凸集上的一个凸函数亦必为该凸集上的一个凸函数 Xf X Xf X Xf 4 4 设 设是凸集是凸集D上的凸函数 而上的凸函数 而是是 一个极小点 则一个极小点 则在在D上的全域最小点 上的全域最小点 也必是也必是 在在D上的上的 2 1 2 1 1 T f Xf XXXf X 恒成立恒成立 2 1 XX和 Xf 5 5 设 设是凸函数是凸函数 在凸集在凸集D D中的两个最小点 中的两个最小点 连线上的所有点都是函数的最小点 连线上的所有点都是函数的最小点 则这两点则这两点 判断函数是否具有凸性的方法 判断函数是否具有凸性的方法 1 1 若函数 若函数 1 2 fD XD XD X且连续 则且连续 则 f X 是凸函数是凸函数的充要条件是 的充要条件是 判断函数是否具有凸性的方法 判断函数是否具有凸性的方法 2 2 若函数 若函数 fD XD X且连续有二阶导数 则且连续有二阶导数 则 是凸函数是凸函数的充要条件是 的充要条件是 f X 的的Hessian矩阵是半正定矩阵矩阵是半正定矩阵 若若Hessian矩阵在凸集矩阵在凸集D上处处是正定的 则为严格上处处是正定的 则为严格 凸函数 凸函数 4 凸规划凸规划 对于约束优化问题对于约束优化问题 12 min 01 2 n n j f Xf xxxXR stgXjm 式中若式中若f X 均均为凸函数 为凸函数 则称此问题为则称此问题为凸规划凸规划 j gX 凸规划的性质 凸规划的任何局部最优解就是全局最优解 30284 212 2 3 2 2 2 1 xxxxxxf X 3 2 1 a 0127 161 18 2221 1211 aa aa 0254 200 0161 018 333231 232221 131211 aaa aaa aaa 因此 函数因此 函数 Xf为凸函数 而且是严格凸函数为凸函数 而且是严格凸函数 故一定存在极小值 故一定存在极小值 解 解 作业 作业 1 判别函数 判别函数 4222 112121 225f Xxx xxxx 是不是凸函数 在是不是凸函数 在 0 1 1 X 是否为极值 是否为极值 2 判别下列函数是否为凸函数 它有无极值 若有 判别下列函数是否为凸函数 它有无极值 若有 是全局的 还是局部的 是极大还是极小 是全局的 还是局部的 是极大还是极小 22 121212 26215230f Xxxx xxx 第五节 等式约束优化问题的极值条件 约束优化 等式约束 不等式约束 求解这一问题的方法 消元法 拉格朗日乘子法 min f x st 0 k hx 1 2 kl 1 消元法 降维法 看起来简单 实际求解困难很大 一 联立看起来简单 实际求解困难很大 一 联立 求解方程困难 二 代入后 目标函数较复求解方程困难 二 代入后 目标函数较复 杂 不好处理 杂 不好处理 实用意义不大 具有启发意义 实用意义不大 具有启发意义 根