Center-of-gravity method explained

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] 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ⁿ.

\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 := .

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( (n)/(n +1) \right) ^{n\right] ⋅} Volume(G _{t)} .

Therefore,

f(x _{t)} - min _{G} f \leq \left[ 1- \left( (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( (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

The ellipsoid method can be seen as a tractable approximation to the center-of-gravity method. Instead of maintaining the feasible polytope G_t, it maintains an ellipsoid that contains it. Computing the center-of-gravity of an ellipsoid is much easier than of a general polytope, and hence the ellipsoid method can usually be computed in polynomial time.

Notes and References

1. Web site: Nemirovsky and Ben-Tal . 2023 . Optimization III: Convex Optimization .