第5章 无约束优化.ppt

《第5章 无约束优化.ppt》由会员分享，可在线阅读，更多相关《第5章 无约束优化.ppt（54页珍藏版）》请在优知文库上搜索。

1、1第第5章章 无约束优化无约束优化目的目的内容内容2、掌握用、掌握用MATLAB求解无约束优化问题求解无约束优化问题1、了解无约束优化基本算法、了解无约束优化基本算法2、无约束优化的基本方法、无约束优化的基本方法3、用、用MATLAB求解无约束优化问题求解无约束优化问题1、实际问题中的无约束优化模型、实际问题中的无约束优化模型2 优化问题的数学模型可行域目标函数，决策变量，fxnxRxxfz),(min 可行解可行解（只满足（只满足(2)）与）与 最优解最优解（满足（满足(1),(2)）无约束优化无约束优化（只有（只有(1)）与）与 约束优化约束优化（(1),(2)）)2(,2,1,0)(.)

2、1()(minmixgtsxfzix 实际问题一般总有约束，何时可用无约束优化处理？实际问题一般总有约束，何时可用无约束优化处理？3实例实例1 1 产销量的最佳安排产销量的最佳安排某厂生产甲、乙两个牌号的同一种产品，在产销平某厂生产甲、乙两个牌号的同一种产品，在产销平衡的情况下，如何确定各自产量使利润最大？衡的情况下，如何确定各自产量使利润最大？注：产销平衡指工厂的产量等于市场上的销量。注：产销平衡指工厂的产量等于市场上的销量。目标：利润目标：利润销量、（单件）价格销量、（单件）价格产量、（单件）成本产量、（单件）成本4规律规律 1甲价格甲价格p1随随其销量其销量x1增增长长而而降低；降低；乙

3、销量乙销量x2的增长使的增长使p1下降下降假设假设1 价格与销量价格与销量呈线性关系呈线性关系0,1211121211111aabxaxabp0,2221222212122aabxaxabp乙的价格也有同样的规律乙的价格也有同样的规律522211121,)()(),(max21xqpxqpxxzxx目目 标标利润最大利润最大0,0,2222221111112211crcerqcrcerqxx成本成本随随其产量其产量增加而增加而降低降低，且有一渐进值且有一渐进值假设假设 2 成本与产量成本与产量呈负指数关系呈负指数关系规律规律 2无约束无约束(非线性非线性)规划规划x1,x2 0?60yx点点2

4、 2x=629,y=375309.00(1.30)864.3(2.0)飞机飞机x x=?,=?,y y=?=?点点1 1x=764,y=1393161.20(0.80)点点3 3x=1571,y=25945.10(0.60)北北点点4 4x=155,y=987飞机与监控台（图中坐标和测量距离的单位是飞机与监控台（图中坐标和测量距离的单位是“千米千米”）实例实例2 飞机精确定位问题飞机精确定位问题 7）飞机位置坐标（要求计算：，距离误差为记测量距离为，角度误差为记测量线倾斜角为分别为已知数据：监控台坐标yxdiiyxiiii,.;3,.,1,1,.4;),(44xiyi原始观测角度原始观测角度(

5、或或d4）误差误差点点1 17461393161.20（2.81347弧度）弧度）0.80（0.0140弧度）弧度）点点2 262937545.10（0.78714弧度）弧度）0.60（0.0105弧度）弧度）点点3 31571259309.00（5.39307弧度）弧度）1.30（0.0227弧度）弧度）点点4 4155987d4=864.3（km）2.0（km）8242424312)()(tan dyyxxxxyyMiniiiix,y42424)()()3,2,1(tandyyxxixxyyiii不考虑误差因素不考虑误差因素超定方程组，超定方程组，非线性最小二乘！非线性最小二乘！量纲不符！

6、量纲不符！？2442424312)()(tantan ddyyxxxxyyMiniiiiix,y9考虑误差因素考虑误差因素Min x;Min y;Max x;Max y.非线性规划！非线性规划！不等式组？不等式组？)2()()()1)(3,2,1)(tan()tan(44242444dyyxxdixxyyiiiiii误差非均匀分布！误差非均匀分布！？10 以距离为约束，优化角度误差之和（或平方和）以距离为约束，优化角度误差之和（或平方和）或以角度为约束，优化距离误差或以角度为约束，优化距离误差 有人也可能会采用其他目标，如：有人也可能会采用其他目标，如：仅部分考虑误差仅部分考虑误差!角度与距离

7、的角度与距离的“地位地位”不应不同！不应不同！312tan iiiix,yxxyyMin242424)()(dyyxxMinx,y44242444)()(s.t.dyyxxd)3,2,1)(tan()tan(s.t.ixxyyiiiiii11误差一般服从什么分布？误差一般服从什么分布？正态分布！正态分布！不同的量纲如何处理？不同的量纲如何处理？无约束非线性最小二乘模型无约束非线性最小二乘模型归一化处理！归一化处理！2442424231)()(tantan),(dyyxxxxyyyxEMiniiiii随着思考的深入，模型趋于合理随着思考的深入，模型趋于合理2442424312)()(tantan

8、 ddyyxxxxyyMiniiiiix,y12 优化问题的数学模型可行域目标函数，决策变量，fxnxRxxfz),(min 可行解可行解（只满足（只满足(2)）与）与 最优解最优解（满足（满足(1),(2)）无约束优化无约束优化（只有（只有(1)）与）与 约束优化约束优化（(1),(2)）)2(,2,1,0)(.)1()(minmixgtsxfzix 实际问题一般总有约束，何时可用无约束优化处理？实际问题一般总有约束，何时可用无约束优化处理？135.1 无约束优化的基本方法无约束优化的基本方法)(minxfx给定一个函数给定一个函数 f(x),),寻找寻找 x*使得使得 f(x*)最小，即最

9、小，即nTnRxxxx),(21其中其中无约束非线性规划无约束非线性规划 多元函数无条件极值问题多元函数无条件极值问题 极值问题的解（极值点），都是极值问题的解（极值点），都是局部最优解局部最优解 全局最优解全局最优解从局部最优解的比较中得到从局部最优解的比较中得到 以后所谓最优解均指以后所谓最优解均指局部最优解局部最优解145.1.1 预备知识预备知识一、梯度（一阶导数）一、梯度（一阶导数）)(xfnTnRxxxx),(21其中其中TxxTnnffxfxfxf),(),()(11 梯度方向是使函数梯度方向是使函数f(x)在在x处增长最快的方向，处增长最快的方向，即函数变化率最大的方向；即函数

10、变化率最大的方向；梯度的模是函数梯度的模是函数f(x)沿梯度方向的变化率；沿梯度方向的变化率；满足梯度满足梯度 的点称为的点称为驻点驻点。0)(xf15二、黑赛（二、黑赛（Hessian）矩阵（二阶导数）矩阵（二阶导数）nnjixxfxf22)(当当f在点在点x处的所有二阶偏导数连续时，有处的所有二阶偏导数连续时，有),1,(22njixxfxxfijji此时，此时，是是n阶对称矩阵；阶对称矩阵；)(2xf 当当f(x)是二次函数：是二次函数：cxbAxxxfTT21)(AxfbAxxf)(,)(216三、多元函数的泰勒展开式三、多元函数的泰勒展开式1、一阶展开式、一阶展开式|)*(|*)(*

11、)(*)()(xxoxxxfxfxfT2、二阶展开式、二阶展开式)|*(|*)*)(*)(21*)(*)(*)()(22xxoxxxfxxxxxfxfxfTT近似计算近似计算17四、正定、负定、半定矩阵四、正定、负定、半定矩阵设实对称阵设实对称阵Ann，各阶主子式为，各阶主子式为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为偶数为偶数185.1.2 最优解条件最优解条件1、必要条件、必要条件设设f在点在点x处可微。若处可微

12、。若x是最优解，则是最优解，则2、充分条件、充分条件设设f在点在点x处处Hessian矩阵存在。若矩阵存在。若则则x是最优解。是最优解。注：对于有实际意义的极值问题，我们通常只用注：对于有实际意义的极值问题，我们通常只用必必要条件要条件，理论上只需求解方程组，理论上只需求解方程组 即可。即可。0)(xf正定并且)(0)(2xfxf0)(xf195.1.3 数值迭代法的基本思路数值迭代法的基本思路在在nR中某一点，确定一个中某一点，确定一个搜索方向搜索方向及沿该方向的搜索及沿该方向的搜索步长步长，得到使目标函数下降的新的点，得到使目标函数下降的新的点基本思想基本思想x*xf(x)f(x*)20迭

13、代步骤迭代步骤Step 1 初始化：初始点初始化：初始点x0，终止条件等，终止条件等Step 2 迭代改进：搜索方向迭代改进：搜索方向pk，步长，步长 tkkkkkptxx1Step 3 若若 xk+1 满足终止条件，则停止迭代；满足终止条件，则停止迭代；否则，令否则，令 k:=k+1 转转 Step2 不同的算法在于不同的算法在于pk,tk选择不同选择不同 算法的关键在于寻找搜索方向算法的关键在于寻找搜索方向p pk k基本迭代格式基本迭代格式21终止迭代条件终止迭代条件（1）根据相继两次迭代的）根据相继两次迭代的绝对误差绝对误差|xk+1-xk|e1|f(xk+1)-f(xk)|e2（2）

14、根据相继两次迭代的）根据相继两次迭代的相对误差相对误差|xk+1-xk|/|xk|e3|f(xk+1)-f(xk)|/|f(xk)|e4（3）根据目标函数）根据目标函数梯度的模梯度的模足够小足够小5|)(|exfk其中其中e1,e2,e3,e4,e5为给定足够小的正数为给定足够小的正数22线性（一维）搜索线性（一维）搜索(Line Search)确定步长方法确定步长方法问题问题已知当前点已知当前点 xk 和搜索方向和搜索方向 pk,确定步长确定步长tk,使得使得)(min)(minttpxftkkt优化优化算法算法近似黄金分割近似黄金分割(0.618)法、法、Fibonacci法、法、Newt

15、on法、法、2次或次或3次插值法次插值法等等 一维优化问题一维优化问题0)(kktkTkktdtdptpxfdtdf5.1.4 搜索步长的确定搜索步长的确定23一、一、0.618法（近似黄金分割法）法（近似黄金分割法）单谷函数与单谷区间单谷函数与单谷区间若存在一个若存在一个t*a,b，使得，使得f(t)在在 a,t*上严格递减上严格递减,且且在在 t*,b 上严格递增上严格递增f(t)a,b上的单谷函数上的单谷函数a,b f(t)的单谷区间的单谷区间a t*b24性质性质在在a,b内任取两点内任取两点t1,t2(t10收敛收敛,0达到最大迭代次数达到最大迭代次数,0不收敛不收敛output 包

16、含优化结果信息的输出结构包含优化结果信息的输出结构 iterations 实际迭代次数实际迭代次数 funcCount 实际函数调用次数实际函数调用次数 algorithm 实际采用的算法实际采用的算法38例例5-1 求求f=2e-xsinx在在0,8上的最小值与最大值上的最小值与最大值39xmin=3.9270 fmin=-0.0279xmax=0.7854 fmax=0.644840例例5-2 对边长为对边长为3m的正方形铁板，在四个角剪去相的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？槽的容积最大？解：设剪去的正方形的边长为解：设剪去的正方形的边长为x，则水槽的容积为，则水槽的容积为(3-2x)2x。建立无约束优化模型为：。建立无约束优化模型为：min y=-(3-2x)2x,x0,1.5fexm0502.m41xmax=0.5000ymax=2.0000剪掉正方形边长为剪掉正方形边长为0.5m时，水槽容积最大为时，水槽容积最大为2m342二、多元函数无约束优化问题二、多元函数无约束优化问题nxR