第六章-约束优化方法

第六章约束优化方法6.1概述6.2随机方向法6.3复合形方法6.4可行方向法6.5惩罚函数法6.6增广乘子法6.7遗传优化算法机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为min(),..()01,2,,()01,2,,njkfRstgjmhklxxxx§6.1概述§6.1概述直接解法：随机方向搜索法、复合形法、可行方向法间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法一.有约束问题解法分类：二.直接解法的基本思想：合理选择初始点，确定搜索方向，在可行域中寻优，经过若干次迭代，收敛至最优点。xk+1=xk+αkdkdk::可行搜索方向。即设计点沿该方向作微量移动时,目标函数值将下降,且不会超出可行域直接解法通常适用于仅含不等式约束的问题§6.1概述特点：①由于求解过程在可行域内进行；无论迭代计算何时终止,都可以获得一个比初始点好的设计点;②若可行域是凸集，目标函数是定义在凸集上的凸函数，则收敛到全局最优点；否则，结果与初始点有关。凸可行域非凸可行域§6.1概述)(),,(21xfrrx)]([)]([1211xhHrxgGrpvvmuu原理：将有约束优化问题转化为无约束优化问题来解决。方法：以原目标函数和加权的约束函数共同构成一个新的目标函数Φ(x,r1,r2)，成为无约束优化问题。通过不断调整加权因子，产生一系列Φ函数的极小点序列x(k)*(r1(k),r2(k))k=0,1,2…，逐渐收敛到原目标函数的约束最优解。其中：新目标函数：三.间接解法的基本思想：惩罚因子：r1,r2§6.2随机方向法一.基本思想：随机产生初始点，随机产生若干个搜索方向dk，并从中选择一个能使目标函数值下降最快的方向作为可行搜索方向进行搜索。确保：①新迭代点在可行域中②目标函数值的下降性。x(0)x(L)x(1)x*二.初始点的选择随机方向法的初始点x0必须是一个可行点，既满足全部不等式约束条件。初始点可以通过随机选择的方法产生。1）输入设计变量的下限值和上限值，即iiiaxb2）在区间（0，1）内产生n个伪随机数iq3）计算随机点x的各分量()iiiiixabaq4）判别随机点x是否可行，若随机点可行，用x0←x为初始点；若非可行点，转到步骤2）重新产生随机点，直到可行为止。§6.2随机方向法三.可行搜索方向的产生从k个随机方向中，选取一个较好的方向。121211...jjjnjjinirrerrjir1）在(-1,1)区间内产生伪随机数，得随机单位向量je2)取一试验步长a0，按下式计算k个随机点00jjxxae§6.2随机方向法3）检验k个随机点是否为可行点，除去非可行点，计算余下的可行点的目标函数值，比较其大小，选出目标函数最小的点xL。4)比较xL和x0两点的目标函数值:①若f(xL)f(x0)，则取xL和x0连线方向为可行搜索方向；②若f(xL)≥f(x0)，则缩小步长α0，转步骤1）重新计算，直至f(xL)f(x0)为止。③α0缩小到很小仍然找不到一个xL，使f(xL)f(x0),则说明x0是一个局部极小点，更换初始点转步骤1）。§6.2随机方向法产生可行搜索方向的条件为：00min1,2,...,LjLjLgxfxfxjkfxfx则可行搜索方向为：0Ldxx四、搜索步长的确定步长由加速步长法确定：τ为步长加速系数，一般取1.3§6.2随机方向法五.计算步骤1)选择一个可行的初始点x0;2)产生k个n维随机单位向量ej(j=1,2,…,k);3)取试验步长0，计算出k个随机点xj;4)在k个随机点中，找出可行的的随机点xL,产生可行搜索方向d=xLx0.5)从初始点x0出发，沿可行搜索方向d以步长进行迭代计算，直到搜索到一个满足全部约束条件，且目标函数值不再下降的新点x。6)若收敛条件满足，停止迭代。否则，令x0x转步骤2。例6-1求下列约束优化问题的最优解解：用随机方向法程序，在计算机上运行，迭代13次，求得约束最优解：x*=[0.00273.0]T,f(x*)=30109..min21222211221xxxgxxxgtsxxxf迭代次数设计变量x1设计变量x1目标函数值0-2.02.06.01-0.01681.1171.1964-0.0331.0241.0257-0.1140.7170.73010-0.077-2.998-2.99713-0.002-3.0-3.0§6.3复合形法一.单纯形法：基本思想：以一个目标函数值较小的新点，代替原单纯形中目标函数值最大的顶点，组成新的单纯形，不断地迭代，逐渐逼近最优点。二维空间中映射法比较单纯形x(1)x(2)x(3)的顶点，f(x(1))f(x(2))f(x(3)),x(1)为最坏点，称为x(H)，通过映射得到新点x(R)，x(R)＝x(S)＋a(x(S)-x(H))以x(R)来代替x(H)，组成新的单纯形x(R)x(2)x(3)。其中f(x(R))f(x(H));a1；称为映射因子；X(1)=X(H)X(2)X(3)X(S)X(R)=X(4)X(5)X(6)定义：在n维空间中，由n+1个点组成的图形称单纯形。X*()()11,1,2,1nSiiiHxxinn除x(H)外，其它顶点的几何中心二.复合形法：定义：在n维空间中，由k≥n+1个点组成的多面体称为复合形。基本思想：以一个较好的新点，代替原复合形中的最坏点，组成新的复合形，以不断的迭代，使新复合形逐渐逼近最优点。说明：单纯形是无约束优化方法，复合形用于约束优化的方法。因为顶点数较多，所以比单纯形更灵活易变。复合形只能解决不等式约束问题。因为迭代过程始终在可行域内进行，运行结果可靠。三.迭代方法：1.映射法：例：二维空间中，k=4，复合形是四面体x(1)x(2)x(3)x(4)，计算得：f(x(1))f(x(2))f(x(3))f(x(4)),确定最坏点x(H)=x(4)，次坏点x(G)=x(3)，最好点x(L)=x(1)。x(S)为除x(H)以外，各点的几何中心。映射迭代公式：x(R)=x(S)+α(x(S)-x(H))搜索方向：沿x(H)→x(S)的方向。步长因子（映射系数）α：α1，建议先取1.3。若求得的x(R)在可行域内，且f(x(R))f(x(H))，则以x(R)代替x(H)组成新复合形，再进行下轮迭代。●X(S)X(R)X(H)2.变形法一——扩张：若f(x(R))f(x(L))，则可沿此方向扩张取若f(x(E))f(x(L))，则扩张成功，以x(E)代替x(H)组成新复合形若f(x(E))f(x(L))，则扩张失败，以x(R)代替x(H)组成新复合形()()()()(),1ESRSxxxx●X(S)X(R)X(H)X(E)3.变形法二——收缩：若在映射法中f(x(R))f(x(H)),则以a＝0.5a重复采用映射法若直至a10-5仍不成功，考虑采用收缩法取若f(x(K))f(x(H)),则成功，以x(K)代替x(H)组成新复合形。()()()()(),1KSSHxxxx●X(S)X(R)X(H)X(K)4.变形法三——压缩：如采用上述方法均无效，还可以将复合形各顶点向最好点x(L)靠拢，即采用压缩的方法改变复合形的形状。取()()()()0.5()iLLixxxxX(L)四.初始复合形的形成：1.人工选择初始复合形2.随机产生初始复合形：①先在可行域内确定一个初始顶点；②确定xi的上下界：ai、bi；③产生区间[0,1]中的k-1组伪随机数ri(j)；④产生k-1个顶点，xi(j)=αi+ri(j)(bi-ai)⑤检查k-1个顶点的可行性，若有q个顶点满足约束，求q个顶点的几何中心：⑥以x(q+1)=x(t)+α(x(q+1)-x(t)),a=0.5将不满足约束的顶点移向可行域若可行域是非凸集，可能失败，需减小上、下界再进行。()11qtjiijxxq五.步骤：1.形成初始复合形2.计算各顶点的函数值,找到最坏点x(H)、次坏点x(G)和最好点x(L)3.计算除最坏点外，其余顶点的形心:检查形心是否在可行域内4.则可行域为非凸集，取ai＝min[ai(L),ai(S)],bi＝max[ai(L),ai(S)]作为上下界；计算xi(j)=αi+ri(j)(bi-ai)，重新构成复合形，转步骤25.计算映射点：x(R)=x(S)+a(x(S)-x(H))检查是否在可行域内1()()11,1kSjijjHxxinjkk是，a=1.3,转步骤5否，转步骤4是，转步骤6否，a=0.5a,重新计算反射点6.计算f(x(R))，若7.若a:8.检查终止准则若f(x(R))f(x(H))，以x(R)代替x(H)重构复合形后转步骤2f(x(R))≥f(x(H))，转步骤71是，则a=0.5a，转步骤5否，则调用收缩法或压缩法，重构复合形后转步骤22111,...,111,...,kkjccjijjinfxfxxxkkjk，，其中：；是，则迭代结束，以此复合形的x(L)为x＊否，则以重构的复合形转步骤2六.方法评价：•计算简单，不必求导，占内存小；•随着维数的增加，效率大大下降；•不能解含等式约束的问题；建议：①初始α取1.3。②n+1≤k≤2n，当n≤5时，k取值接近2n；当n5时，k取值可小些。§6.4可行方向法一.基本思想：在可行域内选择一个初始点x(0)，确定了一个可行方向和适当的步长后，按照下式进行迭代计算：x(k+1)=x(k)+ad通过不断的调整可行方向，使迭代点逐步逼近约束最优点。§6.4可行方向法二.搜索策略：根据目标函数和约束函数的不同性态，选择不同的搜索策略。①边界反弹法：第一次搜索为负梯度方向，终止于边界。以后各次搜索方向均为适用可行方向，以最大步长从一个边界反弹到另一个边界，直至满足收敛条件。x(1)x(2)x(3)x*x(0)§6.4可行方向法②最优步长法：第一次搜索为负梯度方向，终止于边界。第二次搜索沿适用可行方向作一维搜索以最优步长因子求得最优点。反复以上两步，直至得到最优点x*。x(1)x(2)x(3)x*x(0)§6.4可行方向法③贴边搜索法：第一次搜索为负梯度方向，终止于边界。以后各次搜索贴边（约束面）进行。若适时约束面是线性约束，每次搜索到约束面的交集时，移至另一个约束面，经过有限的几步就可以收敛到最优点。x(1)x(2)x*x(0)§6.4可行方向法若约束面是非线性时，从x(k)点沿切线（面）方向d(k)搜索，会进入非可行域。容差带δ：建立约束面的容差带+δ，从x(k)出发，沿d(k)方向搜索到d(k)方向与g(x)+δ=0的交点x’后，再沿适时约束的负梯度方向返回约束面的x(k+1)点。'11'xgxxkx(k)x(k+1)g(x)g(x)+δx’-▽g(x)d(k)§6.4可行方向法调整步长因子α1：x(k+1)=x’-a1▽g(x’)将g(x)在x’点泰勒展开，取一阶近似式：g(x)≈g(x’)+[▽g(x’)]T(x-x’)进而得到：g(x(k+1))≈g(x’)+[▽g(x’)]T[-a1▽g(x’)]为了让x(k+1)到达约束面，令g(x(k+1))=0得:1'[']'Tgxgxgx§6.4可行方向法三.可行方向的确定可行方向应该满足设计点可行及目标函数值下降两个条件①可行条件:[▽gj(xk)]Tdk≤0j=1,2,…J(起作用约束的个数)▽g(xk)dk▽g1(xk)▽g2(xk)dk§6.4可行方向法三.可行方向的确定②目标函数值下降条件:[▽f(xk)]Tdk0▽f(xk)dk§6.4