5-2罚函数法

5.1约束优化问题的最优性条件5.2罚函数法5.3乘子法5.4可行方向法5.5投影梯度法5.6既约梯度法第五章约束最优化问题第二节罚函数法(SUMT法)外点罚函数法(外点法)内点罚函数法(内点法)混合点罚函数法(混合点法))(minXf()0,1,2,,()0,1,2,,ijgXimhXjp..ts)(NP第五章约束最优化问题一.外点罚函数法(外点法)外点法迭代原理外点法迭代步骤外点法举例外点法的优缺点)(minXf()0,1,2,,()0,1,2,,ijgXimhXjp..ts)(NP第五章约束最优化问题一.外点法迭代原理)(minXf()0,1,2,,()0,1,2,,ijgXimhXjp..ts)(NP)(minXf0)(Xgimi,,2,1)(NP..ts约束问题5-2一.外点法迭代原理..ts)(minXf0)(Xgimi,,2,1构造罚函数：miiXgMXfMX12))](,0[min()(),(基本思想：通过建立罚函数,将约束极值问题转化成一系列无约束极值问题去求解.惩罚项罚因子罚函数的特点：),(MX),(XfDXDX02()iMgX0)(00Xgii使至少)(NPf(X)+很大的正数,(当M取值很大时)惩罚项可行域Dmin(,)nXRXM约束问题5-2研究X*(M)与(NP)的最优解X*之间的关系一.外点法迭代原理构造罚函数：miiXgMXfMX12))](,0[min()(),(基本思想：通过建立罚函数,将约束极值问题转化成一系列无约束极值问题去求解惩罚项罚因子罚函数的特点：)(NPmin(,)nXRXM)(NP),(MX),(XfDXDXf(X)+很大的正数,设其最优解为X*(M)，..ts)(minXf0)(Xgimi,,2,1求解约束问题5-2设最优解为线性规划3-6一.外点法迭代原理miiXgMXfMX12))](,0[min()(),()(NPmin(,)nXRXM)(MX证明：(,)((),)XNXMXMM()XDNfX))(()(MXfDMX),(MX),(XfDX,)(很大的正数XfDX研究X*(M)与(NP)的最优解X*之间的关系10若(可行域)，则X*(M)是(NP)最优解。()XMDX*(M)是(NP)的最优解。是的最优解，有：()XMmin(,)nXRXM..ts)(minXf0)(Xgimi,,2,1D设最优解为一.外点法迭代原理miiXgMXfMX12))](,0[min()(),()(NPmin(,)nXRXM)(MX研究X*(M)与(NP)的最优解X*之间的关系10若(可行域)，则X*(M)是(NP)最优解。()XMD20若当M很大时，X*(M)也会相当靠近(),XMD(NP)可行域D的边界，是(NP)的最优解X*的近似解(通常约束极值问题的最优解X*在可行域的边界上)..ts)(minXf0)(Xgimi,,2,1约束问题5-220若当M很大时，X*(M)也会相当靠近(),XMD(NP)可行域D的边界，是(NP)的最优解X*的近似解一.外点法迭代原理2))](,0[min()(),(XgMXfMXi)(NP的最优解为设),(minMXnRX)(MX,)(DMX2((),)(())[min(0,(()))]iXMMfXMMgXM222)))]((,0[min())((0MXgMXgii即))((0MXgi0(())0igXM证明：..ts)(minXf0)(Xgimi,,2,1至少存在i0使0(())0igXM是的最优解，()XM又min(,)nXRXM是局部极小值当M很大时，2[min(0,(()))]igXM会相当小。约束问题5-2M越大，越小，X*(M)越靠近D的边界，即越靠近X*。增大罚因子M的作用是将X*(M)拉向D的边界(即X*)。20若当M很大时，X*(M)也会相当靠近(),XMD(NP)可行域D的边界，是(NP)的最优解X*的近似解一.外点法迭代原理2))](,0[min()(),(XgMXfMXi)(NP的最优解为设),(minMXnRX)(MXDX()XM0)(0Xgi证明：,)(DMX..ts)(minXf0)(Xgimi,,2,1至少存在i0使0(())0igXM当M很大时，有0(())0igXM0()0igX0()0igX0()igX约束问题5-2设最优解为一.外点法迭代原理miiXgMXfMX12))](,0[min()(),()(NPmin(,)nXRXM)(MX研究X*(M)与(NP)的最优解X*之间的关系10若(可行域)，则X*(M)是(NP)最优解。()XMD20若当M很大时，X*(M)也会相当靠近(),XMD(NP)可行域D的边界，是(NP)的最优解X*的近似解(通常约束极值问题的最优解X*在可行域的边界上)问题：如何取M，使得X*(M)是所需要的近似解？..ts)(minXf0)(Xgimi,,2,1约束问题5-2一.外点法迭代原理miiXgMXfMX12))](,0[min()(),((1)1(),XMD1min(,),nXRXM收敛结论：XMXkMkk)()(D通过建立罚函数,将约束极值问题转化成一系列无约束极值问题去求解.)(NP通过迭代逐渐增大罚因子M：任意给定初始点X(0)，初始罚因子M1(=1)0则是(NP)的最优解.否则M2=10M1则是(NP)的最优解.否则M3=10M2则是(NP)的最优解.否则Mk+1=10Mk(NP)的最优解..ts)(minXf0)(Xgimi,,2,1若(2)2(),XMD若()(),kkXMD若求解2min(,),nXRXM求解min(,),nkXRXM求解约束问题5-2一.外点罚函数法(外点法)外点法迭代原理外点法迭代步骤外点法举例外点法的优缺点)(minXf()0,1,2,,()0,1,2,,ijgXimhXjp..ts)(NP第五章约束最优化问题二.外点法迭代步骤miiXgMXfMX12))](,0[min()(),()(NP,,,2,1mi()(()),kikgXM)()(kkMXXD()0igX()igX()()kkXM()0igXX20求的最优解min(,)nkXRXM()()kkXM(用数值迭代的方法求解)10给定X(0)，M1(=1)0，0,:1k30若则迭代终止，否则取Mk+1=CMk,其中C=5~10令k:=k+1转20..ts)(minXf0)(Xgimi,,2,1约束问题5-2一.外点罚函数法(外点法)外点法迭代原理外点法迭代步骤外点法举例外点法的优缺点)(minXf()0,1,2,,()0,1,2,,ijgXimhXjp..ts)(NP第五章约束最优化问题三.外点法举例miiXgMXfMX12))](,0[min()(),(例5-221)(minxxXf解：})],0[min()],0{[min(),(21222121xxxMxxMXkk])[(21222121xxxMxxk0221xx01x..ts0221xx01x1x2xD0)(1Xg0)(2Xg外点法，XD1()0gX2()0gX约束问题5-2三.外点法举例miiXgMXfMX12))](,0[min()(),(21)(minxxXf解：})],0[min()],0{[min(),(21222121xxxMxxMXkkmin(,)nkXRXM])[(21222121xxxMxxk02)2)((21112211xMxxxMxkk0)(212212xxMxk..ts0221xx01x()212(1)()114(1)2kkkkkMXMMM1x2xD0)(1Xg0)(2Xg(用解析法)00XkM解得：求解(,)0kXM约束问题5-2例5-2三.外点法举例miiXgMXfMX12))](,0[min()(),(21)(minxxXf解：..ts0221xx01x00XkMkkkkkMMMMX21)1(41)1(21)(2)(1x2xD0)(1Xg0)(2XgX)()(kkMX(1)(1)(14,11612)X11M102M(2)(10)(122,120)X1003M(3)(100)(1200,1200)X10004M(4)(1000)(12000,12000)X约束问题5-2例5-2一.外点法迭代原理)(minXf()0,1,2,,()0,1,2,,ijgXimhXjp..ts)(NP)(minXf0)(Xgimi,,2,1)(NP..ts约束问题5-2外点法也适用于一般情况:)(minXfpjXhmiXgji,,2,1,0)(,,2,1,0)(..ts)(NP)(12XhMpjj罚函数：XMXkMkk)()()())(()(XhMXhjMkkjk))(()(kkjMXhpj,,2,1因此在迭代算法中需加入,))(()(kkjMXhpj,,2,1miiXgMXfMX12))](,0[min()(),(0收敛结论：XMXkMkk)()(D等式约束的停机准则：设其最优解为X(k)(Mk)(NP)的最优解min(,)nkXRXM求解约束问题5-2二.外点法迭代步骤)(minXf0)(XgimiiXgMXfMX12))](,0[min()(),()(NP,,,2,1mi()(()),kikgXM)()(kkMXX..ts20求的最优解min(,)nkXRXM()()kkXM(用数值迭代的方法求解)10给定X(0)，M1(=1)0，0,:1k30若则迭代终止，否则取Mk+1=CMk,其中C=5~10令k:=k+1转20))(()(kkjMXhpj,,2,10)(Xhj)(12XhMpjj约束问题5-2一.外点罚函数法(外点法)外点法迭代原理外点法迭代步骤外点法举例外点法的优缺点)(minXf()0,1,2,,()0,1,2,,ijgXimhXjp..ts)(NP第五章约束最优化问题四.外点法的优缺点优点：1.方法简单,计算方便.2.初始点选择容易,它可以在整个n维空间中选取.缺点：1.当接近最优解时，即罚因子Mk很大时，()()kkXMmin(,)nkXRXM罚函数的性质变坏,这就使得求解非常困难。X(,)kXM2.外点法的中间结果不是可行解，不能作为近似最优解。只有迭代到最后才能得到最优解的近似解。约束问题5-2一.外点罚函数法(外点法)外点法迭代原理外点法迭代步骤外点法举例外点法的优缺点)(minXf()0,1,2,,()0,1,2,,ijgXimhXjp..ts)(NP第五章约束最优化问题第二节罚函数法(SUMT法)外点罚函数法(外点法)内点罚函数法(内点法)混合点罚函数法(混合点法))(minXf()0,1,2,,()0,1,2,,i