решить квадратичное программирование для матрицы вместо векторов

Я работаю над задачей квадратичного программирования.

Итак, у меня есть две матрицы A и B (на самом деле временные ряды), и я хочу найти матрицу X, ст. A*X ближе всего к B при условии, что X содержит все положительные значения. (поэтому X можно рассматривать как весовую матрицу)

Поскольку это проблема минимизации и есть ограничение на X, я рассматриваю возможность использования квадратичного программирования. В частности, моя цель - найти X с помощью:

min sum (A*X - B).^2,   that is:

min sum 1/2 X^t * (A^t*A) * X - (B^t*A) * X
s.t. X is positive

эта форма кажется очень похожей на проблему QP:

1/2 x^t*Q*x + c^t*x
s.t. A*x < b

Мои проблемы:

My X is a matrix instead of a vector in QP.
Is there a variant of QP for this problem? Am I right to head to QP?

How to represent the limitation on X positive?

Было бы здорово, если бы вы могли конкретизировать функции R.

Большое спасибо!


person dirt    schedule 11.01.2018    source источник
comment
Какие размеры? Мат-мул работает алгебраически? QP является довольно общим, и в основном возможна только положительно-полуопределенная QP (для решения с глобальной опцией; выпуклая). Создать стандартную форму не так сложно, но пока неясно, является ли это правильным инструментом/подходом. Это звучит как матричная факторизация, потенциально NMF, где доступны специальные алгоритмы. Но даже NMF, вообще говоря, невыпуклый. Итак: будьте гораздо точнее и формальнее!   -  person sascha    schedule 11.01.2018
comment
@sascha Большое спасибо за ответ! Поскольку X должен состоять из неотрицательных значений, mat-mul не работает. На самом деле я тоже думаю о NMF, но когда вес вручную устанавливается положительным, функция потерь всегда уходит в бесконечность, и штраф не помогает. Я думаю, это потому, что отрицательные принудительно обнуляются. Вот почему я рассматриваю QP. Для размеров матриц, скажем, A равно t * m, B равно t * n и X равно m * n.   -  person dirt    schedule 11.01.2018
comment
Я совершенно неправильно понял задачу здесь. NMF — совсем другая задача. Ответ Эрвина выглядит правильным.   -  person sascha    schedule 11.01.2018
comment
@sascha Да, LP работает очень хорошо. Все равно спасибо!   -  person dirt    schedule 12.01.2018


Ответы (1)


Это должно быть выпуклым и простым для решения с помощью алгоритма QP. Я часто переписываю это как:

 min sum((i,k),d^2(i,k))
 d(i,k) = sum(j, a(i,j)*x(j,k)) - b(i,k)
 x(j,k) ≥ 0, d(i,k) free

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

 min sum((i,k),abs(d(i,k)))
 d(i,k) = sum(j, a(i,j)*x(j,k)) - b(i,k)
 x(j,k) ≥ 0, d(i,k) free

or

 min sum((i,k),y(i,k))
 -y(i,k) ≤ d(i,k) ≤ y(i,k)
 d(i,k) = sum(j, a(i,j)*x(j,k)) - b(i,k)
 x(j,k) ≥ 0, y(i,k) ≥ 0, d(i,k) free
person Erwin Kalvelagen    schedule 11.01.2018
comment
Большое спасибо! Я также думаю, что это то, что я надеюсь сделать. Пробую LP с третьей формой, но получились огромные матрицы. Все еще пытаюсь... - person dirt; 11.01.2018
comment
Я просто запутался в первом QP и втором LP с абсолютным значением. Я использую пакеты R, но QP предоставляет только матричную форму, невозможную для поэлементного квадрата и суммирования. Также LP невозможен для абсолютных значений. Вы случайно не знаете какие-нибудь пакеты или другие инструменты, которые могут справиться с этим? Большое спасибо! - person dirt; 11.01.2018
comment
(1) Большинство или все алгоритмы QP в R используют матричный интерфейс. Это не всегда легко использовать, но для этой проблемы не должно быть слишком плохо. (2) Функция abs() линеаризуется в третьей модели (просто продолжайте читать). (3) Пакет OMPR позволяет алгебраически формулировать модели LP и MIP. - person Erwin Kalvelagen; 11.01.2018
comment
Да, я продолжал играть на LP. И я только что получил очень хороший результат. Спасибо!! - person dirt; 12.01.2018
comment
Меня немного смущает обозначение sum((i,j), f(i,j)) здесь. Означает ли первый кортеж, что у нас есть вложенные символы суммы над i и j? Итак, эквивалентно ли это sum(i, sum(j, f(i,j)))? - person hansolo; 16.11.2020
comment
@hansolo То же самое: сумма всех комбинаций i,j. - person Erwin Kalvelagen; 16.11.2020