最优化-可行方向法

Zoutendijk可行方向法

约束条件一般有两种

ax - b = 0

ax - b <= 0

取可行初始点x₁  x₁满足所有的约束条件

取约束条件中所有<= 0 的约束条件，并判断他们是否为0

获得线性规划子问题

一般使用图解法

min    ▽f(x_k).T * d

ad = 0

ad <= 0  此条件来源于对x_k满足 ax - b <= 0 中，等于0 的约束条件

-1<=d_i<=1

得到d_k

若▽f(x_k).T * d_k = 0，则x_k为KT点，终止计算

然后在可行域内，做一维搜索

获得x_k+1

详细做法如下

Rosen 投影梯度法

既约梯度法

感觉大概率要考这个

对于最优化问题min f(x) 

s.t.  AX = b

　　x >= 0

矩阵A是A_m*n

对于初始点x⁽¹⁾ 

找出x中前m个最大的分量，将他们的下标作为集合J

B = (a_i)  i属于集合j   为m*m矩阵

N = (ai) i不属于集合j 为(n-m)*m矩阵

▽_Bf(x⁽¹⁾) 为▽f(x)中 下标属于J的  m*1

▽_Nf(x⁽¹⁾) 为▽f(x)中 下标不属于J的  (n-m) * 1

r = ▽_Nf(x⁽¹⁾)_{.T - ▽Bf(x⁽¹⁾) * B^-1 * N      为 (n-m) *1}

d_N = 将r中的负数，变为正数，  正数变为 - x * r

d_B = -B^-1 * N * d_N

可行的方向就是dN和d_B组合起来

然后在可行域内做精确一维搜索即可

当可行梯度为0时，终止计算