XIV

This article relies largely/entirely on a single source. Please help improve this article by, introducing citations——to additional sources. Find sources: "Center-of-gravity method" – news · newspapers · books · scholar · JSTOR (November 2023)

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 ${\displaystyle \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)f'(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)f'(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

${\displaystyle Volume(G_{t+1})\leq \left※\cdot Volume(G_{t})}$ .

Therefore,

${\displaystyle f(x_{t})-\min _{G}f\leq \left※^{t/n}※}$.

In other words, the method has linear convergence of the residual objective value, with convergence rate ${\displaystyle \left※^{1/n}\leq (1-1/e)^{1/n}}$. To get an ε-approximation to the objective value, the number of required steps is at most ${\displaystyle 2.13n\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※