第十章+可行方向法.pdf

第十章 可行方向法 min f (x ) x ∈R n s.t . aT x −b 0,i =∈E {1,,l } i i （10.0.1） aT x b 0, i I {l 1, , l m} − ≤ ∈ =+ + i i 一、可行方向法 （一）可行方向与可行下降方向 1． 可行方向 d (d ≠0, d ∈Rn ) 是约束问题（10.0.1）在可行点 x 处的可行方向是指存在δ 0 ，使得当a ∈(0,δ] 时，有x +aδ∈D 。这里D 是（10.0.1）的可行域。 判定：d 是可行点x 处的可行方向的充要条 件是 T a d 0, i =∈E i T a d ≤0, i ∈I (x) i 2 ． 可行下降方向 d 既是可行点x 处的可行方向，又是 x 处的 下降方向。 判定：若 d 满足 T a d 0, i =∈E i T a d 0, i I (x) ≤ ∈ i （10.1.1） T f (x ) d 0 ∇ 则 d 是x 处的可行下降方向。 （二）可行下降方向的求取 T 寻找满足条件（10.1.1），且使∇f (x ) d 达到最 小的 d ： ∇ T min f (x ) d T s t a d i =∈E . . i 0, （10.1.2） T a d ≤ i ∈I x i 0, ( ) 线性规划问题（10.1.2）无有限最优解，这是因 T ˆ ˆ ( ) 0 为若d 是线性规划问题的可行解，且∇f x d 。 ˆ d ad ,a =≠0 d 令 ，则 也是（10.1.2）的可行解，且