×

On global optimization with indefinite quadratics. (English) Zbl 1384.90075

Summary: We present an algorithmic framework for global optimization problems in which the non-convexity is manifested as an indefinite-quadratic as part of the objective function. Our solution approach consists of applying a spatial branch-and-bound algorithm, exploiting convexity as much as possible, not only convexity in the constraints, but also extracted from the indefinite-quadratic. A preprocessing stage is proposed to split the indefinite-quadratic into a difference of convex quadratic functions, leading to a more efficient spatial branch-and-bound focused on the isolated non-convexity. We investigate several natural possibilities for splitting an indefinite quadratic at the preprocessing stage, and prove the equivalence of some of them. Through computational experiments with our new solver iquad, we analyze how the splitting strategies affect the performance of our algorithm, and find guidelines for choosing amongst them.

MSC:

90C26 Nonconvex programming, global optimization
90C11 Mixed integer programming
90C20 Quadratic programming
90C22 Semidefinite programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adjiman CS, Dallwig S, Floudas CA, Neumaier A (1998a) A global optimization method, \[ \alpha\] αBB, for general twice-differentiable constrained NLPs—I. Theoretical advances. Comput Chem Eng 22(9):1137-1158 · doi:10.1016/S0098-1354(98)00027-1
[2] Adjiman CS, Dallwig S, Floudas CA, Neumaier A (1998b) A global optimization method, \[ \alpha\] αBB, for general twice-differentiable constrained NLPs—II. Implementation and computational results. Comput Chem Eng 22(9):1159-1179 · doi:10.1016/S0098-1354(98)00218-X
[3] Alizadeh F (1993) Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J Optim 5:13-51 · Zbl 0833.90087 · doi:10.1137/0805002
[4] An LTH, Tao PD, Muu LD (1998) A combined d.c. optimization—ellipsoidal branch-and-bound algorithm for solving nonconvex quadratic programming problems. Semidefinite programming and interior-point approaches for combinatorial optimization problems (Toronto, ON, 1996). J Comb Optim 2(1):9-28 · Zbl 0904.90134 · doi:10.1023/A:1009777410170
[5] An LTH, Tao PD (2005) The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann Oper Res 133:23-46 · Zbl 1116.90122 · doi:10.1007/s10479-004-5022-1
[6] Anstreicher KM, Burer S (2005) D.C. versus copositive bounds for standard QP. J Glob Optim 33:299-312 · Zbl 1093.90033 · doi:10.1007/s10898-004-4312-0
[7] Belotti P, Lee J, Liberti L, Margot F, Wächter A (2009) Branching and bounds tightening techniques for non-convex MINLP. Optim Methods Softw 24:597-634 · Zbl 1179.90237 · doi:10.1080/10556780903087124
[8] Billionnet A, Elloumi S, Lambert A (2014) A branch and bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation. J Comb Optim 2(28):376-399 · Zbl 1291.90145 · doi:10.1007/s10878-012-9560-1
[9] Bomze IM, Dür MD, De Klerk E, Roos C, Quist AJ, Terlaky T (2000) On copositive programming and standard quadratic optimization problems. J Glob Optim 18:301-320 · Zbl 0967.00090 · doi:10.1023/A:1026583532263
[10] Bomze IM, Locatelli M (2004) Undominated d.c. decompositions of quadratic functions and applications to branch-and-bound approaches. Comput Optim Appl 28(2):227-245 · Zbl 1056.90112 · doi:10.1023/B:COAP.0000026886.61324.e4
[11] Bradley SP, Hax AC, Magnanti TL (1977) Applied mathematical programming. Addison-Wesley, Boston
[12] Burer S, Chen J (2012) Globally solving nonconvex quadratic programming problems via completely positive programming. Math Program Comput 4:33-52 · Zbl 1257.90065 · doi:10.1007/s12532-011-0033-9
[13] Burer S, Saxena A (2012) The MILP road to MIQCP. In: Lee J, Leyffer S (eds) Mixed-integer nonlinear programming. The IMA volumes in mathematics and its applications, vol 154. Springer, New York, pp 373-405 · Zbl 1242.90122
[14] Burer S, Vandenbussche D (2008) A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math Program Ser A 113:259-282 · Zbl 1135.90034 · doi:10.1007/s10107-006-0080-6
[15] Burkard RE, Çela E, Pardalos PM, Pitsoulis LS (1998) The quadratic assignment problem. Handbook of combinatorial optimization, vol 3. Kluwer Acad. Publ., Boston, pp 241-237 · Zbl 0944.90071
[16] Calamai PH, Vicente LN, Júdice JJ (1993) A new technique for generating quadratic programming test problems. Math Program 61:215-231 · Zbl 0795.90047 · doi:10.1007/BF01582148
[17] COUENNE http://projects.coin-or.org/Couenne
[18] CPLEX http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/ · Zbl 0876.90071
[19] D’Ambrosio C, Lee J, Wächter A (2012) An algorithmic framework for MINLP with separable non-convexity. In: Lee J, Leyffer S (eds) Mixed-integer nonlinear programming. The IMA volumes in mathematics and its applications, vol 154, pp 315-347 · Zbl 1242.90124
[20] Hemmecke R, Köppe M, Lee J, Weismantel R (2010) Nonlinear integer programming. In: Jünger M, Liebling T, Naddef D, Nemhauser G, Pulleyblank W, Reinelt G, Rinaldi G, Wolsey L (eds) 50 Years of integer programming 1958-2008: the early years and state-of-the-art surveys. Springer, Berlin, pp 561-618 · Zbl 1099.90047
[21] Horst R, Thoai NV (1999) DC programming: overview. J Optim Theory Appl 103:1-43 · Zbl 1073.90537 · doi:10.1023/A:1021765131316
[22] Lee J (2007) In situ column generation for a cutting-stock problem. Comput Oper Res 34(8):2345-2358 · Zbl 1149.90187 · doi:10.1016/j.cor.2005.09.007
[23] Lee J, Leyffer S (eds) (2012) Mixed-integer nonlinear programming. The IMA volumes in mathematics and its applications, vol 154. Springer, New York · Zbl 1254.90151
[24] Rendl F, Rinaldi G, Wiegele A (2010) Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math Program Ser A 121(2):307-335 · Zbl 1184.90118 · doi:10.1007/s10107-008-0235-8
[25] Saxena A, Bonami P, Lee J (2010) Convex relaxations of non-convex mixed-integer quadratically-constrained programs: extended formulations. Math Program Ser B 124(1-2):383-411 · Zbl 1198.90330 · doi:10.1007/s10107-010-0371-9
[26] Saxena A, Bonami P, Lee J (2011) Convex relaxations of non-convex mixed-integer quadratically-constrained programs: projected formulations. Math Program Ser A 130(2):359-413 · Zbl 1229.90144 · doi:10.1007/s10107-010-0340-3
[27] Tao PD, An LTH (1996) d.c. (difference of convex functions) optimization algorithms (DCA) for globally minimizing nonconvex quadratic forms on Euclidean balls and spheres. Oper Res Lett 19:207-216 · Zbl 0876.90071 · doi:10.1016/S0167-6377(96)00036-3
[28] Tawarmalani M, Sahinidis NV (2005) A polyhedral branch-and-cut approach to global optimization. Math Program 103(2):225-249 · Zbl 1099.90047 · doi:10.1007/s10107-005-0581-8
[29] Zheng XJ, Sun XL, Li D (2011) Nonconvex quadratically constrained quadratic programming: best d.c. decompositions and their SDP representations. J Glob Optim 50:695-712 · Zbl 1254.90151 · doi:10.1007/s10898-010-9630-9
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.