第十一次可行方向法.pdfVIP

可行方向法 1. Frank −Wolfe 方法 2. 可行方向法 3. 既约梯度法 一. Frank −Wolfe 方法 1. 问题 给定非线性规划问题 min f (x ) Ax b ⎧ . . (1) s t ⎨ ⎩x ≥0 其中A 是m ×n 矩阵，秩为m ，b 是m 维列向量，f (x ) 是可微 n 函数，x ∈R 。 令 D {x |Ax b , x ≥0 }, 称D 为可行域。 2. 算法分析 算法思想：在每次迭代中，将目标 函数f (x ) 线性化，再利用 线性规划方法求解。 算法分析： 设已知可行点 x k , 则有 ≈ k +∇ k T − k f (x ) f (x ) f (x ) ( x x ) ∇f x k T x + f x k −∇f x k T x k ( ) [ ( ) ( ) ] 求解线性规划 ∇ k T min f (x ) x (2) s .t . x ∈D f x x k D y k 定理 设 可微， ，如果 是线性规划（ ）的最优解， ( ) ∈ 2 则有 f x k T y k x k x k K T （）当 时 则 是（）的 点。 i ∇ ( ) ( − ) 0 , 1 − ii f x k T y k x k d k y k x k f x （ ）当 时 则向量 是 在点 ∇ ( ) ( − ) ≠0 , − ( ) x k D 处关于 的可行下降方向。 证明：(i) Qy k 是线性规划的最优解， 而∇f (x k )T y k ∇f (x k )T x k . ∴x k 也是线性规划问题的最优解。 ∴x k 也是线性规划问题(2) 的K −T 点。 ⎧ f (x k ) λ AT u 0 ∇ − − ⎪ T k ∴ ⎨ λ x 0 (*) ⎪ λ 0 ⎩