Matlab的优化工具箱.doc

1、9.1 概 述利用 Matlab 的优化工具箱，可以求解线性规划、非线性规划和多目标规划问题。具体而言，包括线性、非线性最小化，最大最小化，二次规划，半无限问题，线性、非线性方程（组）的求解，线性、非线性的最小二乘问题。另外，该工具箱还提供了线性、非线性最小化，方程求解，曲线拟合，二次规划等问题中大型课题的求解方法，为优化方法在工程中的实际应用提供了更方便快捷的途径。9.1.1 优化工具箱中的函数优化工具箱中的函数包括下面几类：1最小化函数表 9-1 最小化函数表函 数 描 述fgoalattain 多目标达到问题fminbnd 有边界的标量非线性最小化fmincon 有约束的非线性最小化fm

2、inimax 最大最小化fminsearch, fminunc无约束非线性最小化fseminf 半无限问题linprog 线性课题quadprog 二次课题2方程求解函数表 9-2 方程求解函数表函 数 描 述 线性方程求解fsolve 非线性方程求解fzero 标量非线性方程求解3最小二乘（曲线拟合）函数表 9-3 最小二乘函数表函 数 描 述 线性最小二乘lsqlin 有约束线性最小二乘lsqcurvefit 非线性曲线拟合lsqnonlin 非线性最小二乘lsqnonneg 非负线性最小二乘4实用函数表 9-4 实用函数表函 数 描 述optimset 设置参数optimget 5大型方

3、法的演示函数表 9-5 大型方法的演示函数表函 数 描 述circustent 马戏团帐篷问题二次课题molecule 用无约束非线性最小化进行分子组成求解optdeblur 用有边界线性最小二乘法进行图形处理6中型方法的演示函数表 9-6 中型方法的演示函数表函 数 描 述bandemo 香蕉函数的最小化dfildemo 过滤器设计的有限精度goaldemo 目标达到举例optdemo 演示过程菜单tutdemo 教程演示9.1.3 参数设置利用 optimset 函数，可以创建和编辑参数结构；利用 optimget 函数，可以获得 options 优化参数。 optimget 函数功能：获

4、得 options 优化参数。语法：val = optimget(options,param)val = optimget(options,param,default)描述：val = optimget(options,param) 返回优化参数 options 中指定的参数的值。只需要用参数开头的字母来定义参数就行了。val = optimget(options,param,default) 若 options 结构参数中没有定义指定参数，则返回缺省值。注意，这种形式的函数主要用于其它优化函数。举例：1 下面的命令行将显示优化参数 options 返回到 my_options 结构中：val

5、 = optimget(my_options,Display)2 下面的命令行返回显示优化参数 options 到 my_options 结构中（就象前面的例子一样），但如果显示参数没有定义，则返回值final:optnew = optimget(my_options,Display,final);参见：optimset optimset 函数功能：创建或编辑优化选项参数结构。语法：options = optimset(param1,value1,param2,value2,.)optimsetoptions = optimsetoptions = optimset(optimfun)opti

6、ons = optimset(oldopts,param1,value1,.)options = optimset(oldopts,newopts)描述：options = optimset(param1,value1,param2,value2,.) 创建一个称为options 的优化选项参数，其中指定的参数具有指定值。所有未指定的参数都设置为空矩阵（将参数设置为表示当 options 传递给优化函数时给参数赋缺省值）。赋值时只要输入参数前面的字母就行了。optimset 函数没有输入输出变量时，将显示一张完整的带有有效值的参数列表。options = optimset (with no i

7、nput arguments) 创建一个选项结构options，其中所有的元素被设置为。options = optimset(optimfun) 创建一个含有所有参数名和与优化函数optimfun 相关的缺省值的选项结构 options。options = optimset(oldopts,param1,value1,.) 创建一个 oldopts 的拷贝，用指定的数值修改参数。options = optimset(oldopts,newopts) 将已经存在的选项结构 oldopts 与新的选项结构 newopts 进行合并。newopts 参数中的所有元素将覆盖 oldopts 参数中的所

8、有对应元素。举例：1下面的语句创建一个称为 options 的优化选项结构，其中显示参数设为iter，TolFun 参数设置为 1e-8:options = optimset(Display,iter,TolFun,1e-8)2下面的语句创建一个称为 options 的优化结构的拷贝，改变 TolX 参数的值，将新值保存到 optnew 参数中:optnew = optimset(options,TolX,1e-4);3下面的语句返回 options 优化结构，其中包含所有的参数名和与fminbnd 函数相关的缺省值：options = optimset(fminbnd)4若只希望看到 fmi

9、nbnd 函数的缺省值，只需要简单地键入下面的语句就行了：optimset fminbnd或者输入下面的命令，其效果与上面的相同：optimset(fminbnd)参见：optimget9.1.4 模型输入时需要注意的问题使用优化工具箱时，由于优化函数要求目标函数和约束条件满足一定的格式，所以需要用户在进行模型输入时注意以下几个问题：1.目标函数最小化优化函数fminbnd、fminsearch、fminunc、fmincon、fgoalattain、fminmax 和lsqnonlin 都要求目标函数最小化，如果优化问题要求目标函数最大化，可以通过使该目标函数的负值最小化即-f(x)最小化来

10、实现。近似地，对于quadprog 函数提供-H 和-f，对于 linprog 函数提供-f。2.约束非正优化工具箱要求非线性不等式约束的形式为 Ci(x)0，通过对不等式取负可以达到使大于零的约束形式变为小于零的不等式约束形式的目的，如 Ci(x)0 形式的约束等价于- C i(x)0；C i(x)b 形式的约束等价于- C i(x)+b0。3.避免使用全局变量9.1.5 （函数句柄）函数MATLAB6.0 中可以用函数进行函数调用。函数返回指定 MATLAB 函数的句柄，其调用格式为：handle = function利用函数进行函数调用有下面几点好处： 用句柄将一个函数传递给另一个函数；

11、 减少定义函数的文件个数； 改进重复操作； 保证函数计算的可靠性。下面的例子为 humps 函数创建一个函数句柄，并将它指定为 fhandle 变量。fhandle = humps;同样传递句柄给另一个函数，也将传递所有变量。本例将刚刚创建的函数句柄传递给 fminbnd 函数，然后在区间0.3,1上进行最小化。x = fminbnd (humps, 0.3, 1)x =0.63709.2 最小化问题9.2.1 单变量最小化9.2.1.1 基本数学原理本节讨论只有一个变量时的最小化问题，即一维搜索问题。该问题在某些情况下可以直接用于求解实际问题，但大多数情况下它是作为多变量最优化方法的基础在应

12、用，因为进行多变量最优化要用到一维搜索法。该问题的数学模型为：其中， x,x1,和 x2 为标量， f(x)为函数，返回标量。该问题的搜索过程可用下式表达：其中 xk为本次迭代的值， d 为搜索方向， 为搜索方向上的步长参数。所以一维搜索就是要利用本次迭代的信息来构造下次迭代的条件。求解单变量最优化问题的方法有很多种，根据目标函数是否需要求导，可以分为两类，即直接法和间接法。直接法不需要对目标函数进行求导，而间接法则需要用到目标函数的导数。1直接法常用的一维直接法主要有消去法和近似法两种。（1）消去法 该法利用单峰函数具有的消去性质进行反复迭代，逐渐消去不包含极小点的区间，缩小搜索区间，直到搜

13、索区间缩小到给定的允许精度为止。一种典型的消去法为黄金分割法(Golden Section Search)。黄金分割法的基本思想是在单峰区间内适当插入两点，将区间分为三段，然后通过比较这两点函数值的大小来确定是删去最左段还是最右段，或同时删去左右两段保留中间段。重复该过程使区间无限缩小。插入点的位置放在区间的黄金分割点及其对称点上，所以该法称为黄金分割法。该法的优点是算法简单，效率较高，稳定性好。（2）多项式近似法 该法用于目标函数比较复杂的情况。此时寻找一个与它近似的函数代替目标函数，并用近似函数的极小点作为原函数极小点的近似。常用的近似函数为二次和三次多项式。二次内插涉及到形如下式的二次函

14、数数据拟合问题：其中步长极值为：然后只要利用三个梯度或函数方程组就可以确定系数 a 和 b，从而可以确定 *。得到该值以后，进行搜索区间的收缩。在缩短的新区间中，重新安排三点求出下一次的近似极小点 *，如此迭代下去，直到满足终止准则为止。其迭代公式为：其中 二次插值法的计算速度比黄金分割法的快，但是对于一些强烈扭曲或可能多峰的函数，该法的收敛速度会变得很慢，甚至失败。2间接法间接法需要计算目标函数的导数，优点是计算速度很快。常见的间接法包括牛顿切线法、对分法、割线法和三次插值多项式近似法等。优化工具箱中用得较多的是三次插值法。三次插值的基本思想与二次插值的一致，它是用四个已知点构造一个三次多项

15、式 P3(x)，用它逼近函数 f(x)，以 P3(x)的极小点作为 f(x)的近似极小点。一般讲，三次插值法比二次插值法的收敛速度要快些，但每次迭代需要计算两个导数值。三次插值法的迭代公式为其中如果函数的导数容易求得，一般来说首先考虑使用三次插值法，因为它具有较高的效率。对于只需要计算函数值的方法中，二次插值法是一个很好的方法，它的收敛速度较快，尤其在极小点所在区间较小时尤其如此。黄金分割法则是一种十分稳定的方法，并且计算简单。由于以上原因，Matlab 优化工具箱中使用得较多的方法是二次插值法、三次插值法、二次、三次混合插值法和黄金分割法。9.2.1.2 相关函数介绍fminbnd功能：找到

16、固定区间内单变量函数的最小值。语法：x = fminbnd(fun,x1,x2)x = fminbnd(fun,x1,x2,options)x = fminbnd(fun,x1,x2,options,P1,P2,.)x,fval = fminbnd(.)x,fval,exitflag = fminbnd(.)x,fval,exitflag,output = fminbnd(.)描述：fminbnd 求取固定区间内单变量函数的最小值。x = fminbnd(fun,x1,x2)返回区间x1，x2上 fun 参数描述的标量函数的最小值 x。x = fminbnd(fun,x1,x2,options

17、)用 options 参数指定的优化参数进行最小化。x = fminbnd(fun,x1,x2,options,P1,P2,.)提供另外的参数 P1,P2 等,传输给目标函数 fun。如果没有设置 options 选项，则令 options=。x,fval = fminbnd(.)返回解 x 处目标函数的值。x,fval,exitflag = fminbnd(.)返回 exitflag 值描述 fminbnd 函数的退出条件。x,fval,exitflag,output = fminbnd(.)返回包含优化信息的结构输出。变量：函数的输入变量在表 9-7 中进行描述，输出变量在表 9-8 中描

18、述。与 fminbnd函数相关的细节内容包含在 fun,options,exitflag 和 output 等参数中，如表9-10 所示。表 9-10 参数描述表参 数 描 述fun需要最小化的目标函数。fun 函数需要输入标量参数 x，返回 x 处的目标函数标量值 f。可以将 fun 函数指定为命令行，如x = fminbnd(inline(sin(x*x),x0)同样，fun 参数可以是一个包含函数名的字符串。对应的函数可以是 M 文件、内部函数或 MEX文件。若 fun=myfun，则 M 文件函数 myfun.m 必须右下面的形式。function f = myfun(x)f = .

19、%计算 x 处的函数值。options优化参数选项。你可以用 optimset 函数设置或改变这些参数的值。options 参数有以下几个选项： Display 显示的水平。选择off，不显示输出；选择iter，显示每一步迭代过程 的输出；选择final，显示最终结果。 MaxFunEvals 函数评价的最大允许次数。 MaxIter 最大允许迭代次数。 TolX x 处的终止容限。 exitflag描述退出条件: 0 表示目标函数收敛于解 x 处。 0 表示已经达到函数评价或迭代的最大次数。 0 表示目标函数不收敛。output该参数包含下列优化信息： output.iterations 迭

20、代次数。 output.algorithm 所采用的算法。 output.funcCount 函数评价次数。算法：fminbnd 是一个 M 文件。其算法基于黄金分割法和二次插值法。文献1中给出了实现同样算法的 Fortran 程序。局限性： 1目标函数必须是连续的。2fminbnd 函数可能只给出局部最优解。3当问题的解位于区间边界上时，fminbnd 函数的收敛速度常常很慢。此时，fmincon 函数的计算速度更快，计算精度更高。4fminbnd 函数只用于实数变量。参见：fminsearch, fmincon, fminunc, optimset, inline文献：1 Forsythe

21、, G.E., M.A. Malcolm, and C.B. Moler, Computer Methods for Mathematical Computations, Prentice Hall, 1976.9.2.1.3 应用实例例一 在区间（0，2）上求函数 sin(x)的最小值：x = fminbnd(sin,0,2*pi)x = 4.7124所以区间（0，2）上函数 sin(x)的最小值点位于 x=4.7124 处。最小值处的函数值为：y = sin(x)y = -1.0000磁盘中该问题的 M 文件名为 opt21_1.m。例三 对边长为 3m 的正方形铁板，在四个角处剪去相等的

22、正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？假设剪去的正方形的边长为 x，则水槽的容积为现在要求在区间（0，1.5）上确定一个 x，使 最大化。因为优化工具箱中要求目标函数最小化，所以需要对目标函数进行转换，即要求 最小化。首先编写 M 文件 opt21_3o.m:function f = myfun(x)f = -(3-2*x).2 * x;然后调用 fminbnd 函数(磁盘中 M 文件名为 opt21_3.m)：x = fminbnd(opt21_3o,0,1.5)得到问题的解：x =0.5000即剪掉的正方形的边长为 0.5m 时水槽的容积最大。水槽的最大容积计算：y = o

23、ptim2(x)y =-2.0000所以水槽的最大容积为 2.0000m3。9.2.2 线性规划9.2.2.1 基本数学原理线性规划是处理线性目标函数和线性约束的一种较为成熟的方法，目前已经广泛应用于军事、经济、工业、农业、教育、商业和社会科学等许多方面。线性规划问题的标准形式是：或写成矩阵形式为：其中，0 为 n 维列向量。线性规划的标准形式要求目标函数最小化，约束条件取等式，变量非负。不符合这几个条件的线性模型要首先转化成标准形。线性规划的求解方法主要是单纯形法（ Simple Method），该法由 Dantzig于 1947 年提出，以后经过多次改进。单纯形法是一种迭代算法，它从所有基

24、本可行解的一个较小部分中通过迭代过程选出最优解。其迭代过程的一般描述为：1 将线性规划化为典范形式，从而可以得到一个初始基本可行解 x(0)(初始顶点)，将它作为迭代过程的出发点，其目标值为 z(x(0)。2 寻找一个基本可行解 x(1)，使 z(x(1)z(x (0)。方法是通过消去法将产生 x(0)的典范形式化为产生 x(1)的典范形式。3 继续寻找较好的基本可行解 x(2)，x (3)，使目标函数值不断改进，即 z(x(1)z(x (2) z(x (3) 。当某个基本可行解再也不能被其它基本可行解改进时，它就是所求的最优解。Matlab 优化工具箱中采用的是投影法，它是单纯形法的一种变种

25、。9.2.2.2 相关函数介绍linprog 函数功能：求解线性规划问题。 数学模型：其中 f, x, b, beq, lb 和 ub 为向量， A 和 Aeq 为矩阵。语法：x = linprog(f,A,b,Aeq,beq)x = linprog(f,A,b,Aeq,beq,lb,ub)x = linprog(f,A,b,Aeq,beq,lb,ub,x0)x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)x,fval = linprog(.)x,fval,exitflag = linprog(.)x,fval,exitflag,output = linp

26、rog(.)x,fval,exitflag,output,lambda = linprog(.)描述：x = linprog(f,A,b)求解问题 min f*x，约束条件为 A*x = b。x = linprog(f,A,b,Aeq,beq)求解上面的问题，但增加等式约束，即 Aeq*x = beq。若没有不等式存在，则令 A=、b=。x = linprog(f,A,b,Aeq,beq,lb,ub)定义设计变量 x 的下界 lb 和上界 ub，使得 x 始终在该范围内。若没有等式约束，令 Aeq=、beq=。x = linprog(f,A,b,Aeq,beq,lb,ub,x0)设置初值为 x

27、0。该选项只适用于中型问题，缺省时大型算法将忽略初值。x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)用 options 指定的优化参数进行最小化。x,fval = linprog(.) 返回解 x 处的目标函数值 fval。x,lambda,exitflag = linprog(.)返回 exitflag 值，描述函数计算的退出条件。x,lambda,exitflag,output = linprog(.) 返回包含优化信息的输出变量output。x,fval,exitflag,output,lambda = linprog(.) 将解 x 处的拉格朗日

28、乘子返回到 lambda 参数中。变量：lambda 参数lambda 参数是解 x 处的拉格朗日乘子。它有以下一些属性： lambda.lower lambda 的下界。 lambda.upper lambda 的上界。 lambda.ineqlin lambda 的线性不等式。 lambda.eqlin lambda 的线性等式。其它参数意义同前。算法：大型优化算法 大型优化算法采用的是 LIPSOL 法，该法在进行迭代计算之前首先要进行一系列的预处理。中型优化算法 linprog 函数使用的是投影法，就象 quadprog 函数的算法一样。linprog 函数使用的是一种活动集方法，是线

29、性规划中单纯形法的变种。它通过求解另一个线性规划问题来找到初始可行解。诊断：大型优化问题 算法的第一步涉及到一些约束条件的预处理问题。有些问题可能导致 linprog 函数退出，并显示不可行的信息。在本例中，exitflag 参数将被设为负值以表示优化失败。若 Aeq 参数中某行的所有元素都为零，但 Beq 参数中对应的元素不为零，则显示以下退出信息： Exiting due to infeasibility: an all zero row in the constraint matrix does not have a zero in corresponding right hand si

30、ze entry.若 x 的某一个元素没在界内，则给出以下退出信息：Exiting due to infeasibility: objective f*x is unbounded below.若 Aeq 参数的某一行中只有一个非零值，则 x 中的相关值称为奇异变量。这里，x 中该成分的值可以用 Aeq 和 Beq 算得。若算得的值与另一个约束条件相矛盾，则给出以下退出信息：Exiting due to infeasibility: Singleton variables in equality constraints are not feasible.若奇异变量可以求解但其解超出上界或下界，则给出以下退出信息： Exiting due to infeasibility: singleton variables in the equality constraints are not within bounds.9.2.2.3 应用实例 例二 生产决策问题