最优化方法概述

最优化方法概述最优化技术是一门较新的学科分支。它是在上世纪五十年代初在电子计算机广泛应用的推动下才得到迅速发展，并成为一门直到目前仍然十分活跃的新兴学科。最优化方法，顾名思义，就是从所有可能方案中选择最合理的一种以达到最优目标的方法。由于其宗旨是追求最优目标，因此它具有广泛的应用性。最优化问题的一般形式其中x=[x1，x2，…，xn]T∈min..01,2,,()01,2,ijfxsthximgxjp最优化问题的一般形式nRmin..00jifxstgxhx目标函数不等式约束等式约束•x称为决策变量，•满足所有约束的变量称为可行解或可行点，可行点的集合称为可行域。•问题的求解是指在可行域中找一点x*，使得目标函数在该点取极小值，这样的点称为问题的最优点，也称为最小点，而相应的目标函数值f(x*)称为最优值，(x*,f(x*))称为最优解，习惯上x*称为最优解。最优化问题常用的概念定义1：整体（全局）最优解：若，对于一切，恒有则称是最优化问题的整体最优解。定义2：局部最优解：若，存在某邻域，使得对于一切，恒有则称是最优化问题的局部最优解。其中严格最优解：当，有则称为问题的严格最优解。*xDxD*fxfx*x*xD*()Nx*()xNxD*fxfx*x**(){|,0}Nxxxx*xx*fxfx*xf(X)局部最优解整体最优解最优化问题分类非线性规划线性规划约束问题维问题一维问题非线性问题线性问题无约束问题最优化问题n最优化方法的基本方法——迭代法为什么求最优解要用迭代法？下面举例说明。例则最优解必定是方程的解，但x无法显化。而由于可知的解存在22)(minxexfx022)(2xexfx)(,)(,xfxxfx0)(xf最优化方法的基本方法——迭代法()(1)()()1{}*lim*0*kkkkkxAxkkxxxxx从一点出发，按照某种规则，求出后继点，用代替，重复以上过程，得到一个解的序列，若该序列有极限点，即则称它收敛于。下降：在每次迭代中，后继点处的函数值要有所减少。迭代：最优化方法的基本方法——迭代法。，置选定某一初始点0.1)0(kx。确定搜索方向)(.2kd。迭代点，以产生下一个求步长出发，沿方向从)1()()(.3kkkkxdx。，返回止迭代；否则，令小点，若是，则停是否为极小点或近似极检查21:.4)1(kkxk迭代算法的步骤：线性规划是求线性目标函数在线性约束条件下的最大值或最小值的问题。线性规划问题的数学模型是将实际问题转化为一组线性不等式或等式约束下求线性目标函数的最小(大)值问题,它都可以化为如下标准(矩阵)形式：.0,..minxbAxcxtsfnxxx21xmbbb21bA=(aij)m×nc=(c1,c2,…,cn)x≥0指x中的每一个分量xj≥0线性规划单纯形法•单纯形方法基本思路：•从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。•如可能，从可行域中求出具有更优目标函数值的另一个基础可行解（另一个顶点），以改进初始解。•继续寻找更优的基础可行解，进一步改进目标函数值。当某一个基础可行解不能再改善时，该解就是最优解。数学模型maxS=50x1+30x2s.t.4x1+3x2≤1202x1+x2≤50x1,x2≥0x2504030201010203040x1可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）数学模型的标准形:maxS=50x1+30x2s.t.4x1+3x2+x3=1202x1+x2+x4=50x1,x2,x3,x4≥0基础可行解X(1)=(0,0,120,50)T,目标函数值S=0C503000CBXBX1X2X3X4bbΘ0X343101200X4210150σ5030000x2504030201010203040x1可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）X(1)=(0,0,120,50)T相当于O(0,0)X1进基变量，X4出基变量，主元（2）C503000CBXBX1X2X3X4bbΘ0X34310120120/40X4(2)1015050/2σ5030000第二行除以2C503000CBXBX1X2X3X4bbΘ0X343101200X411/201/225σ第一行加上第二行的负4倍C503000CBXBX1X2X3X4bbΘ0X3011-22050X111/201/225σ1250新的基础可行解X(2)=(25,0,20,0)t,目标函数值S=1250计算检验数C503000CBXBX1X2X3X4bbΘ0X3011-22050X111/201/225σ050-251250x2504030201010203040x1可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）X(2)=(25,0,20,0)t相当于Q1(25,0)X2进基变量，X3出基变量，主元（1）C503000CBXBX1X2X3X4bbΘ0X30（1）1-2202050X111/201/22525*2σ050-251250第二行加上第一行的负1/2倍C503000CBXBX1X2X3X4bbΘ30X20（1）1-22050X110-1/23/215σ1350基础可行解X(3)=(15,20,0,0)T,也是最优解,其最优值S=1350x2504030201010203040x1可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）X(3)=(15,20,0,0)T相当于Q2(15,20)x2504030201010203040x1可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）x2504030201010203040x1可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）X(1)=(0,0,120,50)T相当于O(0,0)x2504030201010203040x1可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）X(1)=(0,0,120,50)T相当于O(0,0)x2504030201010203040x1可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）X(2)=(25,0,20,0)T相当于Q1(25,0)x2504030201010203040x1可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）X(2)=(25,0,20,0)T相当于Q1(25,0)x2504030201010203040x1可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）X(3)=(15,20,0,0)T相当于Q2(15,20)用Matlab求解线性规划•模型•••••用命令•[x,fval]=linprog(f,A,b,A1,b1,lb,ub)•minf(x)=-5x1-4x2-6x3s.t.x1-x2+x3≦203x1+2x2+4x3≦423x1+2x2≦300≦x1,0≦x2,0≦x3用Matlab求解线性规划用Matlab求解线性规划•解问题•把问题极小化并将约束标准化用Matlab求解线性规划•键入c=[-2,-3,5];a=[-2,5,-1];•b=-10;a1=[1,1,1];b1=7;LB=[0,0,0];•[x,y]=linprog(c,a,b,a1,b1,LB)•得当X=(6.4286,0.5714,0.0000)时,•z=-14.5714最大.用Matlab求解线性规划exitflag算法终止原因1梯度小于指定值2x的变化小于指定值3目标函数的变化小于指定值0迭代数超过options.MaxIter或函数的计算数超过options.FunEvals-1算法被输出函数终止-2直线搜索沿着目前的搜索方向不能找到可以接受的点output包含优化信息的结构iterations迭代数funcCount函数计算数lgorithm使用的算法cgiterationsPCG迭代数(large-scalealgorithmonly)stepsize最终步长(medium-scalealgorithmonly)无约束非线性规划min{f(x)|x∈En},这里x=(x1,x2,…,xn)T.一元函数无约束优化问题多元函数无约束优化问题•精确线搜索试探法:黄金分割法、Fibonacci法、二分法函数逼近法:Newton法、割线法、抛物线法、三次插值法•非精确线搜索Armijo步长规则、Goldstein步长规则、Wolfe步长规则一元函数无约束优化问题(一维搜索)分割法原理：设函数f(x)在闭区间[a,b]上是下单峰函数,即在(a,b)内f(x)由唯一的极小点x*,在x*的左边f(x)严格单调下降,在x*的右边f(x)严格单调上升.那么对于(a,b)内任意两点x1＜x2,如果f(x1)＜f(x2),则x*∈[a,x2]；否则x*∈[x1,b].如右图我们先介绍求解一元函数y=f(x)极小值的数值迭代算法：一维搜索算法中的黄金分割法(0.618法).一元函数无约束优化问题①取x2=a+0.618(b-a),f2=f(x2),转向②.②取x1=a+0.382(b-a),f1=f(x1),转向③.③若|b–a|＜,则取x*=(a+b)/2,停.否则转向④.④若f1＜f2,则取b=x2,x2=x1,f2=f1,转向②;若f1=f2,则取a=x1,b=x2,转向①;若f1＞f2,则取a=x1,x1=x2,f1=f2,转向⑤.⑤取x2=a+0.618(b-a),f2=f(x2),转向③.给定下单峰区间[a,b]及控制误差＞0,黄金分割法(0.618法)的迭代步骤：函数逼近法：牛顿法基本思想：在极小点附近用二阶Taylor多项式近似。)(minxf2)()()()()())((21))(()()(kkkkkxxxfxxxfxfx令()()()()()()()0kkkxfxfxxx又令)()()()()()()1()1(kkkkkxfxfxxxx，则的驻点，记作得算法步骤:(0)1.,0,0xk给定初始点允许误差置。.3;,|)(|.2)()(否则转则停止计算，得点若kkxxf。，返回置计算点21,)(.3)()()()1()1(kkxfxfxxxkkkkk缺点：初始点选择十分重要。如果初始点靠近极小点，则可能很快收敛；如果初始点远离极小点，迭代产生的点列可能不收敛于极小点。例：.01.0),21(5minxxex2)0(x取初始点解：00002.06096.13012.5012.0612.12349.5349.0677.11388.7388.220)()()(kkkxfxfxk为近似解。6096.1x用Matlab解无约束优化问题1.一元函数无约束优化问题:minf（x）21xxx其中（3）、（4）、（5）的等式右边可选用（1）或（2）的等式右边。函数fminbnd的算法基于黄金分割法，它要求目标函数必须是连续函数，并可能只给出局部最优解。常用格式如下：（1）x=fminbnd(fun,x1,x2)（2）x=fminbnd(fun,x1,x2，options)（3）[x，fval]=fminbnd（...）（4）[x，fval，exitflag]=fminbnd（...）（5）[x，fval，exitflag，output]=fminbnd（...）运行结果：xmin=3.9270ymin=-0.0279xmax=0.7854