Rational catalyst design is one of the most challenging tasks in heterogeneous catalysis, mainly due to the lack of optimization strategies. In this work, we proposed a gradient-based optimization strategy for rational catalyst design. In this strategy, the catalyst design is treated as an optimization process of surface structures toward maximum activity. The bonding contribution equation, a quantitative relationship between the surface structures and the adsorption energies, is utilized to predict the adsorption in the optimization. A traditional catalyst for CO oxidation, platinum, is optimized using this strategy. After eight step optimization, the activity of CO oxidation increases dramatically. It is found that the origin of the high activity of the designed catalyst is not only from the suitable bonding strength of all the species and reaction barriers of all elementary steps, but also from circumventing the BEP relation. Our design strategy offers a powerful tool to understand and design novel catalytic materials.