A parallel algorithm for constrained concave quadratic global minimization. (English) Zbl 0665.90071

Phillips, A. T.; Rosen, J. B.

Math. Program., Ser. B 42, No. 2, 421-448 (1988).

The global minimization of large-scale concave quadratic problems over a bounded polyhedral set using a parallel branch and bound approach is considered. The objective function consists of both a concave part (nonlinear variables) and a strictly linear part, which are coupled by the linear constraints. These large-scale problems are characterized by having the number of linear variables much greater than the number of nonlinear variables. A linear and underestimating function to the concave part of the objective is easily constructed and minimized over the feasible domain to get both upper and lower bounds on the global minimum function value. At each minor iteration of the algorithm, the feasible domain is divided into subregions and linear underestimating problems over each subregion are solved in parallel. Branch and bound techniques can then be used to eliminate parts of the feasible domain from consideration and improve the upper and lower bounds. It is shown that the algorithm guarantees that a solution is obtained to within any specified tolerance in a finite number of steps. Computational results are presented for problems with 25 and 50 nonlinear variables and up to 400 linear variables. These results were obtained on a four processor CRAY2 using both sequential and parallel implementations of the algorithm. The average parallel solution time was approximately 15 seconds for problems with 400 linear variables and a relative tolerance of 0.001. For a relative tolerance of 0.1, the average computation time appears to increase only linearly with the number of linear variables.

MSC:

90C20	Quadratic programming
65K05	Numerical mathematical programming methods

Keywords:

global minimization; large-scale concave quadratic problems; bounded polyhedral set; parallel branch and bound; Computational results

References:

[1]	V. Chvátal,Linear Programming (W.H. Freeman and Company, New York, 1983).
[2]	J.E. Falk and K.R. Hoffman, ”A successive underestimation method for concave minimization problems,”Mathematics of Operations Research 1(3) (1976) 251–259. · Zbl 0362.90082
[3]	D.H. Glinsman and J.B. Rosen, ”Constrained concave quadratic global minimization by integer programming, ”Technical Report 86-37, Computer Science Department, University of Minnesota, Minneapolis, MN (1986).
[4]	R. Horst, ”An algorithm for nonconvex programming problems,”Mathematical Programming 10 (1976) 312–321. · Zbl 0337.90062
[5]	B. Kalantari, ”Large scale global minimization of linearly constrained concave quadratic functions and related problems,” Ph.D. diss., University of Minnesota, Minneapolis, MN (1984).
[6]	P.M. Pardalos and J.B. Rosen, ”Methods for global concave minimization: A bibliographic survey,”SIAM Review 28(3) (1986) 367–379. · Zbl 0602.90105
[7]	P.M. Pardalos and J.B. Rosen, ”Constrained global optimization: Algorithms and applications,” in: G. Goos and J. Hartmans, eds.,Lecture Notes in Computer Science 268, Springer-Verlag, Berlin 1987). · Zbl 0638.90064
[8]	A.T. Phillips and and J.B. Rosen, ”Anomalous acceleration in parallel linear programming,” Technical Report UMSI 88/58, University of Minnesota Supercomputer Institute, Computer Science Department, University of Minnesota, Minneapolis, MN (1988). · Zbl 0752.90048
[9]	A.T. Phillips and J.B. Rosen, ”A parallel algorithm for constrained concave quadratic global minimization,” Technical Report 87-48, Computer Science Department, University of Minnesota, Minneapolis, MN (1987a). · Zbl 0665.90071
[10]	A.T. Phillips and J.B. Rosen, ”A parallel algorithm for constrained concave quadratic global minimization: Computational aspects, ”Technical Report UMSI 87/101, University of Minnesota Supercomputer Institute, University of Minnesota, Minneapolis, MN (1987b).
[11]	M.J. Quinn,Designing Efficient Algorithms for Parallel Computers (McGraw-Hill, New York, 1987). · Zbl 0634.68020
[12]	J.B. Rosen, ”Global minimization of a linearly constrained concave function by partition of feasible domain,”Mathematics of Operations Research 8(2) 1987 215–230. · Zbl 0526.90072
[13]	J.B. Rosen and P.M. Pardalos, ”Global minimization of large-scale constrained concave quadratic problems by separable programming,”Mathematical Programming 34(2) (1986) 163–174. · Zbl 0597.90066
[14]	J.B. Rosen and M. van Vliet, ”A parallel stochastic method for the constrained concave global minimization problem,” Technical Report 87-31, Computer Science Department, University of Minnesota, Minneapolis, MN (1987).
[15]	E. Stuart, J.B. Rosen and A.T. Phillips, ”Fast approximate solution to constrained global minimization problems,” Technical Report 88-9, Computer Science Department, University of Minnesota, Minneapolis, MN (1988).