Convex maximization arises in many applications but is generally NP-hard, even for low-rank objectives. This paper introduces a set of broadly applicable conditions that certify when such problems are polynomially solvable. Our main condition is a new property of the feasible set, which we term co-monotonicity. We show that this property holds for two important families: matroids and permutation-invariant sets. Under co-monotonicity and mild additional assumptions, we develop a geometric framework that generates polynomially many candidate solutions, one of which is optimal. This yields a polynomial-time algorithm. We further derive substantially sharper complexity bounds when the feasible set is permutation-invariant. Our framework recovers existing tractable instances and often improves their complexity. It also expands the frontier of tractability by providing the first polynomial-time guarantees for new applications.