最优化工程与应用基础_第五章

1.约束随机方向搜索法2.复合形法3.罚函数法(1)外点罚函数法(2)内点罚函数法约束最优化方法例：某车间生产A和B两种产品。为了生产A和B，所需的原料分别为每台2与3个单位，所需工时分别为每台4和2个单位。现在可以应用的原料为100个单位，工时为120个单位。每生产一台A和B分别可得利润6元和4元。应当安排生产A、B各多少台，才能获得最大的利润？解：设A、B产品的台数各生产x1,x2台。目标函数－利润函数12Z=64xx限制条件：12121223100421200xxxxxx、原问题表述为：12121212max64S.t.23100421200zxxxxxxxx、标准化后：12121212min64S.t.23100421200zxxxxxxxx、线性规划问题－目标函数与约束函数均是线性的线性规划问题相关定理1、线性规划问题的可行域D是凸集。2、若线性规划问题存在最优解，则目标函数的最优值可在某个极点（顶点）达到。12121212min64S.t.23100421200zxxxxxxxx、x1x2Dz减小的方向最优解最优解：x1=x2=20123n012=012****[,,,],()(,,,)()(,,,),min()min()(),()nuvXxxxxgXumhXvpfXXfXfXXfX约束最优化问题：求维设计变量受约束于，使目标函数为；如果存在，使得＝则称为最优点，为最优值。在工程实际中，所有设计问题几乎都是约束非线性规划问题。目前对于约束非线性最优化问题的解法较多，可以分为两大类。直接法：用原来的目标函数限定在可行域内进行搜索，且在搜索的过程中一步步的降低目标函数值，直到求出在可行域内的一个最优解。主要方法有：有约束变量轮换法、随机试验法、随机方向搜索法、复合形法、可行方向法等。间接法：将约束最优化问题通过变换，转成为无约束最优化问题，然后再用无约束最优化方法来求得最优解。主要方法有：消元法、拉格朗日乘子法、罚函数法等。约束随机方向搜索法是解决小型约束最优化问题的一种较为有效的直接求解方法。约束随机方向搜索法是一种数值迭代解法，其基本思想可用二维最优化问题来进行说明。约束随机方向搜索法约束随机搜索方向法的几何图0()XAC1()SDB1()X2()S2()X3()X*X等值线等值线等值线000101012D()()()()())(()(()()XSXXSfXfXXXDXXSS任意选择一个初始点随机方向取得探索点=+同时符合（即在约束可行域内，（1）、；（）以给定的初始步长沿着某种方法产生的，（3）若该点，则表示点探索成功。并把它作为新的探索起始点，继续按上面的迭代公式在方向上获取新的探索成功点。重复上述步骤下降性可行性，迭代和要求点可沿（）111)()()SX方向前进，直至到达某搜索点不能同时符合下降性和可行性要求时停止。此时废弃该搜索点，并退回到前一个搜索成功点作为作为方向搜索中的最终成功点，记为。01ACBD()()XX若在初始点或某个换向转折点处（如图中的点），沿某随机方向的探索点目标函数值增大（如图中的点、点）或者越出可行域（如点、点），则应相应弃掉该随机方向，重新产生另一随机方向作为进行搜索。搜索成功继续前进，搜索失败再重新产生随机方向。D0()XAC1()SDB1()X2()S2()X3()X*X等值线等值线等值线23505()()XXmaxmaxmax若在某个换向转折点处（如图中的点），沿N个随机方向以步长进行搜索均失败，可以反映以此点为中心，为半径的圆周上各点都难以同时满足下降性和可行性条件。此时，可将搜索步长减半后继续试探，直到已缩减到预定的精度以下，且沿N个随机方向都搜索失败时，则以最后一个成功点（如图中的点作为达到预定精度要求的的约束最优点，结束迭代。N一般可取为至00，对目标函数性态不好的应取较大的值，以提高解题的成功率。二、初始点的选择001212()()(,,,)DuXgXum随机方向搜索法的初始点必须是一个可行点，即必须满足所有的约束条件，确定这一点通常有两种方法：（）即在设计的可行域内，人为的确定一个可行的初始点。（约束条件较为简单时，人为给定随机选定通常这样处理）（）0()X即利用计算机产生的伪随机数来选择一个可行的初始点。12111222121201111102222200012i010101(i=12()()()()()[,],,()()[,]TTXxxaxbaxbrrrrxarbaxarbaxxXnnr输入设计变量的估计上限和下限，以二维问题为例，。在[0,1]区间内产生两个随机数、，，。令将。同理对于维问题，可产随机选定生个随机数、：、……00in)()()()iiiiXxarba、。初始点的各个分量为0()xxx要特指出X：这样产生的初始点＝虽然能满足设计变量的边界条件，但不一定能满足所有约束条件。因此这样产生的初始点还必须经过可行性条件的检验，如能满足，才可作为一个可行的初始别点。(0)(0)(0)T12n[,，，]D0()X*X1a1x1b2a2b2x01()x02()x0()X三、随机搜索方向的产生1212122212(11)1[]1''yy,xxy,yyyTSSSS设、是在区间上的两个随机数。将它们分别作为、坐标轴上的分量所构成的向量即为相应的二维随机向量。其单位向量为。同理，可以产生另外一个随机二维向量。和的端点处于一个半径为的圆上。随机搜索方向的产生1111T12[,]yyST12[',']yy'S1x2x1222212j)12222121[]12(11)1[]()()()()()()y,y,yyyyy(n),,,TnnijjjjjnjTnSinNSyyyyyy（同理类推，n维最优化问题的随机方向单位向量可由下式计算：……，+?…式中、、……、是个在区间上的随机数。过一点要产生个n维随机方向单位向量，有+?………，(1212);injN、、……、、、……、四、随机方向搜索的计算过程000i00012(1)12(2)max()()()()(),((),,)()[,iiiiiiiiinabinNabrXxarbaXxx随机搜索方向法的具体迭代步骤如下：给定优化问题的维数；初始变量估计的上限和下限、、……、；初始步长步长收敛精度；产生随机方向最大次数。随机产生初始点。在区间(内利用随机数产生初始点的各个分量。得＝，00n00012()()()()]()(,,,),TuxXgXumXX……，。检验是否满足可行性条件。若满足则进行下一步；否则重新随机产生初始点，直到成为可行初始点。00012222120(3)10511121()(),(),,(,)()[,,]iTnnXXfXfkjjyinSyyyyyySXXS。(4)置。（）在区间上产生随机数、、……、，获得单位随机向量……，+?…沿方向进行迭代可以得到新点=+。0000(6)012797916()()()(,,,),(),,,,,uXgXumXfXfffXXffjjSXXS检验新点的可行性。若满足满足则进行第（）步；否则转向第（）步。（）检验新点的下降性。计算若则进行第（8）步；否则转向第（）步。(8)置继续沿方向进行迭代可以得到新点=+，返回第（）步。(9)011041011511054max**,,,()().,jjkkkNXXfXfX若置进行第（）步，否则返回第（）步。（）若则进行第（）步，否则返回第（）步。()若,则输出最优解：，终止迭代；否则，将步长减半，即返回第（）步。221222112212min()s.t.()=90()=10fxxgxxgx+xxExxx例：用随机方向法求解下列优化问题取(0)T0[-2,2]11,.x迭代13次，求得T[-0.00247,-3]()3,f-xxkx1x2f(x)0-2.02.06.01-0.1681.1171.196┈┈┈┈4-0.0331.0241.025┈┈┈┈10-0.077-2.998-2.998┈┈┈┈13-0.00247-3.0-3.0迭代过程显示复合形法K坏选然后比较复合形个顶点目标函数值的大小，其中目标函数值最大的点为，以坏点之外其余各点的中心为，寻找坏点的，一般来说映射点的目标函数值总是小于坏点的，也思想：初始复合形，新的复合形。就点映射是说，映射点优于坏点。构成以映射点来替代坏点与原复合形除坏点之外的其余各点构成个顶点的如此反复在可行域中进行迭代计算，使得复合形不断向最优点移动和收缩，直至中心映射点收缩到复合形的各顶点与其形心非常接近。最优解。D2()X*X复合形法的几何表示1a1x1b2a2b2x1()X3()X4()X()CX()RX(1)(2)(3)(4),,,XXXX(1)(2)(3)(R),,,XXXX12111222s.t.00min()()()fXgXgXaxbaxb以二维不等式约束优化问题来作进一步的说明。其数学模型为前两式为隐式约束条件，后两式为显式约束条件。(1)(2)(3)(4)(L)(H)(H)(H)(j)(L)(L)(j)4(){()(j=12?…K)}(){()(j=12?…K)}()maxminXXXXXXXfXfXXfXfXX在可行域中选定、、、四个点作为初始复合形的顶点，计算这四个点的目标函数值，并作比较，得出好点和坏点。：、、、：、、、从图中可以看出为好点14L1234CR()()()()()()()()()()()HHXXXXXXXXXXX，为坏点，即，。以、、三点的中心为映射中心，寻找点的映射点。RRRHRRR23411.3()()()()()()()()()()()()()()()()()CCHHXXXXXfXfXXXXXXXX其中为映射系数，一般，通常取＝。然后计算映射点的目标函数值与坏点目标函数值相比是否下降，同时检查是否在可行域内。如果下降性、可行性这两方面都得到满足。则以点替换，由、、、共四点构成一个新的复合形（蓝线表示）。这个复合形R0.5()X肯定优于原复合形；如果上述两个条件不能同时满足，则可将映射系数减半，即，重新计算新的映射点，使其同时满足下降性和可行性条件。有时必须经过多次缩减映射系数才能使得映射点同时满足这两个条件。R2341.2.()()()()XXXX、、、构成新的复合形，完成了一轮迭代，以后就是用上述方法进行迭代搜索，不断的使复合形向着目标函数值下降的方向移动、收缩，直到逼近最优解。复合形寻优可以归为两大步骤：在可行域内构成初始复合形。通过复合形的收缩、移动不断的调优，逐步逼近最优解。复合形法的迭代过程j(1)12K(2)K12(),(())iinabinXjK根据复合形法的基本原理，其基本迭代步骤如下：给定优化问题的维数；初始变量估计的上限和下限、、……、；复合形顶点数目；精度要求、。产生初始复合形，采用随机数，得到初始复合形的个顶点（、、、(j)(H)(L)(H)(H)(j)(L)(L)(j)(3)()12),(){((12)}(){((12)}8maxminfXjKXXXfXfXjKXfXfXjK计算复合形各个顶点的目标函数值（、、、从中找到最坏点和最好点。：、、……、：、、……、转入第（）步——迭代中止条件检查。(H)(C)(C)(j)1(C)(C)(L)(C)(L)(C)41()15D122()-,(KjiiiiXXXXjHKXXXXxaxbin计算除坏点以外其余各个顶点的中心＝（）检查的可行性。若不在可行域内，则可行域可能是非凸集。则可在以为起点、点为端点的超立方体中利用随机数产生新的复合形的各个顶点。即、、、）。然后转回第（）(C)X步，若在可行域内，则进行下一步。(H)(R)(R)(C)(