非线性规划(运筹学京航空航天大学,党耀国)精要.pptVIP

非线性规划 南京航空航天大学经济与管理学院 教授、博士生导师 管理科学与工程系主任 iamdangyg@163.com 收敛速度 设算法产生的点列{x(k)},收敛到解X*,且X(k)≠X*， ?k，若存在?0,及一个与迭代次数k无关的常数q0，使 1.线性收敛：当 ?＝1, q0时 称为线性收敛速度。 2.超线性收敛：当 1?2, q0，或?＝1, q＝0时，称为超线性收敛速度 3.二阶收敛：当 ?=2 ，k充分大时有 迭代中我们从一点出发沿下降可行方向找一个新的、性质有所改善的点。 △下降方向 ： △可行方向：设 ∈S，d∈Rn,d≠0,若存在 ，使 ，称d 为 点的可行方向。 同时满足上述两个性质的方向称下降可行方向。 4.1 常用的有哪些信誉好的足球投注网站算法结构 模型算法 定理：设Ф：R→R 在[α，β ]上单峰，α≤λ＜μ≤ β 。那么 1°若Ф(λ)≥ Ф(μ)，则Ф(ρ) ≥Ф(μ)， ? ρ ∈[α，λ]；如左下图 2°若Ф(λ)＜ Ф(μ)，则Ф(ρ)≥Ф(λ)， ? ρ ∈[μ ， β]；如右下图 分数法求近似极小点的步骤 由上节讨论知，用分数法以n个试点来缩短某一区间时，区间长度的第一次缩短率为Fn-1 / Fn，其后各次分别为：Fn-2 / Fn-1 ，Fn-3 / Fn-2 ，…，F1 / F2，现将以上数列分为奇数项和偶数项，可以证明，这两个数量收敛于同一个极限 具体算法如下： 三、牛顿法（Newton）（切线法） 上面我们所讨论的方法，只是对一些点的函数值的大小进行比较，而函数本身并没有得到充分利用，至于函数的一些解析性质，更是毫无利用，下面介绍的牛顿法当函数性质具有较好的解析性质时，计算效果要比分数法、0.618法更好。 现在仍设f(x)在[a,b]上仅有一个极小点的单峰函数，且具有二阶导数。 我们知道，如果函数f(x)在x*处取极小值，则必有 f′(x)=0，因此求此函数极小点，只需求出f′(x)在(a,b)内的零点即可。 对f 在x k 点展开： f(x )= f(xk )+ f (xk )(x- xk ) +f″ (xk )(x- xk )2 /2 + o (x- xk )2 取二次式（略去高阶项）： qk(x) = f(xk) + f (xk)(x-xk) + (f ″(xk)(x-xk)2)/2 用qk(x)作为f(x)的近似。 首先求qk(x)的导数，并令其等于零。 q′k(x)= f′(xk) +f″(xk)(x- xk )=0 得 xk +1=xk –f′(xk) / f″(xk) 取xk +1为新的迭代点。 以上过程即Newton法。 特点：二阶、局部收敛。 （算法框图见下页） Newton法算法框图： 例： 求 min f(x)=arctan t d t 解： f′ (x) =arctan x , f″(x)=1／(1+ x2) 迭代公式： xk +1= xk - (1+ x2) arctan xk 取x1= 1，计算结果： k xk f′ (xk) 1／f″(xk ) 1 1 0.7854 2 2 -0.5708 -0.5187 1.3258 3 0.1169 -0.1164 1.0137 4 -0.001095 -0.001095 x4≈ x* =0 取x1=2，计算结果如下： k xk