Differences

This shows you the differences between two versions of the page.

--- keynote:2011-lesson15 [2011/04/25 14:23]
hongxin created
+++ keynote:2011-lesson15 [2023/08/19 21:02] (current)
@@ Line 1: / Line 1: @@
+====== 第十五课 ======
+二、非线性最优化
+张老师语录：科学发展观 拥抱技术 拥抱数学 苹果产品为什么那么受欢迎 细节创新 人们喜欢苹果产品
+和追星一样狂热 用的舒服舒心  用心！
+非线性的数据无处不在 举例 GFW 网络流量分析
+学术刊物被引用的关系 可视化
+最优化的问题的一般形式为
+Min f(x)
+s.t. x∈X
+f(x)为目标函数，X⊂En为可行域。
+如X=En，则以上最优化问题为无约束最优化问题。
+约束最优化问题通常写为
+Min f(x)
+s.t. ci(x)=0, i∈E,
+ci(x)≥0, i∈I,
+其中E, I分别为等式约束的指标集和不等式约束的指标集，ci(x)是约束函数。
+. 无约束非线性最优条件
+.1 局部极小 若存在δ>0，使得对所有满足 || x-x* ||<δ的x, 都有
+f(x)>f(x*),
+则称x * 为f的局部极小点。（抽象-具体）
+如所有满足 || x-x*||<δ的x，都有f(x)>f( x*),
+则称x * 为f的严格局部极小点。
+全局极小 若存在δ>0，使得对所有x, 都有f ( x)>=f ( x*),
+则称x * 为f的总体极小点。
+如所有x，都有f ( x) > f ( x*),
+则称x * 为f的严格总体极小点。  注意 概念：正定矩阵 凸函数
+min f(x) ,x∈Rn
+设g(x)= ∇f(x),G(x)=Δf(x)分别为f的一阶和二阶导数。
+定理（一阶必要条件）：设f：D⊂Rn→R1在开集D上连续可微，若x*∈D是局部最小点，则 g(x*)›=0
+定理（二阶必要条件）：设f：D⊂Rn→R1在开集D上二阶连续可微，若x*∈D是局部最小点，则 g(x*)=0，G(x*)›=0
+.2 最优化方法的结构迭代优化方法的基本思想：
+迭代的优化思想
+好的迭代算法的典型特征
+收敛速度
+终止条件
+.给定一个初始点x0,
+.按照某一迭代规则产生一个点列{xk}
+■当{xk}是有穷点列时，其最后一个点是最优化模型问题的最优解。
+■当{xk}是无穷点列时，其极限点为最优解。
+一个好的算法应具备的典型特征为：
+.迭代点{xk}能稳定地接近局部极小点x*的邻域，然后迅速收敛于x*
+.当给定的某种收敛准则满足时，迭代即终止。
+优化方法的结构给定初始点x0
+. 确定搜索方向dk，即依照一定规则构造 f 在xk的下降方向为搜索方向
+. 确定步长因子αk，使目标函数值有某种意义下降
+. 令xk+1=xk+αkdk,
+          a) 若x<sub>k+1</sub>满足某种终止条件，则停止迭代，得到近似最优解，\\
+          b) 否则，重复以上步骤\\
+收敛速度
+收敛速度也是衡量最优化方法有效性的重要方面。
+ 若存在实数 α及一个与迭代次数k无关的常数q>0，使得
+则称算法产生的迭代点列{xk} 具有Q-α 阶收敛速度。特别地
+（a）当 α＝1，q>0 时，{xk} 具有Q- 线性收敛速度。
+（b）当1<α<2，q>0 时 或者 α＝1,q=0 ， {xk}具有Q- 超线性收敛速度。
+（c）当 α＝2 ，q>0 时，{xk} 具有Q - 二阶收敛速度。
+收敛速度一般认为，具有超线性和二阶收敛速度的方法是比较快速的。
+但对于任何一个算法，收敛线和收敛速度的理论结果并不保证算法在实际执行时一定有好的实际计算结果。
+.3 一维搜索
+进退法  黄金分割法 斐波那契法
+.3.2插值法
+牛顿法
+二点二次、二点三次插值法
+三点二此法
+.3.3不精确的一维搜索法
+Armijo-Goldstein准则
+Wolfe-Powell准则
+EDITED BY 丁治宇 11121007 2011/07/11

Applied Mathematics for Computer Science

User Tools

Site Tools

Differences

Page Tools