第四章：多维有约束优化方法4.1概述一、多维有约束问题的数学模型机械优化设计问题绝大多数是属于多维有约束非线性规划，其数学模型可表示为式中a i、b i分别为x i的下界和上界。
在求解约束优化问题时，虽然可以利用第三章的无约束优化方法，再加上约束的逻辑判断，使搜索点保持在可行域内逐步逼近约束最优解，但这样处理太复杂，缺乏严格的科学性。
因此，出现了一些直接求解约束优化问题的方法，其基本思路也是数值迭代法。
目前，约束优化方法虽然不如无约束优化方法那样多而完善，但对求解工程优化问题已有很多较好的方法。
二、多维有约束优化方法的分类（1)直接法直接法包括：网格法、分层降维枚举法、复合形法、随机试验法、随机方向法、可变容差法和可行方向法。
(2)间接法间接法包括：罚函数法、内点罚函数法、外点罚函数法、混合罚函数法、精确罚函数法、广义乘子法、广义简约梯度法和约束变尺度法。
直接法不需要利用目标函数和约束函数的梯度，就可直接利用迭代点和目标函数值的信息来构造搜索方向。
间接法要利用目标、约束函数的梯度，其中也包括利用差分来近似梯度的应用。
很多约束优化方法是先转变成无约束优化方法来求解。
可见，无约束优化方法也是也是约束优化方法的基础。
4.2复合形法一、方法概述基本思路：在可行域中选取K个设计点（n+1≤K≤2n）作为初始复合形的顶点。
比较各顶点目标函数值的大小，去掉目标函数值最大的顶点(称最坏点)，以坏点以外其余各点的中心为映射中心，用坏点的映射点替换该点，构成新的复合形顶点。
反复迭代计算，使复合形不断向最优点移动和收缩，直至收缩到复合形的顶点与形心非常接近，且满足迭代精度要求为止。
初始复合形产生的全部K个顶点必须都在可行域内。
二、初始复合形的产生复合形法是一种在可行域内收索最优点大直接解法。
(1)确定可行点作为初始复合形的第一个顶点：式中：通过调整随机数，使第一个初始点控制在可行域范围内。
(2)产生其余（K－1）个随机点。
(3)将非可行点调入可行域内。
若从第一个点到第个点均在可行域范围内，但第点不在可行域内，采取下列步骤使其调入可行域范围内：（a）先求出已在可行域范围内的q个点的中心：（b）将点向方向推进：＝＋0.5(－)若推进的点仍不在可行域范围内，则利用上式，使其继续向中心移动，直至新点成为可行点为止。
（c）继续依次检查，…，，若是可行点，即可作为复合形的顶点；若是不可行点，也将其调入可行域内。
三、迭代过程1.给定设计变量数目n、变量界限范围和精度要求，选定复合形顶点数目K （一般取K=2n）。
2.设计产生初始复合形的K个顶点。
3.计算复合形各顶点的目标函数值，找出最坏点、最好点及次坏点。
4.计算除最坏点以外其余各顶点的中心，并判别中心点的可行性。
当中心点为可行点时，转向下一步；否则须重新确定设计变量的上下限，然后重新构造初始复合形。
5.计算映射点，并检查和保证其在可行域内。
6.比较映射点与最坏点的目标函数值，构成新的复合形。
7.检验是否满足迭代终止条件：式中和分别表示第j个可行点的函数值和最坏点的函数值。
四、方法特点（1）复合形法是求解约束非线性最优化问题的一种直接方法，仅通过选取各顶点并比较各点处函数值的大小，就可寻找下一步的探索方向。
但复合形各顶点的选择和替换，不仅要满足目标函数值下降的要求，还应当满足所有的约束条件。
（2）复合形法适用于仅含不等式约束的问题。
4.3罚函数法一、基本思想罚函数法的原问题的数学表达式为：把它转化为一个等价的无约束优化问题的数学模型：式中——罚函数；和——分别为和的泛函（泛函可简单理解为这些函数根据解法要求构造另一些形式的函数，例如和分别为和的泛函）；和——分别为罚参数或罚因子，在迭代过程中总是某个正实数；和——称为惩罚项，恒为非负，其值随着k的增大越来越小，最后P和F值趋于相等，从而达到求解目的。
可以看出，罚函数法的一般求解过程是：定义和的形式，选择不同的和的递推序列和，每调整一次罚因子值，即对数学模型作一次无约束优化，得到一个无约束最优解。
随着罚因子的不断调整，得到无约束最优解的点列，不断逼近有约束的最优解。
当满足收敛准则后，则最后一个无约束最优解就是原问题的最优解。
所以它是一种序列求优过程，常称为“序列无约束极小化方法（Sequential Unconstrained Minimization）”，简称SUMT法。
根据约束形式和定义的泛函及罚因子的递推方法等不同，罚函数法可分为内点法、外点法和混合罚函数法三种。
这种方法是1968年由美国学者A．V．Fiacco和G．P．Mcormick提出的，把不等式约束引入数学模型中，为求多维有约束非线性规划问题开创了一个新局面。
二、内点法1.内点法泛函的构造内点法的数学模型仅适用于不等式约束，其模型格式是内点法的泛函可构造为各个约束函数的导数之和：＝或构造为各个约束函数导数的自然对数之和：=根据泛函构造形式的不同，罚函数的形式可写为：或罚因子的作用是：由于内点法只能在可行域内迭代，而最优解很可能在可行域内靠近边界处或就在边界上，此时尽管泛函的值很大，但罚因子是不断递减的正值，经多次迭代，接近最优解时，惩罚项已是很小的正值。
2．迭代过程（1）在可行域内选一个严格初始点X(0)，最好不要靠近任一约束边界。
（2）选一个适当大的初始罚因子r(0)，用无约束优化方法寻求罚函数的极小点X0*，再选一个罚因子递减率c(0<c<1)，求递减后的罚因子r(1)=cr(0)，以X0*为初始点，再用无约束优化方法求罚函数的极小点X1*。
（3）重复步骤（2），直到满足收敛条件，终止迭代。
3．关于内点法中几个问题的讨论（1）初始点X(0)的选择：初始点必须满足，且最好在可行域内离边界远一点，使一开始作无约束求优时，泛函的值较小，收敛快，成功的机会大。
（2）初始罚因子的选择：r(0)不宜过小。
一般先以一个r(0)值进行计算，由计算结果调整其大小。
（3）递减系数c的选择：一般来说，取0.1。
（4）在一定条件下有如下规律：(a)为严格单调下降函数，即有：>>>…，且(b)为单调非增数列，即：且(c)泛函为单调非降数列，且(5)用内点法求P的无约束极小，只能在可行域内迭代；但沿某一方向作一维搜索寻找极小点区间时可能超出可行域，此时必须把步长收缩到可行域内，取一个P函数值有所下降的点作为一维搜索所得点。
每作一次一维搜索，都要检查是否有破坏约束，如有破坏，应把寻优区间收缩。
4．内点法的迭代终止准则（1）前后两次无约束极小点之间的距离满足精度要求：或相对误差：（2）相邻两点函数值的绝对误差满足：或相邻两点函数值差的相对误差满足：（3）相邻两点罚函数的相对误差满足：（4）及：同时满足三、外点法1．外点法的泛函和罚函数的构造上节介绍的内点法，对工程优化设计有一定优点，可以得到多个可行设计方案。
但必须选择一个严格初始内点。
目前，从理论上和程序设计上虽可以做到由程序自动寻找初始内点，但当原问题的可行域很狭窄，寻找初始内点可能会失败，或仅能找到一个离边界很近的初始内点，使迭代过程很长，甚至失败；此外，不能用来求解具有等式约束的优化问题。
下面介绍的外点法可以克服这些不足。
外点法的数学模型为：对于不等式约束，泛函可这样构造：=对于等式约束，泛函可这样构造：=所以，罚函数的构造形式为：式中罚因子M（k）是正的递增数列，其递增率c’>1，即：M（k）＝c’M （k－1）。
当X使全部约束满足时，惩罚项的值为零，不起惩罚作用；当X使全部约束不同时满足时，惩罚项的值是较大的正值，起较大的惩罚作用。
作用，就把原来的约束问题变为：的求无约束极小问题。
随着罚因子M（k）的递增，迫使惩罚项趋于零，泛函值趋于零，惩罚项也趋于零，最后逼近真值。
故外点法是从可行域外经若干次迭代求无约束极小二逐渐逼近原问题的极小点。
2．迭代过程（1）任选一个初始点X(0)（可以是内点，也可以是外点），再选一个适当大的初始罚因子M(0)和递增率c’，用无约束优化方法求极小点X0*值。
（2）以X0*作为下一个迭代的初始点，取M(1)＝c’M(0)，求极小点X1*值。
（3）M(k)＝c’M(k-1)，逐次递增罚因子，依次取上次极小点作为本次迭代的初始点，重复步骤（2），直至满足终止准则（终止准则与内点法相同）。
3．关于外点法中几个问题的讨论（1）初始点的选取：虽可任选，但应选择有定义的初始点。
（2）初始罚因子的递增率的选择：一般情况下，总是先取适当小的罚因子，再根据运算结果决定如何调整。
（3）在一定条件下，外点法有如下规律：(a)为单调非降数列，即有：且(b)为严格单调增加数列，即：且(c)泛函+为单调非增数列，且：limM(k){+}=0（4）最优解的特点外点法是从可行域外部逐步向可行域逼近。
如原问题的最优解在可行域内部，则可收敛到可行域内。
但对于约束极值，其精确解经常是在一个或几个约束边界上，用外点法不可能收敛到边界上，只能收敛到边界外某个精确的小区域中。
因此，为克服此缺点，可将某些性能约束紧缩一个裕量，即。
4．内点法和外点法的简单比较内点法的特点：1)初始点必须为严格内点2)不适于具有等式约束的数学模型3)迭代过程中各个点均为可行设计方案4)一般收敛较慢5)初始罚因子要选择得当6)罚因子为递减，递减率c有0<c<1外点法的特点：1)初始点可以任选，但应使各函数有定义2)对等式约束和不等式约束均可适用3)仅最优解为可行设计方案4)一般收敛较快5)初始罚因子要选择得当6)罚因子为递增，递增率c’有c’>1四、混合罚函数法1．泛函和罚函数的构造混合罚函数法在一定程度上综合了内点法和外点法的优点，克服某些缺点，可处理等式约束和不等式约束的优化问题。
混合罚函数法的构造形式与外点法的区别是：选定初始点后，对于已满足的不等式约束用内点法构造惩罚项，对于等式和未被满足的不等式约束按外点法构造惩罚项。
混合罚函数法的具体形式是式中为对于已被初始点满足的不等式约束按内点法构造的泛函；为对于未被初始点满足的不等式约束按外点法构造的泛函：为按外点法构造的等式约束的泛函。
为罚因子，对内点法构造的惩罚项，是递减正数列；按外点法构造的惩罚项，其罚因子应为递增的正数列。
为简化程序，取。
下标集合定义为：2．用外推法改进求无约束极小化的初始点用外推法改进无约束极小化的初始点以加快收敛，同时可能对最优解作进一步改善，是混合罚函数法的重要特点和技巧，其基本思想是：利用少数几个值求得相应的序列{X k*}后，由级数展开作函数逼近，向→0的方向外推，求得的外推点虽非原问题的最优解，但一般总是更为靠近最优解的点，然后以外推点作为下一次无约束极小化的初始点，可以减少作无约束极小化的次数，更快地收敛到原问题的最优解。
