{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T04:42:09Z","timestamp":1787719329290,"version":"build-2784847793"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[1998,5]]},"abstract":"<jats:p>This paper is devoted to difference of convex functions (d.c.) optimization: d.c. duality, local and global optimality conditions in d.c. programming, the d.c. algorithm (DCA), and its application to solving the trust-region problem. The DCA is an iterative method that is quite different from well-known related algorithms. Thanks to the particular structure of the trust-region problem, the DCA is very simple (requiring only matrix-vector products) and, in practice, converges to the global solution. The inexpensive implicitly restarted Lanczos method of Sorensen is used to check the optimality of solutions provided by the DCA. When a nonglobal solution is found, a simple numerical procedure is introduced both to find a feasible point having a smaller objective value and to restart the DCA at this point. It is shown that in the nonconvex case, the DCA converges to the global solution of the trust-region problem, using only matrix-vector products and requiring at most 2m+2 restarts, where m is the number of distinct negative eigenvalues of the coefficient matrix that defines the problem. Numerical simulations establish the robustness and efficiency of the DCA compared to standard related methods, especially for large-scale problems.<\/jats:p>","DOI":"10.1137\/s1052623494274313","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"476-505","source":"Crossref","is-referenced-by-count":444,"title":["A D.C. Optimization Algorithm for Solving the Trust-Region Subproblem"],"prefix":"10.1137","volume":"8","author":[{"given":"Pham Dinh","family":"Tao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Le Thi Hoai","family":"An","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1002\/fld.1650130308"},{"key":"R2","volume-title":"Practical methods of optimization","author":"Fletcher R.","year":"1987"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0113073"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(89)90494-1"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0902016"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01385796"},{"key":"R7","unstructured":"L. T. Hoai An,\n                      Analyse num\u00e9rique des algorithmes de l\u2019Optimisation d. c. Approches locales et globales. Code et simulations num\u00e9riques en grande dimension. Applications\n                      , Th\u00e8se de Doctorat de l\u2019Universit\u00e9 de Rouen, Rouen, France, 1994."},{"key":"R8","unstructured":"L. T. Hoai An and T. Pham Dinh,\n                      Solving a class of linearly constrained indefinite quadratic problems by D. c. algorithms\n                      , J. Global Optim., to appear."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"J. B. Hiriart\u2010Urruty,\n                      From convex optimization to non convex optimization. Part I: Necessary and sufficient conditions for global optimality\n                      , in Nonsmooth Optimization and Related Topics, Ettore Majorana International Sci. Ser. Phys. Sci. 43, Plenum Press, New York, 1988.","DOI":"10.1007\/978-1-4757-6019-4_13"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"R. Horst and H. Tuy,\n                      Global Optimization (Deterministic Approaches)\n                      , Springer\u2010Verlag, Berlin, 1993.","DOI":"10.1007\/978-3-662-02947-3"},{"key":"R11","unstructured":"P. J. Laurent,\n                      Approximation et Optimisation\n                      , Hermann, Paris, 1972."},{"key":"R12","unstructured":"R. Lehoucq, D. C. Sorensen, and P. A. Vu,\n                      ARPACK: An implementation of the implicitly restarted Arnoldi iteration that computes some of the eigenvalues and eigenvectors of a large sparse matrix\n                      , available online from netlib@ornl.gov under the directory scalapack."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623494278049"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0805023"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0804009"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"J.Mor\u00e9, Recent developments in algorithms and software for trust region methods, Springer, Berlin, 1983, 258\u201328785b:90066","DOI":"10.1007\/978-3-642-68874-4_11"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0904038"},{"key":"R18","first-page":"153","volume":"21","author":"P\u0103v\u0103loiu Ion","year":"1992","journal-title":"Rev. Anal. Num\u00e9r. Th\u00e9or. Approx."},{"key":"R19","unstructured":"B. N. Parlett,\n                      The Symmetric Eigenvalue Problem\n                      , Prentice\u2010Hall, Englewood Cliffs, NJ, 1980."},{"key":"R20","unstructured":"T. Pham Dinh,\n                      Contribution \u00e0 la th\u00e9orie de normes and ses applications \u00e0 l\u2019analyse num\u00e9rique\n                      , Th\u00e8se de Doctorat d\u2019Etat Es Science, Universit\u00e9 Joseph\u2010Fourier, Grenoble, 1981."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(84)90093-4"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01391415"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Pham Dinh Tao, SouadEl Bernoussi, Duality in D.C. (difference of convex functions) optimization. Subgradient methods, Internat. Schriftenreihe Numer. Math., Vol. 84, Birkh\u00e4user, Basel, 1988, 277\u20132931017958","DOI":"10.1007\/978-3-0348-9297-1_18"},{"key":"R24","unstructured":"T. Pham Dinh,\n                      M\u00e9thodes num\u00e9riques pour la minimisation globale d\u2019une forme quadratique (convexe ou non convexe) sur une boule et une sph\u00e8re euclidiennes\n                      , Rapport de Recherche, Universit\u00e9 Joseph\u2010Fourier, Grenoble, 1989."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1051\/m2an\/1990240405231"},{"key":"R26","unstructured":"T. Pham Dinh and L. T. Hoai An,\n                      Minimisation globale d\u2019une forme quadratique sur une boule and une sph\u00e8re euclidiennes. Stabilit\u00e9 de la dualit\u00e9 lagrangienne. Optimalit\u00e9 globale. M\u00e9thodes num\u00e9riques\n                      , Rapport de Recherche, L.M.I, CNRS URA 1378, INSA\u2010Rouen, 1992."},{"key":"R27","unstructured":"T. Pham Dinh and L. T. Hoai An,\n                      Optimisation d. c. (diff\u00e9rence de deux fonctions convexes). Dualit\u00e9 et Stabilit\u00e9. Optimalit\u00e9s locale et globale. Algorithmes de l\u2019optimisation d. c. (DCA)\n                      , Rapport de Recherche, LMI, CNRS URA 1378, INSA\u2010Rouen, 1994."},{"key":"R28","first-page":"379","volume":"318","author":"Pham Dinh T.","year":"1994","journal-title":"C. R. Acad. Sci. Paris, Ser. I Math."},{"key":"R29","unstructured":"T. Pham Dinh and L. T. Hoai An,\n                      Polyhedral d.c. (Difference of Convex Functions) Programming: Theory, Polyhedral d.c. Algorithm (DCA) and Applications\n                      , preprint, LMI, CNRS URA 1378, INSA\u2010Rouen, 1995."},{"key":"R30","first-page":"263","volume":"2","author":"Pham Dinh Tao","year":"1995","journal-title":"J. Convex Anal."},{"key":"R31","volume-title":"Introduction to optimization","author":"Polyak Boris","year":"1987"},{"key":"R32","unstructured":"F. Rendl and H. Wolkowicz,\n                      A Semidefinite Framework to Trust Region Subproblems with Application to Large Scale Minimization\n                      , CORR Report 94\u201032, Department of Combinatorics and Optimization, University of Waterloo, 1994."},{"key":"R33","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton University Press, Princeton, NJ,1970."},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/0314056"},{"key":"R35","unstructured":"S. A. Santos and D. C. Sorensen,\n                      A new matrix\u2010free algorithm for the large\u2010scale trust\u2010region subproblem\n                      , SIAM J. Optim., submitted."},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1137\/0719026"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1137\/0613025"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623494274374"},{"key":"R39","doi-asserted-by":"crossref","first-page":"177","DOI":"10.24033\/msmf.269","author":"Toland John","year":"1979","journal-title":"Bull. Soc. Math. France M\u00e9m."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S1052623494274313","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:18:05Z","timestamp":1787332685000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S1052623494274313"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,5]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,5]]}},"alternative-id":["10.1137\/S1052623494274313"],"URL":"https:\/\/doi.org\/10.1137\/s1052623494274313","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,5]]}}}