In this paper, we propose a semi-empirical approach for simulating robot locomotion on granular media. We first develop a contact model based on the stick-slip behavior between rigid objects and granular grains, which is then learned through running extensive experiments. The contact model represents all possible contact wrenches that the granular substrate can provide as a convex volume, which our method formulates as constraints in an optimization-based contact force solver. During simulation, granular substrates are treated as rigid objects that allow penetration and the contact solver solves for wrenches that maximize frictional dissipation. We show that our method is able to simulate plausible interaction response with several granular media at interactive rates.