Método del centro de gravedad

El método del centro de gravedad es un algoritmo teórico para la optimización convexa . Puede considerarse como una generalización del método de bisección de funciones unidimensionales a funciones multidimensionales. ^{[1] : Sec.8.2.2} Es importante en teoría, ya que alcanza la tasa de convergencia óptima. Sin embargo, tiene poco valor práctico, ya que cada paso es muy costoso en términos computacionales.

Nuestro objetivo es resolver un problema de optimización convexa de la forma:

minimizar f ( x ) st x en G ,

donde f es una función convexa y G es un subconjunto convexo de un espacio euclidiano R ⁿ .

Suponemos que tenemos un "oráculo de subgradiente": una rutina que puede calcular un subgradiente de f en cualquier punto dado (si f es diferenciable, entonces el único subgradiente es el gradiente ; pero no asumimos que f sea diferenciable). ${\displaystyle \nabla f}$

El método es iterativo . En cada iteración t , mantenemos una región convexa G _t , que seguramente contiene el mínimo deseado. Inicialmente tenemos G ₀ = G . Luego, cada iteración t procede de la siguiente manera.

• Sea x _t el centro de gravedad de G _t .
• Calcular un subgradiente en x _t , denotado f '( x _t ).
  • Por definición de un subgradiente, el gráfico de f está por encima del subgradiente, por lo que para todo x en G _t : f ( x )− f ( x _t ) ≥ ( x − x _t ) ^T f'( x _t ).
• Si f '( x _t )=0, entonces lo anterior implica que x _t es un punto mínimo exacto, por lo que terminamos y devolvemos x _t.
• De lo contrario, sea G _{t +1}  := {x en G _t : ( x − x _t ) ^T f'( x _t ) ≤ 0}.

Nótese que, por la desigualdad anterior, cada punto mínimo de f debe estar en G _{t +1.} ^{[1] : Sec.8.2.2}

Se puede demostrar que

${\displaystyle Volume(G_{t+1})\leq \left[1-\left({\frac {n}{n+1}}\right)^{n}\right]\cdot Volume(G_{t})}$.

Por lo tanto,

${\displaystyle f(x_{t})-\min _{G}f\leq \left[1-\left({\frac {n}{n+1}}\right)^{n}\right]^{t/n}[\max _{G}f-\min _{G}f]}$.

En otras palabras, el método tiene convergencia lineal del valor objetivo residual, con una tasa de convergencia . Para obtener una aproximación ε al valor objetivo, el número de pasos necesarios es como máximo . ^{[1] : Sec.8.2.2}${\displaystyle \left[1-\left({\frac {n}{n+1}}\right)^{n}\right]^{1/n}\leq (1-1/e)^{1/n}}$${\displaystyle 2.13n\ln(1/\epsilon )+1}$

El principal problema del método es que, en cada paso, tenemos que calcular el centro de gravedad de un politopo. Todos los métodos conocidos hasta ahora para este problema requieren un número de operaciones aritméticas exponencial en la dimensión n. ^{[1] : Sec.8.2.2} Por lo tanto, el método no es útil en la práctica cuando hay 5 o más dimensiones.

El método del elipsoide puede considerarse una aproximación manejable al método del centro de gravedad. En lugar de mantener el politopo factible G _t , mantiene un elipsoide que lo contiene. Calcular el centro de gravedad de un elipsoide es mucho más fácil que el de un politopo general y, por lo tanto, el método del elipsoide generalmente se puede calcular en tiempo polinomial.