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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
P. Beck, L. Ladson and M. Engquist, “A reduced gradient algorithm for nonlinear network problems,”ACM Transactions on Mathematical Software 9 (1983) 57–70.
D.P. Bertsekas, “Projected Newton methods for optimization problems with simple constraints,”SIAM Journal of Control and Optimization 20 (1980) 221–246.
G.H. Bradley, G.G. Brown and G.W. Graves, “Design and implementation of large scale transshipment algorithms,”Management Science 24 (1977) 1–34.
J.V. Burke, J.J. Moré and G. Toraldo, “Convergence properties of trust region methods for linear and convex constraints,” Technical Memorandum 116, Mathematics and Computer Science Division, Argonne National Laboratory (Argonne, 1988).
M. Collins, L. Cooper, R.V. Helgason, J.L. Kennington and L.J. LeBlanc, “Solving the pipe network analysis problem using optimization techniques,”Management Science 24 (1978) 747–780.
A.R. Conn, N.I.M. Gould and Ph.L. Toint, “Global convergence of a class of trust region algorithms for optimization with simple bounds,”SIAM Journal on Numerical Analysis 25 (1988) 433–460.
L. Cooper and J. Kennington, “Steady-state analysis of nonlinear resistive networks using optimization techniques,” Technical Report IEOR 77012, Southern Methodist University (Dallas, 1977).
G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).
R.S. Dembo, “A bending backtracking linesearch for constrained optimization,” Yale School of Management, Yale University (New Haven, CT, 1984).
R.S. Dembo, “The performance of NLPNET, a large scale nonlinear network optimizer,”Mathematical Programming Studies 26 (1986) 245–249.
R.S. Dembo, “A primal truncated Newton algorithm with application to large scale nonlinear network optimization,”Mathematical Programming Studies 31 (1987) 43–71.
R.S. Dembo, S.C. Eisenstate and T. Steihaug, “Inexact Newton methods,”SIAM Journal on Numerical Analysis 19(2) (1982) 400–408.
R.S. Dembo and J.G. Klincewicz, “A scaled reduced gradient algorithm for network flow problems with convex separable costs,”Mathematical Programming Studies 15 (1981) 125–147.
R.S. Dembo and T. Steihaug, “Truncated-Newton algorithms for large scale unconstrained optimization,”Mathematical Programming 26 (1983) 190–212.
J.E. Dennis and R.B. Schnabel,Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Prentice-Hall, Englewood Cliffs, NY, 1983).
L.F. Escudero, “A motivation for using the truncated Newton approach in a very large scale nonlinear network problem,”Mathematical Programming Studies 26 (1986) 240–245.
L.F. Escudero, “Performance evaluation of independent superbasic sets on nonlinear replicated networks,”European Journal of Operational Research 23 (1986) 343–355.
R. Fletcher,Practical Methods of Optimization (Wiley, New York, 1980).
M. Florian and S. Nguyen, “An application and validation of equilibrium trip assignment methods,”Transportation Science 10 (1976) 374–389.
J.L. de la Fuente, “Programacion no-lineal: applicaciones en analisis, gestion y planificacion de sistemas electricos,” private communication (1986).
P.E. Gill, W. Murray and M.H. Wright,Practical Optimization (Academic Press, New York, 1981).
F. Glover and D. Klingman, “Basis exchange characterization for the simplex SON algorithm for LP/embedded networks,”Mathematical Programming Studies 24 (1985) 141–157.
A. Griewank and Ph.L. Toint, “Partitioned variable metric updates for large structured optimization problems,”Numerische Mathematik 39 (1982) 119–137.
A. Griewank and Ph.L. Toint, “Local convergence analysis for partitioned quasi-Newton updates,”Numerische Mathematik 39 (1982) 429–448.
A. Griewank and Ph.L. Toint, “On the unconstrained optimization of partially separable functions,” in: M.J.D. Powell, ed.,Nonlinear Optimization 1981 (Academic Press, New York, 1982) pp. 301–312.
A. Griewank and Ph.L. Toint, “Numerical experiments with partially separable optimization problems,” in: D.F. Griffiths, ed.,Numerical Analysis Proceedings Dundee 1983, Lecture Notes in Mathematics, Vol. 1066 (Springer, Berlin, 1984) pp. 203–220.
M.D. Grigoriadis, “An efficient implementation of the network simplex method,”Mathematical Programming Studies 26 (1986) 83–111.
M. Hanscom, V.H. Nguyen and J.J. Strodiot, “A reduced subgradient algorithm for network flow problems with convex nondifferentiable costs,” in: V.F. Demyanov, ed.,Proceedings of the IIASA NDO Workshop, Sopron 1984, Lecture Notes in Economics and Mathematical Systems (Springer, Berlin, 1985) pp. 318–322.
J.L. Kennington and R.V. Helgason,Algorithms for Network Programming (Wiley, New York, 1980).
J.G. Klincewicz, “A Newton method for convex separable network flow problems,”Networks 13 (1983) 427–442.
C. Lawson, R. Hanson, D. Kincaird and F. Krogh, “Basic linear algebra subprograms for Fortran usage,”A.C.M. Transactions on Mathematical Software 5(3) (1979) 308–371.
A. Marin Gracia, “Optimizacion de redes no lineales convexas y separables,” in: J.P. Vilaplana and L.F. Escudero, eds.,Actas I Seminario Internacional de Investigacion Operativa del Pais Vasco, Argitarapen Zerbitzua Euskal Herriko Unibertsitatea (Bilbao, 1987) pp. 173–203.
R.R. Meyer, “Two segment separable programming,”Management Science 15 (1979) 385–395.
B. Murtagh and M. Saunders, “Large scale linearly constrained optimization,”Mathematical Programming 14 (1978) 41–72.
R.E. Rosenthal, “A nonlinear network flow algorithm for maximizing the benefits in a hydroelectric power system,”Operation Research 29 (1981) 763–786.
D.F. Shanno and K.H. Phua, “Matrix conditioning and nonlinear optimization,”Mathematical Programming 14 (1978) 149–160.
Ph.L. Toint, “Towards an efficient sparsity exploiting Newton method for minimization,” in: I.S. Duff, ed.,Sparse Matrices and Their Uses (Academic Press, London, 1981).
Ph.L. Toint, Test problems for partially separable optimization and results for the routine PSPMIN,” Technical Report 83/4, Dept. of Mathematics, FUNDP (Namur, Belgium, 1983).
Ph.L. Toint, “VE08AD, a routine for partially separable optimization with bounded variables,” Harwell Subroutine Library (A.E.R.E., UK, 1983).
Ph.L. Toint, “Numerical solution of large sets of algebraic nonlinear equations,”Mathematics of Computation 46 (1986) 175–189.
Ph.L. Toint. “On large scale nonlinear least squares calculations,”SIAM Journal on Scientific and Statistical Computing 8(3) (1987) 416–435.
Ph.L. Toint, “VE10AD, a routine for large scale nonlinear least squares,” Harwell Subroutine Library (Harwell Laboratory, UK, 1987).
Ph.L. Toint, “Global convergence of a class of trust region methods for nonconvex minimization in Hilbert space,”IMA Journal of Numerical Analysis 8 (1988) 231–252.
D. Tuyttens and J. Teghem, “Théorie des matroides et optimisation combinatoire,”Belgian Journal of Operations Research, Statistics and Computer Science 26(1) (1986) 27–62.
S. Zenios, “Numerical optimization benchmarks on advanced architecture computers,” Report 88-04-03, Decision Sciences Department, The Wharton School, University of Pennsylvania (Philadelphia, PA, 1988).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Toint, P.L., Tuyttens, D. On large scale nonlinear Network optimization. Mathematical Programming 48, 125–159 (1990). https://doi.org/10.1007/BF01582254
Issue Date:
DOI: https://doi.org/10.1007/BF01582254