判定线性不等式围成的空间是否为空的梯度快速算法

Fast projection algorithm to determine the emptiness of regions bounded by linear constraints

给出一个判定线性不等式围成的空间是否为空的快速算法.这个算法利用空间中的投影矩阵将一个射线投影到约束仿射空间的一个向量,使得算法能够用最快的速度逼近交空间中的一个可行点.实验结果表明,这个算法比作者以前的分治算法要快很多倍,特别是在空间的维数很大的情况.

This paper gives a fast algorithm to determine the emptiness of region bounded by linear inequalities. The algorithm makes use of projection matrix to project the moving vector in the constrained affine space. Thus, the algorithm will quickly find a feasible point for a moving point along the projected vector. Experiments show that this algorithm is several times faster than the vector positioning algorithm formerly presented by the author, especially when dimension of the space is large.