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

9

Рассмотрим строго выпуклую задачу неограниченной оптимизации O:=minxRnf(x).Пусть обозначает его уникальные минимумы, а - заданное начальное приближение кМы будем называть вектор в близкое решение , если xoptx0xopt.xϵO

||xxopt||2||x0xopt||2ϵ.

Предположим, что существует два итерационных алгоритма и чтобы найти близкое решение со следующими свойствами:A1A2ϵO

  1. Для любого общее вычислительное усилие, т. Усилие, необходимое для каждой итерации общее число итераций, найти close решение одинаково для обоих алгоритмов.ϵ>0,×ϵ
  2. для усилие на итерацию равно , а для -A1O(n),A2O(n2).

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

Суреш
источник

Ответы:

14

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

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

Брайан Борхерс
источник
7

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

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

Если - это работа и время, но памяти, вы можете предпочесть если большое. может даже быть достаточно большим, чтобы вы могли выбрать поскольку использование памяти с большей вероятностью ограничит вас.A1O(n)O(nk)A2kk=2A2

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

Билл Барт
источник
Я согласен с вами в отношении ограниченности пространства. Мне было интересно, если можно сделать случай только на основе сложности времени.
Суреш