Content deleted Content added
Erel Segal (talk | contribs) |
Added {{One source}} tag |
||
| (3 intermediate revisions 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 9 ⟶ 10:
The method is [[Iterative method|iterative]]. At each iteration ''t'', we keep a convex region ''G<sub>t</sub>'', which surely contains the desired minimum. Initially we have ''G''<sub>0</sub> = ''G''. Then, each iteration ''t'' proceeds as follows.
* Let ''x<sub>t</sub>'' be the [[
* Compute a subgradient at ''x<sub>t</sub>'', denoted ''f''<nowiki/>'(''x<sub>t</sub>'').
** By definition of a subgradient, the graph of ''f'' is above the subgradient, so for all ''x'' in ''G''<sub>t</sub>: ''f''(''x'')−''f''(''x<sub>t</sub>'') ≥ (''x''−''x<sub>t</sub>'')<sup>T</sup>f'(''x<sub>t</sub>'').
Line 22 ⟶ 23:
== 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.<ref name=":0" />{{Rp|___location=Sec.8.2.2}}'' 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<sub>t</sub>'', 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 ==
| |||