2．非线性约束条件下的可行方向法（G.Zoutendijk 法）具有非线性不等式约束的一般规划问题{}⎪⎩⎪⎨⎧=≤=∈P j X g X R X f j R X ,,2,1 ,0)()(min " （1）基本思想 关键是寻找可行下降方向。
若第次迭代得到k k X 后，当p 满足下式时，它是k X 处的可行下降方向，即⎪⎩⎪⎨⎧∈<∇<∇)( ,0)]([0)]([k T k j T k X T j P X g P X f （*） 其中：{}p j X g j X T k j k ,,2,1,0)()("=== （*）式等价于：存在实数α，使得⎪⎩⎪⎨⎧<∈≤∇≤∇0)( ,)]([)]([αααk T k j T k X T j P X g P X f 不妨设),,2,1(1n i P i "=≤，则得下面规划问题：⎪⎪⎩⎪⎪⎨⎧=≤∈≤∇≤∇ni P X T j P X g P X f i k Tk j T k ,,2,1,1)( ,)]([)]([min "ααα设为最优解。
Tk n k k k p p p a ),,,,(21"若，0=k αk X 为最优解；若0≠k α，则，且0<k αT kn kk k P P P P ),,,(21"=为k X 处的可行下降方向。
求一维极值问题的最优解，设为，即：k λ)()(min kk k k k P X f P X f λλλ+=+Λ∈{}R P X k k ∈+≥=Λλλλ,0令：k k k k P X X λ+=+1重复上面的步骤，继续迭代。
若2εα≤k停止迭代，取k X X =min 若k X 为R 内点，取，当)(k k X f p −∇=1)(ε≤∇k X f时，停止迭代，取。
k X X =min （2）G.Zoutendijk 方法的迭代步骤1>选定初始点R X ∈0，给定01>ε及的允许误差k α02>ε，令0=k ；2>确定指标集{}p j X g j X T k jk ,,2,1,0)()("===； 3>若，且Φ=)(k X T 1)(ε≤∇k X f ，则停止迭代，取；如果k X X =min 1)(ε≥∇k X f ，则令，转（6）；)(k k X f P −∇=4>求解线性规划问题⎪⎪⎩⎪⎪⎨⎧=≤∈≤∇≤∇n i P X T j P X g P X f ik T k j T k ,,2,1,1)( ,)]([)]([min "ααα 5>若2ε≤k a ，则停止迭代，取；否则，令，转（6）；k X X =minT k k k k P P P P ),,,(221"=6>求一维极值问题)()(min kk k k k P X f P X f λλλ+=+Λ∈ {}RP X k k ∈+≥=Λλλλ,0 的最优解，设为；k λ7>令，k k k k P X X λ+=+11+=k k 转（2）G.Zoutendijk 方法程序框图如图3-17所示。
【例3－18】用G.Zoutendijk 方法求解下面问题⎪⎪⎪⎩⎪⎪⎪⎨⎧≤−≤−≤−≤+−−−+000255]64222min[212212121212221x x x x x x x x x x x x 解：取，开始第一次迭代，计算 T X )75.0,00.0(0={}TTX g X T X f )0,1()(3)()00.3,50.5()(0300−=∇=−−=∇得线性规划问题⎪⎪⎩⎪⎪⎨⎧=≤≤−≤−≤−−2,1 ,1100.350.5min 121i p p p p i ααα求出最优解为：T P )00.1,00.1(00.100−=−=α为求0P 的最优解，需要先要确定∧。
可以验证，使为可行解的最大00P X λ+λ值为：4114.0max =λ在0P 方向的点为：T P X )75.0,(00λλλ−=+ 相应的目标函数为：75.35.26)(200−−=+λλλP X f0X 处起作用的约束为：02221≤−x x求解：[]]375.35.26[min 24114.0,0−−∈λλλ得最优解为：2083.00=λ令T P X X )5417.0,2083.0(0001=+=λ第二次迭代。
由于T X f )25.4,25.4()(1−−=∇，φ=)(1X T 故取TP )1,1(1=由1X 出发，使为可行解的最大11P X λ+λ值为： 3472.0max =λ起作用约为：5521≤+x x再求[])6354.35.82(min 23472.0,0−−∈λλλ得最优解：3472.01=λ令T P X X )8889.0,5555.0(1112=+=λ重复上述步骤，…，迭代4次后可得：T X )8740.0 ,6302.0(min ≈（3）收敛定理定理 3.16 设、)(X f ),,2,1)((p j X g j "=在包含R 的某一开集上具有连续的一阶偏导数。
若R X k ∈是正则点，则问题的最优解中的充分必要条件是原非线性规0=k α划问题在k X 点满足 K －T 条件；若原非线性规划为凸规划，那么，的充分必要条件是0=k αk X 为原问题的最优解；若在迭代过程中，的情形总不发生，则得到点列0=k α{}kX 。
在更严格的条件下，{}k X 的任意极限点都是原问题的最优解。
四、罚函数法序列无约束极小化技术，简记为SUMT （SequentialUnconstrained Minimization Technique ）。
惩罚函数法——称外点法；障碍函数法——称内点法。
（一）惩罚函数法1．基本原理（1）等式约束的惩罚函数法⎩⎨⎧==m i X h X f i,,2,1,0)()(min " 1>构造惩罚函数令： []∑=+=mi i X h M X f M X q 12)()(),(M ：惩罚因子；),(M X q ：惩罚函数；[∑=mi i X h M 12)(]：称为惩罚项，显然有： []⎩⎨⎧∉>∈=∑=R X R X X h M m i i ,0 ,0)(122>求解无约束问题),(min M X q n EX ∈ 得最优解：)(M X 若R M X ∈)(，则它就是原问题的最优解；若R M X ∉)(，即违反约束，加大)(M X M 再求无约束问题，…，最优解随着M 的增大，从的外部逼近原约束问题的最优解，所以这种又称为SUMT 外点法。
)(M X R （2）一般（含不等式）非线性规划问题的惩罚函数法⎪⎩⎪⎨⎧=≤==p j X g mi X h X f ji ,,2,1,0)(,,2,1,0)()(min ""1>将p j X g j ,,2,1,0)("=≤化为等式约束p j X g j ,,2,1,0)](,0max["==原问题可以化为等式约束问题[]⎪⎩⎪⎨⎧====p j X g mi X h X f j i ,,2,1,0)(,0max ,,2,1,0)()(min ""2>构造惩罚函数：[]2211(,)()()[max(0,()]pm i j i j q X M f M M h X M g X ===++∑∑3>求解无约束问题：]})]([)({min ),(min 12∑=∈∈+=m i i E x E X X h X f M X q n n 21[max(0,()]pj j M g =+∑X 2．经济解释)(X f ：价格；约束：规定；要求：在规定的范围内购买便宜的东西； 违规：处以罚款；采购原则：总花费最小。
3．应注意的几个问题（1）0X 可任取，一般用前一次求出的作为下次min 的初始点，常常会加快收敛速度。
)(1*−k M X ),(k M X q （2）k M 应逐渐加大，即要求k M 满足：∞=<<<∞→k k M M M M lim ,321"（3）判断是否约束问题的最优点)(*k M X *X ，一般要求满足：)(*k M X ⎪⎩⎪⎨⎧=≤=≤pj M X g m i M X h k j k i,,2,1,)(,,2,1,)((1*1*""εε也常用：21**))(())((ε≤−−k k M X f M X f或31**)()(ε≤−−k k M X M X作为收敛标准。
（4）肯定最优解存在。
4．迭代步骤、程序框图（略）【例3－19】 用外点法求解下面规划问题⎩⎨⎧≤−==01)()(min x X g x X f 解：1>构造惩罚函数2)]1,0[max()(),(x M x f M x q k k −+=⎩⎨⎧≤−+>=1,)1(1 ,2x x M x x x k 2>求解),(min kR x M x q ∈令：⎩⎨⎧<−−>==1),1(211,1),(0x x M x dx M x dq k k 解得无约束问题的最小值点k kM x 211−=3>显然，且随着罚因子R x k ∉k M 的增大，离约束最优点越来越近。
k x *x 1)211(lim lim *=−==∞→∞→k k kk Mx x【例3－20】分析下面规划问题⎪⎩⎪⎨⎧=−+==−+=+02)(01)()min(212212221x x X h x x X h x x i解：显然φ=R ，本题无最优解。
如果按惩罚函数法步骤计算，构造惩罚函数222121212(,)(1)(2)q X M x x M x x M x x =+++−++−2令⎪⎪⎩⎪⎪⎨⎧=−++−++=∂∂=−++−++=∂∂0)2(2)1(220)2(2)1(22212122212111x x M x x M x x q x x M x x M x x q解得无约束问题的最优解14321+==M Mx x所以TT M M M M M X ⎟⎠⎞⎜⎝⎛→⎟⎠⎞⎜⎝⎛++=43,43143,143)(*即，按罚法函数法得到了原问题的虚假最优解T⎟⎠⎞⎜⎝⎛43,43。
（二）障碍函数法1．基本原理⎩⎨⎧=≤p j X g X f j ,,2,1,0)()(min " 记0R 为可行域的内部，即{}p j X g X R j ,,2,1,0)(0"=<=想法：希望构造一个函数，在可行域的内部距边界面“越远”的地方与原问题的目标函数越“相近”；而当0R X ∈接近边界面时，新的函值将急骤上升，就象在可行域的边界设立了一道障碍，使得迭代点一旦接近边界便碰壁而回。
