Алгоритъм за минимизиране на най-малките квадрати при разпределение?

Да предположим, че трябва да разпределим 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

Това е специален случай на LP. Минимумът винаги се постига чрез разпределяне така, че вашите делта-k стойности да са еднакви.

Тъй като целевата функция е сбор от квадрати и всички точки от данни са еднакво претеглени, разпределянето на различни от същата стойност delta-ks води до по-висока сума от квадрати. (Имайте предвид, че в решението на josilber quadprog всички стойности delta-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