An interior feasible direction method with constraint projections for linear programming
type: Item
instance of: scholarly article
title: An interior feasible direction method with constraint projections for linear programming
zbMATH Open document ID: 0727.90048
DOI: 10.1016/0898-1221(90)90163-E
author: N. E. Zubov
publication date: 1990-01-01T00:00:00Z
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).
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90-08
Mathematics Subject Classification ID: 65Y05
zbMATH DE Number: 4202015
zbMATH Keywords: gradient projection
zbMATH Keywords: non-simplex feasible direction method
zbMATH Keywords: parallel computing
reviewed by: S. M. Allende-Alonso
describes a project that uses: IMSL Numerical Libraries
MaRDI profile type: Publication
cites work: Q3844775
cites work: A new polynomial-time algorithm for linear programming
cites work: Q3754586
cites work: An external reconstruction approach (ERA) to linear programming
cites work: Q3277015
cites work: The Gradient Projection Method for Nonlinear Programming. Part I. Linear Constraints
cites work: Q5564917
cites work: The Convex Simplex Method
cites work: Q4188659
cites work: Q4051879
published in: Computers & Mathematics with Applications
description: scientific article; zbMATH DE number 4202015