运筹学第六章非线性规划.ppt

运筹学 共轭方向组中最多含n个向量，且线性无关 反之，n维空间的一组基可以构造一组A共轭方向 共轭方向组的构造 由定理知： 二次严格凸函数的无约束最优化问题 定理 6 对于问题(QP)，若 组A共轭方向，则由任意初始点 出发，依次沿 则最多经n次迭代可 得(QP)的整体最优解。 为任意一 进行精确一维搜索， 由任意初始点出发，依此沿某共轭方向组进行一维搜索求解无优化约束的方法叫共轭方向法。 利用迭代点处的负梯度向量为基础产生一组共轭方向，这种方法叫共轭梯度法。 共轭梯度法 首先，取定初始点 x0， 从x0点沿方向p0进行，精确一维搜索求得t0，则 否则，取 （1） 依此进行下去， （2） 共轭梯度法 否则，取 和沿这些方向的迭代点， （4） （3） 从而有 共轭梯度法 （5） （3）可以写成 公式（5）是由Fletcher和Reeves于1964年提出的，称为F-R公式，用公式（5）求解无约束最优化问题最优解的方法简称为F-R法。 第1步 选取初始点x0,给定终止误差 ε0； 第2步 计算 第4步 进行一维搜索，求 t k使得 第3步 F-R法步骤 第5步 计算 第6步 第7步 用F-R公式取 目标函数为单变量的非线性规划问题称为一维搜索问题 数学模型 由定义知，t*是 在[a,b]上的唯一极小点。 一、基本原理 定义1 如果存在一个 ，使得 在 区间 上严格递减，且在区间 上严格递增，则称函数 在区间[a,b]上是单谷的，区间 [a,b] 称为 的单谷区间。 使得 ，称[a, b]为搜索区间。 不断缩短搜索区间的长度，当区间足够小时,得到所求问题的近似最优解。 在区间[a,b]上任取两点t1, t2，设t1 t2， 然后， 图 让下一次迭代中区间缩短相同的比例ω，并且已有一个计算过的点在缩短后的区间内。 二、0.618法（近似黄金分割法） a b t1 t2 设新的探索区间为[a ,t2],其上的两个探索点为 0.618法（近似黄金分割法） 由以上分析得迭代公式： 0.618法（近似黄金分割法） 算法步骤： 例1：试用黄金分割法求解 解 (1) (2) (3) (4) 得最优解 ： 三、斐波那契（Fibonacci）法 定义2 设数列{Fn}满足： 数列{Fk }称为斐波那契（Fibonacci）数列 。 1 1 2 3 5 8 13 21 34 Fk 0 1 2 3 4 5 6 7 8 k 一、斐波那契（Fibonacci）法 计算n次函数值所得最大缩短率为1/Fn 要把区间缩短为原区间的δ(δ 1)倍或更小，只要n足够大时， (1) a b 算法步骤： 第1步 确定试点的个数n. 根据缩短率δ，计算Fn ，求出最小的n。 第2步 由前面公式求前两个测试点 第3步 计算 第4步 计算 迭代公式： 第5步 当 k=n-1 时， 算法步骤： 二、0.618法与Fibonacci法的关系 同理可证， 事实上， 设 由上两式得 在斐波那契法中， 0.618法（近似黄金分割法） 斐波那契（Fibonacci）法 例：试用斐波那契法求函数 要求缩短率为δ = 0.08 四、Newton法 基本思想：用 在探索点tk处的二阶Taylor展开式g(t)近似替代 其中 用g(t)的最小点作为新的探测点。因此， Newton法 第1步 第2步 转第3步； 第3步 例：用Newton法求函数的最优解 解 -0.001061 4 1.0137 0.1163 0.1169 3 1.3258 -0.5178 -0.5708 2 2 0.7854 1 1 t k k Newton法 Goldstein法 Goldstein法步骤 Armijo法 第四节 无约束最优化方法 无约束问题的最优性条件 最速下降法 共轭方向法 一、无约束问题的最优性条件 定理1 证 由Taylor展式，对任意t 0，有 定理2 若x*是(UP)的 定理3 则x*是(UP)的严格局部最优解。 局部最优解，则 一、无约束问题的最优性条件 定理4 则x*是(UP)的全局最优解。 x*是(UP)的全局最优解。 一、无约束问题的最优性条件 例1 解 目标函数的Hesse矩阵为 一、无约束问题的最优性条件 一、无约束问题