Abstract—This paper considers quadruped locomotion control in the presence of uncertainties. Two types of structured uncertainties are considered, namely, uncertain friction constraints and uncertain model dynamics. Then, a min-max optimization model is formulated based on robust optimization, and a robust min-max model predictive controller is proposed by recurrently solving the optimization model. We prove that the min-max optimization model is equivalent to a convex Quadratic Constrained Quadratic Program (QCQP) by exploiting the structure of uncertainties. Moreover, a two-stage optimization algorithm is proposed to solve the optimization problem efficiently, allowing for the deployment of the controller onto the real robot. The results show that the proposed optimization algorithm can improve solving frequency by ∼ 11x compared to Gurobi. The proposed controller is able to stabilize quadruped locomotion in challenging scenarios where the uncertainties are caused by significant disturbances and unknown environments.