Constrained, Global Optimization of Unknown Functions with Lipschitz Continuous Gradients
提出了两种一阶序列优化算法，用于解决目标函数和约束函数未知但梯度Lipschitz连续的非凸约束优化问题，能在有限次调用黑箱函数后给出近似全局最优解或判定不可行。
We present two first-order, sequential optimization algorithms to solve constrained optimization problems. We consider a black-box setting with a priori unknown, nonconvex 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 a prespecified 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. At each iteration, the algorithms identify the next query point by solving a nonconvex, quadratically constrained, quadratic program, characterized by the Lipschitz continuous gradient property of the functions and the oracle responses. In contrast to existing methods, the algorithms compute global suboptimality bounds at every iteration. They can also satisfy user-specified tolerances in the computed solution with near-optimal complexity in oracle calls for a large class of optimization problems. We implement the proposed algorithms using GUROBI, a commercial off-the-shelf solver.