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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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)
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)
Contesse L.: Une caractérisation compléte des minima locaux en programmation quadratique. Numerische Mathematik 34, 315–332 (1980)
Ekeland, I., Temam, R.: Convex Analysis and Variational Problems. North-Holland (1976)
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)
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)
Floudas C.A.: Deterministic Optimization. Theory, Methods, and Applications. Kluwer, London (2000)
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)
Floudas C.A., Visweswaran V.: A primal-relaxed dual global optimization approach. J. Optim. Theory Appl. 78(2), 187–225 (1993)
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)
Gao D.Y.: Duality, triality and complementary extremum principles in nonconvex parametric variational problems with applications. IMA J. Appl. Math. 61, 199–235 (1998)
Gao D.Y.: Duality Principles in Nonconvex Systems: Theory, Methods and Applications, 18+454pp. Kluwer, Dordrecht/Boston/London (2000)
Gao D.Y.: Canonical dual transformation method and generalized triality theory in nonsmooth global optimization. J. Glob. Optim. 17(1/4), 127–160 (2000)
Gao D.Y.: Perfect duality theory and complete solutions to a class of global optimization problems. Optimization 52(4–5), 467–493 (2003)
Gao D.Y.: Canonical duality theory and solutions to constrained nonconvex quadratic programming. J. Glob. Optim. 29, 377–399 (2004)
Gao D.Y.: Solutions and optimality to box constrained nonconvex minimization problems. J. Ind. Maneg. Optim. 3(2), 293–304 (2007)
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
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)
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
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)
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)
Gao D.Y., Strang G.: Geometric nonlinearity: Potential energy, complementary energy, and the gap function. Quart. Appl. Math. 47(3), 487–504 (1989)
Gao D.Y., Yang W.H.: Multi-duality in minimal surface type problems. Stud. Appl. Math. 95, 127–146 (1995)
Goemans M.X., Williamson D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115–1145 (1995)
Grippo L., Lucidi S.: A differentiable exact penalty function for bound constrained quadratic programming problems. Optimization 22(4), 557–578 (1991)
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)
Jones D., Perttunen C., Stuckman B.: Lipschitzian optimization without the lipschitz constant. J. Optim. Theory Appl. 79, 157–181 (1993)
Li S.F., Gupta A.: On dual configuration forces. J. Elast. 84, 13–31 (2006)
Murty K.G., Kabadi S.N.: Some NP-hard problems in quadratic and nonlinear programming. Math. Program. 39, 117–129 (1987)
Pardalos P.M., Schnitger G.: Checking local optimality in constrained quadratic and nonlinear programming. Oper. Res. Lett. 7, 33–35 (1988)
Pardalos P., Vavasis S.: Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 1, 15–23 (1991)
Rockafellar R.T.: Convex Analysis. Princeton University Press, Princeton, NJ (1970)
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
Sherali H.D., Tuncbilek C.: A global optimization for polynomial programming problem using a reformulation-linearization technique. J. Glob. Optim. 2, 101–112 (1992)
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)
Todd M.: Semidefinite optimization. Acta Numerica 10, 515–560 (2001)
Wang, Z.B., Fang, S-C., Gao, D.Y., Xing, W.X.: Canonical duality approach to maximum cut problem, to appear (2009)
Author information
Authors and Affiliations
Corresponding author
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
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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-009-9469-0