An interior feasible direction method with constraint projections for linear programming

DOI10.1016/0898-1221(90)90163-EMaRDI QIDQ804468zbMATH OpenFDO

Authors N. E. Zubov

Publication date 1990

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0898-1221(90)90163-E

zbMATH Keywords

gradient projectionnon-simplex feasible direction methodparallel computing

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Linear programming (90C05)

Review text

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).

Recommendations

• A feasible direction method for linear programming
• The complex interior-boundary method for linear and nonlinear programming with linear constraints
• Search directions for a class of projective methods
• An experimental investigation of a new multiplex method for linear programming
• scientific article; zbMATH DE number 4189470

Cites work

• A new polynomial-time algorithm for linear programming
• An external reconstruction approach (ERA) to linear programming
• scientific article; zbMATH DE number 3159112 (Why is no real title available?)
• scientific article; zbMATH DE number 4002053 (Why is no real title available?)
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 3626518 (Why is no real title available?)
• scientific article; zbMATH DE number 3284927 (Why is no real title available?)
• The Convex Simplex Method
• The Gradient Projection Method for Nonlinear Programming. Part I. Linear Constraints

Cited in

(9)

• A feasible descent cone method for linearly constrained minimization problems
• A steepest feasible direction extension of the simplex method
• scientific article; zbMATH DE number 3852784 (Why is no real title available?)
• An experimental investigation of a new multiplex method for linear programming
• scientific article; zbMATH DE number 22696 (Why is no real title available?)
• Linear programming with a feasible direction interior point technique for smooth optimization
• Search directions for a class of projective methods
• A feasible direction method for linear programming
• The complex interior-boundary method for linear and nonlinear programming with linear constraints

Describes a project that uses

Uses Software

• IMSL Numerical Libraries

This page was built for publication: An interior feasible direction method with constraint projections for linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q804468)