We focus on the problem of determining the structure of complexes formed by the association of two proteins by searching for the global minimum of a function approximating the free energy of the complex. Solving this problem requires the combination of a number of different optimization methods. First we explore the conformational space by systematic global search based on the Fast Fourier Transform (FFT) correlation approach that evaluates the energies of billions of docked conformations on a grid. We show that the method can be efficiently used with pairwise interactions potentials that substantially improve the docking results. A new 5D FFT algorithm is also discussed. The 1000 best energy conformations are clustered, and the 30 largest clusters are retained for refinement. The conformations are refined by a new medium-range optimization method that has been developed to locate the global minima within well defined regions of the conformational space. In each cluster, the energy of the complex is a very noisy funnel-like function on the space of rigid body motions, the Euclidean group SE(3). The Semi-Definite programming based Underestimation (SDU) method constructs a convex quadratic under-estimator to the energy funnel based on a sample of the local mimima of the energy function, and uses the quadratic under-estimator to guide future sampling. We show that the parameterization of SE(3) has a significant impact on the effectiveness of SDU and introduce a parameterization that dramatically reduces the number of very costly energy function evaluations. We also discuss the application of the combined method to recent targets in CAPRI (Critical Assessment of Protein Interactions), the first community-wide docking experiment.