现代设计法概论-6.ppt

Contents 无约束优化:多变量方法 1st order methods: CG 2nd order methods Quasi-Newton Methods 有约束优化: Optimality Criteria 无约束优化 单变量方法 多变量方法 0th order 1st order 2nd order Newton’s 法 概念: 构建局部二次近似 最小化近似 重复 Newton’s method (2) 步长: Newton’s 法 (3) 为避免发散: 线性有哪些信誉好的足球投注网站.有哪些信誉好的足球投注网站方向: Levenberg-Marquardt 方法 Newton 法中的问题: 当远离最优值时，收敛性不好或发散 当 H 单值 / 非正定，该怎么办? Newton 法 总结 二阶方法: Newton’s method 结论: 最有效: 二次项问题1步解决 不稳健! 改善稳健性: Levenberg-Marquardt (混合 Steepest decent / Newton) Trust region approaches 拟-Newton 法 Newton 法的不足: 需要计算 H (常常不实际) H 的存储, 系统方程的求解 拟-Newton 原理 梯度的一阶 Taylor近似: Update functions: rank 1 标注: Update functions: rank 2 Davidson-Fletcher-Powell (DFP): BFGS example 二次函数的最小化: BFGS example (2) BFGS example (3) Check: Comparison on Banana function 无约束优化的多变量算法总结 理论上讲 Newton最优, 但: 计算昂贵，且存储(Hessian)矩阵 不稳健 如果梯度可行，Quasi-Newton (BFGS) 法最好 0-order 方法 稳健并简单, 但当 n 10 时不高效 Contents 无约束优化:多变量方法 1st order methods: CG 2nd order methods Quasi-Newton Methods 有约束优化: 最优性判别 优化条件总结 无约束问题局部最小的条件: 边界优化 主题:  约束问题的优化条件 可行性扰动 / 方向 考虑可行空间 X 边界优化 边界优化的必要条件: f 在 任何可行方向上，不再会减少了 等式约束问题 首先, 只考虑等式约束时: 最简单的事例! 起作用不等式约束可处理成等式约束 起作用不等式约束可以识别出来，如：单调分析 等式约束问题 (2) Each (functionally independent) equality constraint reduces the dimension of the problem: 优化条件 最简单方法: 利用等式约束消去变量 结果: 维数n – m 的无约束问题 应用无约束优化条件 Note, multidimensional version of the method discussed for single variable. Potentially dense system of equations. If sparse, fast techniques are available. Also obtaining H itself can be rather costly. Quadratic convergence: error reduces quadratically. Blend between Newton and Steepest Descent 机械优化设计 Engineering Optimization Yanhua_shen@ces.ustb.edu.cn 局部近似: 2nd order Taylor series: 近似所需的一阶充分条件: Evaluated at x 更新: 注: 1步就能找到二次函数的最小值! 步长包括 求解等式的线性系统 如果 H 非正定, 可能出现发散 更新: Newton’s method 是二次收敛(best!) ，接近最优: Error Iteration 弥补: 修正 H:利用 b 使 H 正定 Levenberg-Marquardt 法: 从大的 bk,开始，并逐渐减小 : b large: Steepest descent b small: Newton 替代: 拟-Newton 法: 基于近似的 H (or H-1) 仅利用一阶微分信息 Newton step: 拟-Newton step: Update (or ) 更新公式: Rank one update