Center-of-gravity method
The center-of-gravity method is a theoretic algorithm for convex optimization. It can be seen as a generalization of the bisection method from one-dimensional functions to multi-dimensional functions.[1]: Sec.8.2.2 It is theoretically important as it attains the optimal convergence rate. However, it has little practical value as each step is very computationally expensive.
Description
We are given a convex optimization problem of the form:
minimize f(x) subject to: x in G,
where f is a convex function and G is a convex subset of a Euclidean space Rd.
References
- ^ Nemirovsky and Ben-Tal (2023). "Optimization III: Convex Optimization" (PDF).