A prototypical problem road agencies are faced with is to find the optimal application schedule of maintenance works for a given road section. To solve such problems what-if models such as the road transport investment model (RTIM), the highway economic requirements system (HERS), and the highway development and management tool (HDM-4) are widely used to predict the consequences of different maintenance options. With these models maintenance options to be compared must be exogenously specified by an analyst, and the “optimization” with these routines simply chooses the best among those compared. As there are usually infinite numbers of options, it is impossible to exhaust all of them and only suboptimal optimizers may be found with this approach. The present article proposes the use of gradient search methods with what-if models to find the true optima without requiring exogenously specified alternatives. It demonstrates through a case study the feasibility of the use of the steepest descent method and the conjugate gradient method along with HDM-4 to find the true optimum maintenance options.