Difference of convex functions optimization algorithms (DCA) for globally minimizing nonconvex quadratic forms on Euclidean balls and spheres. (English) Zbl 0876.90071

Summary: We present DCA for globally minimizing quadratic forms on Euclidean balls and spheres. Since these problems admit at most one local-nonglobal minimizer, DCA converges in general to a solution for these problems. Numerical simulations show robustness, stability and efficiency of DCA with respect to related standard methods.


90C20 Quadratic programming
90C26 Nonconvex programming, global optimization


Full Text: DOI


[1] An, L. T.H., Analyse numérique des algorithmes de l’Optimisation d.c. Approches locales et globales. Code et simulations numériques en grande dimension Applications, (Thèse de Doctorat de l’Université de Rouen (1994))
[2] Bental, A.; Teboulle, M., Hidden convexity in some nonconvex quadratically constrained quadratic programming, (Technical report (1993), Israel Institute of Technology) · Zbl 0851.90087
[3] Clermont, J. R.; De La Lande, M. E.; Tao, P. D., Analysis of plane and axisymmetric flows of incompressible fluids with the stream tube method: Numerical simulation by Trust region algorithm, Internat. J. Numer. Methods Fluids, 13, 339-371 (1991) · Zbl 0739.76050
[4] Fletcher, R., Practical Methods of Optimization (1991), A Wiley-Interscience: A Wiley-Interscience New York · Zbl 0905.65002
[5] Flippo, O. E.; Jansen, B., Duality and sensitivity in nonconvex quadratic optimization over a ellipsoid, (Technical Report (1993), Technical University of Delft: Technical University of Delft Netherlands) · Zbl 0930.90076
[6] Gander, W.; Golub, G. H.; Von Matt, U., A constrained eigenvalue problem, Linear Algebra Appl., 114/115, 815-839 (1989) · Zbl 0666.15006
[7] Gay, D. M., Computing optimal locally constrained steps, SIAM J. Sci. Statist. Comput., 2, 186-197 (1981) · Zbl 0467.65027
[8] Golub, G. H.; Von Matt, U., Quadratically constrained least squares and quadratic problems, Numer. Math., 59, 561-580 (1991) · Zbl 0745.65029
[9] Mahey, P.; Tao, P. D., Partial regularization of the sum of two maximal monotone operators, Math. Modell. Numer. Anal., 27, 375-395 (1993) · Zbl 0778.65042
[10] Mahey, P.; Tao, P. D., Proximal decomposition of the graph of maximal monotone operator, SIAM J. Optim., 5, 454-468 (1995) · Zbl 0834.90105
[11] Martinez, J., Local minimizers of quadratic functions on euclidean balls and spheres, SIAM J. Optim., 4, 159-176 (1994) · Zbl 0801.65057
[12] More, J. J., Recent developments in algorithm and software for trust region methods, (Mathematical Programming, The State of the Art (1983), Springer: Springer Berlin), 258-287 · Zbl 0546.90077
[13] More, J. J.; Sorensen, D. C., Computing a trust region step, SIAM J. Sci. Statist. Comput., 4, 553-572 (1983) · Zbl 0551.65042
[14] Polyak, B., Introduction to Optimization. Optimization Software (1987), Publication Division: Publication Division New York
[15] Tao, P. D., Contribution à la théorie de normes and ses applications à l’analyse numérique, (Thèse de Doctorat d’Etat Es Science (1981), Universite Joseph Fourier: Universite Joseph Fourier Grenoble)
[16] Tao, P. D., Convergence of subgradient method for computing the bound norm of matrices, Linear Algebra Appl., 62, 163-182 (1984) · Zbl 0563.65029
[17] Tao, P. D., Algorithmes de calcul du maximum d’une forme quadratique sur la boule unité de la norme du maximum, Numer. Math., 45, 377-440 (1985)
[18] Tao, P. D., Algorithms for solving a class of non-convex optimization problems, Methods of subgradients, (Urruty, J. B.Hiriart, Fermat Days 85, Mathematics for Optimization (1986), Elsevier: Elsevier Amsterdam, North-Holland)
[19] Tao, P. D.; An, L. T.H., Optimisation d.c. (difference de deux fonctions convexes). Dualite and stability. Optimalités locale and globale. Algorithmes de l’optimisation d.c. (DCA), (L.M.I., CNRS URA 1378 (1994), INSA: INSA Rouen), Preprint
[20] Tao, P. D.; An, L. T.H., Stabilite de la dualité lagrangienne en optimisation d.c. (difference de deux fonctions convexes), C.R. Acad. Sci. Paris, 318 (1994), Sér. I · Zbl 0801.90093
[21] Tao, P. D.; An, L. T.H., Lagrangian stability and global optimality on nonconvex quadratic minimization over Euclidean balls and spheres, J. Convex Anal., 2, 263-276 (1995) · Zbl 0848.49022
[22] Tao, P. D., Méthodes numeriques pour la minimisation globale d’une forme quadratique (convexe ou non convexe) sur une boule et une sphère euclidiennes, (Rapport de Recherche, Université (1989), Joseph-Fourier: Joseph-Fourier Grenoble)
[23] Tao, P. D.; El Bernoussi, S., Duality in d.c. (difference of convex functions) optimization. Subgradient methods, (International Series of Numer Math.. International Series of Numer Math., Trends in Mathematical Optimization, Vol. 84 (1988), Birkhauser: Birkhauser Basel), 276-294
[24] Tao, P. D.; Wang, S., Training multi-layered neural network with a Trust region based algorithm, Math. Modell. Numer. Anal., 24, 523-553 (1990) · Zbl 0707.90097
[25] Rockafellar, R. T., Convex Analysis (1970), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ · Zbl 0229.90020
[26] Rockafellar, R. T., Monotone operators and the proximal point algorithm in convex programming, SIAM J. Control Optim., 14, 877-898 (1976) · Zbl 0358.90053
[27] Sorensen, D. C., Newton’s method with a model trust region modification, SIAM J. Numer. Anal., 19, 409-426 (1982) · Zbl 0483.65039
[28] Stern, R. J.; Wolkowicz, H., Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations, SIAM J. Optim., 5, 286-313 (1993) · Zbl 0846.49017
[29] Toland, J. F., On subdifferential calculus and duality in nonconvex optimization, Bull. Soc. Math. France, 60, 177-183 (1979) · Zbl 0417.90088
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.