On large scale nonlinear Network optimization
Mathematical ProgrammingPublished 1 March 1990
Philippe L. Toint, Daniel Tuyttens
Citations51
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
The method proposed thus uses partial separability and partitioned quasi-Newton updating techniques for handling the cost function, while more classical tools as variable partitioning and specialized data structures are used in handling the network constraints.
Abstract
Partial separability and partitioned quasi-Newton updating have been recently introduced and experimented with success in large scale nonlinear optimization, large nonlinear least squares calculations and in large systems of nonlinear equations. It is the purpose of this paper to apply this idea to large dimensional nonlinear network optimization problems. The method proposed thus uses these techniques for handling the cost function, while more classical tools as variable partitioning and specialized data structures are used in handling the network constraints. The performance of a code implementing this method, as well as more classical techniques, is analyzed on several numerical examples. © 1990 The Mathematical Programming Society, Inc.
Keywords
Computer ScienceMathematics
Society for Industrial and Applied Mathematics eBooksNumerical Methods for Unconstrained Optimization and Nonlinear Equations
7,651 Citations1996J. E. Dennis, Robert B. Schnabel
Practical Methods of Optimization
6,403 Citations2000R. Ian Fletcher
ACM Transactions on Mathematical SoftwareBasic Linear Algebra Subprograms for Fortran Usage
1,633 Citations1979C. L. Lawson, Richard Hanson +2 more
A package of 38 low level subprograms for many of the basic operations of numerical linear algebra is presented, intended to be used with FORTRAN.
SIAM Journal on Numerical AnalysisInexact Newton Methods
1,540 Citations1982Ron S. Dembo, Stanley C. Eisenstat +1 more
SIAM Journal on Control and OptimizationProjected Newton Methods for Optimization Problems with Simple Constraints
622 Citations1982Dimitri P. Bertsekas
Mathematical ProgrammingLarge-scale linearly constrained optimization
528 Citations1978B. A. Murtagh, Michael A. Saunders
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.
Mathematical ProgrammingTruncated-Newton algorithms for large-scale unconstrained optimization
420 Citations1983Ron S. Dembo, Trond Steihaug
An algorithm for large-scale unconstrained optimization based on Newton's method is presented, shown to have strong convergence properties and has the unusual feature that the asymptotic convergence rate is a user specified parameter which can be set to anything between linear and quadratic convergence.
SIAM Journal on Numerical AnalysisGlobal Convergence of a Class of Trust Region Algorithms for Optimization with Simple Bounds
319 Citations1988Andrew R. Conn, Nicholas I. M. Gould +1 more
It is shown that, when the strict complementarily condition holds, the proposed algorithms reduce to an unconstrained calculation after finitely many iterations, allowing a fast asymptotic rate of convergence.
Mathematical ProgrammingMatrix conditioning and nonlinear optimization
231 Citations1978David F. Shanno, Kang -Hoh Phua
Results indicate strong superiority computationally for the Davidon and BFGS update over the self-scaling update, except on a special class of functions, the homogeneous functions.
Management ScienceSolving the Pipe Network Analysis Problem Using Optimization Techniques
201 Citations1978Michael A. Collins, Leroy L. Cooper +3 more
It is shown that the pipe network analysis problem may be described mathematically in terms of a nonlinear convex cost network flow problem and three mathematical programming algorithms for solving this problem have been coded and are computationally compared with a code using the traditional Newton-Raphson technique.
Management ScienceExceptional Paper—Design and Implementation of Large Scale Primal Transshipment Algorithms
200 Citations1977Gordon H. Bradley, Gerald G. Brown +1 more
This report also appears as Working Paper No. 260, Western Management Science Institute, University of California, Los Angeles, November 1976.
Numerische MathematikPartitioned variable metric updates for large structured optimization problems
158 Citations1982Andreas Griewank, Philippe L. Toint
A minimization method based on the idea of partitioned updating of the Hessian matrix in the case where the objective function can be decomposed in a sum of convex “element” functions is presented.
Academic Press eBooksTowards an Efficient Sparsity Exploiting Newton Method for Minimization
157 Citations1981Philippe L. Toint
Numerische MathematikLocal convergence analysis for partitioned quasi-Newton updates
147 Citations1982Andreas Griewank, Philippe L. Toint
Local and Q-superlinear convergence is established for an inexact partitioned variable metric method under mild assumptions on the initial Hessian approximations for the optimization of partially separable objective functions.
Operations ResearchA Nonlinear Network Flow Algorithm for Maximization of Benefits in a Hydroelectric Power System
142 Citations1981Richard E. Rosenthal
A nonlinear network flow algorithm for maximization of benefits in a multireservoir hydroelectric power system is presented and an unusual feature of the algorithm is an integer programming subproblem whose exact solution determines the superbasic set and the search directions.
IMA Journal of Numerical AnalysisGlobal Convergence of a a of Trust-Region Methods for Nonconvex Minimization in Hilbert Space
138 Citations1988Philippe L. Toint
Transportation ScienceAn Application and Validation of Equilibrium Trip Assignment Methods
113 Citations1976Michaël Florian, Sang Quang Nguyen
Mathematical programming studiesAn efficient implementation of the network simplex method
89 Citations1986Michael D. Grigoriadis
This paper describes an efficient implementation of the network simplex method for solving large sparse minimum-cost network flow problems which employs an initial spanning tree of all artificial edges, a gradual penalty method for reducing infeasibilities and a sample pricing strategy which does not require adjacency-ordered edge lists.
Mathematical programming studiesA scaled reduced gradient algorithm for network flow problems with convex separable costs
69 Citations1981Ron S. Dembo, John G. Klincewicz
An algorithm for the convex-cost, separable network flow problem that makes explicit use of the second-order information and also exploits the special network programming data structures originally developed for the linear case is presented.
Mathematical ProgrammingConvergence properties of trust region methods for linear and convex constraints
64 Citations1990James V. Burke, Jorge J. Morè +1 more
A convergence theory for convex and linearly constrained trust region methods which only requires that the step between iterates produce a sufficient reduction in the trust region subproblem to be developed.
Mathematical programming studiesA primal truncated newton algorithm with application to large-scale nonlinear network optimization
48 Citations1987Ron S. Dembo
A new, convergent, primal-feasible algorithm for linearly constrained optimization that is capable of rapid asymptotic behavior and has relatively low storage requirements is described.
Management ScienceTwo-Segment Separable Programming
44 Citations1979R. R. Meyer
New iterative separable programming techniques based on two-segment, piecewise-linear approximations are described for the minimization of convex separable functions over convex sets, showing rapid convergence and very close bounds on the optimal value.
NetworksA Newton method for convex separable network flow problems
44 Citations1983John G. Klincewicz
This paper proposes an approximate implementation of the quadratically convergent Newton algorithm that exploits the network structure in a way that allows certain crucial matrix-vector products to be computed in a simple pass through the arcs.
SIAM Journal on Scientific and Statistical ComputingOn Large Scale Nonlinear Least Squares Calculations
44 Citations1987Philippe L. Toint
Preliminary numerical experience is presented, which shows that actual numerical solution of a large class of fitting problems involving several hundreds of nonlinear parameters is possible at a reasonable cost.
Lecture notes in mathematicsNumerical experiments with partially separable optimization problems
43 Citations1984Andreas Griewank, Philippe L. Toint
It is shown that exploiting the present underlying structure can lead to efficient algorithms, especially when the problem dimension is large, and both unconstrained and bound constrained cases.
Mathematics of ComputationNumerical Solution of Large Sets of Algebraic Nonlinear Equations
40 Citations1986Philippe L. Toint
It is shown that the partitioned updating quasi-Newton methods for the solution of high-dimensional systems of algebraic nonlinear equations presents some advantages in efficiency over competing algorithms, and that use of the partially separable structure of the system can lead to significant improvements also in the more classical discrete Newton method.
Mathematics of ComputationNumerical solution of large sets of algebraic nonlinear equations
36 Citations1986Philippe L. Toint
ACM Transactions on Mathematical SoftwareA Reduced Gradient Algorithm for Nonlinear Network Problems
31 Citations1983Philip Beck, Leon S. Lasdon +1 more
This work considers the specializaton of one reduced gradient method to problems with a nonlinear objective and linear network constraints, and proposes extensions of data structures used in linear network codes that deal with the possibility of varying several nonbasic variables simultaneously.
Mathematical programming studiesBasis exchange characterizations for the simplex son algorithm for LP/embedded networks
22 Citations1985Fred Glover, Darwin Klingman
This paper shows that the topology of the master basis tree and the rules by which it can admissibly be restructured can be characterized by seven mutually exclusive and collectively exhaustive basis exchange cases.
European Journal of Operational ResearchPerformance evaluation of independent superbasic sets on nonlinear replicated networks
19 Citations1986Laureano F. Escudero
By using a networks-specialized implementation of a linearly constrained nonlinear programming algorithm, the computational performance of the new concept of independent superbasic sets that allows to obtain in parallel independent pieces of the solution at each iteration is reported.
Mathematical programming studiesA motivation for using the truncated Newton approach in a very large scale nonlinear network problem
14 Citations1986Laureano F. Escudero
Mathematical programming studiesThe performance of NLPNET, a large-scale nonlinear network optimizer
12 Citations1986Ron S. Dembo
The performance of NLPNET, a state-of-the-art nonlinear network optimizer based on the Primal Truncated Newton algorithm in Dembo, is described and contrasted with other codes for the same problem class.
Lecture notes in economics and mathematical systemsA Reduced Subgradient Algorithm for Network Flow Problems with Convex Nondifferentiable Costs
1 Citations1985Melville A. Hanscom, Van Hien Nguyen +1 more