Lipschitz gradients for global optimization in a one-point-based partitioning scheme

DOI10.1016/J.CAM.2012.02.020zbMATH Open1246.65091arXiv1307.4302OpenAlexW2107530185MaRDI QIDQ433950FDOQ433950

Authors: Dmitri E. Kvasov, Yaroslav D. Sergeyev 

Publication date: 9 July 2012

Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Abstract: A global optimization problem is studied where the objective function $f(x)$ is a multidimensional black-box function and its gradient $f^{\prime }(x)$ satisfies the Lipschitz condition over a hyperinterval with an unknown Lipschitz constant $K$. Different methods for solving this problem by using an a priori given estimate of $K$, its adaptive estimates, and adaptive estimates of local Lipschitz constants are known in the literature. Recently, the authors have proposed a one-dimensional algorithm working with multiple estimates of the Lipschitz constant for $f^{\prime }(x)$ (the existence of such an algorithm was a challenge for 15 years). In this paper, a new multidimensional geometric method evolving the ideas of this one-dimensional scheme and using an efficient one-point-based partitioning strategy is proposed. Numerical experiments executed on 800 multidimensional test functions demonstrate quite a promising performance in comparison with popular DIRECT-based methods.

Full work available at URL: https://arxiv.org/abs/1307.4302

Recommendations

• Global Search Based on Efficient Diagonal Partitions and a Set of Lipschitz Constants
• A deterministic global optimization using smooth diagonal auxiliary functions
• On deterministic diagonal methods for solving global optimization problems with Lipschitz gradients
• A global optimization algorithm for multivariate functions with Lipschitzian first derivatives
• A univariate global search working with a set of Lipschitz constants for the first derivative

zbMATH Keywords

global optimizationalgorithmnumerical experimentsLipschitz gradientsgeometric algorithmsset of Lipschitz constants

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Derivative-free methods and methods using generalized derivatives (90C56)

Cites Work

• Efficient global optimization of expensive black-box functions
• TRIOPT: A triangulation-based partitioning algorithm for global optimization
• Algorithm 829
• Numerical Optimization
• Introductory lectures on convex optimization. A basic course.
• A locally-biased form of the DIRECT algorithm.
• Lipschitzian optimization without the Lipschitz constant
• Global optimization with non-convex constraints. Sequential and parallel algorithms
• Global optimization in action. Continuous and Lipschitz optimization: algorithms, implementations and applications
• Handbook of global optimization
• Title not available (Why is that?)
• Recent developments and trends in global optimization
• Global Search Based on Efficient Diagonal Partitions and a Set of Lipschitz Constants
• Essays and Surveys in Global Optimization
• Global one-dimensional optimization using smooth auxiliary functions
• A deterministic algorithm for global optimization
• A global optimization algorithm for multivariate functions with Lipschitzian first derivatives
• Local tuning and partition strategies for diagonal GO methods
• Efficient partition of \(N\)-dimensional intervals in the framework of one-point-based algorithms
• Parallel global optimization of functions of several variables
• Title not available (Why is that?)
• Efficient strategy for adaptive partition of N-dimensional intervals in the framework of diagonal algorithms
• Stochastic global optimization.
• An Information Global Optimization Algorithm with Local Tuning
• A univariate global search working with a set of Lipschitz constants for the first derivative
• A global minimization algorithm for Lipschitz functions
• An application of the nonuniform covering method to the global optimization of mixed integer nonlinear problems
• Two Methods for Solving Optimization Problems Arising in Electronic Measurements and Electrical Engineering
• A modified DIviding RECTangles algorithm for a problem in astrophysics
• Additive scaling and the \texttt{DIRECT} algorithm
• A set of examples of global and discrete optimization. Applications of Bayesian heuristic approach
• Dynamic data structures for a direct search algorithm
• An information global minimization algorithm using the local improvement technique
• A partition-based global optimization algorithm
• Customizing methods for global optimization -- a geometric viewpoint
• Deterministic parallel global parameter estimation for a model of the budding yeast cell cycle
• A Complexity Analysis of Local Search Algorithms in Global Optimization
• A metamodel-assisted evolutionary algorithm for expensive optimization
• A fully adaptive hybrid optimization of aircraft engine blades
• Surface passivation optimization using DIRECT
• Lipschitz and Hölder global optimization using space-filling curves

Cited In (29)

• Globally-biased disimpl algorithm for expensive global optimization
• Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and Hölder constants
• Diagonal generalizaton of the DIRECT method for problems with constraints
• Incremental method for multiple line detection problem -- iterative reweighted approach
• Geodesic and contour optimization using conformal mapping
• Application of the \texttt{DIRECT} algorithm to searching for an optimal \(k\)-partition of the set \(\mathcal {A}\subset \mathbb {R}^n\) and its application to the multiple circle detection problem
• Global Search Based on Efficient Diagonal Partitions and a Set of Lipschitz Constants
• Simplicial Lipschitz optimization without the Lipschitz constant
• Branching and bounding improvements for global optimization algorithms with Lipschitz continuity properties
• Global optimization based on bisection of rectangles, function values at diagonals, and a set of Lipschitz constants
• A \textsc{direct}-type global optimization algorithm for image registration
• Lipschitz global optimization methods in control problems
• Performance of convex underestimators in a branch-and-bound framework
• Adaptive nested optimization scheme for multidimensional global search
• A one-step worst-case optimal algorithm for bi-objective univariate optimization
• A modification of the \texttt{DIRECT} method for Lipschitz global optimization for a symmetric function
• A new global optimization method for a symmetric Lipschitz continuous function and the application to searching for a globally optimal partition of a one-dimensional set
• MSO: a framework for bound-constrained black-box global optimization algorithms
• On a global optimization algorithm for bivariate smooth functions
• Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints
• Continuation Newton methods with deflation techniques for global optimization problems
• Adaptation of a one-step worst-case optimal univariate algorithm of bi-objective Lipschitz optimization to multidimensional problems
• Multidimensional global optimization using the first derivatives
• A deterministic global optimization using smooth diagonal auxiliary functions
• Convergence rate of a rectangular subdivision-based optimization algorithm for smooth multivariate functions
• Application of reduced-set Pareto-Lipschitzian optimization to truss optimization
• Optimization challenges in the structured low rank approximation problem
• On Deterministic Diagonal Methods for Solving Global Optimization Problems with Lipschitz Gradients
• On one-step worst-case optimal trisection in univariate bi-objective Lipschitz optimization

Uses Software

• LGO
• TRIOPT
• DIRECT
• Algorithm 829
• EGO

This page was built for publication: Lipschitz gradients for global optimization in a one-point-based partitioning scheme

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q433950)