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

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''₊₁ := .

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_)\leq \left -\left(\frac\right)^n\rightcdot Volume(G_t) .

Therefore,

f(x_t) - \min_G f \leq \left -\left(\frac\right)^n\right max_G f - \min_G f.

In other words, the method has linear convergence of the residual objective value, with convergence rate \left -\left(\frac\right)^n\right \leq (1-1/e)^ . 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.

References

{{Reflist
Convex optimization