This chapter develops algorithms for parameter optimization under multiple functional (inequality) constraints. Both the objective as well as the constraint functions depend on the parameter and are suitable long-run averages. The Lagrangian relaxation technique is used together with multi-timescale stochastic approximation and algorithms based on gradient and Newton SPSA/SF ideas where the afore-mentioned parameter is updated on a faster timescale as compared to the Lagrange parameters are presented. © 2013, Springer-Verlag London.