×

zbMATH — the first resource for mathematics

An LPCC approach to nonconvex quadratic programs. (English) Zbl 1244.90177
Summary: Filling a gap in nonconvex quadratic programming, this paper shows that the global resolution of a feasible quadratic program (QP), which is not known a priori to be bounded or unbounded below, can be accomplished in finite time by solving two linear programs with linear complementarity constraints, i.e., LPCCs. Specifically, this task can be divided into two LPCCs: the first confirms whether the QP is bounded below on the feasible set and, if not, computes a feasible ray on which the QP is unbounded; the second LPCC computes a globally optimal solution if it exists, by identifying a stationary point that yields the best quadratic objective value. In turn, the global resolution of these LPCCs can be accomplished by a parameter-free, mixed integer-programming based, finitely terminating algorithm developed recently by the authors, which can be enhanced in this context by a new kind of valid cut derived from the second-order conditions of the QP and by exploiting the special structure of the LPCCs. Throughout, our treatment makes no boundedness assumption of the QP; this is a significant departure from much of the existing literature which consistently employs the boundedness of the feasible set as a blanket assumption. The general theory is illustrated by 3 classes of indefinite problems: QPs with simple upper and lower bounds (existence of optimal solutions is guaranteed); same QPs with an additional inequality constraint (extending the case of simple bound constraints); and nonnegatively constrained copositive QPs (no guarantee of the existence of an optimal solution). We also present numerical results to support the special cuts obtained due to the QP connection.

MSC:
90C20 Quadratic programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C26 Nonconvex programming, global optimization
90C10 Integer programming
Software:
MINTO; Chaff
PDF BibTeX Cite
Full Text: DOI
References:
[1] Audet C., Hansen P., Jaumard B., Savard G.: A symmetrical linear maxmin approach to disjoint bilinear programming. Math. Program. 85, 573–592 (1999) · Zbl 0980.90051
[2] Balas E.: Nonconvex quadratic programming via generalized polars. SIAM J. Appl. Math. 28, 335–349 (1975) · Zbl 0294.90066
[3] Balas E.: Disjunctive programming. Ann. Discr. Math. 5, 3–51 (1979) · Zbl 0409.90061
[4] Borchers B., Furman J.: A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT Problems. J. Combinatorial Optim. 2, 299–306 (1998) · Zbl 0954.90026
[5] Burer S., Vandenbussche D.: Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound. Comput. Optim. Appl. 43, 181–195 (2009) · Zbl 1170.90522
[6] Burer S., Vandenbussche D.: A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Program. 113, 259–282 (2008) · Zbl 1135.90034
[7] Codato G., Fischetti M.: Combinatorial Benders’ Cuts for mixed-integer linear programming. Oper. Res. 54, 758–766 (2006) · Zbl 1167.90601
[8] Duran M., Grossmann I.E.: An outer-approximation algorithm for a class of mixed integer nonlinear programs. Math. Program. 36, 307–339 (1986) · Zbl 0619.90052
[9] Eaves B.C.: On quadratic programming. Manag. Sci. 17, 698–711 (1971) · Zbl 0242.90040
[10] Floudas C.A., Visweswaran V.: Quadratic Programming. Handbook of Global Optimization, pp. 217–269. Kluwer Academic Publishers, Dordrecht (1995) · Zbl 0833.90091
[11] Frank M., Wolfe P.: An algorithm for quadratic programming. Naval Res. Logist. Q. 3, 149–154 (1956)
[12] Giannessi F., Tomasin E.: Nonconvex quadratic programs, linear complementarity problems, and integer linear programs. In: Conti, R., Ruberti, A. (eds) Fifth Conference on Optimization Techniques (Rome 1973), Part I, Lecture Notes in Computer Science, vol. 3, pp. 437–449. Springer, Berlin (1973) · Zbl 0274.90039
[13] Grossmann I.E.: MINLP: logic-based methods. In: Floudas, C.A., Pardalos, P.M. (eds) Encyclopedia of Optimization, vol. II., pp. 369–373. Kluwer Academic Publishers, Dordrecht (2001)
[14] Grossmann I.E.: Generalized disjunctive programming. In: Floudas, C.A., Pardalos, P.M. (eds) Encyclopedia of Optimization, Springer, New York (2007)
[15] Hager W.W., Pardalos P.M., Sahinoglou H.D.: Active constraints, indefinite quadratic test problems, and complexity. J. Optim. Theory Appl. 68, 499–511 (1991) · Zbl 0697.90059
[16] Hansen P., Jaumard B., Ruiz M., Xiong J.: Global minimization of indefinite quadratic functions subject to box constraints. Naval Res. Logist. Q. 40, 373–392 (1993) · Zbl 0782.90071
[17] Hooker J.N.: Logic-Based Methods for Optimization. Wiley, London (2000) · Zbl 0974.90001
[18] Hooker J.N.: Integrated Methods for Optimization. Springer, New York (2006) · Zbl 1103.68811
[19] Hooker J.N., Ottosson G.: Logic-based benders decomposition. Math. Program. 96, 33–60 (2003) · Zbl 1023.90082
[20] Hu, J.: On linear programs with linear complementarity constraints. Ph.D. thesis, Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy (August 2008)
[21] Hu J., Mitchell J., Pang J.S., Bennett K., Kunapuli G.: On the global solution of linear programs with linear complementarity constraints. SIAM J. Optim. 19, 445–471 (2008) · Zbl 1163.90031
[22] Hu, J., Mitchell, J.E., Pang, J.S., Yu, B.: On linear programs with linear complementarity constraints. RPI Mathematical Sciences Technical Report. Accepted for publication in the Journal of Global Optimization (September 2009) · Zbl 1254.90111
[23] Joy, S., Mitchell, J.E., Borchers, B.: A branch-and-cut algorithm for MAX-SAT and weighted MAX-SAT. In: Du, D., Gu, J., Pardalos, P.M. (eds.) Satisfiability Problem: Theory and Applications, [DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 35]. American Mathematical Society, pp. 519–536 (1997) · Zbl 0889.68074
[24] Lee S., Grossmann I.E.: New algorithms for nonlinear disjunctive programming. Comput. Chem. Eng. 24, 2125–2141 (2000)
[25] Luo Z.Q., Tseng P.: Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem. SIAM J. Optim. 2, 43–54 (1992) · Zbl 0777.49010
[26] Majthay A.: Optimality conditions for quadratic programming. Math. Program. 1, 359–365 (1971) · Zbl 0246.90038
[27] Moskewicz, M., Madigan, C., Zhao, Y., Zhang, L., Malik, S.: Chaff: Engineering an efficient SAT solver. In: 39th Design automation conference (DAC 2001), Las Vegas, pp. 530–535 (June 2001)
[28] Nemhauser G.L., Savelsbergh M.W.P., Sigismondi G.C.: MINTO, a mixed INTeger optimizer. Oper. Res. Lett. 15, 47–58 (1994) · Zbl 0806.90095
[29] Pang J.S., Leyffer S.: On the global minimization of the value-at-risk. Optim. Methods Softw. 19, 611–631 (2004) · Zbl 1114.91320
[30] Pardalos P.M., Vavasis S.A.: Quadratic programming with one negative eigenvalue is NP-hard. J. Global Optim. 1, 15–23 (1991) · Zbl 0755.90065
[31] Saxena, A., Bonami, P., Lee, J.: Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations. IBM Research Report RC24695. Mathematical Programming, online first (August 2008) · Zbl 1229.90144
[32] Tawarmalani M., Sahinidis N.V.: Convexification and Global Optimization in Continuous and Mixed Integer Nonlinear Programming. Kluwer Academic Publishers, Dordrecht (2002) · Zbl 1031.90022
[33] Vandenbussche D., Nemhauser G.L.: A polyhedral study of nonconvex quadratic programs with box constraints. Math. Program., Series A 102, 531–557 (2005) · Zbl 1137.90009
[34] Vandenbussche D., Nemhauser G.L.: A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math. Program., Series A 102, 559–575 (2005) · Zbl 1137.90010
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.