第4讲 无约束优化

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

2、0)(. .)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

4、0 ?60yx点点2 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;)

5、,(44xiyi原始观测角度原始观测角度 (或或d4）误差误差点点120（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随着

8、思考的深入，模型趋于合理随着思考的深入，模型趋于合理2442424312)()(tantan ddyyxxxxyyMiniiiiix,y12 优化问题的数学模型可行域目标函数，决策变量，fxnxRxxfz),(min 可行解可行解（只满足（只满足(2)）与）与 最优解最优解（满足（满足(1),(2)） 无约束优化无约束优化（只有（只有(1)）与）与 约束优化约束优化（(1),(2)）)2(, 2 , 1, 0)(. .)1 ()(minmixgtsxfzix 实际问题一般总有约束，何时可用无约束优化处理？实际问题一般总有约束，何时可用无约束优化处理？135.1 无约束优化的基本方法无约束优化的

9、基本方法)(minxfx给定一个函数给定一个函数 f( (x),),寻找寻找 x* 使得使得 f( (x*)最小，即最小，即nTnRxxxx),(21其中其中无约束非线性规划无约束非线性规划 多元函数无条件极值问题多元函数无条件极值问题 极值问题的解（极值点），都是极值问题的解（极值点），都是局部最优解局部最优解 全局最优解全局最优解从局部最优解的比较中得到从局部最优解的比较中得到 以后所谓最优解均指以后所谓最优解均指局部最优解局部最优解145.1.1 预备知识预备知识一、梯度（一阶导数）一、梯度（一阶导数）)(xfnTnRxxxx),(21其中其中TxxTnnffxfxfxf),(),()(

10、11 梯度方向是使函数梯度方向是使函数f(x)在在x处增长最快的方向，处增长最快的方向，即函数变化率最大的方向；即函数变化率最大的方向； 梯度的模是函数梯度的模是函数f(x)沿梯度方向的变化率；沿梯度方向的变化率； 满足梯度满足梯度 的点称为的点称为驻点驻点。0)(xf15二、黑赛（二、黑赛（Hessian）矩阵（二阶导数）矩阵（二阶导数）nnjixxfxf22)( 当当f在点在点x处的所有二阶偏导数连续时，有处的所有二阶偏导数连续时，有), 1,(22njixxfxxfijji此时，此时， 是是n阶对称矩阵；阶对称矩阵；)(2xf 当当f(x)是二次函数：是二次函数：cxbAxxxfTT21

11、)(AxfbAxxf)(,)(216三、多元函数的泰勒展开式三、多元函数的泰勒展开式1、一阶展开式、一阶展开式|)*(|*)(*)(*)()(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为偶数为偶数半负定矩阵：半负定矩阵：

12、Ai 0, i为奇数为奇数 Ai 0, i为偶数为偶数185.1.2 最优解条件最优解条件1、必要条件、必要条件设设f在点在点x处可微。若处可微。若x是最优解，则是最优解，则2、充分条件、充分条件设设f在点在点x处处Hessian矩阵存在。若矩阵存在。若则则x是最优解。是最优解。注：对于有实际意义的极值问题，我们通常只用注：对于有实际意义的极值问题，我们通常只用必必要条件要条件，理论上只需求解方程组，理论上只需求解方程组 即可。即可。0)(xf正定并且)(0)(2xfxf0)(xf195.1.3 数值迭代法的基本思路数值迭代法的基本思路在在nR中某一点，确定一个中某一点，确定一个搜索方向搜索方

13、向及沿该方向的搜索及沿该方向的搜索步长步长，得到使目标函数下降的新的点，得到使目标函数下降的新的点基本思想基本思想x*xf(x)f(x*)20迭代步骤迭代步骤Step 1 初始化：初始点初始化：初始点x0，终止条件等，终止条件等Step 2 迭代改进：搜索方向迭代改进：搜索方向pk，步长，步长 tkkkkkptxx1Step 3 若若 xk+1 满足终止条件，则停止迭代；满足终止条件，则停止迭代； 否则，令否则，令 k:=k+1 转转 Step2 不同的算法在于不同的算法在于pk , tk选择不同选择不同 算法的关键在于寻找搜索方向算法的关键在于寻找搜索方向p pk k基本迭代格式基本迭代格式

14、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）根据目标函数）根据目标函数梯度的模梯度的模足够小足够小5| )(|exfk其中其中e1, e2, e3, e4, e5为给定足够小的正数为给定足够小的正数22线性（一维）搜索线性（一维）搜索 (Line Search) 确定步长方法确定步长方法问题问题已知当前点已知当前点 xk 和搜

15、索方向和搜索方向 pk, 确定步长确定步长tk, 使得使得)(min)(minttpxftkkt优化优化算法算法近似黄金分割近似黄金分割(0.618)法、法、Fibonacci法、法、Newton法、法、2次或次或3次插值法次插值法等等 一维优化问题一维优化问题0)(kktkTkktdtdptpxfdtdf5.1.4 搜索步长的确定搜索步长的确定23一、一、0.618法（近似黄金分割法）法（近似黄金分割法）单谷函数与单谷区间单谷函数与单谷区间若存在一个若存在一个t*a,b，使得，使得f(t)在在 a,t* 上严格递减上严格递减, 且且在在 t*,b 上严格递增上严格递增f(t) a,b上的单谷

16、函数上的单谷函数a,b f(t)的单谷区间的单谷区间a t* b24性质性质在在a,b内任取两点内任取两点t1, t2 (t10收敛收敛, 0达到最大迭代次数达到最大迭代次数, 0不收敛不收敛output 包含优化结果信息的输出结构包含优化结果信息的输出结构 iterations 实际迭代次数实际迭代次数 funcCount 实际函数调用次数实际函数调用次数 algorithm 实际采用的算法实际采用的算法38例例5-1 求求f=2e-xsinx在在0,8上的最小值与最大值上的最小值与最大值39xmin = 3.9270 fmin = -0.0279xmax = 0.7854 fmax = 0

17、.644840例例5-2 对边长为对边长为3m的正方形铁板，在四个角剪去相的正方形铁板，在四个角剪去相等的正方形以制成方形无盖水槽，问如何剪法使水等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？槽的容积最大？解：设剪去的正方形的边长为解：设剪去的正方形的边长为x，则水槽的容积为，则水槽的容积为(3-2x)2x。建立无约束优化模型为：。建立无约束优化模型为：min y=- (3-2x)2x, x0,1.5fexm0502.m41xmax = 0.5000ymax = 2.0000剪掉正方形边长为剪掉正方形边长为0.5m时，水槽容积最大为时，水槽容积最大为2m342二、多元函数无约束优化

18、问题二、多元函数无约束优化问题nxRxxf),(min模型：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中常用的几个参数的名称、含义

19、、取值如下中常用的几个参数的名称、含义、取值如下: :(1) Display: : 显示水平。取值为显示水平。取值为off时时, ,不显不显示输出示输出; ; 取值为取值为iter时时, ,显示每次迭代的信息显示每次迭代的信息; ;取值为取值为final时时, ,显示最终结果。默认值显示最终结果。默认值为为final；(3) TolFun: : 函数值的控制精度。函数值的控制精度。44控制参数控制参数options可以通过函数可以通过函数 optimset 创建或创建或修改。命令的格式如下：修改。命令的格式如下：(1) options = optimset (optimfun)创建一个含有所有

20、参数名创建一个含有所有参数名, ,并与优化函数并与优化函数optimfun有有相同默认值的选项结构相同默认值的选项结构options。（2）options = optimset (param1, value1, param2, value2,.)创建一个名称为创建一个名称为options的优化选项参数的优化选项参数, ,其中指定的其中指定的参数具有指定值参数具有指定值, ,所有未指定的参数取默认值。所有未指定的参数取默认值。45例：例：opts = optimset(Display,iter,TolFun,1e-8) 该语句创建一个名称为该语句创建一个名称为opts的优化选项结构的优化选项结构

21、, ,其中显其中显示参数设为示参数设为iter, TolFun参数设为参数设为1e-8。(3)options=optimset (oldops, param1, value1, param2, value2,.)创建名称为创建名称为oldops的参数选项的拷贝的参数选项的拷贝, ,用指定的参数值用指定的参数值修改修改oldops中相应的参数。中相应的参数。46 使用使用fminunc和和fminsearch可能会得到局部最优解可能会得到局部最优解 fminsearch是用单纯形法寻优；是用单纯形法寻优； fminunc的算法见以下几点说明：的算法见以下几点说明：（1）fminunc 提供了大型

22、和中型优化算法，由提供了大型和中型优化算法，由options中的参数中的参数 LargeScale 控制：控制： LargeScale=on（默认值）默认值）, ,使用大型算法使用大型算法 LargeScale=off , ,使用中型算法使用中型算法算法选择：算法选择：optimset 中参数控制中参数控制47（2）fminunc 为中型优化算法的为中型优化算法的搜索方向搜索方向提供了以下提供了以下算法，由算法，由options中的参数中的参数HessUpdate控制：控制： HessUpdate=bfgs( (默认值默认值),),拟牛顿法的拟牛顿法的BFGS公式公式 HessUpdate=d

23、fp, 拟牛顿法的拟牛顿法的DFP公式公式 HessUpdate=steepdesc, 最速下降法最速下降法（3）fminunc为中型优化算法的为中型优化算法的步长一维搜索步长一维搜索提供了提供了两种算法，由两种算法，由options中参数中参数LineSearchType控制：控制： LineSearchType = quadcubic(默认值默认值) ) 混合的混合的2、3多项式插值；多项式插值； LineSearchType = cubicpoly，3次多项式插值次多项式插值48输输出出项项 x,fval= fminunc() x,fval= fminsearch() x,fval,ex

24、itflag,output = fminunc() x,fval,exitflag,output = fminsearch()Output iterations 实际迭代次数实际迭代次数 funcCount 实际函数调用次数实际函数调用次数 algorithm 实际采用的算法实际采用的算法 cgiterations 实际实际PCG迭代次数（大型优化算法）迭代次数（大型优化算法） stepsize 最后迭代步长（中型优化模算法）最后迭代步长（中型优化模算法） firstorderopt 一阶最优条件（梯度的模）一阶最优条件（梯度的模） message 收敛信息等收敛信息等49例例5-3 min f(x)=(4x12+2x22+4x1x2+2x2+1)*exp(x1)fexm0503.m50 x = 0.5000 -1.0000f = 1.3028e-010例例5-4 Rosenbrock函数（香蕉函数）函数（香蕉函数）f(x1,x2) = 100(x2-x12)2 + (1-x1)2的精确极小点为的精确极小点为x*=(1,1)，极小值为，极小值为f*=0。试用不同算法（搜索方向和搜索步长）求数值最优试用不同算法（搜索方向和搜索步长）求数值最优解。初值选