Chapter 1_最优化的数学准备.pdf

最优化理论 方法及应用最优化理论 方法及应用 侯忠生 北京交通大学自动控制系教授 电话 51688617 办公室 9号楼西504 第一章 最优化问题的数学准备第一章 最优化问题的数学准备 1 引言 引言 在高等数学中遇到过极值问题 大体上归结为 对 求的极值问题 对 求的极值问题 具有等式约束的极值问题 Rx xf0 xf 0 0 21 xx ff 2 Rx 12 min n f x xx 12 0 1 2 jn sth x xxjl ln n时 约束方程的个数多于变量的个数 问 题变成LS问题 l DxNx xfxf x xf 严格局部极小点严格局部极小点 上述定义中如果 有 xx xfxf 全局极小点全局极小点 设 若存在点 都有 则称为在D上的全局极小点全局极小点 1 RRDf n DxDx xfxf x xf 严格全局极小点严格全局极小点 上述定义中如果 有 xx xfxf 0 t 00 xftpxf 则称p为f在点处的上升方向上升方向 0 x 若 则从点出发在附近沿p 方向是下降的下降的 0 0 p xf xf 0 x 0 x 方向导数 0 定理定理2 设在点处可微 则 其中e是p方向上的单位向量 1 RRf n 0 x exf p xf T 0 0 000 0 0 0 0 lim lim t T T t f xf xtef x pt t f xet fx e t 梯度在p方向上的投 影 就是方向导数 台劳公式 结论结论 若 则p方向是函数 在点处的下降方向下降方向 成钝角 0 0 pxf T 0 x xf 处的上升方向上升方向 成锐角 p方向单 位向量 exf p xf T 注意与区别exf T 0 越大 则升降的速度越快 p xf 0 方向导数 0 函数值 0 函数值 只有当p为负梯度时 右端才能等于梯度的 模 即取得最大值 最速下降方向最速下降方向 函数值下降最快的方向 0 pf x 00 0 xfexf p xf T 0 00 T fx f xpf xpp p 与方向成锐角 的方向统为上升方 向 与方向成锐角 的方向统为下降方 向 梯度方向的单位向量为 0 0 xf xf 0 xf 0 xf 一些常用的梯度公式 1 若常数 则 2 3 4 是正定阵 则 cxf 0 xf bxb T xxx T 2 2 T x QxQx Q 练习 1 计算在点 处的负梯度向量的值 并求出其单位向量的值 2 计算在点处的最速下降方 向 并求沿这一方向移动一个单位步长后新点的 目标函数值 2 2 2 1 25 xxxf TTT 0 88 1 1 96 1 2 2 1 2 2 2 1 xxxf T 3 0 2 2 1 1 2 2 x x xf x x xf 1 2 10 0 2 3 20 26 x x x f x x 0 0 0 1 f x e f x 10 000 312 xxe 122 0215f x 新的迭代点 解 Hessian矩阵 向量函数 向量函数在点处可微 如果的所有 分量在点都可微 向量函数的梯度 mn RRDg xg 1 xgxg m 0 x 0 xg m m m m x xg x xg x xg x xg x xg xg 001 1 0 1 02 1 01 0 xg 0 x 称为是在处的Jacobian阵 T xg 0 xg 0 x n元函数的Hessian阵定义为 xg 2 2 2 2 1 2 2 2 2 2 2 12 2 1 2 21 2 2 1 2 2 nnn n n x xf xx xf xx xf xx xf x xf xx xf xx xf xx xf x xf xf n元函数的 二阶导数 当二阶偏导数连续 且 时 则有此时Hessian 矩阵是对称的 nji xx xf xx xf ijji 2 1 22 练习 1 求目标函数 2 31322 2 1 2 3 3 2 4 1 432 xxxxxxxxxxf 3123 3 2 1 2 2 2 321 3 1 246 46 24 xxxx xxx xxxx xf 13 21 312 2 1 2 2642 4122 22212 xx xx xxxx xf 解 2 设 其中 0 tpxft 111 RRRRxf n ptpxft T 0 ptpxfpt T 0 2 则 多元函数的Taylor展开式 定理定理 设具有二阶连续偏导数 则 1 RRf n 2 1 2 TT f xpf xf xppf x p 01xxp 其中 tpxft证明 设 于是有 2 1 0 0 2 ttt pxf T 0 ppxfp T 2 代入上式 即可得到 利用 一元函数的 Taylor展开式 在t 0处展开 5 凸集与凸函数凸集与凸函数 凸集凸集 Convex set 直观上说 就是集合中的 任两点之间的连线仍然是集合中的点 严格的定义严格的定义 设集合 如果对 n RK Kxx 21 它们的任意凸组合仍然属于K 即 1 12 2 1 0 1 2 ii xxKi 则称K为凸集 运算 凸集的交集仍然为凸集 超平面超平面 Superplane 集合 nnnT RbRaRxbxax 称为中的超平面 n R 向量a称为此超平面的法方向法方向 任何的超平面将分划成两个半空间 n R n R 凸函数凸函数 设 C是凸集 对 都有 1 RRCf n Cxx 21 0 1 22112211ii xfxfxxf 则称为定义在凸集C上的凸函数凸函数 xf 若对任何的 2 1 1 0 1 2 1 i i i i 均有 22112211 xfxfxxf 则称f为定义在凸集C上的严格凸函数严格凸函数 凹函数凹函数 若是凸函数 即 f 22112211 xfxfxxf 定理定理1 设 C是凸集 若f是凸函 数 则对 水平集 1 RRCf n CxxfxD 是凸集 证明 规定空集是凸集 因为非空 则任取 则 D Dxx 21 21 xfxf 故有 1 1221122 12 fxxf xf x 凸规划凸规划 min x C f x 目标函数 是凸的 约束集合 xf 0 1 2 0 1 2 n ij Cx s xim h xjl xR 均是上的凹函数 n R是线性函数时 0 1 n i Cx s xim xR 0 1 2 n j Cx h xxRjm Cx Axb 凸函数 凸集 线性函数 凸集 凸集 注意 凸规划的性质性质 定理定理2 凸规划问题的局部极小也是全局极小 证明 反证法 假设不是全局极小 而是局部 极小 则一定存在使得 x x xfxf 2 1 xxx 1 i 2 1 xfxfxfxf 1 2 与局部极小矛盾 x 令 则有 则凸组合点 凸函数性质 f xf x 2 f为严格凸函数的充要条件是 且都有 12112 xxxfxfxf T 21 xx Cxx 21 21 xx Cxx 21 证明 1 充分性 已知f凸 证明 因为f凸 即对有 12112 xxxfxfxf T 12 0 1 1 i 22112211 xfxfxxf 21 1tt 1212211 xxtxfxxf 令 则有 从而有 1 12121 xftxtfxxtxf 亦即 121121 xfxftxfxxtxf 12 1121 xfxf t xfxxtxf 0 lim t 121 T f xxx 12112 xxxfxfxf T 要证明f是凸函数 考虑点 则有 必要性 已知对都有Cxx 21 12112 xxxfxfxf T 11 xxxfxfxf T 22 xxxfxfxf T 2211 xxx 1 2 22112211 xxxxxfxfxfxf T 2211 xxxxfxf T 2211 xxf 2 类似可以得到证明 定理定理4 f是上的二次可微函数 C非空 开凸集 则f在C上为 严格 凸函数的充要条件 为Hessian阵在C上半正定 正定 证明 必要性 Taylor公式 1 RRC n 2 xf 2 1 2 2 22 tppxfptpxftxftpxf TT 0 由pxftxftpxf T 从而正定 充分性 有Taylor公式Cxx 21 2 211212121 1 2 TT f xf xf xxxxxf xxx 0 21121 T f xf xf xxx f是凸函数 例 1 2 TT f xx Qxb xc 111 1 n nnn qq Q qq 1 n b b b 其中 Q对称正定 Q半正定 严格凸函数 凸函数 一元函数 6 极小点的判别条件 定理定理1 设具有连续的一阶偏导数 1 RRDf n 若是的局部极小点 并且是D的内点 则 x xf 0 xf 证明 是的局部极小点 故及点 x xf0 xNtex 任意的单位向量 有 xftexf t 是局部极小点 从而 0 0 0 exf T 注意 仅是必要性 而不 是充分条件 由于e的任意性 如 在处梯度向量为 但不是极小点 鞍点 2121 xxxxf T x 0 0 0 0 0 0 f 注意注意 此条件不是充分条件 定理定理2 设具有连续的二阶偏导数 是D的一个内点 若且半正定 正 定 则是的局部 严格局部 极小点 证明 Taylor公式 1 RRDf n 2 1 2 2 xxxxxfxxxxxfxfxf T 0 xf 2 xf x xf 0 x 0 0 xf f xf x 对任意的x 附近的x均成立 迭代算法迭代算法 开始选定一个初始点 置 然后按某种规则A把第k迭代点映射为新的一点 记为 这称为第K 1次迭代 这个过程进行下去就生成一个点列 规则A称 为迭代算法 k x Xx k 1 1kk xAx k x Xx 0 0 k 7 算法及有关概念 算法及有关概念 算法收敛算法收敛 若收敛于问题 minxf x ljxh mixs ts j i 2 10 2 10 k x 有约束问题 无约束问题 的最优解 则称算法A是收敛的 否则称为发散 的 步长因子步长因子 迭代算法 使得 下降方向下降方向 设第k迭代点已求得 对于可微函数 来说 满足的方向向量p 下降算法下降算法 若对于每个k都有 则称A为下降迭代算法 简称下降算法 1kk xfxf 0 pxf T k kkkk ptxx 1 1kkkkk xfptxfxf k t 称为步长因子 k x 成立的 优化算法的两个关键 下降方向的选取 步长因子的选取 k p k t 不同的方案对应 着不同的最优化 方法 设计优化算法就 是选择不同的下 降方向和步长 后面讲算法时一 定要记住某一个 算法的下降方向 和步长的确定方 法 算法的基本格式算法的基本格式 步1 选定初始点 置 步2 按某种规则确定 使得 步3 按某种规则确定 使得 步4 迭代 步5 判别是否满足终止准则 若满足 停止 否 令 转步2 重新迭代 0 x 0 k k p 0 k T k pxf kkkk xfptxf 1 xxxx kk 则称该算法具有线性收敛 或一阶收敛 级收敛级收敛 对序列来说 存在 及常数 和 N 当时 有 k x0 Nk 1 xxxx kk 21 2 称为 阶收敛 当 称为超线性收敛 称为2次收敛 当 线性 慢 超线性 中 二次 快 例1 0 0 10 qqx k k 1 0 1 0 k k x q x k qxk 2 1