×

Sufficient global optimality conditions for non-convex quadratic minimization problems with box constraints. (English) Zbl 1131.90060

Summary: In this paper we establish conditions which ensure that a feasible point is a global minimizer of a quadratic minimization problem subject to box constraints or binary constraints. In particular, we show that our conditions provide a complete characterization of global optimality for non-convex weighted least squares minimization problems. We present a new approach which makes use of a global subdifferential. It is formed by a set of functions which are not necessarily linear functions, and it enjoys explicit descriptions for quadratic functions. We also provide numerical examples to illustrate our optimality conditions.

MSC:

90C30 Nonlinear programming
41A65 Abstract approximation theory (approximation in normed linear spaces and other abstract spaces)
41A29 Approximation with constraints
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Pardalos, P.M., Rosen, J.B. Constrained Global Optimization: Algorithms and Applications. Lecture Notes in Computer Sciences, vol. 268. Springer (1987) · Zbl 0638.90064
[2] Horst R., Pardalos P. (1995) Handbook of Global Optimization Nonconvex Optimization and its Applications. Kluwer, Dordrecht · Zbl 0805.00009
[3] Beck A., Teboulle M. (2000) Global optimality conditions for quadratic optimization problems with binary constraints. SIAM J. Optim. 11, 179–188 · Zbl 0990.90089 · doi:10.1137/S1052623498336930
[4] Pardalos P.M. (1991) Construction of test problems in quadratic bivalent programming. ACM Trans. Math. Softw. 17(1): 74–87 · Zbl 0900.65183 · doi:10.1145/103147.103156
[5] Gary M.R., Johnson D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman, San Francisco · Zbl 0411.68039
[6] Floudas C.A., Visweswaran V. (1993) Primal-relaxed dual global optimization approach. J. Optim. Theo. Appl. 78, 187–225 · Zbl 0796.90056 · doi:10.1007/BF00939667
[7] Floudas C.A., Visweswaran V. (1990) A global optimization algorithm (GOP) for certain classes of nonconvex NLPsII–Theory. Comput. Chem. Eng. 14, 1397–1417 · doi:10.1016/0098-1354(90)80020-C
[8] De, P. Angelis, Pardalos, P., Toraldo, G. Quadratic programming with box constraints. In: Szeged (ed.) Developments in Global Optimization, Nonconvex Optim. Appl., pp. 73–93. 18. Kluwer, Dordrecht (1997) · Zbl 0886.90130
[9] Floudas C.A. (2000) Deterministic Global Optimization. Theory, Methods and Applications. Nonconvex Optimization and its Applications, vol. 37. Kluwer, Dordrecht
[10] Floudas C.A., Visweswaran V. (1995) Quadratic optimization. In: Horst R., Pardalos P.M. (eds). Handbook of Global Optimization. Kluwer, The Netherlands, pp. 217–269 · Zbl 0833.90091
[11] Hiriart-Urruty J.B. (2001) Global optimality conditions in maximizing a convex quadratic function under convex quadratic constraints. J. Global Optim. 21, 445–455 · Zbl 1172.90501 · doi:10.1023/A:1012752110010
[12] Hiriart-Urruty J.B. (1998) Conditions for global optimality 2. J. Global Optim. 13, 349–367 · Zbl 0922.90109 · doi:10.1023/A:1008365206132
[13] Pinar M.C. (2004) Sufficient global optimality conditions for bivalent quadratic optimization. J. Optim. Theor. Appl. 122(2): 443–440 · Zbl 1091.90059 · doi:10.1023/B:JOTA.0000042530.24671.80
[14] Pallaschke D., Rolewicz S. (1997) Foundations of Mathematical Optimization. Kluwer, Dordrechet · Zbl 0887.49001
[15] Rubinov A.M. (2000) Abstract Convexity and Global Optimization. Kluwer, Dordrecht · Zbl 0985.90074
[16] Zalinescu C. (2002) Convex Analysis in General Vector Spaces. World Scientific, London
[17] Dahl G. (2000) A note on diagonally dominant matrices. Linear Algebra Appl. 317, 217–224 · Zbl 0970.15017 · doi:10.1016/S0024-3795(00)00178-6
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.