CODEWITHSUNDEEP
matrixoptimizationlinear-algebraminimizationquadratic-programming
dirt
dirt

Reputation: 3

solve quadratic programming for matrix instead of vectors

I am working on a quadratic programming problem.

So I got two matrices A and B (time series actually), and I wanna find the matrix X, s.t. A*X is closest to B, on the condition that X contains all positive values. (so X can be seen as a weight matrix)

Since it's a minimize problem, and there is limitation on X, I am considering using quadratic programming. Specifically, my goal is to find X with:

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

this form seems quite similar to the QP problem:

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

My problems are:

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?

It would be great if you could be specific about R functions.

Thanks a lot!

Upvotes: 0

Views: 957

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16724

This should be convex and straightforward to solve with a QP algorithm. I often rewrite this as:

 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

This is now obviously convex (a diagonal Q matrix). In some cases this form may be easier to solve than putting everything in the objective. In a sense we made the problem less non-linear. You can also solve this as an LP by using a different norm:

 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

Upvotes: 1

Related Questions