第9章 最优化计算.ppt

第9章最优化计算,9.1无约束优化问题,9.2约束优化问题,9.3GUI优化工具,9.4综合实例,9.1无约束优化问题,9.1.1一元函数最小值,格式x=fminbnd(fun,x1,x2)x=fminbnd(fun,x1,x2,options)x,fval,exitflag,output=fminbnd()说明fun：目标函数的表达式字符串、MATLAB自定义函数的函数柄或句柄函数。x1、x2：自变量x在区间的左右端点。options：指定优化参数选项，用来选择允许计算误差、迭代次数、算法等。x：返回区间上函数fun的最小值点。若exitflag0，则x为解；否则，x不是最终解，它只是迭代终止时优化过程的值。,首页,fval：为目标函数最优值，即fval=f*x。exitflag：返回算法的终止标志，若exitflag=1表示目标函数收敛于解x处，说明优化收敛到局部最优解；exitflag=0表示已经达到函数评价或迭代的最大次数，说明优化失败；exitflag=-1表示算法终止、输出，exitflag=-2表示优化过程超出区间范围，exitflagx,fval,exitflag,output=fminbnd(exp(x)-sin(x)-1),-1,1)x=4.3009e-06fval=9.2486e-12exitflag=1output=iterations:10funcCount:11algorithm:goldensectionsearch,parabolicinterpolationmessage:1x111char,9.1.2多元函数最小值,1利用fminsearch函数求最小值格式x=fminsearch(fun,x0)x=fminsearch(fun,x0,options)x,fval,exitflag,output=fminsearch()说明fun：目标函数的表达式字符串、MATLAB自定义函数的函数柄、句柄函数或内联函数；x0：初始值；options：指定优化参数选项。x：为最优解。fval：为目标函数最优值，即fval=f*x。exitflag：返回算法的终止标志，若exitflag=1表示目标函数收敛于解x处，说明优化收敛到局部最优解；exitflag=0表示已经达到函数评价或迭代的最大次数，说明优化失败；exitflag=-1表示算法终止、输出，说明没有收敛到局部最优解x。output：为输出优化信息，iterations表示优化过程的迭代次数，funcCount表示函数评价次数，algorithm表示采用Nelder-Mead型简单搜寻法的算法，message表示优化退出信息。,【例9-2】求一元函数的最小值。,x,fval=fminsearch(x3-2*x2-6*x+5,0)%初始点设为0 x=2.2301fval=-7.2362,【例9-3】求二元函数的最小值。,（3）利用句柄。x,fval=fminsearch(x)x(1)3+2*x(1)*x(2)2-6*x(1)*x(2)+x(2)3,0,0)x=1.13250.9288fval=2.1035,格式x=fminunc(fun,x0)x=fminunc(fun,x0,options)x,fval,exitflag,output,grad,hessian=fminunc()说明fun：目标函数的表达式字符串、MATLAB自定义函数的函数柄、句柄函数或内联函数；x0：初始值；options：指定优化参数选项。x：为指定初始点x0处的最小值点。fval：为目标函数最优值，即fval=f*x。exitflag：=1，梯度在函数值最终允许误差内；=2，在变量x的最终允许误差内；=3，目标函数值在函数值最终允许误差内；=5，预测目标函数下降小于在函数值最终允许误差内；=0，表示已经达到函数评价或迭代的最大次数，说明优化失败；=-1，表示算法终止、输出，说明没有收敛到局部最优解x处；=-3，表示目标函数无界。正值都表示收敛到局部最优解x处。output：Iterations表示优化过程的迭代次数；funcCount表示函数评价次数；stepsize表示最终步长的大小(只用在中型算法)；firstorderopt表示一阶优性的度量，解x处梯度的范数；algorithm表示所采用的优化算法；message表示优化退出信息。grad：目标函数在最优解x点的梯度值。hessian：目标函数在最优解x点的Hessian矩阵值。,2利用函数fminunc求最小值,【例9-4】求函数的最小值。,fun5=inline(x(1)2-x(1)*x(2)+6*x(1)+x(2)2);x0=-1,-1;x,fval,exitflag,output,grad,hessian=fminunc(fun5,x0)x=-4.0000-2.0000fval=-12.0000exitflag=1output=iterations:7funcCount:24stepsize:1firstorderopt:4.5299e-06algorithm:medium-scale:Quasi-Newtonlinesearchmessage:1x436chargrad=1.0e-05*0.0775-0.4530hessian=2.0000-1.0000-1.00002.0000,（1）常用的几个参数。Display：显示水平，取值为“off”时，不显示输出；取值为“iter”时，显示迭代次数；取值为“final”时，显示最终输出（默认值）；取值为“notify”表示在函数不收敛时显示输出。MaxFunEvals：允许函数估值的最大次数，取值为正整数。MaxIter：允许迭代的最大次数，取值为正整数。TolCon：约束变量最终允许误差。TolX：变量x最终允许误差。TolFun：函数值最终允许误差。,3控制参数options的设置,（2）参数options选项是采用optimset函数来设置的。格式options=optimset(optimfun)说明创建一个含所有参数名，并与优化函数optimfun相关的默认值选项结构option。例如，options=optimset(fminsearch)返回一个最优化的选项结构，它包含所有的参数名和默认值，相当于优化函数fminsearch。格式options=optimset(param1,value1,param2,value2,)说明创建一个名称为options的优化选项参数，其中param1,param2为优化参数名，value1,value2为指定的参数对应的指定值，所有未指定的参数取默认值。,4fminunc的算法说明,（1）有大型优化和中型优化算法，由options中的参数LargeScale控制。LargeScale=on（默认值），使用大型算法。LargeScale=off（默认值），使用中型算法。（2）为中型优化算法的搜索方向提供4种算法，由options中的参数HessUpdate控制。HessUpdate=bfgs（默认值），拟牛顿法的BFGS公式。HessUpdate=dfp（默认值），拟牛顿法的DFP公式。HessUpdate=steepdesc，快速下降法。,首页,9.2约束优化问题,9.2.1线性规划问题,首页,格式x=linprog(f,A,b)%不等式约束的目标函数f的最优解xx=linprog(f,A,b,Aeq,beq)%含有等式约束。若没有不等式约束%，则A=，b=x=linprog(f,A,b,Aeq,beq,lb,ub)%指定x的范围。若没有等式约束%，则Aeq=，beq=x=linprog(f,A,b,Aeq,beq,lb,ub,x0)%设置初值x0 x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)%options为指定的优化参数x,fval,exitflag,output,lambda=linprog(),说明x：为最优解。fval：为目标函数最优值，即fval=f*x。exitflag：=1,函数收敛于解x；=0，迭代次数超过最大允许值；=-2，目标函数无最优可行解；=-3，目标函数无界；=-4，在算法执行过程中遇到非数值；=-5，对原问题与对偶问题都无可行解；=-7，当前点的搜索方向的幅度太小，迭代无法继续。output：iterations表示优化过程的迭代次数，algorithm表示优化所采用的运算规则，cgiterations表示共轭梯度迭代次数，message表示退出信息，constrviolation表示约束函数的最大值，firstorderopt表示一阶最优性度量。,首页,lambda：ineqlin是线性不等式约束条件，eqlin是线性等式约束条件，upper是变量的上界约束条件，lower是变量的下界约束条件。它们的返回值分别表示相应的约束条件在优化过程中是否有效。lambda中的非零元素表示对应的约束是有效约束。,【例9-5】求下列优化问题：,首页,目标函数:min,约束条件:,f=-1;-3;-6;A=1-21;325;b=3;12;Aeq=214;beq=9;lb=0;0;0;x,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,beq,lb)运行结果如下：Optimizationterminated.x=0.00001.00002.0000fval=-15.0000,9.2.2非线性规划问题,格式x=fmincon(fun,x0,A,b)%含不等约束条件、目标函数fun以初始值%x0时的最优解xx=fmincon(fun,x0,A,b,Aeq,beq)%含等式约束条件。若没有不等式%约束，则A=，b=x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub)%指定x的范围。若没有等式约%束，则Aeq=，beq=x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)%指含非线性不等约束，约束，lb、ub满足，%若没有界，可设lb=，ub=。%nonlcon的作用是通过接受的向量x来计算非线性不等约束和等式%约束分别在x处的估计C和Ceq，通过指定函数柄来使用,首页,%例如若写成如下形式：%x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,myfun)%这时，需先建立非线性约束函数：%functionC,Ceq=myfun(x)%C=%计算x处的非线性不等约束的函数值%Ceq=%计算x处的非线性等式约束的函数值%并保存为myfun.m。x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)%options指定优化参数x,fval,exitflag,output,lambda,grad,hessian=fmincon()说明x：最小值点。fval：目标函数最优值。exitflag：返回算法的终止标志。output：为输出优化信息。lambda体现哪一个约束有效。grad表示目标函数在x处的梯度。hessian表示目标函数在x处的海森值。,首页,【例9-7】求下面问题在初始点（0，1）处的最优解。,首页,目标函数:min,约束条件:,解：（1）建立非线性约束函数文件：functionc,ceq=myfun1(x)c=(x(1)-1)2-x(2);%非线性约束ceq=;%无非线性等式约束end（2）建立M文件：fun6=x(1)2+x(2)2-x(1)*x(2)-2*x(1)-5*x(2);%目标函数x0=01;A=-23;b=6;Aeq=;beq=;%无线性等式约束lb=;ub=;%x没有下、上界x,fval,exitflag,output,lambda,grad,hessian=fmincon(fun6,x0,A,b,Aeq,beq,lb,ub,myfun1),9.2.30-1整数规划问题,格式x=bintprog(f)%求解无约束条件的0-1整数规划x=bintprog(f,A,b)%带不等式约束条件的0-1整数规划x=bintprog(f,A,b,Aeq,beq)%带等式约束条件的的0-1整数规划x=bintprog(f,A,b,Aeq,beq,x0)%提供初始值x0 x=bintprog(f,A,b,Aeq,beq,x0,options)%提供优化的参数选项optionsx,fval,exitflag,output=bintprog(.),首页,说明x：最小值点。fval：目标函数最优值。exitflag：=1,函数收敛于解x；=0，迭代次数超过最大允许值；=-2，目标函数无最优可行解；=-4，已到达最大节点数；=-5，已到达最大时间；=-6，在节点进行LP松弛问题的解的迭代次数超过最大RLP迭代次数。output：iterations表示优化过程的迭代次数，nodes表示探索节点数，time表示执行时间，algorithm表示优化所采用的运算规则，branchStrategy表示分支策略，nodeSrchStrategy表示节点寻找策略，message表示退出信息。,首页,【例9-10】求0-1整数规划的最优解。,首页,目标函数:,约束条件:,MATLAB程序如下：f=1;2;3;1;1;A=-2-3-5-4-7;-1-1-4-2-2;%改变不等式符号b=-8;-5;x,fval,exitflag,output=bintprog(f,A,b)运行结果如下：Optimizationterminated.x=%显示x的转置x10011fval=3,9.2.4二次规划问题,格式x=quadprog(H,f,A,b)%x=quadprog(H,f,A,b,Aeq,beq)%x=quadprog(H,f,A,b,Aeq,beq,lb,ub)%x=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)%x0初始点x=quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)%options为指定的优化参数x,fval,exitflag,output,lambda=quadprog(),首页,说明H二次规划中的二次项矩阵；f二次规划中的一次项向量。x：最小值点。fval：目标函数最优值。exitflag：=1，成功求得最优解；=3，求得一个解，且对应的目标函数值的精度等于给定值；=4，求得的解为局部极小值；=0，迭代步骤超过最大允许值；=-2，目标函数无最优可行解；=-3，目标函数无界；=-4，当前点的搜索方向不是下降方向，迭代无法继续；=-7，当前点的搜索方向的幅度太小，迭代无法继续。output：Iterations为迭代步骤，algorithm为优化算法，cgiterations为总的PCG迭代步数，firstorderopt为一般优化的度量。lambda：lower为下界LB，upper为上界UB，ineqlin为线性不等式，eqlin为线性等式。,首页,【例9-11】求二次规划的最优解：,首页,目标函数:,约束条件:,H=2-4;-48;f=3;-4;A=21;-12;b=2;3;lb=0;0;x,fval,exitflag,output,lambda=quadprog(H,f,A,b,lb)运行结果如下：x=00.5000fval=-1,9.3GUI优化工具,1工具启动在MATLAB命令窗口输入optimtool，或在MATLAB主界面单击左下角的“Start”按钮，然后依次选择“Toolboxes”“Optimization”“OptimizationTool(optimtool)”，即可打开优化工具界面,首页,2界面组成,首页,（1）“ProblemSetupandResults”部分主要包括：Solver：求解器。Algorithm：算法。Objectivefunction：目标函数。Derivatives：微分或梯度。Startpoint：初始点。Constraints：约束条件。Start：开始（运行求解）。Currentiterative：目前迭代（运行状态）。Finalpoint：最终值点（求解结果）。（2）“Options”选项主要包括9大类：Stoopingcriteria：停止准则。Functionvaluecheek：函数值检查。User-suppliedderivatives：用户自定义微分（或梯度）。Approximatedderivatives：自适应微分（或梯度）。Algorithmsettings：算法设置。Inneriterationstoopingcriteria：内迭代停止准则。Plotfunctions：用户自定义绘图函数。Outputfunctions：用户自定义输出函数。Displaytocommandwindow：输出到命令行窗口。,3使用步骤（1）选择求解器“solver”中的优化算法。（2）选定目标函数“Objectivefunction”。（3）设定目标函数的相关参数：初始点“Startpoint”，约束条件“Constraints”。（4）设置优化选项“Options”。（5）单击“Start”按钮，运行求解。（6）查看求解器的状态和求解结果。（7）将目标函数、选项和结果导入/导出（利用菜单File文件）。,首页,9.3.2GUI优化工具实例操作,1fminbnd求解器例如，对【例9-1】中的优化问题求解。只需将界面（见图9-1）上的“Solver”，选择为“fminbnd-Single-variablenonlinearminimizationwithbounds”；“Objectivefunction”中直接填写函数的字符串exp(x)-sin(x)-1，或(x)exp(x)-sin(x)-1；选择“x1”处为-1，“x2”处为1，点击按钮“Start”，就显示出运行结果,首页,（在目标函数中，我们可以选择所定义的函数名，譬如文件名为“fun1.m”的函数文件：functionf=fun1(x)f=exp(x)-sin(x)-1;end这时只需在“Objectivefunction”中填写fun1即可。我们也可以将优化问题和结果输出到“Workspace”，并在命令窗口显示出来。其方法为：（1）打开“File”下拉菜单，点击“ExportToWorkspace”，得到,首页,（2）选中“optimproblem”、“options”和“optimresults”左边的单选框，点击“OK”，其内容输出到“Workspace”，并在命令窗口中给出提示：Thevariablesoptimproblem,optionsandoptimresultshavebeencreatedinthecurrentworkspace.,2fminsearch求解器对【例9-3】中的优化问题求解。只需将界面上的“Solver”，选择为“fminsearch-Unconstrainednonlinearminimization”；“Objectivefunction”中直接填写函数x(1)3+2*x(1)*x(2)2-6*x(1)*x(2)+x(2)3；“Startpoint”处填写0,0，点击按钮“Start”，就显示出运行结果，如图所示。,首页,3fminunc求解器例如，对【例9-4】中的优化问题求解。只需将界面上的“Solver”，选择为“fminunc-Unconstrainednonlinearminimization”；“Algorithm”下拉选框中选择“Mediumscale”；“Objectivefunction”中直接填写函数x(1)2-x(1)*x(2)+6*x(1)+x(2)2；“Startpoint”处填写-1,-1，点击按钮“Start”，就显示出运行结果,首页,结果导出如下：optimproblemoptimproblem=objective:x(1)2-x(1)*x(2)+6*x(1)+x(2)2x0:-11solver:fminuncoptions:1x1structoptimresultsoptimresults=x:-4-2fval:-12exitflag:1output:1x1structgrad:2x1doublehessian:2x2double,4linprog求解器线性规划求解器中的算法有三种：“Largescale”（大规模算法）、“Mediumscale-simplex”（中等规模-单纯形算法）和“Mediumscale-activeset”（中等规模-有效集算法），当选用“Mediumscale-activeset”，还要提供初始点。,首页,例如，对【例9-5】中的优化问题求解。只需将界面上的“Solver”，选择为“linprog-Linearprogramming”；“Algorithm”下拉选框中选择“Mediumscale-activeset”；“f”处填写-1;-3;-6，“A”处填写1-21;325，“b”处填写3;12，“Aeq”处填写214，“beq”处填写9，“Lower”处填写0;0;0，“Upper”处填写或不填，“Startpoint”选择单选框“Letalgorithmchoosepoint”（算法自动选择）；点击按钮“Start”，就显示出运行结果，如图所示。,首页,5fmincon求解器求解器为fmincon的可用算法有：“Interiorpoint”（内点算法）、“SQP”算法、“Activeset”（有效集算法）和“Trustregionreflective”（信赖域反射算法）。利用“Trustregionreflective”算法，不能有线性不等式约束条件。,首页,例如，对【例9-7】中的优化问题求解。只需将界面上的“Solver”选择为“fmincon-Constrainednonlinearminimization”；“Algorithm”下拉选框中选择“Interiorpoint”，“Objectivefunction”中直接填写函数x(1)2+x(2)2-x(1)*x(2)-2*x(1)-5*x(2)，“Startpoint”处填写0,1，“A”填写-23，“b”填写6，“Nonlinearconstraintfunction”填写所定义的文件名myfun1，其中函数程序为：functionc,ceq=myfun1(x)c=(x(1)-1)2-x(2);ceq=;end点击按钮“Start”，就显示出运行结果，如图所示。,首页,6bintprog求解器,例如，对【例9-10】中的优化问题求解。只需将界面上的“Solver”，选择为“bintpro