《工程优化复习课件》由会员分享，可在线阅读，更多相关《工程优化复习课件（193页珍藏版）》请在金锄头文库上搜索。
1、第1章 绪论,给一个实际问题，要求能建立数学模型,第2章 基础知识,规定：空集和单元素集也是凸集。 三角形，矩形，圆，球，凸多边形，第一象限，第一卦限等都是凸的。,等价定义（凸集）：设,凸集与性质,定义（凸集）：若集合 中任意两点的连线都属于 ，则称 为凸集。,因为两点 连线上任一点可以表示为,凸集的几何特征,凸集的代数特征,称集合 为凸集 。,恒有,凸集、凸函数与凸规划,例1: 证明集合 S = xAx = b 是凸集，其中A为 mn矩阵，b为m维向量。,凸集与性质,所以,即S是凸集。,定义：设 那么称 是 的凸组合。,性质2：S 是凸集 S 中任意有限个点的凸组合属于 S。,凸集与性质,性
2、质1：设 是凸集，则 也是凸集。,注： 不一定是凸集。,定义（凸函数）: 设集合 D Rn 为凸集，函数 f :DR, 若 x, y D, (0 , 1) ，均有 f( x+(1- ) y ) f(x)+(1- )f(y) ， 则称 f(x)为凸集 D 上的凸函数。 若进一步有上面不等式以严格不等式成立，则称 f(x)为凸集 D 上的严格凸函数。 当-f(x)为凸函数(严格凸函数)时，则称 f(x)为凹函数 (严格凹函数)。,严格凸函数,凸函数,严格凹函数,凸函数-推广到多元函数,定理(一阶条件): 设D Rn 为非空凸集，函数 f :DR 在 D 上可微，则 (1) f在D上为凸函数 任意x
3、，yD，恒有 f (y) f (x)+ f T(x)(y-x) (1) (2) f在D上为严格凸函数 任意xyD，恒有 f (y) f (x)+ f T(x)(y-x) . (2),凸函数的判定定理,定理（二阶条件）: 设D Rn 为含有内点的非空凸集，函数 f :DR在 D 上二次可微，则 a) f在D上为凸函数 xD，2f (x) 半正定； b) 若 xD，2f (x) 正定，则f在D上为严格凸函数。 回忆：一个矩阵半正定充要条件是所有主子式非负； 一个矩阵正定充要条件是所有顺序主子式非负。,凸函数的判定定理,例：设二次函数 (1)：若 为半定矩阵， 在 中为凸函数 ； (2)：若 为正定
4、矩阵， 在 中为严格凸函数。,例：判断f(x)=5x12-6x1x2+5x22在凸集D上是否是凸函数？ 的顺序主子式都是正的，所以正定，因此 f(x)在凸集D上是严格凸函数。,凸函数的判定定理,定义（凸规划）: 考虑如下非线性规划,当 都是凸函数时,称规划 为凸规划,凸规划,性质1: 设(1)为凸规划，则 i) (1)的可行集R是凸集； ii) (1)的最优解集是凸集； iii) (1)的任何局部极小点都是全局极小点。,性质2: 设(1)为凸规划，若f(x)在非空可行集R上是严格凸函 数，则(1)的全局极小点是唯一的。 证明：见书中(P24)定理 3.11.,注: 非线性规划的局部最优解不一定
5、是 全局最优解,其可行解和最优解集也 不一定是凸集,甚至不是连通集.如 果是凸规划, 就有很多好的性质。,凸规划的性质,证明：见书中(P23)定理 3.9、3.10.,n=1时，是一维无约束优化问题-第三章 一维搜索 n1时，是多维无约束优化问题-第四章 无约束优化方法,n元函数,求解无约束优化问题,“成功失败” 法（进退法）,基本思想：一种试探法：从一点出发，按一定步长搜索新点，若搜索成功，加大步长继续搜索；若搜索失败，缩小步长小步后退。,“成功失败” 法（进退法）,步骤1：选取初始点 xR , 初始步长 h 0 及精度 0， 步骤2：计算 步骤3：若 搜索成功, 转步骤4；否则，搜索失败，
6、 转步骤5。 步骤4：令 x:= x + h, 转步骤 2。 步骤5：判断 若 停止迭代， ；否则令 转步骤 2。 缺点：效率低。优点：可以求搜索区间。,注意：初始步长不能选得太小,例1：设给定初始点为 a 及初始步长为 h, 求搜索区间c, d 1) 前进运算 首先计算 f (a), f (a+h), 如果 f (a) f (a+h), 则步长加倍, 计 算f (a+3h). 若 f (a+h)= f (a+3h), 则c=a, d=a+3h; 否则将步 长再加倍，并重复上面运算. 2) 后退运算 如果 f (a) f (a+h), 则将步长缩为原来的1/4并改变符号，即 将步长改为-h/4
7、, 如果 f (a) f (a-h/4),则c=a-h /4,d=a+h; 否则 将步长加倍，并继续后退。,注意: 1. h 选择要适当.(太大含多个单峰区间,太小迭代次数多)； 2. f (x)单调时无结果, (加迭代次数限制)；,“成功失败” 法（进退法）,0.618法（黄金分割法）,0.618法是求单峰函数极值的一种试探法，有的书上也称为区间收缩法。 在搜索区间a,b上插入两个点，将区间分为三个子区间，通过比较2个插入点的函数值大小，可删去左端或者右端子区间，使搜索区间缩短。重复上述过程，使包含极小点的搜索区间不断缩短，当区间缩短到一定程度时，区间上各点都可以作为极小点的近似。 仅适用于
8、求解单峰函数,例 ：利用“成功-失败”法求函数 的搜索区间， 取初始点 ，步长,解：取初始点 ，步长,“成功失败”法-算例,得到搜索区间为,0.618法（黄金分割法）,定义(单峰函数)：设 f(x) 是定义在a, b上的函数，若 1） x* a, b 是在a, b上的最小点 ， 2） 若对任意 x1 , x2, a x1 f (x2); 2 若x1 x* ，则 f (x1) f (x2). 则称 f(x) 为a, b上的单峰函数。,定理：设 f：RR 在a, b 上是单峰函数， a x1 x2 b 。 那么 1若 f (x1) f (x2)，则 x* x1 , b ,如左下图 2若 f (x1
9、) f (x2) ，则 x* a, x2 , 如右下图,0.618法（黄金分割法）,缩短区间的第一个原则-去坏留好原则,选二点 x1 x2 , 比较 f (x1 ) 与 f (x2 ) ,可去掉a , x1 或者x2 , b.,考虑条件： 对称原则： x1 a = b- x2 （1） （使“坏”的情况去掉，区间长度不小于“好”的情况） 保持缩减比原则 t =(保留的区间长度原区间长度) 不变。 （使每次保留下来的节点， x1或 x2 ，在下一次的比较中成 为一个相应比例位置的节点 ）。 推导缩减比 t : 如图设第一次保留a, x2 (去掉x2 , b), 第二次保留的长度为, x1 , 则,
10、0.618法（黄金分割法）,整理（2） ： x2 = a + t ( b - ) x1 = a + t ( x2 -) 结合（1）式：t 2 + t 1 = 0 故 t0.618 注意: 上式有 t 2 = 1-t , 故有 x1 = a+(1-t)(b-a)=a+0.328(b-a) x2 = a+t(b-a)= a+0.618(b-a),0.618法（黄金分割法）,0.618 法-算法,0.618法-计算步骤,步骤1：选取初始区间a,b, 给定误差限 0，计算插入点 x1=a+0.328(b-a)，x2=a+0.618(b-a)； 步骤2：若|b-a|f(x2) 时, 转步骤3；当f(x1
11、) f(x2) 时, 转步骤4; 步骤3：令a:=x1, x1：=x2, 计算 x2=a+0.618(b-a), 转步骤2； 步骤4：令b:=x2, x2：=x1, 计算 x1=a+0.382(b-a), 转步骤2；,优点：不要求函数可微，且每次迭代只需计算一 个函数值， 计算量小，程序简单 缺点：收敛速度慢,例 ：试用0.618法求目标函数 的最优解。 给定初始区间0,2，收敛精度,解：第一次区间缩短计算过程：,计算两点及对应函数值：,作数值比较，可见 ,再做置换：,0.618法-算例,第二次区间缩短计算过程：,作数值比较， ,再做置换：,第三次区间缩短计算过程：,作数值比较， ,再做置换：
12、,各次的迭代结果如下：,缺点：收敛速度慢 优点：不要求函数可微，且每次迭代只需计算一个函数 值，计算量小,设 f (x)在 a ,b上可微，求函数f在a,b的极小点，就是求 函数导数为零的点。如果 ，则在(a,b) 内一定存在一点x，使得 。为求极小点，可取 ，若 , x0 为最小点, x*= x0 ; , x0 在上升段, x* x0，去掉a, x0 .,二分法-基本思想,用 或者 作新的区间a,b，继续这个过程， 逐步将区间a,b缩小， 当区间a,b的长度充分小时，可将a,b的中点取做极小 点的近似点。,二分法-基本思想,优点：计算量较少，而且总能收敛到一个局部极小点。 缺点：收敛速度较慢
13、,二分法-计算步骤,步骤1：计算 步骤2：若 ，令 ，转步骤3； 若 ，令 ，转步骤3； 若 ，停止， 。 步骤3：若 ，则 ，停止，否则，转步骤1.,例 ：试用二分法求目标函数 的最优解。 给定初始区间0,2，收敛精度,解：,在0,2内有极小点。,二分法-算例,第一次区间缩短计算过程：,因为,所以函数,第二次区间缩短计算过程：,第三次区间缩短计算过程：,各次的迭代结果如下：,迭代9次后，|b-a|=0.003910.004, 故,牛顿法（Newton）-基本思想,对 f (x) 在 x k 点二阶泰勒展开： 略去高阶项得 两边对x求导， 令 ，得到,牛顿法是一种函数逼近法，基本思想是：在极小
14、点附近用函数的二阶泰勒多项式近似代替目标函数，从而求得目标函数的极小点的近似值。,牛顿法（Newton）-基本思想,取 作为新的迭代点，继续迭代，直到达到精度，这样就得到了 函数 f 的一个驻点 。,牛顿法（Newton）-计算步骤,步骤1：给定初始点 令 。 步骤2：计算 。 步骤3：若 ，停止， ，否则转步骤4。 步骤4：计算 令 ，转步骤2。,特点：收敛速度快，局部二阶收敛。 缺点：须计算二次导数，工作量大；对初始点要求高，要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点；局部收敛。,例 ：试用Newton法求函数 的最优解。,解：,Newton法-算例,Newton法-算例,Newton
