This paper presents an approach to optimally design the air bearing surface (ABS) of the head slider by using the approximation methods. The reduced basis concept is used to reduce the number of design variables. In the numerical calculation, the progressive quadratic response surface modeling (PQRSM) is used to handle the non-smooth and discontinuous cost function. A multi-criteria optimization problem is formulated to enhance the flying performances over the entire recording band during the steady state and track seek operations. The optimal solutions of the sliders, whose target flying heights are 12 nm and 9 nm, are automatically obtained. The flying heights during the steady state operation become closer to the target values and the flying height variations during the track seek operation are smaller than those for the initial one. The pitch and roll angles are also kept within suitable ranges over the recording band.