Large-scale linearly constrained optimization
Mathematical ProgrammingPublished 1 December 1978
B. A. Murtagh, Michael A. Saunders
Citations528
SJR quartileQ1
SJR score1.73
SNIP2.20
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An algorithm for solving large-scale nonlinear programs with linear constraints is presented, which combines efficient sparse-matrix techniques as in the revised simplex method with stable quasi-Newton methods for handling the nonlinearities.
Abstract
An algorithm for solving large-scale nonlinear programs with linear constraints is presented. The method combines efficient sparse-matrix techniques as in the revised simplex method with stable quasi-Newton methods for handling the nonlinearities. A general-purpose production code (MINOS) is described, along with computational experience on a wide variety of problems.
Keywords
Computer ScienceMathematics
The Computer JournalA Rapidly Convergent Descent Method for Minimization
4,571 Citations1963R. Fletcher, M. J. D. Powell
Archives of Sexual BehaviorApplied Nonlinear Programming
2,536 Citations1972D. M. Himmelblau
The high prevalence of Internet use as a method of meeting sexual partners suggests that sexual networks may be forming over the Internet and the Internet therefore provides opportunities for new HIV primary prevention interventions.
Mathematical ProgrammingRestart procedures for the conjugate gradient method
1,700 Citations1977M. J. D. Powell
The main purpose of this paper is to provide an algorithm with a restart procedure that takes account of the objective function automatically and to study a multiplying factor that occurs in the definition of the search direction of each iteration.
Management ScienceBimatrix Equilibrium Points and Mathematical Programming
1,020 Citations1965C. E. Lemke
SIAM Journal on OptimizationVariable Metric Method for Minimization
867 Citations1991William C. Davidon
This is a method for determining numerically local minima of differentiable functions of several variables by suitable choice of starting values, and without modification of the procedure, linear constraints can be imposed upon the variables.
Mathematics of ComputationMethods for modifying matrix factorizations
581 Citations1974Philip E. Gill, Gene H. Golub +2 more
Several methods are described for modifying Cholesky factors and a new algorithm is presented for modifying the complete orthogonal factorization of a general matrix, from which the conventional QR factors are obtained as a special case.
IMA Journal of Applied MathematicsQuasi-Newton Methods for Unconstrained Optimization
357 Citations1972Philip E. Gill, Walter Murray
Mathematical ProgrammingNewton-type methods for unconstrained and linearly constrained optimization
335 Citations1974Philip E. Gill, Walter Murray
The methods are intimately based on the recurrence of matrix factorizations and are linked to earlier work on quasi-Newton methods and quadratic programming.
Communications of the ACMThe simplex method of linear programming using LU decomposition
271 Citations1969Richard H. Bartels, Gene H. Golub
The theoretical background for an implementation which is based upon the LU decomposition, computed with row interchanges, of the basic matrix of the simplex method, which is slow, but has good round-off error behavior.
Sparse Matrices and their Applications
266 Citations1972Donald J. Rose, Ralph A. Willoughby
The Role of Partitioning in the Numerical Solution of Sparse Systems and several Strategies for Reducing the Bandwidth of Matrices are discussed.
SIAM Journal on Applied MathematicsExtension of Davidon’s Variable Metric Method to Maximization Under Linear Inequality and Equality Constraints
202 Citations1969Donald Goldfarb
ACM Transactions on Mathematical SoftwareAn Implementation of Tarjan's Algorithm for the Block Triangularization of a Matrix
199 Citations1978Iain Duff, John Reid
An implementation of Tarj an's algorithm for symmetrically permuting a given matrix to block tmangular form is described and results are presented from several experiments using the code developed by the authors.
Mathematical ProgrammingReinversion with the preassigned pivot procedure
154 Citations1971Eli Hellerman, Dennis C. Rarick
The consequences of column, pivot selection and sequence upon the transformation vector (ETA) density are shown and an algorithm which will tend to minimize eta density and work done per iteration is given.
The Bell Journal of EconomicsETA: A Model for Energy Technology Assessment
128 Citations1976Alan S. Manne
Selected applications of nonlinear programming
124 Citations1968Jerome Bracken, Garth P. McCormick
The first chapter, which is a general introduction to nonlinear programming, contains definitions, classifications of problems, mathematical characteristics, and solution procedures.
The Partitioned Preassigned Pivot Procedure (P4)
124 Citations1972Eli Hellerman, Dennis C. Rarick
Both speed and the preservation of sparsity are prime considerations during reinversion because no progress is made towards optimization during this process and a sparse ETA set will speed succeeding interations.
Numerische MathematikA stabilization of the simplex method
120 Citations1971Richard H. Bartels
An alternative implementation of the simplex method based upon L U decompositions of the basic matrices is presented, and its computational stability is indicated by a round-off error analysis.
Communications of the ACMReducing the retrieval time of scatter storage techniques
88 Citations1973Richard P. Brent
A new method for entering and retrieving information in a hash table is described, intended to be efficient if most entries are looked up several times.
Large-scale linear programming using the Cholesky factorization.
84 Citations1972Michael A. Saunders
A variation of the revised simplex method is proposed for solving the standard linear programming problem, based upon the orthogonal factorization B = LQ or, equivalently, upon the Cholesky factorization ${BB}^T = {LL]^T$ where B is the usual square basis, L is lower triangular and Q is Orthogonal.
Elsevier eBooksA FAST, STABLE IMPLEMENTATION OF THE SIMPLEX METHOD USING BARTELS-GOLUB UPDATING††Research for this paper was supported by the Energy Research and Development Administration Contract AT(04-3)-326 PA #18, at Stanford University.
79 Citations1976Michael A. Saunders
It is shown that the remainder of U (the part which is modified during updating) is typically small enough to be stored in-core as a dense matrix, which allows L and most of U to reside on disk.
Mathematics of ComputationMethods for computing and modifying the 𝐿𝐷𝑉 factors of a matrix
74 Citations1975Philip E. Gill, Walter Murray +1 more
Methods are given for computing the LDV factorization of a matrix B and modifying the factorization when columns of B are added or deleted and it is shown how these techniques lead to two numerically stable methods for updating the Cholesky factorizationof a matrix following the addition or subtraction,respectively, of a Matrix of rank one.
Aspects of large-scale in-core linear programming
66 Citations1971James E. Kalan
Minor changes in the computational aspects of the simplex algorithm coupled with efficient inverse matrix representation show that the major portion of the inverse in product form of a basis may be embedded in the constraint matrix.
Journal of the Operational Research SocietyNumerical Methods for Non-Linear Optimization
59 Citations1973S. Vajda
Mathematical ProgrammingProjection methods for non-linear programming
55 Citations1973R.W.H. Sargent, B. A. Murtagh
Several algorithms are presented for solving the non-linear programming problem, based on “variable-metric” projections of the gradient of the objective function into a local approximation to the constraints.
Mathematical ProgrammingAn alternate implementation of Goldfarb's minimization algorithm
48 Citations1975A. Buckley
The Goldfarb's algorithm can be regarded as an extension of linear programming to allow a non-linear objective function.
Mathematical ProgrammingOn the Bartels—Golub decomposition for linear programming bases
46 Citations1977Donald Goldfarb
It is shown that if the Bartels—Golub algorithm or one of its variants is used to update theLU factorization of B, then less computing is needed if one works with the factors of the updatedB than with those ofB.
Mathematical ProgrammingOn pricing and backward transformation in linear programming
42 Citations1974J. A. Tomlin
It is shown that a simple formula for updating the pricing vector can be used with some advantage in the standard product form simplex algorithm and with very considerable advantage in two recent developments: P.J. Harris' dynamic scaling method and the Forrest—Tomlin method for maintaining triangular factors of the basis.
SIAM Journal on Numerical AnalysisLinear Programming via a Nondifferentiable Penalty Function
39 Citations1976Andrew R. Conn
A numerically stable form of an algorithm that is closely related to the work of Gill and Murray and Conn is presented, and this feature enables it to be readily generalized to quadratic programming.
Mathematical programming studiesRobust implementation of Lemke's method for the linear complementarity problem
34 Citations1978John A. Tomlin
Management ScienceThe Variable Reduction Method for Nonlinear Programming
23 Citations1970Garth P. McCormick
A first-order method for solving the problem: minimize f(x) subject to Ax - b \geqq 0 is presented and contains ideas based on variable reduction with anti-zig-zagging and acceleration devices based on the Variable Metric Method.
Elsevier eBooksA Second Order Method for the Linearly Constrained Nonlinear Programming Problem
19 Citations1970Garth P. McCormick
If the strict second-order sufficiency conditions hold, the rate of convergence of the algorithm is shown to be superlinear or even quadratic with aLipschitz condition on the second derivatives of f(x) subject to Ax − b ≥ 0.
The modelling of energy production and consumption in New Zealand
1 Citations1975BA Murtagh, P.L. Lucas
This paper discusses the effectiveness of computer-based models for the quantitative assessment of energy policy issues and early experience with a model of Maui gas utilization is discussed, and current efforts to develop an entire energy industry model are described.