Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Pardalos, P.M., Rosen, J.B. Constrained Global Optimization: Algorithms and Applications. Lecture Notes in Computer Sciences, vol. 268. Springer (1987)
Horst R., Pardalos P. (1995) Handbook of Global Optimization Nonconvex Optimization and its Applications. Kluwer, Dordrecht
Beck A., Teboulle M. (2000) Global optimality conditions for quadratic optimization problems with binary constraints. SIAM J. Optim. 11, 179–188
Pardalos P.M. (1991) Construction of test problems in quadratic bivalent programming. ACM Trans. Math. Softw. 17(1): 74–87
Gary M.R., Johnson D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman, San Francisco
Floudas C.A., Visweswaran V. (1993) Primal-relaxed dual global optimization approach. J. Optim. Theo. Appl. 78, 187–225
Floudas C.A., Visweswaran V. (1990) A global optimization algorithm (GOP) for certain classes of nonconvex NLPsII—Theory. Comput. Chem. Eng. 14, 1397–1417
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)
Floudas C.A. (2000) Deterministic Global Optimization. Theory, Methods and Applications. Nonconvex Optimization and its Applications, vol. 37. Kluwer, Dordrecht
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
Hiriart-Urruty J.B. (2001) Global optimality conditions in maximizing a convex quadratic function under convex quadratic constraints. J. Global Optim. 21, 445–455
Hiriart-Urruty J.B. (1998) Conditions for global optimality 2. J. Global Optim. 13, 349–367
Pinar M.C. (2004) Sufficient global optimality conditions for bivalent quadratic optimization. J. Optim. Theor. Appl. 122(2): 443–440
Pallaschke D., Rolewicz S. (1997) Foundations of Mathematical Optimization. Kluwer, Dordrechet
Rubinov A.M. (2000) Abstract Convexity and Global Optimization. Kluwer, Dordrecht
Zalinescu C. (2002) Convex Analysis in General Vector Spaces. World Scientific, London
Dahl G. (2000) A note on diagonally dominant matrices. Linear Algebra Appl. 317, 217–224
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Jeyakumar, V., Rubinov, A.M. & Wu, Z.Y. Sufficient Global Optimality Conditions for Non-convex Quadratic Minimization Problems With Box Constraints. J Glob Optim 36, 471–481 (2006). https://doi.org/10.1007/s10898-006-9022-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-006-9022-3
Keywords
- Quadratic optimization
- Global optimality conditions
- Non-convex minimization
- Weighted least squares
- Box constraints
- Bivalent programs