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

Pham Dinh Tao; Le Thi Hoai An

Oper. Res. Lett. 19, No. 5, 207-216 (1996).

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.

MSC:

90C20	Quadratic programming
90C26	Nonconvex programming, global optimization

Keywords:

difference of convex functions; nonconvex quadratic minimization; local and global optimality conditions; d.c. optimization; DCA; robustness; stability; efficiency

Software:

GQTPAR

References:

[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