Content deleted Content added
Erel Segal (talk | contribs) ←Created page with '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 a...' |
Erel Segal (talk | contribs) Tags: nowiki added Visual edit |
||
Line 1:
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.
==
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]] <math>\nabla f</math>; but we do not assume that ''f'' is differentiable).
== Method ==
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 [[List of Beyond Live shows|center of gravity]] of ''G''<sub>t</sub>.
* 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>'').
* If ''f''<nowiki/>'(''x<sub>t</sub>'')=0, then the above implies that ''x<sub>t</sub>'' is an exact minimum point, so we terminate and return ''x<sub>t.</sub>''
* Otherwise, let ''G<sub>t</sub>''<sub>+1</sub> := {x in G<sub>t</sub>: (''x''−''x<sub>t</sub>'')<sup>T</sup>f'(''x<sub>t</sub>'') ≤ 0}.
Note that, by the above inequality, every minimum point of ''f'' must be in ''G<sub>t</sub>''<sub>+1.</sub><ref name=":0" />{{Rp|___location=Sec.8.2.2}}
== Convergence ==
It can be proved that <blockquote><math>Volume(G_{t+1})\leq \left[1-\left(\frac{n}{n+1}\right)^n\right]\cdot Volume(G_t)</math> .</blockquote>Therefore, <ref name=":0" />{{Rp|___location=Sec.8.2.2}}
== References ==
| |||