运筹学非线性规划5.ppt

《运筹学非线性规划5.ppt》由会员分享，可在线阅读，更多相关《运筹学非线性规划5.ppt（19页珍藏版）》请在优知文库上搜索。

1、 线性约束最优化方法OR第二章 线性规划 mins.t.,1,1,(1)TiieTiiefxa xbima xbimm0,1,.nfxRmmenaRbRimii其 中为上 的 非 线 性 光 滑 函 数，由 于 约 束 的 线 性 性 质，易 于 寻 求 其 可 行 方 向，且 L S 亦 比 较 容 易 实 现。线性约束最优化方法线性约束最优化方法可行方向法OR第二章 线性规划等式线性约束问题的简约梯度法求解LP问题的单纯形法的推广 min.0 (2),0m nmnlf xst AxbxARbRXxRAxb xOR第二章 线性规划mAm1 任一可行点至少有 个大非退化于零的分量2的任设意假列

2、线性无关 11kkkkkxxmnmf xxxx在每个迭代点 处，将 的 个最大的正分量作为基变量，其余个分量作为非基变量，并将看作为非基基变量的函数，求其负梯度方向，并依据该方向构造从 到的可行下降搜索方向，最后进行LS具体确定本思想：OR第二章 线性规划BNxxxx设 可分解为0 mBn mNxRxR基变量非基变量1,AB NB存在11 =BNBNAxbBxNxbxB bB Nx f x 作为非基变量的函数的梯度OR第二章 线性规划11=,F=,BNNNNfxfxxxfBbBN xx 1 (3)TNNBNrFxBNfxfx 由 链 导 法 则fxB在 处对应于基矩阵 的简约梯度 (4)BNf

3、 xf xf xf 对基变量的偏导数所组成的向量f 对非基变量的偏导数所组成的向量OR第二章 线性规划由简约梯度构造搜索方向11 Such that kkkkkNkkkrpxxt pfxfx目 的：0 kkBkxmxB设 的 个最大分量组成的向量为相应的下标为I,kkAB N（）OR第二章 线性规划 kkfx 和在处对应于的简约梯度 1 6TkkNkkBNrBNfxfx 7kBkkNppp相 应 地，置kkNNfpr由 之简约梯度 ,?f可保证 的下降 可行性OR第二章 线性规划?f可保证 的下降、可行性0,0kkNikkBiririIx若的 第 个 分 量则对 应 于 非 基 变 量1,0,

4、0()kkkkkiik ik itxxt rt r 这样 对破坏了 中的非负性约束 0 (8)0?kkiikkiBkkkiiikBrrpiIx rrpOR第二章 线性规划1,0 0kkkkkkkkkkkkpAxAxt pAxt ApxAxbtAp为 确 保为 一 可 行 方可 行向 应 有 157 0 (9)kkkkkkNBkkNB pNppBNp kp(8)(9)一起则给出搜索方向的具体构造=kBkkNppp1kkkNB N p 0,(10)0kkiikkiBkkkiiirrpiIx rrOR第二章 线性规划TH()kp搜索方向 的性质(),0.,(10),)0,();)=0(2)-.kBk

5、kkklBkNkkkkkfxxXxxpxppxpx对于线性约束规划问题 设 连续可微 给定当前迭代点且有分解那么若搜索方向 由确定则有若则为问题 在 处的可行下降方向的为问题的点(2)OR第二章 线性规划Proof:11)0,()()(10),()()()klkkkkkkkBkNkkkkkNkNtxXpA xtpAxtApbt B pN pbt BB N pN pbk对因有 及的构造知:,00,kkkBBikBiiIxxiI对任意指标若若(10):0,.=0,0kkiikkiixpx又知 仅当时才可能取负值若则必有pOR第二章 线性规划 0kkkktxtppx只要选取适当小的正数，则可保证这与

6、（）意味着为问题（2）在处的一个可行方向 146710 0kBTTTkkkkKkBBNNTTkKkBkkNNTkkkkNNiii If xpf xpf xpf xB Nf xprpr p 由和In fac0,0,t0kkNTkkkkppfxppfxx因从 而为在处 的 一 个 下 降 方 向。OR第二章 线性规划2）充分性,000knmkTTkxRRfxAx由为问题（2）K-T点意味着存在约束问题的K-T条件 5BN对应于，将分解为OR第二章 线性规划000,0 (11)0,0kTBBkkTNNkTkTkBBNNBNf xBf xNxx100 kBBTkkBxBf x 1TkTkkNNkkBN

7、f xNBf xr OR第二章 线性规划0 120TkkNNkNrxr 0kNx=0,kkkiiBr xiI(7)0,(10)000kkkkNNBrppp必要性 1010120112kTkkBNNkBkprBf xxKT 若，由知成立令，则中各个条件得到满足，从而知 为问题的点。OR第二章 线性规划搜索步长的确定10,0,kkkkkkA ptA xAxt pb由 上 述，故 对均 有1 0,1,kkkiikixxt pin从 而 只 需 保 证0,1,0,0,kikikkiikkixinpxptp 因上 式 总 成 立max1 If 0min0 Otherwisekkkkiiki niptxpp 搜索步长的上界OR第二章 线性规划Wolfe简约梯度法01,0,:0lSxXk：选取初始可行点给定精度参数令2 ,kkBkkSxmAAB N：设I 是 的 个最大分量的下标集，对 进行相应划分13 kBkkNTkkkNkkBNf xSf xf xrB Nf xf x：计算计算简约梯度OR第二章 线性规划4kBkkNpSpp：按下列分式构造可行下降方向1 0:0kkiikkkNiBkkkiiikkBkkNrrppiIx rrpB N p,5kkpxS若停止，输出否则转max015 min,:1,2kkkt tkkkkkSf xtptxxt pkkS：执行一维搜索得最优步长令转