约束优化方法

有约束的优化方法5-1约束最优解及其一阶必要条件5-2随机方向法5-3复合形法5-4-1内惩罚函数法5-4-2外惩罚函数法5-4-3混合惩罚函数法第五章约束优化方法约束最优解（a）§5-1约束最优解及其必要条件约束最优解（b）§5-1约束最优解及其必要条件约束最优解（c）§5-1约束最优解及其必要条件§5-1约束最优解及其必要条件约束优化问题的最优性条件：在满足等式和不等式约束条件下，其目标函数值最小的点所必需满足的条件。（局部最优解）最优点可能出现的情况：1）在可行域内部2）在约束边界上约束最优解§5-1约束最优解及其必要条件约束最优解的搜索路线约束优化问题的最优性条件：在满足等式和不等式约束条件下，其目标函数值最小的点所必需满足的条件。约束优化设计问题数学模型为:min(),..()01,2,,()01,2,,njkfRstgjmhklxxxx§5-1约束最优解及其必要条件x(k)不是约束最优点单起作用约束条件极小点的必要条件x(k)是约束最优点)()(kxg§5-1约束最优解及其必要条件因而得出单约束条件极小点的必要条件可以表示成：)()()()(xxgf0§5-1约束最优解及其必要条件)(k§5-1约束最优解及其必要条件两个起作用约束条件极小点的必要条件x(k)不是约束最优点x(k)是约束最优点x)()(kxf)()(1kgx)()(2kgx)()(2kgx)()(kxf§5-1约束最优解及其必要条件若x(k)为约束最优点x*，约束条件极小点的必要条件可以表示成：0,0)()()(21)(22)(11)(xxxggf它的几何意义：如果x*是一个局部极小点，则该点的目标函数梯度应落在该点起作用约束的梯度所组成的锥角之内。几何意义：如果x(k)是一个局部极小点，则该点的目标函数梯度应落在该点起作用约束的梯度所组成的锥角之内。x(k)不是约束最优点x(k)是约束最优点§5-1约束最优解及其必要条件推广到n维设计空间的具有m个不等式约束的问题，即为检验约束优化问题局部最优点的著名的K-T条件：JugfuJukuuk,,2,10)()(1)()(xxJuxxgxxfuJuikuuik,,2,10)()(1)()(或：即只有当λu为非负乘子时，x(k)才是约束最优点x*。§5-1约束最优解及其必要条件§5-1约束最优解及其必要条件K-T条件对于约束问题的重要性在于：1）检验某点是否为约束最优点；2）检验一种搜索方法是否可行。例1：判断x(k)=[10]T是否为下列约束优化问题最优点：01),(0),(0),(..)2(),(min22121322121211222121xxxxgxxxgxxxgtsxxxxf§5-1约束最优解及其必要条件01),(0),(0),(..)2(),(min22121322121211222121xxxxgxxxgxxxgtsxxxxf解：1）判断该点起作用约束：01),(211xxg0),(212xxg0),(213xxg2）计算目标函数及起作用约束在该点梯度：022)2(2)()(21)(kxkxxfx10)()(2kgx1212)()(1)(3kxgkxx§5-1约束最优解及其必要条件2）计算目标函数及起作用约束在该点梯度：022)2(2)()(21)(kxkxxfx10)()(2kgx1212)()(1)(3kxgkxx3）代入K-T条件，求乘子：)()()()(33)(22)(kkkggfxxx12100232解得：1,132因此判断该点是约束最优点。§5-1约束最优解及其必要条件01),(0),(0),(..)2(),(min22121322121211222121xxxxgxxxgxxxgtsxxxxf§5-1约束最优解及其必要条件0)1(),(0),(0),(..)2(),(min31221322121211222121xxxxgxxxgxxxgtsxxxxf练习：判断x(k)=[10]T是否为下列约束优化问题的最优点：答案：乘子无解，故非最优点。§5-1约束最优解及其必要条件对于仅有等式约束的优化设计问题，以一个等式约束为例：)()()(xxxhhf0)(xh可以写成：0)(0)(xxhh从而得出等式约束问题的K-T条件：)()(xxhf即：§5-1约束最优解及其必要条件从而得出多个等式约束问题pvvvhf1)()(xxpvhv,,10)(xK-T条件：§5-1约束最优解及其必要条件因此，容易得出对于具有等式约束和不等式约束的优化设计问题，其约束最优点的一阶必要条件：JuJughgfuupvvvJuuu00)()()()(11xxxxK-T条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件。对于目标函数和约束函数都是凸函数的情况，符合K-T条件的点一定是全局最优点。这种情况K-T条件即为多元函数取得约束极值的充分必要条件。§5-1约束最优解及其必要条件（1）直接法直接法是在满足不等式约束的可行设计区域内直接搜索问题的最优解x*和f(x*)。（2）间接法间接法是将优化问题转化为一系列无约束优化问题来求解。约束优化设计问题求解方式:直接解法思路:1(0,1,2,)kkkkdkxxkkd步长可行搜索方向可行搜索方向:当设计点沿该方向作微量移动时，目标函数值将下降，且不会越出可行域。通常适用于仅含不等式约束的问题！§5-2随机方向法基本思想：在可行域内，利用随机产生的可行方向进行搜索的一种直接解法。随机方向法基本原理1初始点的选择1)人为确定；2)随机选择：(1)输入设计变量的下限值和上限值，即ai≤xi≤bi(i=1,2,…,n)(2)产生n个随机数qi.（0≤qi≤1）(3)计算随机点x的各分量：xi=ai+qi(bi-ai)(4)判别随机点x是否可行，若随机点x为可行点，则取初始点x0=x；若随机点x为非可行点，则转步骤2)重新计算，直到产生的随机点是可行点为止。1)在[-1,1]区间内产生随机数ri(i=1,2,……,n)12iir计算随机单位向量snniirrrr21121e2)取一试验步长，按下式计算k个随机点:),,2,1(0kjxxjje2随机方向的产生同样方法计算出k个随机单位向量（k≥n）§5-2随机方向法3)检验k个随机点的可行性，比较其大小，选出目标函数值最小的点xL。4)比较两点xL和x0的目标函数值(适用性)：0xxLd则将步长缩小，转步骤2)重新计算)()()0(xxffL若则若)()()0(xxffL1)选择一个可行的初始点x0。2)产生k个n维随机单位向量。3)取试验步长，计算出k个随机点。4)在k个随机点中，根据可行性和适用性，找出可行搜索方向。5)从初始点x0出发，沿可行搜索方向d以步长进行迭代计算，直到搜索到一个满足全部约束条件，且目标函数值不再下降的新点x。随机方向法的计算步骤：5)从初始点x0出发，沿可行搜索方向d以步长进行迭代计算，直到搜索到一个满足全部约束条件，且目标函数值不再下降的新点x。满足，迭代终止。约束最优解为x*＝x，否则，x0=x，转到步骤2。6)若收敛条件随机方向法的计算步骤：例：用随机方向法求解下面问题的约束最优解：04),(0),(01),(..)3(),(min22121322121211222121xxxxgxxxgxxxgtsxxxxf解：1）确定初始点：2）产生k个随机方向（k=3）：8.06.04.03.04.0)3.0(1221e65.076.06.07.07.0)6.0(1222e0105.005.01223e9)(]00[)0()0(xfxT3）计算k个随机点：8.06.01)0(1exx65.076.02)0(2exx013)0(3exx4）判断k个随机点的可行性：1x3x5）判断可行搜索方向：40)31(223f6.138.0)36.0(221f)()0(3xffT]01[)0(3xxd6）从可行点沿着可行方向前进：02010130dxdxx验证其可行性和适用性：10)32()(22xf3)(ffx7）从可行点沿着可行方向前进：0301020dxdxx验证其可行性和适用性：不可行性8）产生k个随机方向（k=3）计算各随机点：12.099.01.08.01.0)8.0(1221e95.032.06.02.02.0)6.0(1222e6.08.03.04.03.04.01223e12.099.2101exx95.032.2202exx6.02.1303exx9）判断可行性与适用性：均不可行10）步长减半计算各随机点：06.049.2101exx48.016.2202exx3.06.1303exx11）判断可行性与适用性：均不可行12）步长再减半计算各随机点，直到步长很小依然找不到一个可行点，则此时的x0即为x*=[20]T,f(x*))=1是否是最优点呢？用什么方法判断？04),(0),(01),(..)3(),(min22121322121211222121xxxxgxxxgxxxgtsxxxxf)()()()(33)(22)(kkkggfxxx1410023204.032因此，所求是约束极小点。判断：本次小结：1约束优化问题的最优化条件：JuJughgfuupvvvJuuu00)()()()(11xxxx2用随机方向法求解约束优化问题：1）基本思想2）求解方法和步骤12()1FXxx120;0xx引例1、求解函数的极小值，约束条件为：起始点：[1，0]T；[0，1]T；[1，1]T说明复合形法的基本思想(分区搜索)。§5-3复合形法复合形法是求解约束非线性最优化问题的一种重要的直接方法。引例2：5.3.1复合形法的基本思想011)(08)(06)(01)(0)(..41060)(min2152413221121222121xxgxgxgxgxgtsxxxxxxfxxxxxx5.3.1复合形法的基本思想5.3.1复合形法的基本思想基本思想：是在可行域内构造一个具有k个顶点的初始复合形。对该复合形各顶点的目标函数值进行比较，找到目标函数值最大的顶点(称最坏点)，然后按一定的法则求出目标函数值有所下降的可行的新点，并用此点代替最坏点，构成新的复合形，复合形的形状每改变一次，就向最优点移动一步，直至逼近最优点。5.3.1复合形法的基本思想在可行域内构成初始复合形。找