Алгоритм минимизации наименьших квадратов при распределении?

Предположим, нам нужно распределить сумму x на k желаемых сумм. Существует ли для этого алгоритм, который минимизирует квадрат расстояния между фактическими k выделенными значениями и k желаемыми суммами?

Например, предположим, что нам нужно выделить от x=5 до k=3 желаемое количество 2,-3,4.

Мы могли бы распределить 5 по 2,-3,6, получив квадрат расстояния 0^2 + 0^2 + 2^2 = 4.

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


algorithm math mathematical-optimization quadratic-programming
person steviekm3    schedule 02.08.2015    source источник

Ответы (4)


arrow_upward
1
arrow_downward

Пусть y будет суммой желаемых сумм, а d будет разницей между x и y. Минимум получается путем распределения d поровну между k желаемыми количествами. Упражнение для читателя: докажите это с помощью множителей Лагранжа.

В данном примере y = 2 - 3 + 4 = 3 и d = 5 - 3 = 2. Равномерное распределение d = 2 среди k желаемых значений означает добавление 2/3 к каждому из элементов, что приводит к распределению 2 2/3, -2 1/3 и 4 2/3.

person mhum    schedule 03.08.2015

arrow_upward
0
arrow_downward

В основном для вектора v (длины k) данных и общего бюджета b у вас есть следующая проблема оптимизации:

min_{x1, x2, ..., xk} (x1-v1)^2 + (x2-v2)^2 + ... + (xk-vk)^2
s.t. x1 + x2 + ... + xk = b

Это квадратичная программа с линейными ограничениями, которую можно решить с помощью пакетов программного обеспечения для квадратичного программирования. Например, вот решение с пакетом quadprog на языке R:

# Setup data
v <- c(2, -3, 4)
b <- 5

# Solve quadratic program
library(quadprog)
solve.QP(diag(length(v)), v, matrix(rep(1, length(v))), b, 1)$solution
# [1]  2.666667 -2.333333  4.666667

В этом примере мы получаем целевое значение 4/3, меньшее, чем целевое значение 4 для распределения, указанного в исходном посте.

person josliber♦    schedule 03.08.2015

arrow_upward
0
arrow_downward

Это частный случай ЛП. Минимум всегда достигается путем распределения таким образом, чтобы ваши значения delta-k были одинаковыми.

Поскольку целевая функция представляет собой сумму квадратов, а все точки данных имеют одинаковый вес, распределение дельта-к, отличных от одинаковых значений, приводит к более высокой сумме квадратов. (Обратите внимание, что в решении josilber quadprog все значения дельта-k равны 2/3. Где-то в области частных производных скрывается доказательство, которое я слишком устал или глуп, чтобы разобраться.)

person Community    schedule 03.08.2015

arrow_upward
0
arrow_downward

На ум приходят два подхода:

  1. Множители Лагранжа. Идеально подходит для минимизации квадратичной функции стоимости с линейным ограничением. Ссылка содержит несколько примеров того, как настроить и решить проблему.

    стоимость

    lagrange

    который дает

    lambda1

    применение ограничения и определение

    y

    дает

    lambda2

    замена обратно дает окончательное решение

    soln

    Другими словами, мы вычисляем разницу между общими желаемыми результатами и общими ограничениями и делим ее поровну между ними.

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

person dpmcmlxxvi    schedule 02.08.2015