×

A quadratically convergent method for minimizing a sum of Euclidean norms. (English) Zbl 0536.65053

The author considers the problem of minimizing a sum of Euclidean norms \[ F(x)=\sum^{m}_{i=1}r_i(x) \] where the residuals \(r_i(x)\) are affine functions from \(R^n\) to \(R^l\) (\(n\geq l\geq 2,\quad m\geq 2)\). This arises in a number of applications, including single- and multi-facility location problems. The function \(F\) is, in general, not differentiable at \(x\) if at least one \(r_i(x)\) is zero. Computational methods described previously in the literature generally converge quite slowly if the solution is at such a point. A new method is described which, at each iteration, computes a direction of search by solving the Newton system of equations, projected, if necessary, into a linear manifold along which \(F\) is locally differentiable. A special line search is used to obtain the next iterate. The algorithm is closely related to a method given recently by P. H. Calamai and A. R. Conn [Numerical analysis, Proc. 9th bienn. Conf., Dundee/Scotl. 1981, Lect. Notes 912, 1–25 (1982; Zbl 0485.65013)]. The new method has quadratic convergence to a solution \(x\) under given conditions. The reason for this property depends on the nature of the solution. If none of the residuals is zero at \(x\), then \(F\) is differentiable at \(x\) and the quadratic convergence follows from standard properties of Newton’s method. If one of the residuals, say \(r_i(x)\), is zero, then, as the iteration proceeds, the Hessian of \(F\) becomes extremely ill-conditioned. It is proved that this ill-conditioning, instead of creating difficulties, actually causes quadratic convergence to the manifold \(\{x \mid r_i(x)=0\}\). If this is a single point, the solution is thus identified. Otherwise it is necessary to continue the iteration restricted to this manifold, where the usual quadratic convergence of Newton’s method applies. If several residuals are zero at \(x\), several stages of quadratic convergence take place as the correct index set is constructed. Thus the ill-conditioning property accelerates the identification of the residuals which are zero at the solution. Numerical experiments are presented, illustrating these results. The proof of the convergence rate in the nondifferentiable case involves the development of estimates for the change in eigenvalues and eigenvectors of a symmetric matrix with multiple eigenvalues which undergoes a symmetric perturbation.
Reviewer: Michael L. Overton

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming

Citations:

Zbl 0485.65013

Software:

BRENT
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] I. Barrodale and F.D.K. Roberts ”An efficient algorithm for discreteL 1 linear approximation with constraints”,SIAM Journal on Numerical Analysis 15 (1978) 603–611. · Zbl 0387.65027 · doi:10.1137/0715040
[2] R. Bartels, A.R. Conn and J.W. Sinclai ”Minimization techniques for piecewise differentiable functions: Thel 1 solution to an overdetermined linear system,”SIAM Journal on Numerical Analysis 15 (1978) 224–241. · Zbl 0376.65018 · doi:10.1137/0715015
[3] R.P. Brent,Algorithms for minimization without derivatives (Prentice-Hall, Englewood Cliffs, NJ. 1973). · Zbl 0245.65032
[4] P. Businger and G.H. Golub, ”Linear least squares solutions by Householder transformations,”Numerische Mathematik 7 (1965) 269–276. · Zbl 0142.11503 · doi:10.1007/BF01436084
[5] P.H. Calamai and A.R. Conn, ”A stable algorithm for solving the multifacility location problem involving Euclidean distances,”SIAM Journal on Scientific and Statistical Computing 1 (1980) 512–526. · Zbl 0469.65040 · doi:10.1137/0901037
[6] P.H. Calamai and A.R. Conn, ”A second-order method for solving the continuous multificacility location problem,” in G.A. Watson, ed.,Numerical analysis: Proceedings of the Ninth Biennial Conference, Dundee. Scotland Lecture Notes in Mathematics 912 (Springer-Verlag, Berlin, Heidelberg and New York, 1982) pp. 1–25. · Zbl 0485.65013
[7] J.A. Chatelon, D.W. Hearn and T.J. Lowe, ”A subgradient algorithm for certain minimax and minisum problems,”Mathematical Programming 15 (1978) 130–145. · Zbl 0392.90065 · doi:10.1007/BF01609012
[8] P. Concus, ”Numerical solution of the minimal surface equation,”Mathematics of Computation 21 (1967) 340–350. · Zbl 0189.16605 · doi:10.1090/S0025-5718-1967-0229394-6
[9] F. Cordellier and J.Ch. Fiorot, ”On the Fermat-Weber problem with convex cost functionals,”Mathematical Programming 14 (1978) 295–311. · Zbl 0374.90057 · doi:10.1007/BF01588972
[10] T.J. Dekker, ”Finding a zero by means of successive linear interpolation,” in: B. Dejon and P. Henrici, eds.,Constructive aspects of the fundamental theorem of algebra (Wiley Interscience New York and London, 1969) pp. 37–38.
[11] U. Eckhardt, ”On an optimization problem related to minimal surfaces with obstacles,” in: R. Bulirsch, W. Oettli and J. Stoer, eds.,Optimization and optimal control, Lecture Notes in Mathematics 477 (Springer-Verlag, Berlin, Heidelberg and New York, 1975) pp. 95–101. · Zbl 0313.49020
[12] U. Eckhardt, ”Weber’s problem and Weiszfeld’s algorithm in general spaces,”Mathematical Programming 18 (1980) 186–196. · Zbl 0433.65035 · doi:10.1007/BF01588313
[13] J.W. Eyster, J.A. White and W.W. Wierwille, ”On solving multifacility location problems using a hyperboloid approximation procedure,”AIIE Transactions 5 (1973) 1–6.
[14] R.L. Francis and J.M. Goldstein, ”Location theory: A selective bibliography,”Operations Research 22 (1974) 400–410. · Zbl 0274.90028 · doi:10.1287/opre.22.2.400
[15] P.E. Gill, G.H. Golub, W. Murray and M.A. Saunders, ”Methods for modifying matrix factorizations,”Mathematics of Computation 28 (1974) 505–535. · Zbl 0289.65021 · doi:10.1090/S0025-5718-1974-0343558-6
[16] P.E. Gill and W. Murray, ”Newton-type methods for linearly constrained optimization,” in: P.E. Gill and W. Murray, eds.,Numerical methods for constrained optimization (Academic Press, London and New York, 1974a) pp 29–66 · Zbl 0297.90082
[17] P.E. Gill and W. Murray, ”Newton-type methods for unconstrained and linearly constrained optimization”,Mathematical Programming 7 (1974b) 311–350. · Zbl 0297.90082 · doi:10.1007/BF01585529
[18] P.E. Gill and W. Murray, ”Safeguarded steplength algorithms for optimization using descent methods,” National Physical Laboratory Report NAC 37 (Teddington, England, 1974c).
[19] H.W. Kuhn, ”On a pair of dual nonlinear programs,” in: J. Abadie, ed.,Nonlinear programming (North-Holland, Amsterdam, 1967) pp. 38–54. · Zbl 0183.22804
[20] H.W. Kuhn, ”A note on Fermat’s problem,”Mathematical Programming 4 (1973) 98–107. · Zbl 0255.90063 · doi:10.1007/BF01584648
[21] R.F. Love, ”Locating facilities in three-dimensional space by convex programming,”Naval Research Logistics Quarterly 16 (1969) 503–516. · Zbl 0194.20805
[22] W. Murray and M.L. Overton, ”Steplength algorithms for minimizing a class of nondifferentiable functions,”Computing 23 (1979) 309–331. · Zbl 0445.65060 · doi:10.1007/BF02254861
[23] J.M. Ortega,Numerical analysis: a second course (Academic Press, New York and London, 1972). · Zbl 0248.65001
[24] J.M. Ortega and W.C. Rheinboldt,Iterative solution of nonlinear equations in several variables (Academic Press, New York and London, 1970). · Zbl 0241.65046
[25] A.M. Ostrowski, ”On the convergence of the Rayleigh quotient iteration for the computation of characteristic roots and vectors, I and II”,Archives for Rational Mechanics and Analysis 1 (1958) 233–241; 2 (1959) 423–428. · Zbl 0083.12002 · doi:10.1007/BF00298007
[26] B.N. Parlett,The symmetric eigenvalue problem (Prentice-Hall, Englewood Cliffs, NJ, 1980). · Zbl 0431.65017
[27] G. Peters and J.H. Wilkinson, ”Inverse iteration, ill-conditioned equations and Newton’s method,”SIAM Review 21 (1979) 339–360. · Zbl 0424.65021 · doi:10.1137/1021052
[28] S. Schechter, ”Minimization of a convex function by relaxation,” in: J. Abadie, ed.,Integer and nonlinear programming (North-Holland, Amsterdam and London, 1970) pp. 177–190. · Zbl 0346.90037
[29] G.W. Stewart,Introduction to matrix computations (Academic Press, New York and London 1973). · Zbl 0302.65021
[30] J. Thomas, ”Zur Statik eines gewissen Federsystems imE n ,”Mathematische Nachrichten 23 (1961) 185–195. · Zbl 0103.16901
[31] H. Voss and U. Eckhardt, ”Linear convergence of generalized Weiszfeld’s method,”Computing 25 (1980) 243–251. · Zbl 0439.65051 · doi:10.1007/BF02242002
[32] E. Weiszfeld, ”Sur le point par lequel la somme des distances den points donnés est minimum”,Tohoku Mathematics Journal 43 (1937) 355–386. · JFM 63.0583.01
[33] J.H. Wilkinson, ”Inverse iteration in theory and practice”, in:Symposia Mathematica Volume X (Istituto Nazionale di Alta Mathematica Monograf, Bologna, 1972) pp. 361–379. · Zbl 0267.65029
[34] W.L. Wilson, Jr., ”On discrete Dirichlet and Plateau problems,”Numerische Mathematik 3 (1961) 359–373. · Zbl 0111.29903 · doi:10.1007/BF01386035
[35] M.H. Wright and S.C. Glassman, ”Fortran subroutines to solve the linear least-squares problem and compute the complete orthogonal factorization,” Systems Optimization Laboratory Report SOL-78-8, Stanford University (Stanford, CA, 1978).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.