Solutions and optimality criteria for nonconvex constrained global optimization problems with connections between canonical and Lagrangian duality. (English) Zbl 1213.90258
Summary: This paper presents a canonical duality theory for solving a general nonconvex quadratic minimization problem with nonconvex constraints. By using the canonical dual transformation developed by the first author, the nonconvex primal problem can be converted into a canonical dual problem with zero duality gap. A general analytical solution form is obtained. Both global and local extrema of the nonconvex problem can be identified by the triality theory associated with the canonical duality theory. Illustrative applications to quadratic minimization with multiple quadratic constraints, box/integer constraints, and general nonconvex polynomial constraints are discussed, along with insightful connections to classical Lagrangian duality. Criteria for the existence and uniqueness of optimal solutions are presented. Several numerical examples are provided.
Reviewer: Stephan Dempe (Freiberg)
MSC:
| 90C46 | Optimality conditions and duality in mathematical programming |
| 90C20 | Quadratic programming |
| 90C26 | Nonconvex programming, global optimization |
References:
| [1] | Bazaraa M.S., Sherali H.D., Shetty C.M.: Nonlinear Programming: Theory and Algorithms, 3rd edn. Wiley, New York (2006) · Zbl 1140.90040 |
| [2] | Ekeland, I., Temam, R.: Convex Analysis and Variational Problems. North-Holland, Amsterdam (1976) · Zbl 0322.90046 |
| [3] | 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) · Zbl 1180.90195 |
| [4] | Fang, S.C., Gao, D.Y., Sheu, R.L., Xing, W.X.: Global optimization for a class of fractional programming problems. J. Glob. Optim., (2008) (in press) |
| [5] | Gao D.Y.: Extended bounding theorems of limit analysis. Appl. Math. Mech. 4, 571–584 (1983) · Zbl 0525.73040 · doi:10.1007/BF01874669 |
| [6] | Gao D.Y.: Panpenalty finite element programming for limit analysis. Comput. Struct. 28, 749–755 (1988) · Zbl 0632.73031 · doi:10.1016/0045-7949(88)90415-4 |
| [7] | Gao D.Y.: Duality, triality and complementary extremun principles in nonconvex parametric variational problems with applications. IMA J. Appl. Math. 61, 199–235 (1998) · Zbl 0923.49017 · doi:10.1093/imamat/61.3.199 |
| [8] | Gao D.Y.: Pure complementary energy principle and triality theory in finite elasticity. Mech. Res. Comm. 26(1), 31–37 (1999) · Zbl 0992.74013 · doi:10.1016/S0093-6413(98)00096-2 |
| [9] | Gao D.Y.: General analytic solutions and complementary variational principles for large deformation nonsmooth mechanics. Meccanica 34, 169–198 (1999) · Zbl 0970.74011 |
| [10] | Gao D.Y.: Duality Principles in Nonconvex Systems: Theory, Methods and Applications, pp. 454. Kluwer Academic Publishers, Dordrecht (2000) · Zbl 0940.49001 |
| [11] | Gao D.Y.: Analytic solution and triality theory for nonconvex and nonsmooth vatiational problems with applications. Nonlinear Anal. 42(7), 1161–1193 (2000) · Zbl 0983.49024 · doi:10.1016/S0362-546X(99)00129-7 |
| [12] | Gao D.Y.: Canonical dual transformation method and generalized triality theory in nonsmooth global optimization. J. Glob. Optim. 17(1/4), 127–160 (2000) · Zbl 0983.74053 · doi:10.1023/A:1026537630859 |
| [13] | Gao D.Y.: Finite deformation beam models and triality theory in dynamical post-buckling analysis. Int. J. Non-Linear Mech. 5, 103–131 (2000) · Zbl 1068.74569 · doi:10.1016/S0020-7462(98)00091-2 |
| [14] | Gao, D.Y.: Tri-duality in global optimization. In: Floudas, C.A., Pardalos, P.D. (eds.) Encyclopedia of Optimization, Vol. 1, pp. 485–491. Kluwer Academic Publishers, Dordrecht (2001) |
| [15] | Gao D.Y.: Nonconvex Semi-linear Problems and Canonical Dual Solutions. Advances in Mechanics and Mathematics, Vol. II, pp. 261–312. Kluwer Academic Publishers, Dordrecht (2003) · Zbl 1067.49024 |
| [16] | Gao D.Y.: Perfect duality theory and complete solutions to a class of global optimization problems. Optimization 52(4–5), 467–493 (2003) · Zbl 1040.49036 · doi:10.1080/02331930310001611501 |
| [17] | Gao D.Y.: Complete solutions to constrained quadratic optimization problems, Special issue on Duality. J. Glob. Optim. 29, 377–399 (2004) · Zbl 1075.90074 · doi:10.1023/B:JOGO.0000048034.94449.e3 |
| [18] | Gao D.Y.: Sufficient conditions and perfect duality in nonconvex minimization with inequality constraints. J. Ind. Manag. Optim. 1, 59–69 (2005) |
| [19] | Gao D.Y.: Complete solutions and extremality criteria to polynomial optimization problems. J. Glob. Optim. 35, 131–143 (2006) · Zbl 1104.90038 · doi:10.1007/s10898-005-3068-5 |
| [20] | Gao D.Y.: Solutions and optimality to box constrained nonconvex minimization problems. J. Ind. Maneg. Optim. 3(2), 293–304 (2007) · Zbl 1171.90504 |
| [21] | Gao, D.Y.: Advances in canonical duality theory with applications to global optimization. In: Ierapetriou, M., Bassett, M., Pistikopoulos, S. (eds.) Proceedings of the Fifth International Conference on Foundations of Computer-Aided Process Operations, pp.73–82. Omni Press, Cambridge, MA (2008) |
| [22] | Gao D.Y., Ogden R.W.: Closed-form solutions, extremality and nonsmoothness criteria in a large deformation elasticity problem. Zeitschrift für angewandte Mathematik und Physik 59(3), 498–517 (2008) · Zbl 1143.74018 · doi:10.1007/s00033-007-7047-1 |
| [23] | Gao D.Y., Ogden R.W.: Multi-solutions to nonconvex variational problems with implications for phase transitions and numerical computation. Q. J. Mech. Appl. Math. 61(4), 497–522 (2008) · Zbl 1153.74032 · doi:10.1093/qjmam/hbn014 |
| [24] | Gao D.Y., Ruan N.: Solutions and optimality criteria for nonconvex quadratic-exponential minimization problem. Math. Methods Oper. Res. 67(3), 479–496 (2008) · Zbl 1145.90054 · doi:10.1007/s00186-007-0204-7 |
| [25] | Gao, D.Y., Ruan, N.: On the solutions to quadratic minimization problems with box and integer constraints. J. Glob. Optim. (2008) (in press) |
| [26] | Gao D.Y., Sherali H.D.: Canonical Duality Theory: Connections Between Nonconvex Mechanics and Global Optimization, Advances in Applied Mathematics and Global Optimization, pp. 249–316. Springer, New York (2008) |
| [27] | Gao D.Y., Strang G.: Geometric nonlinearity: potential energy, complementary energy, and the gap function. Q. Appl. Math. 47(3), 487–504 (1989) · Zbl 0691.73012 |
| [28] | Gao D.Y., Yang W.C.: Complete solutions to minimal distance problem between two nonconvex surfaces. Optimization 57(5), 705–714 (2008) · Zbl 1152.90552 · doi:10.1080/02331930802355309 |
| [29] | Gao D.Y., Yu H.F.: Multi-scale modelling and canonical dual finite element method in phase transitions of solids. Int. J. Solids Struct. 45, 3660–3673 (2008) · Zbl 1169.74518 · doi:10.1016/j.ijsolstr.2007.08.027 |
| [30] | Gao, D.Y., Ruan, N., Pardalos, P.M.: Canonical dual solutions to sum of fourth-order polynomials minimization problems with applications to sensor network localization, to appear. In: Pardalos, P.M., Ye, Y., Boginski, V.L., Commander, C.W. (eds.) Sensors: Theory, Algorithms, and Applications. Springer, Berlin (2008) |
| [31] | Hansen, P., Jaumard, B., Ruiz, M., Xiong, J.: Global minimization of indefinite quadratic functions subject to box constraints. Technical report, Technical Report G-91-54, Gread. École Polytechnique, Université McGill, Montreal (1991) · Zbl 0782.90071 |
| [32] | Hellinger, E.: Die allgemeine Ansätze der Mechanik der Kontinua. Encyklopädie der Mathematischen Wissenschaften IV(Part 4), 602–694 (1914) |
| [33] | Horst R., Pardalos P.M., Thoai N.V.: Introduction to Global Optimization. Kluwer Academic Publishers, Dordrecht (2000) · Zbl 0966.90073 |
| [34] | 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(3), 471–481 (2006) · Zbl 1131.90060 · doi:10.1007/s10898-006-9022-3 |
| [35] | Jeyakumar V., Rubinov A.M., Wu Z.Y.: Non-convex quadratic minimization problems with quadratic constraints: global optimality conditions. Math. Program. 110(3), 521–541 (2007) · Zbl 1206.90178 · doi:10.1007/s10107-006-0012-5 |
| [36] | Johnson, D.E., Cohen, E.: A framework for efficient minimum distance computations. In: Proc. IEEE International Conference on Robotics and Automation, pp. 3678–3684. Leuven, Belgium (1998) |
| [37] | Koiter, W.T.: On the complementary energy theorem in nonlinear elasticity theory. In: G. Fichera (ed.) Trends Appl. Pure Math. Mech., Pitman, London (1976) · Zbl 0348.73022 |
| [38] | Lagrange J.L.: Mécanique Analytique. Gauthier-Villars, Paris (1788) |
| [39] | Li S.F., Gupta A.: On dual configuration forces. J. Elast. 84, 13–31 (2006) · Zbl 1103.74013 · doi:10.1007/s10659-005-9047-8 |
| [40] | Nash S.G., Sofer A.: Linear and Nonlinear Programming. McGraw-Hill, New York (1996) |
| [41] | Ogden R.W.: A note on variational theorems in non-linear elastostatics. Math. Proc. Camb. Phil. Soc 77, 609–615 (1975) · Zbl 0312.73052 · doi:10.1017/S0305004100051422 |
| [42] | Pardalos P.M., Vavasis S.A.: Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 21, 843–855 (1991) · Zbl 0755.90065 |
| [43] | Reissner, E.: On a variational theorem for finite elastic deformations. J. Math. Phys., 32(2–3), 129-135 (1953). (See also Selected Works in Applied Mechanics and Mathematics, Jones and Bartlett Publishers, Boston, MA, 1996) · Zbl 0051.16303 |
| [44] | Rockafellar R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401 |
| [45] | Ruan, N., Gao, D.Y., Jiao, Y.: Canonical dual least square method for solving general nonlinear systems of quadratic equations. Comput. Optim. Appl. (published online: http://www.springerlink.com/content/c6090221p4g41858/ ) (2008). DOI: 10.1007/s10589-008-9222-5 · Zbl 1200.90139 |
| [46] | Sahni S.: Computationally related problems. SIAM J. Comp. 3, 262–279 (1974) · doi:10.1137/0203021 |
| [47] | Sherali H.D., Tuncbilek C.: A global optimization for polynomial programming problem using a reformulation-linearization technique. J. Glob. Optim. 2, 101–112 (1992) · Zbl 0787.90088 · doi:10.1007/BF00121304 |
| [48] | Sherali H.D., Tuncbilek C.: New reformulation-linearization technique based relaxation for univariate and multivariate polynomial programming problems. Oper. Res. Lett. 21(1), 1–10 (1997) · Zbl 0885.90105 · doi:10.1016/S0167-6377(97)00013-8 |
| [49] | Wang Z., Fang S.C., Gao D.Y., Xing W.: Global extremal conditions for multi-integer quadratic programming. J. Ind. Manag. Optim. 4(2), 213–226 (2008) · Zbl 1161.90457 |
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.
