《无约束优化课件》由会员分享，可在线阅读，更多相关《无约束优化课件（55页珍藏版）》请在金锄头文库上搜索。
1、1,第5章 无约束优化,目的,内容,2、掌握用MATLAB求解无约束优化问题,1、了解无约束优化基本算法,2、无约束优化的基本方法,3、用MATLAB求解无约束优化问题,1、实际问题中的无约束优化模型,2,优化问题的数学模型,可行解（只满足(2)）与 最优解（满足(1),(2)）,无约束优化（只有(1)）与 约束优化（(1),(2)）,实际问题一般总有约束，何时可用无约束优化处理？,3,实例1 产销量的最佳安排,某厂生产甲、乙两个牌号的同一种产品，在产销平衡的情况下，如何确定各自产量使利润最大？ 注：产销平衡指工厂的产量等于市场上的销量。,目标：利润,销量、（单件）价格 产量、（单件）成本,4
2、,乙的价格也有同样的规律,5,无约束(非线性)规划,x1, x2 0 ?,6,0,y,x,点2 x=629, y=375,309.00 (1.30),864.3(2.0),飞机 x=?,y=?,点1 x=764, y=1393,161.20 (0.80),点3 x=1571, y=259,45.10 (0.60),北,点4 x=155, y=987,飞机与监控台（图中坐标和测量距离的单位是“千米”）,实例2 飞机精确定位问题,7,8,不考虑误差因素,超定方程组， 非线性最小二乘！,量纲不符！？,9,考虑误差因素,Min x; Min y; Max x; Max y.,非线性规划！,不等式组？,
3、误差非均匀分布！？,10,以距离为约束，优化角度误差之和（或平方和）或以角度为约束，优化距离误差,有人也可能会采用其他目标，如：,仅部分考虑误差! 角度与距离的 “地位”不应不同！,11,误差一般服从什么分布？,正态分布！,不同的量纲如何处理？,无约束非线性最小二乘模型,归一化处理！,随着思考的深入，模型趋于合理,12,优化问题的数学模型,可行解（只满足(2)）与 最优解（满足(1),(2)）,无约束优化（只有(1)）与 约束优化（(1),(2)）,实际问题一般总有约束，何时可用无约束优化处理？,13,5.1 无约束优化的基本方法,给定一个函数 f(x),寻找 x* 使得 f(x*)最小，即,
4、其中,无约束非线性规划,多元函数无条件极值问题极值问题的解（极值点），都是局部最优解全局最优解从局部最优解的比较中得到以后所谓最优解均指局部最优解,14,5.1.1 预备知识 一、梯度（一阶导数）,其中,梯度方向是使函数f(x)在x处增长最快的方向，即函数变化率最大的方向；梯度的模是函数f(x)沿梯度方向的变化率；满足梯度 的点称为驻点。,15,二、黑赛（Hessian）矩阵（二阶导数）,当f在点x处的所有二阶偏导数连续时，有,此时， 是n阶对称矩阵；,当f(x)是二次函数：,16,三、多元函数的泰勒展开式 1、一阶展开式,2、二阶展开式,近似计算,17,四、正定、负定、半定矩阵 设实对称阵A
5、nn，各阶主子式为Ai，i=1,2,n 正定矩阵： Ai 0, i=1,2,n 半正定矩阵：Ai 0, i=1,2,n 负定矩阵： Ai 0, i为偶数 半负定矩阵： Ai 0, i为奇数Ai 0, i为偶数,18,5.1.2 最优解条件 1、必要条件 设f在点x处可微。若x是最优解，则 2、充分条件 设f在点x处Hessian矩阵存在。若则x是最优解。 注：对于有实际意义的极值问题，我们通常只用必 要条件，理论上只需求解方程组 即可。,19,5.1.3 数值迭代法的基本思路,基本思想,x*,x,f(x)f(x*),20,迭代步骤,Step 1 初始化：初始点x0，终止条件等,Step 2 迭
6、代改进：搜索方向pk，步长 tk,Step 3 若 xk+1 满足终止条件，则停止迭代；否则，令 k:=k+1 转 Step2,不同的算法在于pk , tk选择不同算法的关键在于寻找搜索方向pk,基本迭代格式,21,终止迭代条件,（1）根据相继两次迭代的绝对误差|xk+1-xk| e1|f(xk+1)-f(xk)| e2 （2）根据相继两次迭代的相对误差|xk+1-xk| / |xk| e3|f(xk+1)-f(xk)| / |f(xk)| e4 （3）根据目标函数梯度的模足够小,其中e1, e2, e3, e4, e5为给定足够小的正数,22,线性（一维）搜索 (Line Search) 确
7、定步长方法,问题,已知当前点 xk 和搜索方向 pk, 确定步长tk, 使得,优化算法,近似黄金分割(0.618)法、Fibonacci法、 Newton法、2次或3次插值法等, 一维优化问题,5.1.4 搜索步长的确定,23,一、0.618法（近似黄金分割法）,单谷函数与单谷区间,若存在一个t*a,b，使得f(t)在 a,t* 上严格递减, 且在 t*,b 上严格递增 f(t) a,b上的单谷函数 a,b f(t)的单谷区间,a t* b,24,性质,在a,b内任取两点t1, t2 (t10收敛, 0达到最大迭代次数, 0不收敛 output 包含优化结果信息的输出结构iterations
8、实际迭代次数funcCount 实际函数调用次数algorithm 实际采用的算法,38,例5-1 求f=2e-xsinx在0,8上的最小值与最大值,39,xmin = 3.9270 fmin = -0.0279xmax = 0.7854 fmax = 0.6448,40,例5-2 对边长为3m的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？ 解：设剪去的正方形的边长为x，则水槽的容积为(3-2x)2x。建立无约束优化模型为： min y=- (3-2x)2x, x0,1.5,fexm0502.m,41,xmax =0.5000ymax =2.0000剪掉
9、正方形边长为0.5m时，水槽容积最大为2m3,42,二、多元函数无约束优化问题,fminunc, fminsearch,输入项,x=fminunc(fun,x0) x=fminsearch(fun,x0) x=fminunc(fun,x0,options) x=fminsearch(fun,x0,options),fun 同fminbnd用法 x0 初始点; x 最优解 中间输入项缺省用 占位,43,控制参数options的设置,(2) MaxIter: 允许进行迭代的最大次数,取值为正整数；,options中常用的几个参数的名称、含义、取值如下:,(1) Display: 显示水平。取值为o
10、ff时,不显示输出; 取值为iter时,显示每次迭代的信息;取值为final时,显示最终结果。默认值为final；,(3) TolFun: 函数值的控制精度。,44,控制参数options可以通过函数 optimset 创建或修改。命令的格式如下：,(1) options = optimset (optimfun) 创建一个含有所有参数名,并与优化函数optimfun有相同默认值的选项结构options。,（2）options = optimset (param1, value1,param2, value2,.) 创建一个名称为options的优化选项参数,其中指定的参数具有指定值,所有未指定的参数取默认值。,45,例：opts = optimset(Display,iter,TolFun,1e-8)该语句创建一个名称为opts的优化选项结构,其中显示参数设为iter, TolFun参数设为1e-8。,
