Randomized smoothing is a leading approach to producing certifiably robust classifiers. The goal of optimal randomized smoothing is to maximize the average certified radius over the space of smoothing distributions. We theoretically study this problem through the lens of infinite-dimensional optimization over measure spaces, and prove that the nonconvex infinite program is lower-bounded by a conic linear program wherein the classifier's confidence acts as a surrogate objective to optimize. A semi-infinite linear programming approximation to the problem is presented, whose sub-problems are proven to attain nontrivial strong duality. A proof-of-concept experiment demonstrates the effectiveness of the proposed approach.