An interior feasible direction method with constraint projections for linear programming (Q804468)

This paper presents a non-simplex feasible direction method to solve linear programming problems which is not boundary following. Its basic ideas are: (1) Given a feasible interior point \(X^ 0\) and a direction that improves the objective function \((C^ TX)\) a point \(X^ 1\) on a constraint surface is calculated. (2) At this point the negative gradient of the constraint surface is projected onto \(H=\{X/C^ TX=C^ TX^ 1\}\), the hyperplane of constant function value. (3) Search n points on n constraints surfaces bounding H and calculate the centre \(\hat y\) of the simplex defined by such points. (4) Calculate the vertex \(x^ v\) corresponding to the n bounding constraints. (5) If \(x^ v\) is not feasible or feasible with a worse function value the next iteration is started from \(\hat y.\) Otherwise \(x^ v\) is tested for optimality (the text results in an application of the Kuhn-Tucker-conditions). If \(x^ v\) is not optimal the next iteration is started from a perturbed point. The application of the method to randomly generated problems is reported. It is remarked that the method allows to exploit parallel computing (an advantage with respect to the highly sequential simplex method).