I've got an Arduino controlling a relay. The relay controls two small DC motors. All of these components are powered through a 9v power regulator. I need the power regulator because the power source is a 16 volt battery, which would fry the motors and arduino if I connected them directly.

When the Arduino powers on the relay is initially open so the motors are powered off. The problem comes when the Arduino switches on the relay and motors start. The inrush current overloads the regulator and as a result, the Arduino loses voltage and resets. I have determined from experimentation that the regulator has enough ampacity to handle the DC motors at steady state, it's just the inrush that is the problem.

I am very inexperienced in this area, so it's not clear to me how to solve this problem. Might I use a capacitor to provide power to the arduino during the inrush period? Or maybe a capacitor could be charged up and provide power to motors on startup? Or maybe capacitors aren't the answer?

Using a voltmeter (on amp mode) it looked like the DC motors pulled about 1.5 amps on startup, and then went down to 0.5 amps on steady state.

Whatever the answer, a detailed explanation of wiring would be helpful, as well as what numbers I need to consider when picking out a capacitor or whatever it is I need to buy.