The thesis explores how to solve simulation-based optimization problems more efficiently using information about the problem structure. Two primary ideas are explored. The first idea involves developing numerical methods to detect the structure of convexity in the output function of a simulation. The second idea exploits simulation traces to generate gradient-like information to guide optimization. The goal of this thesis is to provide insights on solving practical large-scale simulation optimization problems that defy solution by existing simulation-optimization algorithms. In doing so, we hope to inspire algorithmic developments on sub-classes of simulation optimization problems. In the first part of this thesis, we give a asymptotically valid numerical procedure to detect the convexity in the output function of a simulation model. Since the simulated function could be expensive to evaluate, we adapt a Bayesian sequential sampling procedure, in which a set of new (noisy) samples is collected in each iteration to update a posterior model of the function evaluations. Based on that, the posterior probability that the underlying function is convex is estimated using Monte Carlo simulation, for which we develop variance reduction methods with significant improvement in the efficiency. The second and third parts of this thesis are on exploiting gradient-like information from the simulation to solve large-scale simulation optimization problems. In the second part of the thesis, we give heuristics for optimizing the overnight rebalancing of the bike-sharing system in New York City with 466 stations and hence 932 decision variables. The heuristics use the number of failed trips incurred by each station to indicate approximate gradient directions, and show effective improvement given any starting solution. In the third part of the thesis we further propose the idea of pseudo-gradient defined as an approximate gradient estimated from the historical simulation traces without rerunning the simulation. We prove that when the objective is strongly convex and the pseudo-gradient is accurately approximated, a pseudo-gradient-search procedure will converge to the near-optimal solution. We give examples of the pseudo-gradient in the cases of rebalancing a bike-sharing system and scheduling and staffing agents in a multiskill call center. The resulting search procedures perform better than the existing methods for the bike-sharing case and show comparable results to the state-of-art cutting-plane method for the call center example. The results indicate the effectiveness of pseudo-gradient search and its potential of replacing more sophisticated methods.