Abstract
A central problem of branch-and-bound methods for global optimization is that often a lower bound do not match with the optimal value of the corresponding subproblem even if the diameter of the partition set shrinks to zero. This can lead to a large number of subdivisions preventing the method from terminating in reasonable time. For the all-quadratic optimization problem with convex constraints we present optimality cuts which cut off a given local minimizer from the feasible set. We propose a branch-and-bound algorithm using optimality cuts which is finite if all global minimizers fulfill a certain second order optimality condition. The optimality cuts are based on the formulation of a dual problem where additional redundant constraints are added. This technique is also used for constructing tight lower bounds. Moreover we present for the box-constrained and the standard quadratic programming problem dual bounds which have under certain conditions a zero duality gap.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Adjiman, C.S., Androulakis, I.P. and C.A. Floudas, (1998), 'A global optimization method, αBB, for general twice-differentiable constrained NLPs—I. Theoretical advances'. Computers and Chemical Engineering, 1137-1158.
Al-Khayyal, F.A., Larsen, C. and van Voorhis, T. (1995), A Relaxation Method for Nonconvex Quadratically Constrained Quadratic Programs. J. Global Opt. 6: 215-230.
An, L.T.H. and Tao, P.D. (1996), 'Solving a Class of Linearly Constrained Indefinite Quadratic Problems by D.C. Algorithms. J. of Global Opt., 11: 253-285.
An, L.T.H. and Tao, P.D. (1998), 'A Branch and Bound Method via d.c. Optimization Algorithms and Ellipsoidal Technique for Box Constrained Nonconvex Quadratic Problems'. J. of Global Opt., 13: 171-206.
Anstreicher, K. and Wolkowicz, H. (1998), 'On Lagrangian Relaxation of Quadratic Matrix Constraints'. Research Report CORR 98-24, Department of Combinatorics and Optimization, University of Waterloo.
Audet, C., Hansen, P., Jaumard, B. and Savard, G. (1997), 'A Branch and Cut Algorithm for Nonconvex Quadratically Constrained Quadratic Programming'. Technical report, Les Cashiers du GERAD G-97-67, Montréal, 1997.
Feltenmark, S. and Kiwiel, K.C. (1999), 'Dual Applications of Proximal Bundle Methods, including Lagrangian relaxation of nonconvex problems'. to appear in SIAM Journal on Optimization.
Floudas, C.A. and Visweswaran, V. (1995), 'Quadratic Optimization'. In R. Horst and P. Pardalos, (eds.), Handbook of Global Optimization, pp. 217-269. Kluwer Academic Publishers.
Helmberg, C. (1999), http://www.zib.de/helmberg/semidef.html.
Helmberg, C. and Kiwiel, K.C. (1999), 'A Spectral Bundle Method with Bounds'. Preprint SC 99-37, Konrad-Zuse-Zentrum für Informationstechnik, Berlin, 1999.
Helmberg, C. and Rendl, F. (1997), 'A Spectral BundleMethod for Semidefinite Programming'. Preprint SC 97-37, Konrad-Zuse-Zentrum für Informationstechnik, Berlin.
Horst, R., Pardalos, P. and Thoai, N. (1995), Introduction to Global Optimization. Kluwer Academic Publishers, 1995.
Horst, R. and Thoai, N.V. (1996), 'A New Algorithm for Solving the General Quadratic Programming Problem. Comp. Opt. Appl., 5: 39-48.
Lemaréchal, C. and Renaud, A. (1996), Dual-equivalent convex and non-convex problems. Technical report, INRIA, Rocquencourt, 1996.
Lemaréchal, C. and Renaud, A. (1999), 'A geometric study of duality gaps, with applications'. to appear in Mathematical Programming.
Nowak, I. (1998a), 'A Global Optimality Criterion for Nonconvex Quadratic Programming over a Simplex. Technical report, Preprint 98-18, Humboldt University Berlin.
Nowak, I. (1998b) 'Some Heuristics and Test Problems for Nonconvex Quadratic Programming over a Simplex'. Technical report, Preprint 98-17, Humboldt University Berlin.
Nowak, I. (1999), 'A new semidefinite programming bound for indefinite quadratic forms over a simplex'. J. Global Opt., 14: 357-364.
Pardalos, P., Glick, J.H. and Rosen, J.B. (1987), 'Global Minimization of Indefinite Quadratic Problems'. Computing, 39: 281-291.
Phillips, A.T. and Rosen, J.B. (1990), 'Guaranteed \(\varepsilon \)-approximate Solution for Indefinite Quadratic Global Minimization. Naval Research Logistics, 37: 499-514.
Raber, U. (1998), 'A Simplicial Branch and Bound Method for Solving Nonconvex All-Quadratic Programs'. J. Global Opt., 13: 417-432.
Sherali, H.D. and Tuncbilek, C.H., (1995), 'A Reformulation-Convexification Approach for Solving Nonconvex Quadratic Programming Problems'. J. of Global Optimization, 7: 1-31.
Shor, N.Z. (1992), 'Dual Estimates in Multiextremal Problems'. J. of Global Opt., 2: 411-418.
Shor, N.Z. (1998), Nondifferentiable Optimization and Polynomial Problems. Kluwer Academic Publishers.
Spellucci, P. (1993), Numerische Verfahren der nichtlinearen Optimierung. Birkhäuser Verlag, ISNM, Darmstadt.
Thoai, N. (1997), 'A decomposition method using duality bounds for nonconvex optimization'. Technical report, Research Report 97-24, University of Trier, 1997.
Thoai, N. (2000), Duality bound method for the general quadratic programming problem with quadratic constraints. Journal of Optimization Theory and Applications, 107(2), 2000.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Nowak, I. Dual Bounds and Optimality Cuts for All-Quadratic Programs with Convex Constraints. Journal of Global Optimization 18, 337–356 (2000). https://doi.org/10.1023/A:1026596100403
Issue Date:
DOI: https://doi.org/10.1023/A:1026596100403