In this paper a global optimization algorithm is presented to rigorously solve the MINLP model by Yee and Grossmann (1990) for the synthesis of heat exchanger networks under the simplifying assumptions of linear area cost, arithmetic mean temperature difference driving forces and no stream splitting. The proposed approach relies on the use of two new different sets of convex underestimators for the heat transfer area. A thermodynamic analysis is used to derive the first set of analytical linear and nonlinear convex underestimators as well as variable bounds and bounds contraction relationships. The second set of convex underestimators is generated by a relaxation of the heat transport equation through the introduction of a new variable, and an inequality that contains a nonconvex term that is subsequently replaced by its concave envelope. Based on these new underestimator functions, the original nonconvex MINLP is replaced by a convex MINLP that predicts tight lower bounds to the global optimum, and which is used in a hybrid branch and bound/outer-approximation search method. Application of the proposed ideas, and the algorithm are illustrated with several numerical examples.