The solution of complex constrained optimization problems is often prohibitively expensive because of the computational expense of evaluating the constraints. Under these circumstances the only viable solution is to employ inexpensive constraint approximations accompanied by move-limits that guard against large errors in the approximated constraints. The NEWSUMT-A program is a general purpose optimization program which automates the process of selecting constraint approximations and move-limits to ensure smooth convergence. The present paper describes the theoretical basis and the implementation of the optimization procedure. Examples from the field of structural optimization are presented. These involve stress and displacement constraints which require a costly finite element analysis. Additionally, the performance of two first-order constraint approximations is compared.