Column Generation Algorithms for Nonlinear Optimization, I: Convergence Analysis

References

• Aubin , J.-P. and Frankowska , H. 1990 . Set-Valued Analysis , Boston , MA : Birkhäuser .
   Google Scholar
• Barnhart , C. , Johnson , E.L. , Nemhauser , G.L. , Savelsberg , G.L. and Vance , P.H. 1998 . Branch-and-price: column generation for solving huge integer programs . Operations Research , 46 : 316 – 329 .
   Web of Science ®Google Scholar
• Bazaraa , M.S. , Sherali , H.D. and Shetty , C.M. 1993 . Nonlinear Programming: Theory and Algorithms, , 2nd Edn. , New York , NY : John Wiley and Sons .
   Google Scholar
• Bertsekas , D.P. 1982 . Projected Newton methods optimization problems with simple constraints . SIAM Journal on Control and Optimization , 20 : 221 – 246 .
   Web of Science ®Google Scholar
• Burke , J.V. and Ferris , M.C. 1991 . Characterization of solution sets of convex programs . Operations Research Letters , 10 : 57 – 60 .
   Web of Science ®Google Scholar
• Burke , J.V. and Ferris , M.C. 1993 . Weak sharp minima in mathematical programming . SIAM Journal on Control and Optimization , 31 : 1340 – 1359 .
   Web of Science ®Google Scholar
• Burke , J.V. and Moré , J.J. 1988 . On the identification of active constraints . SIAM Journal on Numerical Analysis , 25 : 1197 – 1211 .
   Web of Science ®Google Scholar
• Burke , J.V. and Moré , J.J. 1994 . Exposing constraints . SIAM Journal on Optimization , 4 : 573 – 595 .
   Web of Science ®Google Scholar
• Dantzig , G.B. and Wolfe , P. 1960 . Decomposition principle for linear programs . Operations Research , 8 : 101 – 111 .
   Web of Science ®Google Scholar
• Dembo , R.S. and Tulowitzki , U. 1988 . Computing equilibria on large multicomodity networks: An application of truncated quadratic programming algorithms . Networks , 18 : 273 – 284 .
   Web of Science ®Google Scholar
• Dunn , J.C. 1987 . On the convergence of projected gradient processes to singular critical points . Journal of Optimization Theory and Applications , 55 : 203 – 216 .
   Web of Science ®Google Scholar
• Dussault , J.P. and Marcotte , P. 1989 . Conditions de régularité géométrique pour les inéquations variationnelles . Recherche opérationelle , 23 : 1 – 16 .
   Google Scholar
• Evans , S.P. 1976 . Derivation and analysis of some models for combining trip distribution and assignment . Transportation Research , 10 : 37 – 57 .
   Google Scholar
• Fukushima , M. 1992 . Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems . Mathematical Programming , 53 : 99 – 110 .
   Web of Science ®Google Scholar
• García , R. and Marín , A. Urban multimodal interchanges (Macro Vision) . Conference presentation at the EURO XV-INFORMS XXXIV Joint International Meeting . July 14-17 , Barcelona .
   Google Scholar
• García , R. and Marín , A. Using RSD within partial linearization methods . Conference presentation at the 16th International Symposium on Mathematical Programming . August 24-29 , Lausanne .
   Google Scholar
• García , R. , Marín , A. and Patriksson , M. 2003 . Column Generation Algorithms for Nonlinear Optimization, II: Numerical Investigations, Report , Gothenburg , , Sweden : Department of Mathematics, Chalmers University of Technology . (to appear)
   Google Scholar
• Goffin , J.-L. , Haurie , A. and Vial , J.-P. 1992 . Decomposition and nondifferentiable optimization with the protective algorithm . Management Science , 37 : 284 – 302 .
   Web of Science ®Google Scholar
• Goldstein , A.A. 1964 . Convex programming in Hubert space . Bulletin of the American Mathematical Society , 70 : 709 – 710 .
   Web of Science ®Google Scholar
• Guignard , M. 1969 . Generalized Kuhn-Tucker conditions for mathematical programming problems in a Danach space . SIAM Journal on Control , 7 : 232 – 241 .
   Web of Science ®Google Scholar
• Hammond , J.H. 1984 . “ Solving Asymmetric Variational Inequality Problems and Systems of Equations with Generalized Nonlinear Programming Algorithms ” . Cambridge , MA : Department of Mathematics, Massachusetts Institute of Technology . PhD thesis
   Google Scholar
• Harker , P.T. and Pang , J.-S. 1990 . Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications . Mathematical Programming , 48 : 161 – 220 .
   Web of Science ®Google Scholar
• Hearn , D.W. , Lawphongpanich , S. and Ventura , J.A. 1985 . Finiteness in restricted simplicial decomposition . Operations Research Letters , 4 : 125 – 130 .
   Web of Science ®Google Scholar
• Hearn , D.W. , Lawphongpanich , S. and Ventura , J.A. 1987 . Restricted simplicial decomposition: computation and extensions . Mathematical Programming Study , 31 : 99 – 118 .
   Web of Science ®Google Scholar
• Higgins , J.E. and Polak , E. 1990 . Minimizing pseudoconvex functions on convex compact sets . Journal of Optimization Theory and Applications , 65 : 1 – 27 .
   Web of Science ®Google Scholar
• Holloway , C.A. 1974 . An extension of the Frank and Wolfe method of feasible directions . Mathematical Programming , 6 : 14 – 27 .
   Google Scholar
• Hooke , R. and Jeeves , T.A. 1961 . Direct search solution of numerical and statistical problems . Journal of the Association for Computer Machinery , 8 : 212 – 229 .
   Google Scholar
• Jayakrishnan , R. , Tsai , W.K. , Prashker , J.N. and Rajadhyaksha , S. 1994 . Faster path-based algorithm for traffic assignment . Transportation Research Record , 1443 : 75 – 83 .
   Google Scholar
• Jones , K.L. , Lustig , I.J. , Farvolden , J.M. and Powell , W.B. 1993 . Multicommodity network flows: the impact of formulation on decomposition . Mathematical Programming , 62 : 95 – 117 .
   Web of Science ®Google Scholar
• Kim , K. and Nazareth , J.L. 1991 . The decomposition principle and algorithms for linear programming . Linear Algebra and its Applications , 152 : 119 – 133 .
   Web of Science ®Google Scholar
• Larsson , T. , Migdalas , A. and Patriksson , M. July 1999 . A Generic Column Generation Scheme , Report LiTH-MAT-R-94-18 July , Lilnköping , , Sweden : Department of Mathematics, Linköpint Institute of Technology . 1994. Revised version
   Google Scholar
• Larsson , T. and Patriksson , M. 1992 . Simplicial decomposition with disaggregated representation for the traffic assignment problem . Transportation Science , 26 : 4 – 17 .
   Web of Science ®Google Scholar
• Larsson , T. , Patriksson , M. and Rydergren , C. 1997 . “ Applications of simplicial decomposition with nonlinear column generation to nonlinear network flows ” . In Network Optimization , Edited by: Pardalos , P.M. , Hager , W.W. and Hearn , D.W. 346 – 373 . Berlin : Springer-Verlag .
   Google Scholar
• Lasdon , L.S. 1970 . Optimization Theory for Large Systems , New York , NY : Macmillan .
   Google Scholar
• Lawphongpanich , S. and Hearn , D.W. 1984 . Simplicial decomposition of the asymmetric traffic assignment problem . Transportation Research , 18B : 123 – 133 .
   Google Scholar
• Levitin , E.S. and Polyak , B.T. 1966 . Constrained minimization methods . USSR Computational Mathematics and Mathematical Physics , 6 : 1 – 50 .
   Google Scholar
• Luenberger , D.G. 1984 . Linear and Nonlinear Programming, , 2nd Edn. , Reading , MA : Addison-Wesley .
   Google Scholar
• Lundgren , J.T. and Patriksson , M. Transportation networks: recent methodological advances . Selected Proceedings of the 4th EURO Transportation Meeting, Newcastle University, Newcastle, UK . September 9-11 . An Algorithm for the Combined Distribution and Assignment Model , Edited by: Bell , M.G. H. pp. 239 – 253 . Amsterdam : Peragamon Press .
   Google Scholar
• Marcotte , P. and Dussault , J.-P. 1989 . A sequential linear programming algorithm for solving monotone variational inequalities . SIAM Journal on Control and Optimization , 27 : 1260 – 1278 .
   Web of Science ®Google Scholar
• Marcotte , P. and Zhu , D. 1998 . Weak sharp solutions of variational inequalities . SIAM Journal on Optimization , 9 : 179 – 189 .
   Web of Science ®Google Scholar
• Migdalas , A. 1994 . A regularization of the Frank-Wolfe method and unification of certain nonlinear programming methods . Mathematical Programming , 65 : 331 – 345 .
   Web of Science ®Google Scholar
• Patriksson , M. 1993 . Partial linearization methods in nonlinear programming . Journal of Optimization Theory and Applications , 78 : 227 – 246 .
   Web of Science ®Google Scholar
• Patriksson , M. 1993 . A unified description of iterative algorithms for traffic equilibria . European Journal of Operational Research , 71 : 154 – 176 .
   Web of Science ®Google Scholar
• Patriksson , M. 1998 . Cost approximation: a unified framework of descent algorithms for nonlinear programs . SIAM Journal on Optimization , 8 : 561 – 582 .
   Web of Science ®Google Scholar
• Patriksson , M. 1998 . Nonlinear Programming and Variational Inequality Problems--A Unified Approach , The Netherlands : Kluwer Academic Publishers, Utrecht .
   Google Scholar
• Polyak , B.T. 1987 . Introduction to Optimization , New York , NY : Optimization Software .
   Google Scholar
• Rockafellar , R.T. 1970 . Convex Analysis , Princeton , NJ : Princeton University Press .
   Google Scholar
• Rockafellar , R.T. and Wets , R.J.-B. 1998 . Variational Analysis , Berlin : Springer-Verlag .
   Google Scholar
• Rudin , W. 1976 . Principles of Mathematical Analysis, , 3rd Edn. , Auckland : McOraw-Hill .
   Google Scholar
• Salinetti , G. and Wets , R.-B. 1979 . On the convergence of sequences of convex sets in finite dimensions . SIAM Review , 21 : 18 – 33 .
   Web of Science ®Google Scholar
• Tseng , P. 1991 . Decomposition algorithm for convex differentiable minimization . Journal of Optimization Theory and Applications , 70 : 109 – 135 .
   Web of Science ®Google Scholar
• Ventura , J.A. and Heam , D.W. 1993 . Restricted simplicial decomposition for convex constrained problems . Mathematical Programming , 59 : 71 – 85 .
   Web of Science ®Google Scholar
• VonHohenbalken , B. 1977 . Simplicial decomposition in nonlinear programming algorithms . Mathematical Programming , 13 : 49 – 68 .
   Web of Science ®Google Scholar
• Wolfe , P. 1970 . “ Convergence theory in nonlinear programming ” . In Integer and Nonlinear Programming , Edited by: Abadie , J. 1 – 36 . New York , NY : North-Holland .
   Google Scholar
• Wolsey , L.A. 1998 . Integer Programming , New York , NY : John Wiley and Sons .
   Google Scholar
• Zhangwill , W.I. 1969 . Nonlinear Programming: A Unified Approach , Englewood Cliffs , NJ : Prentice-Hall .
   Google Scholar
• Zhu , D.L. and Marcotte , P. 1995 . Coupling the auxiliary problem principle with descent methods of pseudoconvex programming . European Journal of Operational Research , 83 : 670 – 685 .
   Google Scholar