{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:28:23Z","timestamp":1787336903918,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2000,1]]},"abstract":"<jats:p>The problem of minimizing a sum of Euclidean norms dates from the 17th century and may be the earliest example of duality in the mathematical programming literature. This nonsmooth optimization problem arises in many different kinds of modern scientific applications. We derive a primal-dual interior-point algorithm for the problem, by applying Newton's method directly to a system of nonlinear equations characterizing primal and dual feasibility and a perturbed complementarity condition. The main work at each step consists of solving a system of linear equations (the Schur complement equations). This Schur complement matrix is not symmetric, unlike in linear programming. We incorporate a Mehrotra-type predictor-corrector scheme and present some experimental results comparing several variations of the algorithm, including, as one option, explicit symmetrization of the Schur complement with a skew corrector term. We also present results obtained from a code implemented to solve large sparse problems, using a symmetrized Schur complement. This has been applied to problems arising in plastic collapse analysis, with hundreds of thousands of variables and millions of nonzeros in the constraint matrix. The algorithm typically finds accurate solutions in less than 50 iterations and determines physically meaningful solutions previously unobtainable.<\/jats:p>","DOI":"10.1137\/s1064827598343954","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"243-262","source":"Crossref","is-referenced-by-count":117,"title":["An Efficient Primal-Dual Interior-Point Method for Minimizing a Sum of Euclidean Norms"],"prefix":"10.1137","volume":"22","author":[{"given":"Knud D.","family":"Andersen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Edmund","family":"Christiansen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew R.","family":"Conn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael L.","family":"Overton","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,25]]},"reference":[{"key":"R1","unstructured":"I. Adler and F. Alizadeh,\n                      Primal\u2010Dual Interior Point Algorithms for Convex Quadratically Constrained and Semidefinite Optimization Problems\n                      , Technical Report 46\u201095, RUTCOR, Rutgers University, New Brunswick, NJ, 1995."},{"key":"R2","unstructured":"E. D. Andersen and K. D. Andersen,\n                      The APOS Linear Programming Solver: An Implementation of the Homogeneous Algorithm\n                      , Technical Report, CORE Discussion Paper 9730, CORE, Universit\u00e9 Catholique de Louvain, Belgium, 1997."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018322318259"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1109\/43.673628"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827594275303"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1177\/027836499301200303"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/232826.232937"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0806006"},{"key":"R9","unstructured":"Erling Andersen, Yinyu Ye, On a homogeneous algorithm for a monotone complementarity problem with nonlinear equality constraints, SIAM, Philadelphia, PA, 1997, 1\u20131198d:90120"},{"key":"R10","unstructured":"D. V. Byrnes and L. E. Bright,\n                      Design of High\u2010Accuracy Multiple Flyby Trajectories Using Constrained Optimization\n                      , AAS Paper 95\u2010307, AAS\/AIAA Astrodynamics Specialist Conference, Halifax, NS, Canada, 1995."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0901037"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591853"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596299767"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Edmund Christiansen, Limit analysis of collapse states, Handb. Numer. Anal., IV, North\u2010Holland, Amsterdam, 1996, 193\u20133121422505","DOI":"10.1016\/S1570-8659(96)80004-4"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008285504599"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1051\/m2an:1999102"},{"key":"R17","unstructured":"H. W. Kuhn,\n                      On a pair of dual nonlinear programs\n                      , in Nonlinear Programming, J. Abadie, ed., North\u2013Holland, Amsterdam, 1967, pp. 38\u201354."},{"key":"R18","unstructured":"Harold Kuhn, Nonlinear programming: a historical note, North\u2010Holland, Amsterdam, 1991, 82\u2013961183953"},{"key":"R19","unstructured":"E. H. Maize,\n                      Linear statistical analysis of maneuver optimization strategies\n                      , in Proceedings of the American Astronautical Society and American Insititute of Aeronautics and Astronautics Astrodynamics Specialist Conference, Kalispell, MT, 1987."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0802028"},{"key":"R21","unstructured":"J. Michel,\n                      Private Communication\n                      , Marietta College, Marietta, OH, and Jet Propulsion Laboratory, Pasadena, CA."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Y. Nesterov and A. Nemirovskii,\n                      Interior Point Polynomial Algorithms in Convex Programming\n                      , SIAM, Philadelphia, 1994.","DOI":"10.1137\/1.9781611970791"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623495290209"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1287\/moor.22.1.1"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591963"},{"key":"R26","unstructured":"Michael Overton, Numerical solution of a model problem from collapse load analysis, North\u2010Holland, Amsterdam, 1984, 421\u201343786m:73031"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/0913027"},{"key":"R28","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton University Press, Princeton, NJ, 1970."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Gilbert Strang, A minimax problem in plasticity theory, Lecture Notes in Math., Vol. 701, Springer, Berlin, 1979, 319\u201333383c:73021","DOI":"10.1007\/BFb0062087"},{"key":"R30","first-page":"355","volume":"43","author":"Weiszfeld E.","year":"1937","journal-title":"Tohoku Math. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0040-8735","issn-type":"print"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"S. J. Wright,\n                      Primal\u2010Dual Interior\u2010Point Methods\n                      , SIAM, Philadelphia, 1997.","DOI":"10.1137\/1.9781611971453"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623496313684"},{"key":"R33","unstructured":"G. Xue, G.\u2010H. Lin, and D.\u2010Z. Du,\n                      Grade of service minimum Steiner Euclidean trees\n                      , in Proceedings IEEE International Symposium on Circuits and Systems, Orlando, FL, 1999, IEEE Press, Piscataway, NJ."},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623495288362"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S1064827598343954","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:35:54Z","timestamp":1787333754000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S1064827598343954"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["10.1137\/S1064827598343954"],"URL":"https:\/\/doi.org\/10.1137\/s1064827598343954","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}