© 2015, MIT Press Journals. All rights reserved. Optimization is often difficult to apply to robots due to the presence of modeling errors, which may cause constraints to be violated during execution on a real robot. This work presents a method to optimize trajectories with large modeling errors using a combination of robust optimization and parameter learning. In particular it considers the problem of computing a dynamically-feasible trajectory along a fixed path under frictional contact, where friction is uncertain and actuator effort is noisy. It introduces a robust time-scaling method that is able to accept confidence intervals on uncertain parameters, and uses a convex parameterization that allows dynamically-feasible motions under contact to be computed in seconds. This is combined with an iterative learning method that uses feedback from execution to learn confidence bounds on modeling parameters. Experiments on a manipulator performing a "waiter" task, on which an object is moved on a carried tray as quickly as possible, demonstrate this method can compensate for modeling uncertainties within a handful of iterations.