×

Solution to nonconvex quadratic programming with both inequality and box constraints. (English) Zbl 1178.90268

Summary: This paper presents a canonical dual approach for solving nonconvex quadratic programming problems subjected to both linear inequality constraints and box constrains. It is proved that the constrained nonconvex primal problem can be reformulated as a concave maximization dual problem with zero duality gap, which can be solved under certain conditions. Both global and local extremimality conditions are presented by the triality theory. Several applications are illustrated.

MSC:

90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
90C46 Optimality conditions and duality in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akrotirianakis IG, Floudas X (2004) Computational experience with a new class of convex underestimators: Box-constrained NLP problems. J Global Optim 29:249–264 · Zbl 1133.90420 · doi:10.1023/B:JOGO.0000044768.75992.10
[2] Floudas CA, Visweswaran V (1995) Handbook of global optimization. Kluwer Academic, Dordrecht, Boston, London · Zbl 0833.90091
[3] Gao DY (1988) Panpenalty finite element programming for limit analysis. Comput Struct 28:749–755 · Zbl 0632.73031 · doi:10.1016/0045-7949(88)90415-4
[4] Gao DY (2000a) Duality principles in nonconvex systems, theory, methods and applications. Kluwer Academic, Dordrecht, Boston, London, xviii+454pp · Zbl 0940.49001
[5] Gao DY (2000b) Canonical dual transformation method and generalized triality theory in nonsmooth global optimization. J Glob Optim 17:127–160 · Zbl 0983.74053 · doi:10.1023/A:1026537630859
[6] Gao DY (2004) Canonical duality theory and solutions to constrained nonconvex quadratic programming. J Glob Optim 29:377–399 · Zbl 1075.90074 · doi:10.1023/B:JOGO.0000048034.94449.e3
[7] Gao DY, Ruan N, Sherali X (2008) Solutions and optimality criteria for nonconvex constrained global optimization problems with connections between canonical and Lagrangian duality. J Glob Optim (to appear) · Zbl 1213.90258
[8] Murty KG, Kabadi X (1987) Some NP-hard problems in quadratic and nonlinear programming. Math Program 39:117–129 · Zbl 0637.90078 · doi:10.1007/BF02592948
[9] Pardalos PM, Schnitger X (1988) Checking local optimality in constrained quadratic and nonlinear programming. Oper Res Lett 7:33–35 · Zbl 0644.90067 · doi:10.1016/0167-6377(88)90049-1
[10] Sherali HD, Tuncbilek X (1997) New reformulation-linearization technique based relaxation for univariate and multivariate polynominal programming problems. Oper Res Lett 21(1):1–10 · Zbl 0885.90105 · doi:10.1016/S0167-6377(97)00013-8
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.