Center-of-gravity method

Our goal is to solve a convex optimization problem of the form:'minimize f(x) s.t. x in G,'where f is a convex function, and G is a convex subset of a Euclidean space Rn. We assume that we have a "subgradient oracle": a routine that can compute a subgradient of f at any given point (if f is differentiable, then the only subgradient is the gradient \nabla f; but we do not assume that f is differentiable). == Method ==

The method is iterative. At each iteration t, we keep a convex region Gt, which surely contains the desired minimum. Initially we have G0 = G. Then, each iteration t proceeds as follows. • Let xt be the center of gravity of Gt. • Compute a subgradient at xt, denoted f'(xt). • By definition of a subgradient, the graph of f is above the subgradient, so for all x in Gt: f(x)−f(xt) ≥ (x−xt)Tf'(xt). • If f'(xt)=0, then the above implies that xt is an exact minimum point, so we terminate and return xt. • Otherwise, let Gt+1 := {x in Gt: (x−xt)Tf'(xt) ≤ 0}. Note that, by the above inequality, every minimum point of f must be in Gt+1. == Convergence ==

It can be proved that Volume(G_{t+1})\leq \left[1-\left(\frac{n}{n+1}\right)^n\right]\cdot Volume(G_t) .Therefore,f(x_t) - \min_G f \leq \left[1-\left(\frac{n}{n+1}\right)^n\right]^{t/n} [\max_G f - \min_G f] .In other words, the method has linear convergence of the residual objective value, with convergence rate \left[1-\left(\frac{n}{n+1}\right)^n\right]^{1/n} \leq (1-1/e)^{1/n} . To get an ε-approximation to the objective value, the number of required steps is at most 2.13 n \ln(1/\epsilon) + 1 . == Computational complexity ==

The main problem with the method is that, in each step, we have to compute the center-of-gravity of a polytope. All the methods known so far for this problem require a number of arithmetic operations that is exponential in the dimension n. Therefore, the method is not useful in practice when there are 5 or more dimensions. == See also ==