2020/11/17 by Abraham P. Vinod, Vinod, Abraham P., Arie Israel +3
Decision Sciences · Engineering · Mathematics · #Advanced Bandit Algorithms Research #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2011.08997
openalex publication_date 2020/11/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present two first-order, sequential optimization algorithms to solve\nconstrained optimization problems. We consider a black-box setting with a\npriori unknown, non-convex objective and constraint functions that have\nLipschitz continuous gradients. The proposed algorithms balance the exploration\nof the a priori unknown feasible space with the pursuit of global optimality\nwithin in a pre-specified finite number of first-order oracle calls. The first\nalgorithm accommodates an infeasible start, and provides either a near-optimal\nglobal solution or establishes infeasibility. However, the algorithm may\nproduce infeasible iterates during the search. For a strongly-convex constraint\nfunction and a feasible initial solution guess, the second algorithm returns a\nnear-optimal global solution without any constraint violation. In contrast to\nexisting methods, both of the algorithms also compute global suboptimality\nbounds at every iteration. We also show that the algorithms can satisfy\nuser-specified tolerances in the computed solution with near-optimal complexity\nin oracle calls for a large class of optimization problems. We propose\ntractable implementations of the algorithms by exploiting the structure\nafforded by the Lipschitz continuous gradient property.\n