Decomposition methods for solving a class of nonconvex programming problems dealing with bilinear and quadratic functions. (English) Zbl 0834.90101

Muu, Le Dung; Phong, Thai Quynh; Tao, Pham Dinh

Comput. Optim. Appl. 4, No. 3, 203-216 (1995).

Summary: We develop convergent decomposition branch-and-bound algorithms for solving a class of bilinear programming problems. As an application of the proposed method, we apply it to quadratic programs with a few negative eigenvalues, and to a class of mixed integer programming problems.

MSC:

90C20	Quadratic programming
90C26	Nonconvex programming, global optimization
90C11	Mixed integer programming

Keywords:

adaptive bisection; convergent decomposition branch-and-bound algorithms; bilinear programming

References:

[1]	F.A. Al-Khayyal and J.E. Falk, ?Jointly constrained biconvex programming,? Mathematics of Operations Research, Vol. 8 pp. 273-286, 1983. · Zbl 0521.90087
[2]	R. Horst and H. Tuy, ?Global Optimization: Deterministic Approaches,? 2 edition Berlin, New York: Springer-Verlag, 1993. · Zbl 0704.90057
[3]	H. Konno, ?A cutting plane algorithm for solving bilinear programs,? Mathematical Programming, Vol. 11, pp. 14-27, 1976. · Zbl 0353.90069
[4]	L.D. Muu and W. Oettli, ?A method for minimizing a convex?concave function over a convex set,? J. of Optimization Theory and Applications, Vol. 70 pp. 337-384, 1991. · Zbl 0743.90101
[5]	L.D. Muu and W. Oettli. ?Combined branch and bound and cutting plane methods for solving a class of nonlinear programming problems,? J. of Global Optimization, Vol. 3, pp. 377-391, 1993. · Zbl 0780.90088
[6]	L.D. Muu and B.T. Tam, ?Efficient methods for solving certain bilinear programming problem,? to appear in Acta Mathematica Vietnamica. · Zbl 0889.90139
[7]	P.M. Pardalos and J.B. Rosen, ?Constrained global optimization: Algorithms and applications,? in G. Goos and J. Hartmans, editors, Lecture Notes in Computer Science, number 268. Berlin: Springer-Verlag, 1987. · Zbl 0638.90064
[8]	P.M. Pardalos and S.A. Vavasis, ?Quadratic programming with one negative eigenvalue is NP-hard,? J. of Global Optimization, Vol. 21, pp. 843-855, 1991.
[9]	A.T. Phillips and J.B. Rosen, ?A parallel algorithm for constrained concave quadratic global minimization,? Mathematical Programming, Vol. 42, pp. 412-448, 1988. · Zbl 0665.90071
[10]	T.Q. Phong, L.T.H. An, and Pham D. Tao, ?On globally solving linearly constrained indefinite quadratic minimization problems by decomposition branch and bound method,? (submitted). · Zbl 0857.90098
[11]	H.D. Sherali and A. Alameddine, ?A new reformulation?linearization technique for bilinear programming problems,? J. of Global Optimization, Vol. 2, pp. 379-410, 1992. · Zbl 0791.90056
[12]	H.D. Sherali and C.M. Shetty, ?A finitely convergent algorithm for bilinear programming problem using polar cuts and disjunctive face cuts,? Mathematical Programming, Vol. 19, pp. 379-410, 1980. · Zbl 0436.90079
[13]	Pham D. Tao ?Un algorithme pour la résolution du programme linéaire général,? RAIRO-Recherche opérationnelle, Vol. 25, pp. 183-201, 1991.
[14]	T.V. Thieu, ?Relationship between bilinear programming and concave programming,? Acta Mathematica Vietnamica, Vol. 2, pp. 106-113 (1980). · Zbl 0486.90061
[15]	N. V. Thoai and H. Tuy, ?Convergent algorithms for minimizing a concave function,? Mathematics of Operations Research, Vol. 5 pp. 556-566 (1980). · Zbl 0472.90054
[16]	H. Vaish and C.M. Shetty, ?The bilinear programming problems,? Naval Res. Log. Quar., Vol. 23, pp. 303-319, 1976. · Zbl 0349.90071
[17]	H. Vaish and C.M. Shetty, ?A cutting plane algorithm for bilinear programming problems,? Naval Res. Log. Quar., Vol. 24, pp. 83-94, 1976. · Zbl 0372.90082
[18]	Y. Yajima and H. Konno, ?Efficient algorithm for solving rank two and rank three bilinear programming problems,? J. of Global Optimization, Vol. 1, pp. 155-173, 1991. · Zbl 0748.90050