青科大化工-最优化方法

pse2009最优化1/53第3章非线性规划1、直接代入法SolutionbyDirectSubstitution2、罚函数法PenaltyFunction3、拉格朗日乘子法LagrangeMultiplierMethod4、二次规划法和序列二次规划法

5、几何规划法

6、复合形法

7、可变容差法pse2009最优化2/53§3非线性规划策略：

1.消去约束条件，转化为无约束优化问题，如直接代入法、经典的拉格朗日法、罚函数法和序列无约束极小化方法（SUMT法）等实现这种转化。

2.将非线性规划问题转化为线性规划问题，如序列二次规划法。

3.直接求解法：几何规划法、简约梯度法、单形法、复合形法、可变容差法等。非线性规划的一般数学表达式：pse2009最优化3/53一、直接代入法SolutionbyDirectSubstitution例1：pse2009最优化4/53

直接代入法可用于求解较为简单的问题。若约束条件为非线性，则该法处理起来较困难。思路：由约束方程组求得m个变量的表达式，代入目标函数中，得到一新的目标函数，此即为无约束条件的目标函数。pse2009最优化5/53图解示意：x2x1若无约束条件，则pse2009最优化6/53二、罚函数法PenaltyFunction罚因子，很大的正的常数求最小值时为+求最大值时为-当时，不施加惩罚，当时，施以罚因子ki。对于具有等式约束的问题：思路：把约束条件用罚

因子连接到目标

函数上去，使约

束问题转化为无约

束问题。新的目标函数具有这样性质：对于那些在求解过程中企图违反约束的迭代点给以很大的罚因子，使得目标函数变得很大（求最小问题）。而且离约束条件愈远，则惩罚愈大。于是迫使迭代解无限地向可行域靠近，或者一直保持在可行域内移动，直到收敛于原问题的最小点。pse2009最优化7/53对于具有不等式约束的问题：二、罚函数法PenaltyFunctionpse2009最优化8/53例2：解：罚函数法pse2009最优化9/53式4代入式3得：当k时，要使上式成立，则解上述方程组式2、3：pse2009最优化10/53此法是处理等式约束最优化问题最常用的方法之一。

三、拉格朗日乘子法LagrangeMultiplierMethod------Lagrangian其极值存在的必要条件为：思路：引进待定的拉格朗日乘子，将有约束问题转化为无约束问题。以两变量、一等式约束的最优化问题为例：

联立求解上述三个方程，解出、x1*、x2*，代入f后可得最优值。pse2009最优化11/53

事实上，如果f是无约束函数，则最优化的必要条件为。但由于x1、x2受到约束，不能再任意规定函数f的两个偏导数等于0。然而，在最优点处f必定是一极值，即df=0仍然成立。又由于存在约束，必须满足dh=0。所以，有约束的最优化必要条件为：

三、拉格朗日乘子法LagrangeMultiplierMethodpse2009最优化12/53代入式1得：拉格朗日乘子，常数，表示目标函数随约束条件h微小变化而变化的程度。

式3和原约束方程一起，三个方程解出、x1*、x2*，此x1*、x2*即为满足约束条件的极值点。pse2009最优化13/53一般地，对于多元等式约束最优化问题：可构造Lagrangian函数：其极值的必要条件为：再推广至多维的情况。pse2009最优化14/53

以上共计n+m个方程，可解出x1、x2、……、xn；

1、1、…...m，共计n+m个变量。此解就是Lagrangian函数的驻点，而x1、x2、……、xn就有可能是上述问题的最优解。pse2009最优化15/53例3：见前面例1：结果为解：构造Lagrangian：pse2009最优化16/53练习1：用拉格朗日乘子法解下列非线性规划问题。pse2009最优化17/53练习2：用拉格朗日乘子法解下列非线性规划问题。X1=3.54,X2=-3.54,λ=-0.5X1=-3.54,X2=3.54,λ=-0.5pse2009最优化18/53

如图所示四台换热器系列。试选择四台换热器的换热面积，使冷流体出口温度t4最高，而总换热面积为200m2。各换热器总传热系数Ki及热流体入口温度Ti给定，冷流体入口温度t0为已知，冷热流体流量给定。换热为逆流。解：建模-----目标函数-----约束条件1例4：热交换器序列的最优化设计pse2009最优化19/53约束条件2：pse2009最优化20/53又由式1得：式4代入式3得：pse2009最优化21/53-----约束条件2构造Lagrangian：-----共计13个方程pse2009最优化22/53

四、二次规划法和序列二次规划法什么是二次规划？所谓二次规划是指目标函数为二次函数，约束条件为线性函数的优化问题。其表达式为：（一）二次规划法X为n维向量。（m个）（n个）例如：一元二次规划问题pse2009最优化23/53

四、二次规划法和序列二次规划法二次规划问题处理方法：（1）引入松弛变量，将不等式约束化为等式约束：一元：多元：pse2009最优化24/53

四、二次规划法和序列二次规划法（2）引入拉格朗日乘子：一元：多元：pse2009最优化25/53

四、二次规划法和序列二次规划法（3）根据函数极值存在的必要条件有：一元：---线性代数方程组，未知数4个（x、y、、），方程4个，有唯一解，此解即为原二次规划问题的最优解。pse2009最优化26/53

四、二次规划法和序列二次规划法多元：------线性代数方程组，未知数2（n＋m）个，方程2（n＋m）个，有唯一解，此解即为原二次规划问题的最优解。000202022111=+-=¶¶=-+=¶¶==¶¶==¶¶=-++=¶¶ååå===jjjiinjjijijjjiiijmiiijjmiiijjtxLbsxaLttLssLacxdxLlmlmlmpse2009最优化27/53

四、二次规划法和序列二次规划法（二）序列二次规划法基本思路：将非线性规划问题在近似解xk处处理成二次规划问题。

由Wilson1963年首先提出，1977年形成一个快速、有效的算法WHP(又称SQP)法。目前此法在化工领域优化中起着举足轻重的作用。

pse2009最优化28/53

四、二次规划法和序列二次规划法（二）序列二次规划法假设一个非线性规划问题：为n维向量。（1）引入拉格朗日乘子，构造拉格朗日函数：pse2009最优化29/53

四、二次规划法和序列二次规划法（二）序列二次规划法（2）将上式在xk、k、k处泰勒展开，取至二阶导数项：考虑到：pse2009最优化30/53

四、二次规划法和序列二次规划法（二）序列二次规划法于是，上式改写为：对照：二次规划上式等价于下述二次规划问题，即pse2009最优化31/53

五、几何规划法

几何规划适宜解决用因次分析得出的设计关系式或由实验结果以幂函数拟合而得的关系式进行最优化的情形。它的优点是可将一个复杂的优化问题简化为解一个线性代数方程组的问题。下面先讨论无约束几何规划问题，然后再介绍有约束几何规划问题。几何规划法要求目标函数和约束条件均为正项式。所谓正项式（Posynomial）指系数、变量均为正数的多项式。无约束几何规划优化问题的一般表达式为：（1）（2）pse2009最优化32/53

五、几何规划法根据“算术平均与几何平均定理”有：只有a1＝a2＝…＝aN时，上式等式成立。将式3进一步推广，引入N个加权因子j>0，j＝1～N，有：（3）------正则条件（归一化条件）pse2009最优化33/53

五、几何规划法（4）将式4用于式1，得:原函数对偶函数（5）（6）正项式pse2009最优化34/53

五、几何规划法将式2代入式5的右侧得：pse2009最优化35/53

五、几何规划法若使加权因子满足以下正交条件：（7）（8）pse2009最优化36/53

五、几何规划法将式8代入式7得：（9）将式9代入式5得：

可以证明，若f*是原目标函数的最小值，*是对偶函数的最大值，则有---对偶函数pse2009最优化37/53

五、几何规划法因此，应用几何规划法的步骤为：（1）根据正定多项式的项数N引入N个加权因子；（2）根据正则条件和正交条件，求解加权因子的值j，i=1~n，j＝1～N；

（3）由j（j＝1～N）值求对偶函数的最大值*，再代入f*＝*中即可求出f*；（4）将f*值代入，可求出xi，i＝1～n。pse2009最优化38/53例5

由管道、一个泵和容器组成的系统，其管道费用为（100D+50D2）其中D为管径，cm。容器的费用可表示为20/Q，其中Q为流量，m3/s。泵的费用为300Q2/D5。求使总费用最少的管径和流体处理量。解：总费用pse2009最优化39/53例5

由管道、一个泵和容器组成的系统，其管道费用为（100D+50D2）其中D为管径，cm。容器的费用可表示为20/Q，其中Q为流量，m3/s。泵的费用为300Q2/D5。求使总费用最少的管径和流体处理量。引入4个加权因子1、2

、3

、4pse2009最优化40/53

根据正则条件和正交条件，求解加权因子的值j，i=1~2，j＝1～4:代入对偶函数中：pse2009最优化41/53迭代求极值得：于是将j，j＝1～N的值代入f*＝*中即可求出f*将f*值代入可求出最优值时的变量值：pse2009最优化42/53解之得：pse2009最优化43/53有约束几何规划优化问题的一般表达式为：pse2009最优化44/53对目标函数和约束条件分别应用式4和正则条件，得：pse2009最优化45/53将以上两式相乘得：pse2009最优化46/53-----正交条件pse2009最优化47/53

六、复合形法基本思想：来源于无约束问题最优化的单纯形法。此法只限于求解带有不等式约束条件的极值问题：步骤：（1）产生初始复合形n维空间中由n+2个顶点构成的多面体，称为复合形。之所以使用复合形，是为了避免单纯形容易产生退化即降维的缺点。要求复合形的各个顶点必须在可行域内。pse2009最优化48/53

六、复合形法（2）计算中心点产生初始复合形的方法：方法一：用随机数产生全部顶点；方法二：在可行域内人为选定一个顶点，其余顶点用随机数产生。；方法三：人为选定全部顶点。

先计算全部顶点的函数值，找出函数值最大的点xh（最差点），舍去，再用下式计算其余各顶点的中心点xc：pse2009最优化49/53

六、复合形法检查xc是否在可行域内。若在，求xh的反射点；否则，联结最好点xg（函数值最小的）与xc，在此区间内利用随机数构成新的复合形。（3）计算反射点用下式计算反射点xr：反射系数通常取1.3

检查xr是否在可行域内。若不在，将反射系数减半，重新计算xr，如此反复，直至xr在可行域内为止。由于采用了上述可变的反射系数，因此，复合形的延伸、收缩、压缩的方法就没必要采用了。pse2009最优化50/53（4）判断反射结果

六、复合形法

计算反射点的函数值，然后判断：若有，则认为反射成功，用xr代替xh，构成新的复合形。

若有，则可将反射系数减半，求新的反射点。若反射系数已经很小，则可用次坏点代替最坏点，重新计算中心点和反射点。（5）中止搜索给定收敛判据，计算精度要求，若有：中止搜索。pse2009最优化51/53七、可变容差法基本思想：来源于无约束问题最优化的单纯形法。此法适用于求解等式、不等式约束条件的极值问题：步骤：（1）产生初始多面体

通常多面体顶点选r＋1个（r＝n－m），但当r<2时，取r＝3。给定初始点和多面体边长。多面体边长的选取十分重要。边长大，易于进入可行域（由不等式构成的），但偏离梯度方向也大，不易收敛。为n维向量。pse2009最优化52/53七、可变容差法（2）计算多面体的形心点与复合形法相同：算出全部顶点的函数值，舍去最大值点