Upper and lower bounds of the collapse load factor are here obtained as the optimum values of two discrete constrained optimization problems. The membership constraints for Von Mises and Mohr–Coulomb plasticity criteria are written as a set of quadratic constraints, which permits one to solve the optimization problem using specific algorithms for Second‐Order Conic Program (SOCP). From the stress field at the lower bound and the velocities at the upper bound, we construct a novel error estimate based on elemental and edge contributions to the bound gap. These contributions are employed in an adaptive remeshing strategy that is able to reproduce fan‐type mesh patterns around points with discontinuous surface loading. The solution of this type of problems is analysed in detail, and from this study some additional meshing strategies are also described. We particularise the resulting formulation and strategies to two‐dimensional problems in plane strain and we demonstrate the effectiveness of the method with a set of numerical examples extracted from the literature.