Интуитивно понятная причина, по которой минимизация сложнее в нескольких измерениях для разделяемых функций

#algorithm #optimization #time-complexity #computation-theory #minimization

#алгоритм #оптимизация #временная сложность #теория вычислений #минимизация

Вопрос:

Допустим, у меня есть N одномерных функций с положительным значением. Требуется ли больше вычислений функций для числового минимизатора, чтобы минимизировать их произведение в N-мерном пространстве, а не выполнять N отдельных одномерных минимизаций?

Если да, есть ли интуитивный способ понять это? Почему-то я чувствую, что обе проблемы должны быть равны по сложности.

Ответ №1:

Минимизация их продукта — это минимизация суммы их журналов. Существует множество алгоритмов для минимальной (максимальной) имитации N-мерных функций. Одним из них является старый резервный OPTIF9. Если вам приходится использовать жесткие ограничения, то есть вы минимизируете в рамке, это может быть намного сложнее, но обычно вы можете этого избежать.

1. Но быстрее ли решить проблему в N-d, чем выполнять N отдельных одномерных минимизаций? И если да, то почему?

2. @Alex, если проблема разрешима, то конечно. В общем, вы выполняете N-мерную оптимизацию, если измерения взаимосвязаны. Если решение для каждого измерения i зависит от решений для некоторых или всех других измерений. Например, в моей работе по фармакометрии, если у вас есть множество образцов крови, взятых с течением времени после приема дозы, вам нужно оценить как объем крови, так и скорость выведения почками. Эти два измерения взаимосвязаны. Вы не можете оценить их независимо.

Ответ №2:

Сложность не линейна по количеству переменных. Обычно n небольшие проблемы лучше, чем одна большая проблема. Или, другими словами: увеличение задачи в два раза (с точки зрения переменных) сделает ее решение более чем в два раза дороже.

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

1. Что управляет этим нелинейным масштабированием, особенно в случае разделяемой функции?

2. Решатели не знают, что проблема разделима, поэтому они просто рассматривают ее как большую N-мерную задачу. Ни один из известных мне алгоритмов не обладает линейной сложностью. Простым примером является просто решение Ax=b : это O(n^3) .

3. Мое внутреннее ощущение заключалось в том, что каким-то образом выполнение одного шага вдоль N-го градиента приведет вас к тому же месту, что и выполнение N одномерных шагов, которые вы сделали бы при минимизации отдельных функций (ЕСЛИ N-я функция является произведением N одномерных функций).