A parallel algorithm for partially separable non-convex global minimization: Linear constraints. (English) Zbl 0723.90063

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

Ann. Oper. Res. 25, No. 1-4, 101-118 (1990).

The global minimization of large-scale partially separable non-convex problems over a bounded polyhedral set using a parallel branch and bound approach is considered. The objective function is a sum of a separable concave part, an unseparated convex part and a linear part. These large- scale problems are characterized by having the number of linear variables much greater than the number of nonlinear variables. A convex underestimating function to the objective function is constructed and minimized over the feasible domain to get both upper and lower bounds on the global minimum function value. At each iteration of the algorithm the feasible domain is divided into subregions and convex underestimating problems over each subregion are solved in parallel. Branch and bound techniques are used. Computational results are also presented.

Reviewer: S.Mititelu (Bucureşti)

MSC:

90C26	Nonconvex programming, global optimization
90-08	Computational methods for problems pertaining to operations research and mathematical programming
90C30	Nonlinear programming
90C06	Large-scale problems in mathematical programming
90C25	Convex programming

Keywords:

large-scale partially separable non-convex problems; parallel branch and bound; convex underestimating function; Branch and bound

References:

[1]	M. Avriel, M.J. Rijckaert, and D.J. Wilde,Optimization and Design (Prentice Hall, Englewood Cliffs, NJ, 1973).
[2]	C.S. Beightler and D.T. Phillips,Applied Geometric Programming (Wiley, New York, 1976). · Zbl 0344.90034
[3]	C.S. Beightler, D.T. Phillips and D.J. Wilde,Foundations of Optimization (Prentice Hall, Englewood Cliffs, NJ, 1976). · Zbl 0189.19702
[4]	V. Chvátal,Linear Programming (Freeman, New York, 1983).
[5]	R.J. Duffin, E.L. Peterson and C. Zener,Geometric Programming–Theory and Application (Wiley, New York, 1967). · Zbl 0171.17601
[6]	J.E. Falk and R.M. Soland, An algorithm for separable nonconvex programming problems, Management Sci. 15(9) (1969) 550–569. · Zbl 0172.43802
[7]	W.W. Hager, P.M. Pardalos, I.M. Roussos and H.D. Sahinoglou, Active constraints in optimization, J. Optimization Theory Appl. (in press). · Zbl 0697.90059
[8]	A.V. Kiselev, On estimation of the global minimum of a problem with synomial constraints and synomial objective function, Sov. J. Comp. Syst. Sci. 26 (4) (1988) 156–161. · Zbl 0678.90071
[9]	A.T. Phillips, Parallel algorithms for constrained optimization, PhD dissertation, University of Minnesota, Minneapolis, MN (1988). · Zbl 0665.90071
[10]	A.T. Phillips and J.B. Rosen, A parallel algorithm for constrained concave quadratic global minimization, Math. Programming 42 (2) (1988) 421–448. · Zbl 0665.90071
[11]	A.T. Phillips and J.B. Rosen, A parallel algorithm for partially separable nonconvex global minimization, Technical Report UMSI 88/137, University of Minnesota Supercomputer Institute, University of Minnesota, Minneapolis, MN (1988). · Zbl 0665.90071
[12]	A.T. Phillips and J.B. Rosen, Anomalous acceleration in parallel multiple-cost-row linear programming, ORSA J. Computing 1 (4) (1989) 247–251. · Zbl 0752.90048
[13]	R.M. Soland, An algorithm for separable nonconvex programming problems II: Nonconvex constraints, Management Sci. 17 (11) (1971) 759–773. · Zbl 0226.90038
[14]	L.S. Thakur, Error analysis for convex separable programs: The piecewise linear approximation and the bounds on the optimal objective value, SIAM J. Appl. Math. 34 (4) (1978) 704–714. · Zbl 0379.90084
[15]	C. Zener,Engineering Design by Geometric Programming (Wiley, New York, 1971).