3数学规划法.pptx

结构优化设计南京航空航天大学飞机设计技术研究所第三章第三章数学规划法数学规划法3.1 数学规划问题的分类及解法数学规划问题的分类及解法I.数学规划问题的一般提法是：数学规划问题的一般提法是：寻找一组设计变量变寻找一组设计变量变 X=X1,X2,X3,XnT 使得使得 f(x)min s.t.g i(X)0 i=1,2,m g e(X)=0 e=1,2,n 其中其中,X-设计变量设计变量 f(x)-目标函数目标函数 g i(X)和和 g e(X)-约束条件约束条件(1)按约束的有无，可分为：按约束的有无，可分为：无约束最优化问题无约束最优化问题有约束最优化问题有约束最优化问题准无约束最优化问题准无约束最优化问题II.数学规划问题的分类数学规划问题的分类线性规划线性规划非线性规划非线性规划如果目标函数与约束函数都是凸函数，则称为凸规划如果目标函数与约束函数都是凸函数，则称为凸规划如果目标函数是二次函数而约束函数是一次函数，则称如果目标函数是二次函数而约束函数是一次函数，则称为二次规划为二次规划如果设计变量只允许取整数，则称为整数规划如果设计变量只允许取整数，则称为整数规划如果在目标函数和约束函数中包含具有随机性质的参数如果在目标函数和约束函数中包含具有随机性质的参数则称为随机规划则称为随机规划(2)按目标函数和约束函数是否为线性，可分为：按目标函数和约束函数是否为线性，可分为：对于线性规划问题，单纯形法十分有效对于线性规划问题，单纯形法十分有效无约束非线性规划问题无约束非线性规划问题不利用梯度的算法：不利用梯度的算法：0.618法、单纯形法、法、单纯形法、Powell法和随机搜法和随机搜索法索法利用梯度的算法：最速下降法、共轭梯度法、牛顿法、拟牛利用梯度的算法：最速下降法、共轭梯度法、牛顿法、拟牛顿法顿法有约束非线性规划问题有约束非线性规划问题转化法：内罚函数法、外罚函数法转化法：内罚函数法、外罚函数法直接法：可行方向法、最佳矢量法、梯度投影法直接法：可行方向法、最佳矢量法、梯度投影法序列近似规划法：序列二次规划方法、序列线性规划方法序列近似规划法：序列二次规划方法、序列线性规划方法III.数学规划问题的求解数学规划问题的求解IV.无约束优化问题的基本下降算法无约束优化问题的基本下降算法原问题：原问题：min f(x)x=x1,x2,x3,xnT(1)求解其最优化的必要条件：求解其最优化的必要条件：f(x*)=0 (2)但是式但是式(2)是一个非线性方程组，与求解原问题同样困难。是一个非线性方程组，与求解原问题同样困难。在数学规划法中，是用迭代下降的算法找到极小值点。在数学规划法中，是用迭代下降的算法找到极小值点。即先假定一个初始设计即先假定一个初始设计x(0),然后在第然后在第k次迭代次迭代(k=0,1,2,),用用x(k+1)代替代替x(k)，要求，要求x(k+1)比比x(k)更接近最更接近最优解。对于无约束优化问题，也就是要求目标函数有优解。对于无约束优化问题，也就是要求目标函数有所下降，即所下降，即 f(x(k+1)f(x(k)在数学规划中，一般迭代格式可以写成：在数学规划中，一般迭代格式可以写成：x(k+1)=x(k)+P(k),-步长步长(Step length)，正标量，正标量 P(k)-方向向量方向向量(Directional vector)因此目标函数的下降要求可以改写成：因此目标函数的下降要求可以改写成：f(x(k)+P(k)f(x(k)如果函数如果函数f(x)在在x(k)是一次可微的，则对足够下小的是一次可微的，则对足够下小的 有：有：f(x(k)+P(k)-f(x(k)Tf(x(k)P(k)0由于由于 是正标量，所以：是正标量，所以：Tf(x(k)P(k)0这说明搜索方向应该和目标函数负梯度方向夹角小于这说明搜索方向应该和目标函数负梯度方向夹角小于90，这样的方向称之为下山方向。，这样的方向称之为下山方向。基本的下降算法：基本的下降算法：1)令令k=0,给定初始解给定初始解x(0)；2)*求搜索方向求搜索方向P(k),使使Tf(x(k)P(k)0它意味最优化必要条件已经以足够的精度得到满足。它意味最优化必要条件已经以足够的精度得到满足。n前后两次迭代所得的设计点之间的距离小于指定的小前后两次迭代所得的设计点之间的距离小于指定的小量量n前后两次迭代目标函数值下降的相对值已经足够小前后两次迭代目标函数值下降的相对值已经足够小n工程结构优化时常采用固定的迭代次数作为停止迭代工程结构优化时常采用固定的迭代次数作为停止迭代准则准则3.2 一维搜索方法一维搜索方法一维搜索方法是数学规划方法的一种基本一维搜索方法是数学规划方法的一种基本方法，也是其它优化方法的一种中间手方法，也是其它优化方法的一种中间手段段i.0.618法法0.618法的基本思想法的基本思想是通过取试探点和进是通过取试探点和进行函数值比较，使包行函数值比较，使包含极小点的搜索区间含极小点的搜索区间不断缩短，从而各点不断缩短，从而各点可以看作为极小点的可以看作为极小点的近似。这类方法仅需近似。这类方法仅需计算函数值，用途广计算函数值，用途广泛，尤其适用于非光泛，尤其适用于非光滑函数形式。滑函数形式。ii.插值法插值法插值法是一类重要的一维搜索方法。其基本思想插值法是一类重要的一维搜索方法。其基本思想是在搜索区间中不断用低次（通常不超过三次）是在搜索区间中不断用低次（通常不超过三次）多项式来近似目标函数，并逐渐用插值多项式的多项式来近似目标函数，并逐渐用插值多项式的极小点来逼近一维搜索问题。当函数具体比较好极小点来逼近一维搜索问题。当函数具体比较好的解析性质时，插值法比直接方法效果更好。的解析性质时，插值法比直接方法效果更好。一点二次插值法（牛顿法）一点二次插值法（牛顿法）二点二次插值法二点二次插值法I二点二次插值法二点二次插值法II（割线法）（割线法）不同搜索方法比较不同搜索方法比较连续性连续性收敛性收敛性适用范围适用范围0.618法法0阶0.618最优点在所选最优点在所选最优点在所选最优点在所选区间中区间中区间中区间中牛顿法牛顿法2阶2靠近最优点靠近最优点靠近最优点靠近最优点二点二次插值法二点二次插值法1阶1.618靠近最优点靠近最优点靠近最优点靠近最优点割线法割线法1阶1.618靠近最优点靠近最优点靠近最优点靠近最优点3.3 确定搜索方向的算法确定搜索方向的算法ni.最速下降法最速下降法前面已经知道，目标函数沿负梯度方向下降最快，因此前面已经知道，目标函数沿负梯度方向下降最快，因此取负梯度方向为搜索方向，即：取负梯度方向为搜索方向，即：P(k)=-f(x(k)x(k+1)x(k)-f(x(k)基本算法：基本算法：n给定初始点给定初始点x(0)，令，令k=0；n计算计算f(x(k)若若f(x(k)成立，则成立，则x*=x(k)，停机，停机，否则转下一步；否则转下一步；n求求P(k)=-f(x(k)，求，求 (k)=min f(x(k)-f(x(k)；n调整设计调整设计x(k+1)x(k)-f(x(k)，回第，回第(2)步。步。讨论：讨论：1)在前后两次迭代过程中，搜索方向是相互正交的，在前后两次迭代过程中，搜索方向是相互正交的，z这是因为在一维搜索中这是因为在一维搜索中x(k+1)x(k)-(k)f(x(k)，而而(k)是由是由()=0求得，即求得，即()=-f(x(k)-(k)f(x(k)f(x(k)=-f(x(k)f(x(k)=0 由此可见，最速下降法走的是由此可见，最速下降法走的是“之之”字形字形2)最速下降法是一阶线性收敛，收敛速度较慢。最速下降法是一阶线性收敛，收敛速度较慢。3)最速下降法与变量长度有关，即与变量尺度关系很最速下降法与变量长度有关，即与变量尺度关系很大。大。4)最速下降法迭代过程简单，不受初始点位置限制。最速下降法迭代过程简单，不受初始点位置限制。因此虽然该方法有收敛慢，依赖于变量的尺度等缺因此虽然该方法有收敛慢，依赖于变量的尺度等缺点，但这些缺点往往在最优点附近表现得才明显。点，但这些缺点往往在最优点附近表现得才明显。ii.Newton法法n从从Newton法迭代公式的推导过程可知，对任何二次法迭代公式的推导过程可知，对任何二次函数，用函数，用Newton法求极小点，只需迭代一次（如果法求极小点，只需迭代一次（如果该二次函数有极小点存在的话）该二次函数有极小点存在的话）基本算法：基本算法：n给定初始点给定初始点x(0)，令，令k=0；n计算计算f(x(k)若若f(x(k)成立，则成立，则x*=x(k)，停机，停机，否则转下一步；否则转下一步；n求求P(k)=-2f(x(k)-1f(x(k)；n调整设计调整设计x(k+1)x(k)+P(k)，回第，回第(2)步。步。Newton法为二阶收敛，收敛较快是它最大优点，另外法为二阶收敛，收敛较快是它最大优点，另外Newton法与变量尺度无关，如果函数本身为二次函法与变量尺度无关，如果函数本身为二次函数，则只要一次迭代即求得最优解。但数，则只要一次迭代即求得最优解。但Newton法对法对初始点要求较高，一定要在很靠近最优点附近选取初始点要求较高，一定要在很靠近最优点附近选取最优点。同时最优点。同时Newton法要求二阶导数矩阵，工作量法要求二阶导数矩阵，工作量较大，且要求该矩阵的逆，这就要求较大，且要求该矩阵的逆，这就要求2f(x(k)是非奇是非奇异的异的iii.变尺度法变尺度法无约束优化的迭代公式为：无约束优化的迭代公式为：x(k+1)=x(k)+(k)H(k)P(k)对最速下降法对最速下降法H(k)=I，P(k)取负梯度，取负梯度，(k)用一维搜索用一维搜索对对Newton法法H(k)=2f(x(k)-1，P(k)取负梯度，取负梯度，(k)=1最速下降法收敛太慢，最速下降法收敛太慢，Newton法收敛最快，但要计算二法收敛最快，但要计算二阶导数并要求求逆，工作量大，有时还会碰到不可克阶导数并要求求逆，工作量大，有时还会碰到不可克服的困难。服的困难。因此人们想若因此人们想若H(k)的选取不需要计算二阶导数矩阵和求逆，的选取不需要计算二阶导数矩阵和求逆，而又能逼近而又能逼近2f(x(k)-1，那么所确定的算法可能会类，那么所确定的算法可能会类似于似于Newton法收敛很快。基于这种想法，发展了一种法收敛很快。基于这种想法，发展了一种拟拟Newton法。法。H(k)构造方法不同，有不同的拟构造方法不同，有不同的拟Newton法，其中法，其中DFP算法就是这类算法中最为著名的。算法就是这类算法中最为著名的。拟拟Newton法保留了法保留了Newton法的快速收敛性，而又不直接法的快速收敛性，而又不直接求二阶导数，受到了人们欢迎。求二阶导数，受到了人们欢迎。H(k)的产生采用迭代法逐步构成的产生采用迭代法逐步构成先给定先给定H(0)，一般取单位矩阵，则，一般取单位矩阵，则H(1)=H(0)+E(0),H(2)=H(1)+E(1),H(3)=H(2)+E(2),对于对于DFP算法算法对于对于BFGS算法算法3.4 可行方向法可行方向法I.概述概述结构优化的一般数学规划表达式：结构优化的一般数学规划表达式：寻找一组设计变量寻找一组设计变量 X=(X1,X2,Xn)T min f(X)X E n s.t.g i(X)0 i=1,m 设计变量的迭代公式设计变量的迭代公式-X(+1)=X()+P()从从 X()调参至调参至 X(+1),要求设计点可行要求设计点可行,并且目标函数还要下降并且目标函数还要下降,即满足可用可行性条件即满足可用可行性条件:1.满足可用性条件满足可用性条件(Usability condition)f(X()T p()0 2.满足可行性条件满足可行性条件(Feasibility condition)g i(X()+P()0或者或者 g i(X()T P()0 这两个条件的几何意义是这两个条件的几何意义是:目标函目标函数梯度向量和约束条件梯度向量与数梯度向量和约束条件梯度向量与方向向量之间的夹角均大于方向向量之间的夹角均大于900.根据上述要求根据上述要求,可以有三条路线来可以有三条路线来完成调参完成调参:1.沿等重线沿等重线(面面)侧移；侧移；2.沿约束边界侧移梯度投影沿约束边界侧移梯度投影法法(Gradient projection method)；3.沿可用可行方向沿可用可行方向 P 侧移可侧移可行方向法行方向法(Feasible directional method)。由此构成三种不同形式的可行方向由此构成三种不同形式的可行方向法。法。II.最佳矢量法最佳矢量法 Optimum vector method交替使用两种行进方向交替使用两种行进方向:1.当设计点不在约束边界上时当设计点不在约束边界上时,采用最速下降法采用最速下降法(Steepest descent method)或最速上升法或最速上升法(Steepest ascent method).P()=-f(X()or P()=f(X()X(+1)=X()-f(X()-最速下降最速下降 X(+1)=X()+f(X()-最速上升最速上升 其中步长按其中步长按 采用试凑法采用试凑法.=2 0(在可行域内在可行域内)=(1/2)(+1)0 2.从约束边界点开始从约束边界点开始,沿目标函数等值面沿目标函数等值面(线线)内向可行域内向可行域中侧移中侧移,使设计点离开约束边界进入可行域使设计点离开约束边界进入可行域.n两种调参方向交替进行，直到最优点为止。两种调参方向交替进行，直到最优点为止。n这是一种较早期的方法，迭代次数多，代价大，步长这是一种较早期的方法，迭代次数多，代价大，步长试凑，有太多的随意性。试凑，有太多的随意性。III.梯度投影法梯度投影法 Gradient projection methodnRosen 的梯度投影法适用于目标函数为非线性、约束的梯度投影法适用于目标函数为非线性、约束条件为线性的结构优化设计。条件为线性的结构优化设计。n一般结构优化设计问题，多取重量为目标函数，它是一般结构优化设计问题，多取重量为目标函数，它是设计变量的线性函数，约束条件是应力、位移、稳定，设计变量的线性函数，约束条件是应力、位移、稳定，均为设计变量的非线性函数。均为设计变量的非线性函数。n如果引入倒数设计变量，并把约束条件经过显式线性如果引入倒数设计变量，并把约束条件经过显式线性近似处理，则问题正好符合梯度投影法要求。近似处理，则问题正好符合梯度投影法要求。1.给定初始设计给定初始设计,进行结构分析进行结构分析;2.在倒数变量空间进行射线调参在倒数变量空间进行射线调参,将设计点拉到约将设计点拉到约束边界上束边界上(最临界约束边界最临界约束边界);射线调参：在优化设计调参过程中，按所有约束的射线调参：在优化设计调参过程中，按所有约束的最大约束比，将设计点一次性拉到所对应的优化最大约束比，将设计点一次性拉到所对应的优化边界上，这种调参路线正好是过设计点与坐标原边界上，这种调参路线正好是过设计点与坐标原点的连线，并与最临界的约束相交。点的连线，并与最临界的约束相交。3.在倒数变量空间在倒数变量空间,将所有有效约束显式线性近似将所有有效约束显式线性近似;4.用梯度投影法调参用梯度投影法调参,直到获得最优解为止直到获得最优解为止.i.梯度投影法调参的具体过程梯度投影法调参的具体过程ii.梯度投影法调参梯度投影法调参(1)侧移向量的计算侧移向量的计算由推广的由推广的K-T 条件知，条件知，d 向量沿约束曲面的切线方向量沿约束曲面的切线方向。现约束条件变为超平面，向。现约束条件变为超平面，d 即在这个超平面内。即在这个超平面内。在倒数变量空间，有在倒数变量空间，有 G(Z)+d=-f(Z)G(Z)Td=0由此得：由此得：=-G(Z)T G(Z)-1 G(Z)T f(Z)d =-P f(Z)P =I -G(Z)G(Z)T G(Z)-1 G(Z)T其中其中P为正交投影算子，即目标函数梯度投影到有效约束为正交投影算子，即目标函数梯度投影到有效约束边界面上去，边界面上去，梯度投影法由此而得名。梯度投影法由此而得名。令调参向量令调参向量 p()=d=-P f(Z)Z(+1)=Z()+P()步长可以有两种方法确定步长可以有两种方法确定:(1)沿沿 P()(即即d)向量方向对向量方向对 求一维搜索最小点。求一维搜索最小点。这种方法对无约束条件下比较有效；这种方法对无约束条件下比较有效；(2)利用可行性条件求利用可行性条件求 。按按 P()行进到两条线性约束的交点时行进到两条线性约束的交点时,首先要计算出下首先要计算出下一轮侧移向量一轮侧移向量,并加以判断并加以判断:若若 f(Z(+1)T P(+1)0 可沿可沿 P(+1)进一步调参进一步调参;若若 f(Z(+1)T P(+1)0 则不能继续调参则不能继续调参,要用上一个要用上一个设计点设计点 Z()沿沿 P()进行一维搜索求进行一维搜索求 Z*,或者利用或者利用 f(Z*)T P(+1)=0,其中令其中令 Z*=Z()+(+1)P(+1),代入式中代入式中,即可解得即可解得 (+1).(2)步长的确定步长的确定(3)收敛性判别收敛性判别 在最优点处的收敛条件在最优点处的收敛条件 当当 j*0 ,j=1,NC 对所有有效约束对所有有效约束|d*|=0 非线性约束下梯度投影法困难非线性约束下梯度投影法困难IV.可行方向法可行方向法Feasible Directional Methods是由是由G.Zoutendijk 方法发展而来的一种可行方向方法方法发展而来的一种可行方向方法.f(X()T P()0 g j(x()T P()0,j=1,NC 其中其中 P()En.若使上述条件更严格一点若使上述条件更严格一点,令令 E1,上式变为上式变为 f(X()T P()g j(x()T P(),j=1,NC 0 由此得一个由此得一个下降的可行方向下降的可行方向P().n对推离因子对推离因子(Pushoff factor)j 的讨论的讨论:(1)它有效地把设计推离有效约束界面它有效地把设计推离有效约束界面;(2)j =0,P()倾向于有效约束倾向于有效约束,最终与之相切最终与之相切;(3)j 1,即即 j 足够大足够大.P()倾向于目标函数等值线倾向于目标函数等值线;(4)小的小的 j 值将使目标函数值迅速减小值将使目标函数值迅速减小,但很容易到达但很容易到达同一约束边界同一约束边界,即调参步子不可能大即调参步子不可能大;(5)大的大的 j 可使调参步子大可使调参步子大,但目标函数值减小缓慢但目标函数值减小缓慢;(6)j =1,对大多数问题可获得两方面都有利的效果对大多数问题可获得两方面都有利的效果.这里取这里取 j 为有效约束和约束公差为有效约束和约束公差 的平方函数的平方函数上述为典型的线性规划问题上述为典型的线性规划问题,可用单纯型法求解可用单纯型法求解.步长步长 的选取的选取:(1)一维寻查一维寻查(对无约束问题对无约束问题);(2)计算最小截断距离计算最小截断距离(对带约束的优化问题对带约束的优化问题,此此法更合适法更合适)。可行方向法所计算的子规划问题可行方向法所计算的子规划问题,不是求解问题本身不是求解问题本身,而而是做一个子规划是做一个子规划,求求 P()!3.5 序列无约束优化方法序列无约束优化方法(SUMT)为了充分运用无约束优化方法来解决有约束的优化问题，为了充分运用无约束优化方法来解决有约束的优化问题，一种重要的途径是把原有约束问题转化为无约束最优一种重要的途径是把原有约束问题转化为无约束最优化问题来求解，这里的序列无约束优化方法便是其中化问题来求解，这里的序列无约束优化方法便是其中的一种方法。的一种方法。考虑结构优化的数学规划表达式：考虑结构优化的数学规划表达式：寻找一组设计变量寻找一组设计变量 X=(X1,X2,Xn)T min f(X)X E n s.t.g i(X)0 i=1,m 其中的约束函数其中的约束函数g i(X)可以以一定的方式附加到原问题可以以一定的方式附加到原问题的目标函数的目标函数f(X)上，从而得到一系列的无约束优化问上，从而得到一系列的无约束优化问题：题：min F(x)=f(x)+罚项（或障碍项）罚项（或障碍项）使它在转化过程中逐步做到满足原有约束条件并最终归使它在转化过程中逐步做到满足原有约束条件并最终归结为原问题的同一最优解，这就是方法的实结为原问题的同一最优解，这就是方法的实质。质。罚项的意义：当设计变量不满足约束条件或靠近约束边罚项的意义：当设计变量不满足约束条件或靠近约束边界时，其数值变得很大，使目标函数界时，其数值变得很大，使目标函数F(x)与与f(x)相差很相差很远，即受到不满足约束条件的惩罚。远，即受到不满足约束条件的惩罚。I.内罚函数法内罚函数法设原非线性规划问题为：设原非线性规划问题为：寻找，使得寻找，使得 min f(X)X E n s.t.g i(X)0 i=1,m 用内罚函数则转化为下述无约束极小化问题用内罚函数则转化为下述无约束极小化问题内点法的一个显著特点是，设计点要始终落在可内点法的一个显著特点是，设计点要始终落在可行域内，因此而得名内点法。行域内，因此而得名内点法。n罚项具有下述性质：罚项具有下述性质：(1)当远离约束边界时，较小；当远离约束边界时，较小；(2)当靠近约束边界时，就变得很大，甚至趋于无穷。当靠近约束边界时，就变得很大，甚至趋于无穷。由下图可知：由下图可知：原规划最优点在原规划最优点在x*，罚函数，罚函数F(x)的最优解在罚函数等值线中心点，当的最优解在罚函数等值线中心点，当较大时，该中心点离原规划较大时，该中心点离原规划x*较远，随着较远，随着r的减少，中心点离的减少，中心点离x*的距离越来越近。的距离越来越近。因此可以从一个单调下降的系数序列因此可以从一个单调下降的系数序列rk中中逐个选取系数逐个选取系数rk,求得相应目标函数求得相应目标函数F(x,rk)的极小值及设计最优点的极小值及设计最优点x(K)的序列的序列x(1),x(2),x(K)则原规划的最优点则原规划的最优点x*对应于下述极限对应于下述极限II.外罚函数法外罚函数法设原非线性规划问题为：设原非线性规划问题为：寻找，使得寻找，使得 min f(X)X E n s.t.g i(X)0 i=1,m 用外点罚函数则转化为下述无约束极小化问题用外点罚函数则转化为下述无约束极小化问题其中罚项，其含义为在其中罚项，其含义为在g i(X)和之间挑选大者。随值增大，和之间挑选大者。随值增大，F(x)值也增大，即偏值也增大，即偏离离f(x)越远，这可看成对于不满足约束条件的一种惩罚。越远，这可看成对于不满足约束条件的一种惩罚。如图所示，原规划最优解在如图所示，原规划最优解在x*点，而罚函数点，而罚函数F(x,M)的最的最优解在罚函数等值线中心优解在罚函数等值线中心x*处，两者有一定的距离。与处，两者有一定的距离。与内点法不同，内点法不同，x*在不可行域中，但处理问题的方式有相在不可行域中，但处理问题的方式有相同之处。同之处。因此可以从一个单调上升的系数序列因此可以从一个单调上升的系数序列Mk中中逐个选取系数逐个选取系数Mk,求得相应目标函数求得相应目标函数F(x,Mk)的极小值的极小值及设计最优点及设计最优点x(K)的序列的序列x(1),x(2),x(K)，则原规划的，则原规划的最优点最优点x*对应于下述极限对应于下述极限III.内点法和外点法的比较内点法和外点法的比较内点法外点法1)设设计计点点一一定定要要是是可可行行内内点点，要要控制设计点不能超过约束边界；控制设计点不能超过约束边界；2)内内点点法法只只能能处处理理不不等等式式约约束束问问题；题；3)内内点点法法求求解解的的极极小小点点序序列列总总位位于于可可行行域域内内，但但总总不不在在约约束束边边界界上上，对对某某些些工工程程设设计计问问题题，可可任任选选一一个个最最优优解解作作为为较较好好的的设计；设计；4)内内点点法法尽尽管管F(x,r)和和f(x)的的偏偏导导数数阶阶数数相相同同，但但靠靠近近约约束束边边界界处并不连续。处并不连续。1)设设计计点点的的运运动动轨轨迹迹位位于于可可行行域域外外，迭迭代代中中向向可可行行域域靠靠近近，最最后趋近最优点；后趋近最优点；2)可可以以处处理理不不等等式式约约束束，也也可可以以处理等式约束；处理等式约束；3)其其极极小小点点序序列列大大部部分分落落在在不不可可行行域域中中，只只有有当当某某些些约约束束满满足足时时，可可能能到到达达约约束束边边界界上上，但但其中间解均是不可行的；其中间解均是不可行的；4)外点法有连续的一阶偏导数。外点法有连续的一阶偏导数。3.6 序列二次规划方法序列二次规划方法考虑等式约束的优化问题考虑等式约束的优化问题 min f(X)X E n s.t.g j(X)=0 j=1,m 定义其定义其拉格朗奇函数为拉格朗奇函数为根据根据Kuhn-Tucker定理，其稳定点的非线性方程组为：定理，其稳定点的非线性方程组为：其解用其解用Newton-Raphson迭代方法求解：迭代方法求解：其中：其中：其中：其中：上式可以进一步修改为：上式可以进一步修改为：上式可以进一步修改为：上式可以进一步修改为：上式又可以看成是一个下面二次规划的的上式又可以看成是一个下面二次规划的的上式又可以看成是一个下面二次规划的的上式又可以看成是一个下面二次规划的的Kuhn-TuckerKuhn-Tucker条条条条件，即：件，即：件，即：件，即：若该规划满足下列条件：若该规划满足下列条件：若该规划满足下列条件：若该规划满足下列条件：i i）约束函数）约束函数）约束函数）约束函数g g在在在在X Xk k的的的的JacobiJacobi矩阵矩阵矩阵矩阵A(XA(Xk k)行满秩；行满秩；行满秩；行满秩；ii ii）矩阵）矩阵）矩阵）矩阵 在约束函数在约束函数在约束函数在约束函数g g的切空间上是正定的。的切空间上是正定的。的切空间上是正定的。的切空间上是正定的。那么该规划有唯一的解那么该规划有唯一的解那么该规划有唯一的解那么该规划有唯一的解 ，其存在一个新的向量，其存在一个新的向量，其存在一个新的向量，其存在一个新的向量 使得：使得：使得：使得：那么：那么：那么：那么：考虑一般形式的约束优化问题：考虑一般形式的约束优化问题：考虑一般形式的约束优化问题：考虑一般形式的约束优化问题：在给定点在给定点在给定点在给定点 之后，将约束函数线性化，并且之后，将约束函数线性化，并且之后，将约束函数线性化，并且之后，将约束函数线性化，并且对对对对LagrangeLagrange函数进行二次多项式近似，得到如下函数进行二次多项式近似，得到如下函数进行二次多项式近似，得到如下函数进行二次多项式近似，得到如下形式的二次规划子问题：形式的二次规划子问题：形式的二次规划子问题：形式的二次规划子问题：步骤步骤步骤步骤1 1：初始化：初始化：初始化：初始化步骤步骤步骤步骤2 2：计算改进方向：计算改进方向：计算改进方向：计算改进方向步骤步骤步骤步骤3 3：收敛性检验：收敛性检验：收敛性检验：收敛性检验步骤步骤步骤步骤4 4：确定罚因子：确定罚因子：确定罚因子：确定罚因子步骤步骤步骤步骤5 5：步长选择：步长选择：步长选择：步长选择步骤步骤步骤步骤6 6：改进迭代点并校正：改进迭代点并校正：改进迭代点并校正：改进迭代点并校正HesseHesse矩阵矩阵矩阵矩阵算法终止算法终止算法终止算法终止