Skip to main content
SpringerLink
Log in

Solutions to quadratic minimization problems with box and integer constraints

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

This paper presents a canonical duality theory for solving quadratic minimization problems subjected to either box or integer constraints. Results show that under Gao and Strang’s general global optimality condition, these well-known nonconvex and discrete problems can be converted into smooth concave maximization dual problems over closed convex feasible spaces without duality gap, and can be solved by well-developed optimization methods. Both existence and uniqueness of these canonical dual solutions are presented. Based on a second-order canonical dual perturbation, the discrete integer programming problem is equivalent to a continuous unconstrained Lipschitzian optimization problem, which can be solved by certain deterministic technique. Particularly, an analytical solution is obtained under certain condition. A fourth-order canonical dual perturbation algorithm is presented and applications are illustrated. Finally, implication of the canonical duality theory for the popular semi-definite programming method is revealed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Akrotirianakis I.G., Floudas C.A.: Computational experience with a new class of convex underestimators: Box-constrained NLP problems. J. Glob. Optim. 29, 249–264 (2004)

    Article  Google Scholar 

  2. Akrotirianakis I.G., Floudas C.A.: A new class of improved convex underestimators for twice continuously differentiable constrained NLPs. J. Glob. Optim. 30, 367–390 (2004)

    Article  Google Scholar 

  3. Contesse L.: Une caractérisation compléte des minima locaux en programmation quadratique. Numerische Mathematik 34, 315–332 (1980)

    Article  Google Scholar 

  4. Ekeland, I., Temam, R.: Convex Analysis and Variational Problems. North-Holland (1976)

  5. Fang S.C., Gao D.Y., Sheu R.l., Wu S.Y.: Canonical dual approach for solving 0–1 quadratic programming problems. J. Ind. Manag. Optim. 4(1), 125–142 (2008)

    Google Scholar 

  6. Fang, S.C., Gao D.Y., Sheu R.l., Xin, W.X.: Global optimization for a class of fractional programming problems, to appear in. J. Glob. Optim. (2008)

  7. Floudas C.A.: Deterministic Optimization. Theory, Methods, and Applications. Kluwer, London (2000)

    Google Scholar 

  8. Floudas C.A., Akrotirianakis I.G., Caratzoulas S., Meyer C.A., Kallrath J.: Global optimization in the 21th century: Advances and challenges. Comput. Chem. Eng. 29, 1185–1202 (2005)

    Article  Google Scholar 

  9. Floudas C.A., Visweswaran V.: A primal-relaxed dual global optimization approach. J. Optim. Theory Appl. 78(2), 187–225 (1993)

    Article  Google Scholar 

  10. Floudas C.A., Visweswaran V.: Quadratic optimization. In: Horst, R., Pardalos, P.M. (eds) Handbook of Global Optimization, pp. 217–270. Kluwer, Dordrecht/Boston/London (1995)

    Google Scholar 

  11. Gao D.Y.: Duality, triality and complementary extremum principles in nonconvex parametric variational problems with applications. IMA J. Appl. Math. 61, 199–235 (1998)

    Article  Google Scholar 

  12. Gao D.Y.: Duality Principles in Nonconvex Systems: Theory, Methods and Applications, 18+454pp. Kluwer, Dordrecht/Boston/London (2000)

    Google Scholar 

  13. Gao D.Y.: Canonical dual transformation method and generalized triality theory in nonsmooth global optimization. J. Glob. Optim. 17(1/4), 127–160 (2000)

    Article  Google Scholar 

  14. Gao D.Y.: Perfect duality theory and complete solutions to a class of global optimization problems. Optimization 52(4–5), 467–493 (2003)

    Article  Google Scholar 

  15. Gao D.Y.: Canonical duality theory and solutions to constrained nonconvex quadratic programming. J. Glob. Optim. 29, 377–399 (2004)

    Article  Google Scholar 

  16. Gao D.Y.: Solutions and optimality to box constrained nonconvex minimization problems. J. Ind. Maneg. Optim. 3(2), 293–304 (2007)

    Google Scholar 

  17. Gao D.Y.: Canonical duality theory: Unified understanding and generalized solution for global optimization problems. Comp. Chem. Eng. (2009) doi:10.1016/j.compchemeng.2009.06.009

  18. Gao D.Y., Ogden R.W.: Multiple solutions to non-convex variational problems with implications for phase transitions and numerical computation. Quart. J. Mech. Appl. Math. 61(4), 497–522 (2008)

    Article  Google Scholar 

  19. Gao, D.Y., Ruan, N., Sherali, H.D.: Solutions and optimality criteria for nonconvex constrained global optimization problems with connections between canonical and Lagrangian duality, J. Glob. Optim. (2009). doi:10.1007/s10898-009-9399-x

  20. Gao, D.Y., Ruan, N, Walson, L., Tranter, W.H.: Canonical dual approach for solving box and integer constrained minimization problems via a deterministic direct search algorithm. (2009) (in preparation)

  21. Gao D.Y., Sherali H.D.: Canonical duality theory: Connections between nonconvex mechanics and global optimization. In: Gao, D.Y., Sherali, H. (eds) Advances in Applied Mathematics and Global Optimization, pp. 257–326. Springer, USA (2009)

    Google Scholar 

  22. Gao D.Y., Strang G.: Geometric nonlinearity: Potential energy, complementary energy, and the gap function. Quart. Appl. Math. 47(3), 487–504 (1989)

    Google Scholar 

  23. Gao D.Y., Yang W.H.: Multi-duality in minimal surface type problems. Stud. Appl. Math. 95, 127–146 (1995)

    Google Scholar 

  24. Goemans M.X., Williamson D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115–1145 (1995)

    Article  Google Scholar 

  25. Grippo L., Lucidi S.: A differentiable exact penalty function for bound constrained quadratic programming problems. Optimization 22(4), 557–578 (1991)

    Article  Google Scholar 

  26. Hansen, P., Jaumard, B., Ruiz, M., Xiong, J.: Global minimization of indefinite quadratic functions subject to box constraints. Technical Report G-91–54, GERAD, École Polytechnique, Université McGill, Montreal (1991)

  27. Jones D., Perttunen C., Stuckman B.: Lipschitzian optimization without the lipschitz constant. J. Optim. Theory Appl. 79, 157–181 (1993)

    Article  Google Scholar 

  28. Li S.F., Gupta A.: On dual configuration forces. J. Elast. 84, 13–31 (2006)

    Article  Google Scholar 

  29. Murty K.G., Kabadi S.N.: Some NP-hard problems in quadratic and nonlinear programming. Math. Program. 39, 117–129 (1987)

    Article  Google Scholar 

  30. Pardalos P.M., Schnitger G.: Checking local optimality in constrained quadratic and nonlinear programming. Oper. Res. Lett. 7, 33–35 (1988)

    Article  Google Scholar 

  31. Pardalos P., Vavasis S.: Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 1, 15–23 (1991)

    Article  Google Scholar 

  32. Rockafellar R.T.: Convex Analysis. Princeton University Press, Princeton, NJ (1970)

    Google Scholar 

  33. Ruan N., Gao D.Y., Jiao Y. Canonical dual least square method for solving general nonlinear systems of equations. Computational Optimization with Applications (published online: http://www.springerlink.com/content/c6090221p4g41858/). (2008) doi:10.1007/s10589-008-9222-5

  34. Sherali H.D., Tuncbilek C.: A global optimization for polynomial programming problem using a reformulation-linearization technique. J. Glob. Optim. 2, 101–112 (1992)

    Article  Google Scholar 

  35. Sherali H.D., Tuncbilek C.: New reformulation-linearization technique based relaxation for univariate and multivariate polynominal programming problems. Oper. Res. Lett. 21(1), 1–10 (1997)

    Article  Google Scholar 

  36. Todd M.: Semidefinite optimization. Acta Numerica 10, 515–560 (2001)

    Article  Google Scholar 

  37. Wang, Z.B., Fang, S-C., Gao, D.Y., Xing, W.X.: Canonical duality approach to maximum cut problem, to appear (2009)

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Virginia Tech, Blacksburg, VA, 24061, USA

    David Yang Gao & Ning Ruan

Authors
  1. David Yang Gao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ning Ruan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to David Yang Gao.

Additional information

Plenary lecture presented at the Second International Conference on Duality, and Global Optimization with applications in Engineering and Science, University of Florida, February 28–March 2, 2007.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gao, D.Y., Ruan, N. Solutions to quadratic minimization problems with box and integer constraints. J Glob Optim 47, 463–484 (2010). https://doi.org/10.1007/s10898-009-9469-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-009-9469-0

Keywords

Search

Navigation