Classical robust optimization relies on convex and bounded uncertainty sets, an assumption that is inadequate for sparse uncertainty, where only a small, unknown subset of parameters deviates from its nominal value. This sparsity makes the uncertainty set nonconvex and turns separation into a combinatorial problem, so standard duality-based reformulations do not apply. We study two settings. For a pure sparsity constraint, we introduce an adaptive gradient projection method with backtracking for smooth sparse optimization, establish stationarity of its accumulation points, and use its output in a cutting-plane method that provides valid lower bounds. When sparsity is combined with a compact convex set, we derive exact mixed-integer lifted formulations and continuous relaxations. For adjustable robust optimization with fixed recourse, dualization gives a joint separation problem over uncertainty and recourse multipliers, in which every feasible pair yields a valid cut and the resulting master problems provide monotone lower bounds. We also show that continuous sparse box uncertainty and discrete budgeted uncertainty have the same worst-case value for linear dependence on uncertainty. Computational studies across six applications demonstrate the framework’s scalability and reveal how coupling constraints shape relaxation quality.