Center-of-gravity method: Difference between revisions

Revision as of 09:49, 28 November 2023

Latest revision as of 14:37, 29 November 2023

(One intermediate revision by one other user not shown)

Line 1:

{{One source|date=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.<ref name=":0">{{Cite web |last=Nemirovsky and Ben-Tal |date=2023 |title=Optimization III: Convex Optimization |url=http://www2.isye.gatech.edu/~nemirovs/OPTIIILN2023Spring.pdf}}</ref>{{Rp|___location=Sec.8.2.2}} It is theoretically important as it attains the optimal convergence rate. However, it has little practical value as each step is very computationally expensive.

Line 24 ⟶ 25:

== See also ==

The [[ellipsoid method]] can be seen as a modificationtractable ofapproximation to the center-of-gravity method. in which, instead
Instead of maintaining the feasible polytope ''G_t'', weit maintainmaintains 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 ==