资源描述：
《非线性规划讲稿3.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、2．非线性约束条件下的可行方向法（G.Zoutendijk法）具有非线性不等式约束的一般规划问题⎧minf(X)⎪X∈R⎨⎪R={}Xg(X)≤,0j=,2,1?,P⎩j（1）基本思想k关键是寻找可行下降方向。若第k次迭代得到X后，当p满足下式时，它是kX处的可行下降方向，即kT⎧⎪[∇f(X)]P<0⎨kTk（*）⎪⎩[∇gj(X)]P<,0j∈T(X)其中：k{k}T(X)=jg(X)=,0j=,2,1?,pj（*）式等价于：存在实数α，使得kT⎧[∇f(X)]P≤α⎪kTk⎨[∇gj(X)]P≤α,j∈T(X)⎪α<0⎩不妨设Pi≤(1i=,2,1?,n)，则得
2、下面规划问题：⎧minα⎪kT⎪[∇f(X)]P≤α⎨kTk[∇g(X)]P≤α,j∈T(X)⎪j⎪P≤,1i=,2,1?,n⎩ikkkkT设(a,p1,p2,?,pn)为最优解。kk若α=0，X为最优解；k若αk≠0，则α<0，且kkkkTP=(P,P,?,P)12nk为X处的可行下降方向。求一维极值问题的最优解，设为k，即：λkkkkkminf(X+λP)=f(X+λP)λ∈Λ{kk}Λ=λλ≥,0X+λP∈R令：k+1kkkX=X+λP重复上面的步骤，继续迭代。若kα≤ε2k停止迭代，取Xmin=Xkkk若X为R内点，取p=−∇f(X)，当k∇f(X)≤ε1k时
3、，停止迭代，取Xmin=X。（2）G.Zoutendijk方法的迭代步骤0k1>选定初始点X∈R，给定ε1>0及α的允许误差ε>0，令k=0；2k{k}2>确定指标集T(X)=jgj(X)=,0j=,2,1?,p；kk3>若T(X)=Φ，且∇f(X)≤ε1，则停止迭代，取kkkkXmin=X；如果∇f(X)≥ε1，则令P=−∇f(X)，转（6）；4>求解线性规划问题⎧minα⎪kT⎪[∇f(X)]P≤α⎨kTk[∇g(X)]P≤α,j∈T(X)⎪j⎪P≤,1i=,2,1?,n⎩ikk5>若a≤ε2，则停止迭代，取Xmin=X；否则，kkkkT令P=(P1,P2,?,P
4、2)，转（6）；6>求一维极值问题kkkkkminf(X+λP)=f(X+λP)λ∈Λ{kk}Λ=λλ≥,0X+λP∈Rk的最优解，设为λ；k+1kkkk=k+17>令X=X+λP，转（2）G.Zoutendijk方法程序框图如图3-17所示。【例3－18】用G.Zoutendijk方法求解下面问题22⎧min[2x+2x−2xx−4x−6x]121212⎪x+5x≤5⎪12⎪2⎨2x1−x2≤0⎪−x≤0⎪1⎪−x≤0⎩20T解：取X=.0(00.0,75)，开始第一次迭代，计算0T∇f(X)=(−.550,−.300)0{}T(X)=30T∇g(X)=(−)0,1
5、3得线性规划问题⎧minα⎪⎪−.550p1−.300p2≤α⎨−p≤α⎪1⎪−1≤p≤,1i=2,1⎩i求出最优解为：0α=−.1000TP=.1(00,−.100)000为求P的最优解，需要先要确定∧。可以验证，使X+λP为可行解的最大λ值为：λ=.04114max0在P方向的点为：00TX+λP=(λ.0,75−λ)相应的目标函数为：002f(X+λP)=6λ−5.2λ−.3750X处起作用的约束为：22x−x≤012求解：2min6[λ−5.2λ−.3375]λ∈[].0,04114得最优解为：0λ=.02083令1000TX=X+λP=.0(2083.0,5
6、417)第二次迭代。由于1T1∇f(X)=(−.425,−.425)，T(X)=φ故取1TP=)1,1(111由X出发，使X+λP为可行解的最大λ值为：λ=.03472max起作用约为：x+5x≤512再求2min2(λ−5.8λ−.36354)λ∈[].0,03472得最优解：λ=.034721令2111TX=X+λP=.0(5555.0,8889)重复上述步骤，…，迭代4次后可得：TX≈.0(6302.0,8740)min（3）收敛定理定理3.16设f(X)、gj(X)(j=,2,1?,p)在包含R的k某一开集上具有连续的一阶偏导数。若X∈R是正则点，k则问题的最
7、优解中α=0的充分必要条件是原非线性规划问题在kX点满足K－T条件；若原非线性规划为凸规kk划，那么，α=0的充分必要条件是X为原问题的最优解；k若在迭代过程中，α=0的情形总不发生，则得到点列kk{X}。在更严格的条件下，{X}的任意极限点都是原问题的最优解。四、罚函数法序列无约束极小化技术，简记为SUMT（SequentialUnconstrainedMinimizationTechnique）。惩罚函数法——称外点法；障碍函数法——称内点法。（一）惩罚函数法1．基本原理（1）等式约束的惩罚函数法⎧minf(X)⎨h(X)=,0i=,2,1?,m
