Abstract
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 consists of a separable concave part, an unseparated convex part, and a strictly linear part, which are all 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. An important special class of problems which can be reduced to this form are the synomial global minimization problems. Such problems often arise in engineering design, and previous computational methods for such problems have been limited to the convex posynomial case. In the current work, a convex underestimating function to the objective function 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 convex 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 obtained on the four processor Cray 2, both sequentially and in parallel on all four processors, are also presented.
Similar content being viewed by others
References
M. Avriel, M.J. Rijckaert, and D.J. Wilde,Optimization and Design (Prentice Hall, Englewood Cliffs, NJ, 1973).
C.S. Beightler and D.T. Phillips,Applied Geometric Programming (Wiley, New York, 1976).
C.S. Beightler, D.T. Phillips and D.J. Wilde,Foundations of Optimization (Prentice Hall, Englewood Cliffs, NJ, 1976).
V. Chvátal,Linear Programming (Freeman, New York, 1983).
R.J. Duffin, E.L. Peterson and C. Zener,Geometric Programming—Theory and Application (Wiley, New York, 1967).
J.E. Falk and R.M. Soland, An algorithm for separable nonconvex programming problems, Management Sci. 15(9) (1969) 550–569.
W.W. Hager, P.M. Pardalos, I.M. Roussos and H.D. Sahinoglou, Active constraints in optimization, J. Optimization Theory Appl. (in press).
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.
A.T. Phillips, Parallel algorithms for constrained optimization, PhD dissertation, University of Minnesota, Minneapolis, MN (1988).
A.T. Phillips and J.B. Rosen, A parallel algorithm for constrained concave quadratic global minimization, Math. Programming 42 (2) (1988) 421–448.
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).
A.T. Phillips and J.B. Rosen, Anomalous acceleration in parallel multiple-cost-row linear programming, ORSA J. Computing 1 (4) (1989) 247–251.
R.M. Soland, An algorithm for separable nonconvex programming problems II: Nonconvex constraints, Management Sci. 17 (11) (1971) 759–773.
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.
C. Zener,Engineering Design by Geometric Programming (Wiley, New York, 1971).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Phillips, A.T., Rosen, J.B. A parallel algorithm for partially separable non-convex global minimization: Linear constraints. Ann Oper Res 25, 101–118 (1990). https://doi.org/10.1007/BF02283689
Issue Date:
DOI: https://doi.org/10.1007/BF02283689