重庆工商大学数学模型与数学实验课件第11讲 无约束优化

大学数学实验ExperimentsinMathematics实验7无约束优化《数学建模与数学实验》---李焕荣实验7学习并不是人生的全部。但，既然连人生的一部分——学习也无法征服，还能做什么呢？最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题,如:优化模型和算法的重要意义结构设计资源分配生产计划运输方案解决优化问题的手段•经验积累，主观判断•作试验，比优劣•建立数学模型，求解最优策略最优化:在一定条件下，寻求使目标最大(小)的决策实验7实验7运筹学(OR:Operations/OperationalResearch)管理科学(MS:ManagementScience)决策科学(DS:DecisionScience)(最)优化理论是运筹学的重要内容无约束优化OR/MS/DS优化(Optimization),规划(Programming)线性规划非线性规划网络优化组合优化整数规划不确定规划多目标规划目标规划动态规划实验7实验7优化问题的数学模型可行域目标函数，决策变量，~~~fxnxRxxfz),(min•可行解（只满足(2)）与最优解（满足(1),(2)）•无约束优化（只有(1)）与约束优化（(1),(2)）)2(,2,1,0)(..)1()(minmixgtsxfzix•实际问题一般总有约束，何时可用无约束优化处理？实验7实验74.优化工具箱的使用2.无约束优化的基本方法：梯度法，牛顿法，拟牛顿法1.优化问题的最优解条件；算法模式无约束优化的主要内容3.非线性最小二乘法5.实际问题中的无约束优化模型实验7实验7实例1产销量安排牌号产量成本价格甲x1q1p1乙x2q2p2假设A产销平衡假设Bp随x(两种牌号)增加而减小，呈线性关系12111211121211111,0,,,aaaabxaxabp某厂生产两个牌号的同一种产品，如何确定产量使利润最大21222221222212122,0,,,aaaabxaxabp实验7实验722211121,)()(),(max21xqpxqpxxzxx目标利润最大0,,,0,,,2222221111112211crcerqcrcerqxxq随x(本牌号)增加而减小，呈负指数关系假设C实例1产销量安排实验7实验7求解无约束优化的基本思路基本思想在n中某一点，确定一个搜索方向及沿该方向的移动步长，得到使目标函数下降的新的点迭代步骤Step1初始化：初始点x0，终止准则等Step2迭代改进：方向dk，步长k)()(1kkxfxfkkkkdxx1Step3终止检验：得到近优解或k+1k转2选择dk,k使f下降更快不同算法实验7实验7搜索方向的选择1最速下降法（梯度法）下降方向最速下降方向迭代改进格式算法特点初始阶段改进较快，最优解附近改进较慢kkTkkkkdxfxfdxfxf)()()()(10)(kkTdxf)(kkxfd)(1kkkxfxx将)(1kxf在kx点作泰勒展开，只保留一阶项，有暂不考虑搜索步长，可设k=1(负梯度方向)实验7实验72Newton方法特点局部2阶收敛;需计算Hessian阵,它可能病态或不正定将f(xk+1)在xk点作泰勒展开至二阶项，用d替代dk牛顿方程牛顿方向迭代格式)()(2kkxfdxfdxfddxfxfdxfxfkTkTkkk)(21)()()()(21)())((12kkkxfxfd)())((121kkkkxfxfxx)()]([11kkkkxFxFxx比较的牛顿法解0)(xF)()(xfxF求d使f(xk+1)极小右端对d导数为00)()(2dxfxfkk实验7实验73拟Newton方法目的不计算Hessian阵，克服病态、不正定、计算复杂等缺陷，同时保持收敛较快的优点回顾解方程组F(x)=0的拟牛顿法)()()(11kkkkkkxFxFxxAA满足使kkkkAAAA计算用迭代方法11思路)()]([11kkkkxFxFxx)()(11kkkkxFAxx)(xfMinx优化问题)()(xFxf相当fGfxFxf222),()(代替阵不一定正定，构造正定相当实验7实验7搜索步长的确定线性搜索(LineSearch)确定步长方法问题给定xk和方向dk,确定步长k,使得)(minkkdxf优化算法黄金分割(0.618)法、Fibonacci法、Newton切线法、割线法、2次或3次插值法等~一维优化问题0kddf0)()(kkkTkdxfd实验7实验7非线性最小二乘(LeastSquare)拟合问题给定(ti,yi),i=1,…n,拟合一个函数y=f(t,x)，其中x为待定的参数向量,f对x非线性。优化模型)()()(minxrxrxRTx),()(xtfyxriiiTnxrxrxr))(),(()(1记误差根据目标函数是r(x)的二次函数的特点构造简单算法实验7实验7优化工具箱基本用法：x=fminbnd(@f,lb,ub)x=fminunc(@f,x0)x=fminunc(@f,x0,options,P1,P2,...)x=fminsearch(@f,x0,options,P1,P2,...)f.m~f(x)的m文件名x0~初始点;x~最优解P1,P2,…~传给fun的参数中间输入项缺省用[]占位nxRxxfMin),(模型：2min222babyax其中：例实验7实验7非线性最小二乘法)()()(minxrxrxRTubxlb),()(xtfyxriiiTnxrxrxr))(),(()(1[x,resnorm,res,exitf,out,lambda,jacob]=lsqnonlin(@fun,x0,lb,ub,options,P1,P2,…)输入的用法与fminunc类似，但注意：f.m~f(x)的m文件名:functiony=f(x,t)fun.m~r(x)的m文件名:functionr=fun(x,t,y)输出resnom=r(x)T*r(x),res=r(x)(误差向量)[x,resnorm,res,exitf,out,lambda,jacob]=lsqcurvefit(@f,x0,t,y,lb,ub,options,P1,P2,…)实验7实验7非线性最小二乘法)()()(minxrxrxRTubxlbt0.250.511.523468c19.2118.1515.3614.1012.899.327.455.243.01ktretc)(例3用下面一组数据拟合系数r,k:实验7实验7实例1产销量安排28010022.01.0122211211baaaa已知数据)3020(,02.0015.0,10030TTTcr22222212121112121111)()()(min2211xcerxaxabxcerxaxabxfxx,2,1,0,,,212211iaabxaxabpiiiiiii,2,1,0,,,icrcerqiiiixiiii22211121,)()(),(max21xqpxqpxxzxx原问题实验7实验7x=23.902562.4977y=6.4135e+003即甲产量为23.9025，乙产量为62.4977，最大利润为6413.5命令和最优解x=fminunc(@f,x0)702/502/22221111abxabx，其解为初始点的选择实例1产销量安排22.01.0122211211aaaa忽略成本及价格中的a12,a212222211111)()()(minxxabxxabxf问题简化为作为原问题的初始点实验7实验7无约束优化实验内容实验目的1．掌握Matlab优化工具包的基本用法，对不同算法进行初步分析、比较。2．练习建立和求解实际问题的无约束优化模型和非线性最小二乘拟合模型。内容8实验7实验7