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. It is theoretically important as it attains the optimal convergence rate. However, it has little practical value as each step is very computationally expensive.

Input

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 R^d.

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 G_t, which surely contains the desired minimum. Initially we have G₀ = G. Then, each iteration t proceeds as follows.

• Let x_t be the center of gravity of G_t.
• Compute a subgradient at x_t, denoted f'(x_t).
  • By definition of a subgradient, the graph of f is above the subgradient, so for all x in G_t: f(x)−f(x_t) ≥ (x−x_t)^Tf'(x_t).
• If f'(x_t)=0, then the above implies that x_t is an exact minimum point, so we terminate and return x_t.
• Otherwise, let G_t+1 := {x in G_t: (x−x_t)^Tf'(x_t) ≤ 0}.

Note that, by the above inequality, every minimum point of f must be in G_t+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,