Esfuerzo de cálculo de algoritmos

Considere el problema de optimización estrictamente convexo sin restriccionesDeje que x_ \ text {opt} denote sus mínimos únicos y x_0 sea ​​una aproximación inicial dada a x_ \ text {opt}. Llamaremos a un vector x una \ epsilon- solución cercana de \ mathcal {O} if \ begin {ecation} \ frac {|| x - x _ {\ text {opt}} || _2} {|| x_0 - x_ \ texto {opt} || _2} \ leq \ epsilon. \ end {ecuación}x opt x 0 x opt . x ϵ - O | El | x - x opt | El | $\mathcal{O} := \min_{x \in \mathbb{R}^n} f(x).$$x_\text{opt}$$x_0$$x_\text{opt}.$$x$$\epsilon-$$\mathcal{O}$

Suponga que existen dos algoritmos iterativos $\mathcal{A}_1$ y $\mathcal{A}_2$ para encontrar una solución $\epsilon-$ close de $\mathcal{O}$ con las siguientes propiedades:

1. Para cualquier $\epsilon > 0,$ el esfuerzo computacional total, es decir, el esfuerzo requerido por iteración $\times$ número total de iteraciones, para encontrar una solución $\epsilon-$ close es igual para ambos algoritmos.
2. El esfuerzo por iteración para $\mathcal{A}_1$ es $O(n),$ digamos, mientras que el de $\mathcal{A}_2$ es $O(n^2).$

¿Hay situaciones en las que uno preferiría un algoritmo sobre el otro? ¿Por qué?

Por lo general, es muy difícil, si no imposible, implementar una versión paralela de un algoritmo iterativo que se paraleliza entre iteraciones. La finalización de una iteración es un punto de secuencia natural. Si un algoritmo requiere menos iteraciones pero más trabajo por iteración, entonces es más probable que este algoritmo pueda implementarse efectivamente en paralelo.

Un ejemplo de esto es la programación lineal, donde el método de barrera dual primal (punto interior) generalmente usa solo unas pocas docenas de iteraciones incluso para problemas muy grandes, pero el trabajo por iteración es bastante extenso. En comparación, varias versiones del método simplex requieren muchas más iteraciones, pero el trabajo por iteración es menor. En la práctica, las implementaciones paralelas de métodos de punto interior han demostrado una eficiencia paralela mucho mejor que las implementaciones paralelas del método simplex.

Puedo pensar en algunas posibilidades:

Si ambos algoritmos reducen monotónicamente el error con cada iteración, entonces sería preferible para algunos tener más iteraciones más baratas, ya que le da más opciones sobre cuándo dejar de iterar.

Si es trabajo y tiempo pero memoria, puede preferir si es grande. incluso podría ser lo suficientemente grande como para que seleccione ya que es más probable que el uso de memoria lo aquí.$\mathcal{A}_1$$O(n)$$O(n^k)$$\mathcal{A}_2$$k$$k=2$$\mathcal{A}_2$

Esto probablemente se aplica si estamos hablando de optimización o de cualquier otra clase de problema iterativo.