第7章约束问题的优化方法

90 第7 章 约束问题的优化方法 §7 .1 可行方向法 7 .1 .1 可行方向法的基本思想 可行方向法是一类算法,可看作无约束下降算法的自然推广。典型策略是从可行点出发，沿着下降可行方向进行搜索，求出使目标函数值下降的新的可行点． 考虑只含线性约束的非线性规划问题： eExbAxxf s.t.)( min （1） )(xf为非线性函数，nmRA， nlRE，mRb，lRe. 注1：线性约束规格保证了优化问题（1）的可行方向集、线性化可行方向集以及序列化可行方向集是等同的。 当某个可行方向同时也是目标函数的下降方向时，沿此方向移动一定会在满足可行性的情况下改进迭代点的目标函数值。 目前已经提出许多可行方向法，用来处理具有线性约束的非线性规划问题。 搜索方向选择方式不同形成不同的可行方向法： （1）Zoutendijk可行方向法 （2）Rosen梯度投影法 （3）Wolfe既约梯度法 可行方向的判定： 定理 1：设 xˆ 是问题（1）的可行解，在点xˆ 处有11ˆbxA，22 ˆbxA，其中 21AAA， 21bbb 则非零向量 d 为xˆ 处的可行方向的充要条件是 01 dA，0Ed 证明： 必要性：设非零向量 d 是xˆ 处的可行方向．根据可行方向的定义，0，使得对每个),0(  ．有dxˆ为可行点，即bdxA)ˆ(，edxE)ˆ(. 21221121ˆ)ˆ()ˆ(bbdAxAdAbdxAAdxA 由于0，由上式得到01 dA． 又由edxE)ˆ(得到0Ed. 91 充分性：设01 dA，0Ed. 由于22 ˆbxA，则0，使得对于所有的),0(  ,成立22)ˆ(bdxA . 根据假设及11ˆbxA，得到11)ˆ(bdxA . 上述两式组合起来就是bdxA)ˆ(. 又由0Ed及exE ˆ可知 edxE)ˆ( 表明dxˆ是可行点，因此d 是xˆ 处的可行方向． 7.1.2 Zou tendijk 可行方向法 Zou tendijk 子问题： 根据定理1，如果非零向量d 同时满足0)ˆ(dxfT, 01 dA，0Ed,则d 是xˆ 处的下降可行方向． Zou tendijk 可行方向法把确定搜索方向归结为求解线性规划问题 n j | |dEddAdxfjT,,2,1,1 0 0 s.t.)( min1 （2） 在（2）式中，显然0d是可行解，可推知目标函数最优值必定小于或等于零．如果目标函数最优值小于零，则得到下降可行方向d ；否则，如果目标函数最优值为零，则x是...