Constrained, global optimization of unknown functions with Lipschitz continuous gradients
From MaRDI portal
Publication:5081778
Abstract: 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.
Recommendations
- scientific article; zbMATH DE number 757681
- Global optimization under Lipschitzian constraints
- Global optimization method with dual Lipschitz constant estimates for problems with non-convex constraints
- A deterministic algorithm for global optimization
- Optimal algorithms for global optimization in case of unknown Lipschitz constant
Cites work
- A deterministic algorithm for global optimization
- A deterministic algorithm for global optimization
- A Sequential Method Seeking the Global Maximum of a Function
- Abstract convexity and global optimization
- An algorithm for finding the absolute extremum of a function
- Convergence and restart in branch-and-bound algorithms for global optimization. Application to concave minimization and d.c. optimization problems
- Cutting angle method – a tool for constrained global optimization
- Data-driven science and engineering. Machine learning, dynamical systems, and control
- DC programming: overview.
- Gaussian processes for machine learning.
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 43985 (Why is no real title available?)
- scientific article; zbMATH DE number 7030501 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 757674 (Why is no real title available?)
- scientific article; zbMATH DE number 757676 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting
- Introduction to global optimization.
- Lectures on convex optimization
- Lipschitzian optimization without the Lipschitz constant
- Minimax and maximin space-filling designs: some properties and methods for construction
- On covering method for d.c. optimization.
- Reinforcement learning. An introduction
Cited in
(6)- A univariate global search working with a set of Lipschitz constants for the first derivative
- Lipschitz continuous policy functions for strongly concave optimization problems
- Safe global optimization of expensive noisy black-box functions in the -Lipschitz framework
- Global continuous optimization with error bound and fast convergence
- SMGO-\(\Delta\): balancing caution and reward in global optimization with black-box constraints
- Safe zeroth-order optimization using quadratic local approximations
This page was built for publication: Constrained, global optimization of unknown functions with Lipschitz continuous gradients
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5081778)
