约束最优化.ppt

《约束最优化.ppt》由会员分享，可在线阅读，更多相关《约束最优化.ppt（50页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、最优化方法济南大学控制科学与工程学院授课教师：李实cse_1教1007室济南大学控制科学与工程学院最优化方法第六章 约束最优化方法6.1 惩罚函数法6.2 乘子法6.3 序列二次规划法6.4 多目标最优化方法6.5 MATLAB求解约束最优化问题6.6 约束最优化问题应用实例2济南大学控制科学与工程学院最优化方法3约束最优化方法是用来求解如下非线性约束最优化问题的数值迭代算法：求解约束最优化问题的关键在于如何处理各种约束条件。根据处理约束条件的不同方式，其求解方法分为直接法和间接法两类：直接法：直接法：在迭代过程中逐点考察约束，并使迭代点始终局限于可行域之内的算法称为直接法，如可行方向法可行方

2、向法。间接法：间接法：将约束条件引入目标函数，使约束最优化问题转化为无约束最优化问题求解，或者将非线性问题转化为相对简单的二次规划问题或线性规划问题求解，如惩罚函数法、乘子法、序列二次规划法惩罚函数法、乘子法、序列二次规划法。济南大学控制科学与工程学院最优化方法6.1 惩罚函数法4惩罚函数法是一种将约束最优化问题转化为无约束最优化问题求解的算法。对于约束最优化问题：构造无约束问题：为惩罚函数是由不等式约束函数构成的复合函数是由等式约束函数构成的复合函数当X在约束可行域之外时，第二项与第三项的值很大，看做对目标函数加以惩罚。或者当X在约束边界附近时，第二项和第三项的函数值趋于无穷大，使得函数在约

3、束边界筑起一道围墙，迫使迭代点局限在可行域内移动。惩罚因子济南大学控制科学与工程学院最优化方法6.1.1 外点法5构造惩罚函数：对于不等式约束条件：可以证明，当惩罚因子按一个递增的正数序列变化时：惩罚因子rk取一正数，当X点在可行域内，gu(X)0，max(gu(X),0)=0，惩罚项为零，惩罚函数的极小问题变为目标函数的无约束极小问题。当X点在可行域外，gu(X)0,max(gu(X),0)=gu(X)，惩罚项为正数，对惩罚函数求极小。取复合函数：济南大学控制科学与工程学院最优化方法6所得极小点序列：对于等式约束问题，可按同样思想构造惩罚函数，即：是逐步逼近不等式约束问题的最优解的依次求解每

4、个rk对应的惩罚函数极小值问题一般情况下，该极小点序列是由可行域外部向可行域的边界或内部逼近的。这种方法称为外点罚函数法，简称外点法。对于一般性约束问题，将不等式约束与等式约束复合函数组合：济南大学控制科学与工程学院最优化方法7外点惩罚函数的形态和求解过程可以用下图所示的一维问题加以说明，图中的各种曲线分别代表目标函数f(X)和几个不同惩罚因子所对应的惩罚函数的图形：由图可以看出：1.在可行域内，惩罚函数与目标函数重合，忽略约束条件。在可行域外，将约束条件与目标函数构成惩罚函数，惩罚函数的曲线被逐渐抬高，离约束边界越近，曲线被抬高越多。2.惩罚因子的值越大，惩罚函数被抬高越多，极小点越接近约束

5、边界。3.惩罚因子趋于无穷大时，惩罚函数的极小点就是约束最优化问题的最优点。济南大学控制科学与工程学院最优化方法8外点法是针对落在可行域外的迭代点函数值加以惩罚，迫使迭代点向可行域的边界或内部逐步逼近的算法。因此，初始点可以是内点，也可以是外点。外点法可以处理不等式约束与等式约束问题，适应性较好。外点法的迭代步骤如下：给定初始点X0，收敛精度，初始惩罚因子r0和惩罚因子递增系数c，置k=0构造惩罚函数：求解无约束最优化问题：终止判断，满足：迭代终止，否则，k=k+1，转济南大学控制科学与工程学院最优化方法9例6.1 用外点法求解约束最优化问题：解：构造惩罚函数，转化为无约束最优化问题：求解无约

6、束最优化问题，因为惩罚函数构造简单，可以直接用极值条件求解，即令惩罚函数的一阶导数等于零：可行域内：，均不等于零，可知可行域内无极值点。济南大学控制科学与工程学院最优化方法10联立求解，得到：取一组递增的惩罚因子，得到惩罚函数的一组极小点，分别是：可行域外：济南大学控制科学与工程学院最优化方法11外点法的迭代路线如下图所示，向约束问题的最优点0,0T逐步逼近。虚线所示济南大学控制科学与工程学院最优化方法6.1.2 内点法12构造惩罚函数：内点法是另一种惩罚函数法，其惩罚函数构成形式与外点法类似，但要求迭代过程始终限制在可行域内进行。对于不等式约束：取复合函数：倒数形式对数形式济南大学控制科学与

7、工程学院最优化方法13由上式可以看出，给定惩罚因子rk为正数，当点在可行域内，惩罚项的值大于零，当点靠近约束边界时，惩罚项迅速增大并趋于无穷。也就是说，当初始点X0取在可行域内，迭代点Xk不能超出可行域的边界。可以证明，当惩罚因子按一个递减的正数序列变化时：并且初始点X0为内点，得到的极小点序列是逐步向约束问题的最优点逼近的：从惩罚函数的构成可以看出，内点法不适用于等式约束，并且要求初始点必须为内点，这对于约束条件较多或约束函数较为复杂的问题不太方便。但是，内点法在一次求解中除了得到最优解之外，还可以提供一系列不断变化的近似最优解，供设计者进一步分析选用。济南大学控制科学与工程学院最优化方法1

8、4内点惩罚函数的形态和求解过程可以用下图所示的一维问题加以说明，图中的各种曲线分别代表目标函数f(X)和几个不同惩罚因子所对应的惩罚函数的图形：由图可以看出：1.惩罚函数的有效区域是约束的可行域，目标函数在可行域内的所有点都受到惩罚，越靠近边界惩罚越多。2.不同的惩罚因子对应不同的惩罚函数，惩罚因子越小，惩罚函数的极小点越接近与边界处的最优点。3.当惩罚因子趋近与零时，惩罚函数的极小点就是原约束问题的最优点。济南大学控制科学与工程学院最优化方法15内点法的迭代步骤如下：给定初始点X0，收敛精度，初始惩罚因子r0和惩罚因子递减系数c，置k=0构造惩罚函数：求解无约束最优化问题：终止判断，满足：迭

9、代终止，否则，k=k+1，转济南大学控制科学与工程学院最优化方法16例6.2 用内点法求解约束最优化问题：解：构造惩罚函数，转化为无约束最优化问题：求解无约束最优化问题，因为惩罚函数构造简单，可以直接用极值条件求解，即令惩罚函数的一阶导数等于零：济南大学控制科学与工程学院最优化方法17联立求解，得到：取一组递减的惩罚因子，得到惩罚函数的一组极小点，分别是：济南大学控制科学与工程学院最优化方法18外点法的迭代路线如下图所示，向约束问题的最优点0,0T逐步逼近虚线所示。济南大学控制科学与工程学院最优化方法6.1.3 混合法19混合法是综合外点法和内点法的优点建立的一种算法，对不等式约束条件按内点法

10、建立惩罚项，对等式约束条件按外点法建立惩罚项，由此得到惩罚函数：其中，惩罚因子rk1取正的递减数列，rk2取正的递增数列。或将两个惩罚因子合并，令rk=rk1=1/rk1，得到惩罚函数：济南大学控制科学与工程学院最优化方法6.2 乘子法20惩罚函数法具有方法简单、使用方便等优点。但它存在固有的缺点：随着惩罚因子趋向与极限值，带来惩罚函数计算上的困难。为了克服这一困难，Hestenes和Powell与1969年各自提出了乘子法。等式约束问题的乘子法等式约束问题的乘子法对于等式约束问题：用外点法建立的极小化问题：当rk足够大时，得到最优解Xk，由惩罚函数梯度等于零，可以得到：济南大学控制科学与工程

11、学院最优化方法21要使Xk接近于极小点X*，应充分接近 。由于 ，上式右端也应接近与零。但是对于约束最优化问题，一般并不等于零，因此只有无线增大rk的值来满足极值条件。要解决这个问题，可以寻找一个在最优点处梯度等于零的函数去取代f(X)。考虑等于约束问题的拉格朗日函数：根据极值条件，如果等式约束问题有解，必存在乘子向量使得：济南大学控制科学与工程学院最优化方法22对应的无约束最优化问题：称为增广拉格朗日函数。可以证明，如果知道最优乘子向量*，那么只要取足够大的惩罚因子rk，而不需要使其趋向无穷大，就能得到原等式约束问题的最优解，这就是乘子法的基本思想。该拉格朗日函数的梯度必等于零，可用其代替原

12、函数f(X)，因此得到新的等于约束最优化问题：济南大学控制科学与工程学院最优化方法23增广拉格朗日函数的梯度等于零：由以上两式，可得：然而，最优乘子向量*是不能预先得到的。一般的方法是，先给定足够大的惩罚因子rk和初始向量0，然后在迭代过程中逐步修正k，使其趋向*。等式约束问题的k-t条件：实际迭代过程中，将上式看作乘子向量的修正公式：济南大学控制科学与工程学院最优化方法24不等式约束问题的乘子法不等式约束问题的乘子法对于不等式约束问题：引入变量zu(u=1,2,p)，将不等式约束化为等式约束：根据上节介绍的等式约束问题，建立增广拉格朗日函数：令 ，得到济南大学控制科学与工程学院最优化方法25

13、可以得到，当时当 时济南大学控制科学与工程学院最优化方法26综合以上两种情况，可将增广拉格朗日函数写为：根据上节等式约束推导最优乘子向量，同理可得终止准则：济南大学控制科学与工程学院最优化方法27一般约束问题的乘子法一般约束问题的乘子法综合以上两个约束问题的乘子法，得到增广目标函数：拉格朗日乘子迭代公式：终止准则：济南大学控制科学与工程学院最优化方法28乘子法的迭代步骤如下：给定初始点X0，收敛精度，初始惩罚因子r0和惩罚因子递减系数c，初始乘子向量0和0，置k=0构造增广目标函数：求解无约束最优化问题：终止判断，满足终止准则，迭代终止，否则，k=k+1，rk+1=c*rk，转济南大学控制科学

14、与工程学院最优化方法29例6.3 用乘子法求解约束最优化问题：解：构造增广目标函数直接用极值条件求解，得到极小值：济南大学控制科学与工程学院最优化方法30因为乘子系数一般为正值，将x1=0点舍去，得到：乘子的迭代公式为：取rk=1,0=0，得到：可以增大惩罚因子rk来提高逼近速度。济南大学控制科学与工程学院最优化方法6.3序列二次规划算法31序列二次规划(Sequential Quadratic Programming,SQP)算法是将复杂的非线性约束最优化问题转化为比较简单的二次规划问题求解的算法。将目标函数简化为二次函数，将约束函数简化为线性函数。将其简化为二次规划问题：对于约束非线性最优

15、化问题：济南大学控制科学与工程学院最优化方法32将其写成二次规划问题的一般形式：其中：求解该二次规划问题，并将其最优解S*作为原问题的下一个搜索方向Sk，进行搜索，得到原约束问题的下一个迭代点Xk+1，再代入二次规划问题，得到新的最优解，反复迭代，最后得到原问题的最优解。济南大学控制科学与工程学院最优化方法33序列二次规划算法的迭代步骤如下：给定初始点X0，收敛精度，令H0=I（单位矩阵），置k=0在点Xk将原问题简化为二次规划问题：求解该二次规划问题，将得到的最优解S*看作原问题的迭代方向Sk在方向Sk上对原问题的目标函数进行一维搜索，得到最优解X*，记做Xk+1终止判断，满足终止准则，迭代

16、终止，否则，k=k+1，并用变尺度法修正二阶导数矩阵Hk+1，转济南大学控制科学与工程学院最优化方法34二阶导数矩阵二阶导数矩阵H的修正：的修正：采用变尺度法：DFP公式 BFGS公式济南大学控制科学与工程学院最优化方法35二次规划问题的求解：二次规划问题的求解：等式约束二次规划问题：其拉格朗日函数为：由多元函数的极值条件，L的一阶导数等于零，可得：与等式约束联立：得到：济南大学控制科学与工程学院最优化方法36上式方程数与变量数都为n+m，无解或有唯一解，如果有唯一解，根据k-t条件，只要不全为零，得到的Sk即为最优解，可将其作为原约束问题的迭代方向Sk一般性约束二次规划问题：由第二章最优性条

17、件讨论可知，将起作用不等式约束条件变为等式约束条件，再构造拉格朗日函数，根据极值条件，最后推导出具有极值的k-t条件：对于其作用不等式约束的拉格朗日向量必须为非负。具体的推导过程，这里忽略。求得的方向Sk作为原约束问题的迭代方向，继续求解。济南大学控制科学与工程学院最优化方法37例6.4 求解二次规划问题：解：变为二次规划形式初始点为0 0 0T.济南大学控制科学与工程学院最优化方法38建立拉格朗日函数：由极值条件，取梯度等于零，与等式约束联立，可得：由k-t条件，不全为零可知，S为极值点，因此S为二次规划问题的最优解。济南大学控制科学与工程学院最优化方法6.4 多目标最优化方法39实际工程问

18、题通常有多种评价设计质量好坏的技术经济指标。若将这多个技术经济指标都写作设计变量的函数，就构成了多个目标函数或设计目标，分别记做f1(X),f2(X),fq(X)。由此建立起来的数学模型称为多目标优化问题，简称多目标问题。济南大学控制科学与工程学院最优化方法40多目标问题一般不可能存在使每一个目标都同时达到最优的完全最优解，只能对多个优化目标进行折中，找到相对最优解。使每个目标函数都取得极小点的解成为完全最优解。至少使一个目标函数取得最小值的解称为劣解。除了完全最优解与劣解，剩下的解均称为有效解。多目标最优化方法是根据不同目标的重要性对各个目标进行加权量化，求得一个相对最优的有效解。多目标最优

19、化问题一般都是转化为单目标问题求解的，如主要目标法、线性加权法、理想点法济南大学控制科学与工程学院最优化方法41主要目标法：主要目标法：在所有技术经济指标中选出一个最重要的指标作为设计的目标函数，而将其他的指标分别给定一个可以接受的范围，转变为一组约束条件，从而构成一个单目标最优化问题，这就是主要目标法。济南大学控制科学与工程学院最优化方法42线性加权法：线性加权法：由q个目标函数构成如下综合评价函数：得到单目标约束最优化问题：式中wi是反应各个分目标重要性的一组系数，称为权因子，权因子的选择决定了最优化问题的最优解。一般可以按下式计算：是以第i个分目标为目标函数所构成的单目标问题的最优值。济

20、南大学控制科学与工程学院最优化方法43理想点法：理想点法：构造如下单目标最优化问题：可以证明，该问题的最优解是一个最接近完全最优解的有效解，因此叫做理想点法。该问题的最优解即考虑了各个分目标的重要性，又接近与完全最优解。引入权因子，改写成：济南大学控制科学与工程学院最优化方法6.5 MATLAB求解约束最优化44MATLAB中用于求解约束优化问题的函数为 fmincon,采用序列二次规划法，其中每一次用二次规划逼近，Hessian矩阵修正采用BFGS变尺度法x,fval,exitflag,output=fminunc(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,optio

21、ns)：x为最优解，fval为最优值，exitflag输出1或0，为是否成功找到最优值，output输出迭代次数、迭代方法等。fun为目标函数，x0为初始值，options为设置参数。A和b为线性不等式约束，AXb；Aeq和beq为线性等式约束，Aeq=beq；lb和ub分别为变量x的下限和上限；nonlcon为非线性约束济南大学控制科学与工程学院最优化方法45例6.1 用MATLAB求解：建立目标函数的*.m文件，命名为optimfun.mfunction y=optimfun(x)y=x(1)+x(2);g1为非线性不等式约束，g2可做变量的下限约束。建立非线性不等式约束的.m file,

22、命名为nonlconfun.mfunction c,ceq=nonlconfun(x)c=x(1)2-x(2);ceq=;最后在MATLAB窗口输入参数与运行程序x0=1,1;opt=optimset(Display,iter);x,fval,exitflag,output=fmincon(optimfun,x0,0,nonlconfun,opt);济南大学控制科学与工程学院最优化方法46例6.5 用MATLAB求解：初始点(s,t)=(1,2)建立目标函数的*.m文件，命名为optimfun.mfunction y=optimfun(x)y=x(1)4-4*x(1)-8*x(2)+15;建立

23、非线性不等式约束的.m file,命名为nonlconfun.mfunction c,ceq=nonlconfun(x)c=9-x(1)2-x(2)2;ceq=;最后在MATLAB窗口输入参数与运行程序A=2 3;-1 1;b=2;5;%线性不等式约束x0=1,2;%初始值opt=optimset(Display,iter);%参数设定x,fval,exitflag,output=fmincon(optimfun,x0,A,b,nonlconfun,opt)济南大学控制科学与工程学院最优化方法6.6 约束最优化问题应用实例47最大体积问题：最大体积问题：最大体积问题指的是在给定表面积一定的前提

24、下，确定容积的最大值，随着实际问题的不同，不一定是给定表面积，可能是给定容器的形状、可用材料大小，来得到容积最大值。例例6.6 最大体积应用实例：最大体积应用实例：从长为2米、宽为1米的薄铁皮四个角上剪掉相等的正方形，将剩余铁皮折成一个无盖的水箱，怎样裁剪使得水箱的容积最大？济南大学控制科学与工程学院最优化方法48假设正方形的边长为x，写出该优化问题的数学模型：建立目标函数的*.m文件，命名为optimfun.mfunction y=optimfun(x)y=-(2-2*x)*(1-2*x)*x;在MATLAB窗口输入参数与运行程序x,fval=fmincon(optimfun,0.1,0,0

25、.5)济南大学控制科学与工程学院最优化方法49资源分配问题：资源分配问题：资源分配是指在企业的不同组成部分之间进行的资源分配，这些组成部分可能是企业的职能，如营业、财务等，当资源总量一定的情况下，只有通过最优比例分配，才能使资源的配置最优。例例6.7 资源分配问题应用实例：资源分配问题应用实例：某发电厂下属有三个子公司，发电厂计划与2012年总的发电量为2000万度，现将2000万度的任务分配给下属三个子公司，子公司的发电成本为：如何分配生产任务，使总的发电成本最低？济南大学控制科学与工程学院最优化方法50解：假设三个子公司的发电量分别为p1,p2,p3,建立最优化数学模型：建立目标函数的*.m文件，命名为optimfun.mfunction y=optimfun(x)y=x(1)2.1+2*x(2)1.8+0.5*x(3)2.2;在MATLAB窗口输入参数与运行程序Aeq=1 1 1;beq=2000;x0=1000;500;500;x,fval=fmincon(optimfun,x0,Aeq,beq,0;0;0,)