Based on the theory of optimization, we use edges and angles of cells to represent the geometric quality of computational grids, employ the local gradients of the flow variables to describe the variation of flow field, and construct a multi-objective programming model. The solution of this optimization problem gives appropriate balance between the geometric quality and adaptation of grids. By solving the optimization problem, we propose a new grid rezoning method, which not only keeps good geometric quality of grids, but also can track rapid changes in the flow field. In particular, it performs well for some complex concave domains with corners. We also incorporate the rezoning method into an Arbitrary Lagrangian-Eulerian (ALE) method which is widely used in the simulation of high-speed multi-material flows. The proposed rezoning and ALE methods of this paper are tested by a number of numerical examples with complex concave domains and compared with some other rezoning methods. The numerical results validate the robustness of the proposed methods.