Вычислительное усилие алгоритмов

Рассмотрим строго выпуклую задачу неограниченной оптимизации $\mathcal{O} := \min_{x \in \mathbb{R}^n} f(x).$Пусть обозначает его уникальные минимумы, а - заданное начальное приближение кМы будем называть вектор в близкое решение , если $x_\text{opt}$$x_0$$x_\text{opt}.$$x$$\epsilon-$$\mathcal{O}$

Предположим, что существует два итерационных алгоритма и чтобы найти близкое решение со следующими свойствами:$\mathcal{A}_1$$\mathcal{A}_2$$\epsilon-$$\mathcal{O}$

1. Для любого общее вычислительное усилие, т. Усилие, необходимое для каждой итерации общее число итераций, найти close решение одинаково для обоих алгоритмов.$\epsilon > 0,$$\times$$\epsilon-$
2. для усилие на итерацию равно , а для -$\mathcal{A}_1$$O(n),$$\mathcal{A}_2$$O(n^2).$

Существуют ли ситуации, когда один предпочитает один алгоритм другому? Почему?

Обычно очень трудно, если не невозможно, реализовать параллельную версию итеративного алгоритма, который паралеллизуется между итерациями. Завершение одной итерации является естественной точкой последовательности. Если один алгоритм требует меньше итераций, но больше работы на каждую итерацию, то более вероятно, что этот алгоритм может быть эффективно реализован параллельно.

Примером этого является линейное программирование, где метод первично-двойного барьера (внутренней точки) обычно использует всего несколько десятков итераций даже для очень больших задач, но работа на итерацию довольно обширна. Для сравнения, различные версии симплекс-метода обычно требуют гораздо больше итераций, но работа на итерацию меньше. На практике параллельные реализации методов внутренних точек показали гораздо лучшую параллельную эффективность, чем параллельные реализации симплекс-метода.

Я могу думать о некоторых возможностях:

Если оба алгоритма монотонно уменьшают ошибку при каждой итерации, то для некоторых может быть предпочтительнее иметь больше и дешевле итераций, поскольку это дает вам более широкий выбор того, когда прекратить итерацию.

Если - это работа и время, но памяти, вы можете предпочесть если большое. может даже быть достаточно большим, чтобы вы могли выбрать поскольку использование памяти с большей вероятностью ограничит вас.$\mathcal{A}_1$$O(n)$$O(n^k)$$\mathcal{A}_2$$k$$k=2$$\mathcal{A}_2$

Это, вероятно, применимо, говорим ли мы об оптимизации или о любом другом классе итерационных задач.