  We present two first-order, sequential optimization algorithms to solve
constrained optimization problems. We consider a black-box setting with a
priori unknown, non-convex objective and constraint functions that have
Lipschitz continuous gradients. The proposed algorithms balance the exploration
of the a priori unknown feasible space with the pursuit of global optimality
within in a pre-specified finite number of first-order oracle calls. The first
algorithm accommodates an infeasible start, and provides either a near-optimal
global solution or establishes infeasibility. However, the algorithm may
produce infeasible iterates during the search. For a strongly-convex constraint
function and a feasible initial solution guess, the second algorithm returns a
near-optimal global solution without any constraint violation. In contrast to
existing methods, both of the algorithms also compute global suboptimality
bounds at every iteration. We also show that the algorithms can satisfy
user-specified tolerances in the computed solution with near-optimal complexity
in oracle calls for a large class of optimization problems. We propose
tractable implementations of the algorithms by exploiting the structure
afforded by the Lipschitz continuous gradient property.
